11/9/2020 Grok | COMP30026 Practice Exam
Ques on 2 Part B (6 marks)
Ques on 2
A proposi onal logic formula is in prexor normal form (PXNF) if it contains only the
following components and connec ves:
The proposi onal constant true ( ),
proposi onal variables (for example, , ), and conjunc on ( ) and exclusive-or ( ) connec ves.
Part B (6 marks)
Show that all proposi onal logic formulas have an equivalent formula in prexor normal form.
Hint: Your answers to part A may be useful.
Instruc ons
WriteaHaskellfunc ontoPXNF :: Exp -> Expwhichtakesanarbitraryproposi onal expression and returns an equivalent expression in prexor normal form.
Format
The Haskell type Exp has data constructors FALSE, TRUE, VAR, NOT, AND, OR, XOR, BIIM, and IMPL. Its defini on is provided in the file Exp.hs, along with a simple parser parse :: String -> Exp.Thesetoolsarethesameasyouarefamiliarwithfrom worksheets and assignments.
For example, the formula can be expressed as: IMPL (AND (VAR ‘P’) (VAR ‘Q’)) (VAR ‘R’), or
parse “((P & Q) => R)”usingtheparsefunc on. Visualisa on
WehavealsoprovidedaprintExp :: Exp -> Stringfunc onwhichyoucanuse while tes ng your expressions to generate more readable output than the default from show.
R ⇒ )Q ∧ P(
⊕∧ QP
t
https://groklearning.com/learn/unimelb-comp30026-2020-s2/prac-exam/4/ 1/1
Cheng