In this assignment you will work with expression trees for logical formulas. For example, here is the expression tree for the formula (p & q) & ~q:
1
Assignment 4: Logical Formulas
Note: For all parts of this assignment themis will include the files scanner.c and scanner.h automatically, you do not have to upload them. You do not have to modify them for this assignment, but you can overwrite them by uploading files with the same name.
Part 1: Recognizing Formulas
Consider the following grammar for propositional logic with negations and conjunctions.
⟨formula⟩ ⟨literal ⟩ ⟨atom⟩ ⟨identifier ⟩ ⟨letter ⟩ ⟨digit ⟩
::= ⟨literal⟩ { ’&’ ⟨literal⟩ } .
::= ⟨atom⟩ | ’~’ ⟨atom⟩ .
::= ’T’ | ’F’ | ⟨identifier⟩ | ’(’ ⟨formula⟩ ’)’ . ::= ⟨letter⟩ { ⟨letter⟩ | ⟨digit⟩ } .
::= ‘a’|. . . |‘z’.
::= ‘0’|. . . |‘9’.
&
&
~
pqq
1. Extend the above grammar with disjunction ‘|’, implication ‘->’ and biconditional ‘<->’. Disjunction should be n-ary, similar to conjunction above. Implication and
biconditional should be binary. The order of binding strength should be
~ & | -> <->
so negation binds the strongest and biconditional the weakest.
2. In assignment4code.zip you find a parser for negation and conjunction formulas which generates syntax trees. Extend it to the full grammar with all operators.
A note and a hint: Spaces are ignored by the scanner and both ‘->’ and ‘- >’ should be accepted. You do not have to redefine the token type if you use single characters for all operators internally.
3. Also extend the function printTree that prints the formula, with parentheses.
4. Write a function to compute the complexity of a formula, i.e. its maximal nesting degree. This corresponds with the depth of the syntax tree of the formula.
2
An example of input and resulting output:
input
resulting output
p
p & ~q | F | r p -> q -> r
p <-> ~ r – > q ~(p-
~~~p ~(~(~((p))))
!
give a formula: p
with parentheses: p
complexity: 0
give a formula: p & ~ q | F | r
with parentheses: (((p & (~q)) | F) | r)
complexity: 4
give a formula: p – > q – > r
this is not a formula
give a formula: p < - > ~ r – > q
with parentheses: (p <-> ((~r) -> q))
complexity: 3
give a formula: ~ ( p –
this is not a formula
give a formula: ~ ~ ~ p
this is not a formula
give a formula: ~ ( ~ ( ~ ( ( p ) ) ) )
with parentheses: (~(~(~p)))
complexity: 3
give a formula: good bye
Part 2: Simplifying and Translating
1. Define a function simplify that simplifies formulas. Use exactly the following rules, where φ is an arbitrary formula:
• ~(~φ) simplifies to φ
• ~TsimplifiestoF
• ~FsimplifiestoT
• T | φandφ | TsimplifytoT
• F | φandφ | Fsimplifytoφ
• T & φandφ & Tsimplifytoφ
• F & φandφ & FsimplifytoF
• T -> φ simplifies to φ
• F -> φsimplifiestoT
• φ -> TsimplifiestoT
• φ -> Fsimplifiesto~φ
• T <-> φandφ <-> Tsimplifytoφ • F <-> φandφ <-> Fsimplifyto~φ
2. Define a function translate that translates a given formula to a formula that only contains negation and conjunction as operators, i.e. to a formula in the language defined by the original BNF grammar in Part 1. Use exactly the following rules, where ‘. . .’ indicates that the translation continues. Do not simplify at the same time.
φ | ψ → ~(~φ & ~ψ)
φ->ψ → ~φ|ψ → … φ<->ψ → (φ&ψ)|(~φ&~ψ) → …
Hint: For the translation of biconditionals, have a look at Exercise 2.4, part a.
3. Extend the functionality of your program of Part 1 with simplify and translate.
4. Use the function simplify to simplify the result of translate.
3
An example of input and resulting output:
input
resulting output
p & T | r & ~F
~old -> young
~(~one) -> two
p1 -> p2 -> p3
p1 -> (p2 -> p3)
!
give a formula: p & T | r & ~ F
with parentheses: ((p & T) | (r & (~F)))
complexity: 3
simplified: (p | r)
translated: (~((~p) & (~r)))
simplified: (~((~p) & (~r)))
give a formula: ~ old – > young
with parentheses: ((~old) -> young)
complexity: 2
simplified: ((~old) -> young)
translated: (~((~(~(~old))) & (~young)))
simplified: (~((~old) & (~young)))
give a formula: ~ ( ~ one ) – > two
with parentheses: ((~(~one)) -> two)
complexity: 3
simplified: (one -> two)
translated: (~((~(~one)) & (~two)))
simplified: (~(one & (~two)))
give a formula: p1 – > p2 – > p3
this is not a formula
give a formula: p1 – > ( p2 – > p3 )
with parentheses: (p1 -> (p2 -> p3))
complexity: 2
simplified: (p1 -> (p2 -> p3))
translated: (~((~(~p1)) & (~(~((~(~p2)) & (~p3))))))
simplified: (~(p1 & (p2 & (~p3))))
give a formula: good bye
Extra: Detecting Tautologies
Extend your program with a function that checks whether a given formula is a tautology. This extra part can also be submitted on themis and you can earn up to 2 bonus points. The maximum grade is still 10.
An example of input and resulting output:
input
resulting output
~p & p
(p <-> q) -> (~q | p)
F -> p
~~p | p
!
give a formula: ~ p & p
with parentheses: ((~p) & p)
this is not a tautology
give a formula: ( p < - > q ) – > ( ~ q | p )
with parentheses: ((p <-> q) -> ((~q) | p))
this is a tautology
give a formula: F – > p
with parentheses: (F -> p)
this is a tautology
give a formula: ~ ~ p | p
this is not a formula
give a formula: good bye