11/9/2020 Grok | COMP30026 Practice Exam
Ques on 2 Part A (4 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 A (4 marks)
The following four formulas are in prexor normal form:
1. 2. 3. 4.
For each of these formulas, give an equivalent but simplified proposi onal formula that uses exactly one connec ve and does not use exclusive-or.
Note: For this ques on, you do not need to give answers in prexor normal form; you may use any constants ( , ) and any connec ves (that is , , , , or —anything other than ) along with the variables and .
Instruc ons
Give your answer as four proposi onal formulas of type Exp, named exp1, exp2, exp3, and exp4, respec vely.
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 parserparse :: String -> Exp.Thesetoolsarethesameasyouarefamiliarwith from 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. https://groklearning.com/learn/unimelb-comp30026-2020-s2/prac-exam/3/ 1/1
Cheng
⇔ ⇒∨∧¬
QP⊕ ft
R ⇒ )Q ∧ P(
⊕∧ QP
t
)Q∧ P(⊕Q⊕ P )Q∧ P(⊕ P⊕t
Q⊕P⊕t P⊕t