Group B: week 3, Monday 12 March 2001 on,

Group A: week 4, Monday 19 March 2001 on.

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:

- Write a routine to collect the variables (unique identifiers)
in the Wff into a simple data structure.
You can assume that there will be no more than 12 variables.
[2 marks]
- Write a routine to run through all the assignments of
true and false to the variables.
[2 marks]
- Write a routine to evaluate the Wff given such an assignment of
true and false to the variables, and

put the parts together to create a program to print the truth table.[2 marks]

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:- <Wff1> -> <Wff2> == (not <Wff1>) or <Wff2>
- not not <Wff> ==
<Wff>

e.g. not(not(not(not <Wff>))) becomes <Wff>. - <Wff1> and <Wff2> == <Wff2> and <Wff1>
- <Wff1> or <Wff2> == <Wff2> or <Wff1>

- Rules 1 and 2 are to be used to remove implications (->)
and duplicate negations.
[2 marks]
- Rules 3 and 4 are to be used to place
sub-expressions in "canonical order"
i.e. order sub-expressions alphabetically.
[2 marks]
- Using the fact that
- <Wff1> and <Wff1> == <Wff1> or <Wff1> == <Wff1>

[2 marks]

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*.

© L. Allison 2001, School of Computer Science and Software Engineering, Monash University, Australia 3168.