[CSE2304] [progress]

CSSE, Monash University, .au, CSE2304, Practical #1, semester 1, 2001
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, e.g. using `gcc *.c', under Unix (Linux), and try example inputs.

NB. implication: p -> q is equivalent to (not p) or q.

Group B:

Task: Modify the Wff program so that it reads in a Wff and prints its truth table.

e.g. the truth table of   p and q or spx   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      T
  1. 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]
  2. Write a routine to run through all the assignments of true and false to the variables.
    [2 marks]
  3. 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]

Group A

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.

  1. <Wff1> -> <Wff2>   ==   (not <Wff1>) or <Wff2>
  2. not not <Wff>   ==   <Wff>
    e.g. not(not(not(not <Wff>))) becomes <Wff>.
  3. <Wff1> and <Wff2>   ==   <Wff2> and <Wff1>
  4. <Wff1> or <Wff2>   ==   <Wff2> or <Wff1>
  1. Rules 1 and 2 are to be used to remove implications (->) and duplicate negations.
    [2 marks]
  2. Rules 3 and 4 are to be used to place sub-expressions in "canonical order" i.e. order sub-expressions alphabetically.
    [2 marks]
  3. Using the fact that simplify the results of the previous stages.
    [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.