Spring ‘22 AI Homework 4: solutions
Predicate Logic
¬(P v ¬Q) <=> R R => T v U
¬U v Q ^ R (¬V v R) => U
Copyright By PowCoder代写 加微信 powcoder
V => (¬P ^ ¬T)
1. [5 pts.] Convert the above sentences into CNF using: ~, v as operators (you may also use ! and | if you want, just be consistent). Show each iteration of the algorithm, so step 1) eliminate if and only if, etc.
2. [5 pts.] Perform a step-by-step execution of DPLL on the CNF output from the previous. As demonstrated in class, show each key progression, e.g. “Assign pure literal, propagate P=true, or guess W as true. When guessing in DPLL, choose the lowest unbound alphabetical and try True first.
Answers: [I add parens to 3rd sentence based on precedence]
Step 1: Eliminate <=>
[¬(P v ¬Q) => R] ^ [R => ¬(P v ¬Q)] R => T v U
¬U v (Q ^ R) (¬V v R) => U
V => (¬P ^ ¬T)
Step 2: Eliminate =>
[¬¬(P v ¬Q) v R] ^ [¬R v ¬(P v ¬Q)] ¬R v T v U
¬U v (Q ^ R) ¬(¬V v R) v U
¬V v (¬P ^ ¬T)
Step 3: Push in negation, apply DeMorgan’s law
[(P v ¬Q) v R] ^ [¬R v (¬P ^ Q)] ¬R v T v U
¬U v (Q ^ R) (V ^ ¬R) v U
¬V v (¬P ^ ¬T)
Step 4/5: Distribute to make outer ^, split sentences on ^
P v ¬Q v R ¬R v ¬P ¬R v Q
¬R v T v U ¬U v Q
¬U v R VvU ¬R v U ¬V v ¬P ¬V v ¬T
Optional step 6 is to remove tautologies, but there are none
Note: This is valid CNF. It is ok to have dropped the v since it is implied (per Lab 2 CNF inputs) It is not OK to still have () or ^ in your sentences.
2. DPLL – your order of easy case resolution may differ from mine since no rule given. I use alpha.
P v ¬Q v R ¬R v ¬P ¬R v Q
¬R v T v U ¬U v Q
¬U v R VvU ¬R v U ¬V v ¬P ¬V v ¬T
No easy cases. Hard case, guess P=true (using the given rule).
¬R v Q ¬R v T v U
¬U v Q ¬U v R VvU ¬R v U ¬V
Easy case: unit-literals ¬R, ¬V – can only pick one at a time Choose R=false
{P=true, R=false}
¬U v Q ¬U VvU ¬V
Easy case: unit-literals ¬U, ¬V Choose U=false
{P=true, R=false, U=false}
Easy case: unit-literals V, ¬V Choose V=true
{P=true, R=false, U=false, V=true}
Contradiction: ¬V becomes an empty sentence. Backtrack to last guess, try P=false
¬Q v R ¬R v Q ¬R v T v U ¬U v Q ¬U v R VvU
¬R v U ¬V v ¬T
No easy cases. Hard case, guess Q=true (using the given rule).
{P=false, Q=true}
¬R v T v U ¬U v R VvU
Easy case: unit-literal R
{P=false, Q=true, R=true}
Easy case: U is both unit and pure-literal
{P=false, Q=true, R=true, U=true}
Easy case: ¬V ¬T are both pure-literal, choose T=false
{P=false, Q=true, R=true, T=false, U=true,}
Final step, assign unbound V, I arbitrarily choose false
{P=false, Q=true, R=true, T=false, U=true, V=false}
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com