The objective of this practical is to apply CSE2304 material on parsing and the structure and manipulation of trees.
Systems to be used: Linux and gcc.
In
[..../tildeProgLang/C/Wff/]
are a few files which make up a simple parser for
Well Formed Formulae (Wff), i.e. expressions, in
propositional logic
(~boolean algebra).
The parser forms the basis of Prac#1.
Take a copy of all the
*.c and *.h files,
read the source code,
compile the program,
gcc *.c
'
NB. implication:
p -> q
is equivalent to
(not p) or q
.
Task: Modify the Wff program so that it reads in a Wff and prints its truth table.
e.g. the truth table of
is
p q spx p and q or spx ------------------------------- F F F F F F T T F T F F F T T T T F F F T F T T T T F T T T T TSteps:
Task: Modify the Wff program to perform some basic simplifications of Wffs as described:
The following rules can be used to rewrite a Wff without changing its meaning, but beware, their careless use, particularly rules 3 and 4, can lead to programs that loop.
Rules:not(p and not q) -> not q and p becomes (not not(p and not q)) or (not q and p) becomes (p and not q) or (not q and p) becomes (not q and p) or (not q and p) becomes not q and p done
NB. This is a simple example of expression optimization. Full expression optimization, as performed by compilers, or in logic design, is a difficult subject and beyond the scope of this exercise. There are many expressions that the above strategy cannot simplify (find one). Do what is required and no more.