Tutorial 10

Exercise 1

1. Yes, only one negative literal & DNF.
2. No, two positive literals.
3. Yes, only at most one positive literal & DNF
4. Yes.
5. Yes.
6. Yes.

Exercise 2

(1)

Given two atomic formula: ${\varphi }_1,{\varphi }_2$ The mgu is $\sigma$ if ${\varphi }_1\sigma ={\varphi }_2\sigma$.

(2)

1. $Y\mapsto 1,L\mapsto 2,X\mapsto Z,U\mapsto {[}_{|}R]$
2. There is no unifier. Contradiction on $Y$.
3. There is no unifier. Cannot map $[]$ to $[Y|L]$ as it must have at least one element.
4. No unifier.

Exercise 3

$$\begin{array}{rlrlr}P⊢A_1,\dots ,A_n& & (A_1\wedge \dots \wedge A_n)\to P& & P\vee \neg A_1\vee \neg A_2\vee \dots \vee \neg A_n\\ ⊢Q_1,\dots Q_m& & (Q_1,\dots ,Q_m)\to \perp & & \neg Q_1,\dots ,\neg Q_m\end{array}$$

Resolving goal results in: $\begin{array}{r}⊢Q_1,\dots ,Q_{i-1},Q_i,Q_{i+1},\dots ,Q_m\\ ⊢Q_1,\dots ,Q_{i-1},A_1,\dots ,A_n,Q_{i+1},\dots ,Q_m\end{array}$

Exercise 4

$\perp$ is the falsity symbol; boolean false

1. $\neg A\equiv A\to \perp$ which becomes :- A.
2. $A\vee \neg A\equiv A\to A$ which becomes A :- A. (N.B. the A are reversed)
3. $A$ becomes A. (fact)
4. $\neg A\vee \neg B\equiv \neg (A\wedge B)\to \perp \equiv A\wedge B\to \perp$ which becomes :- A, B.
5. $\neg A\vee \neg B\vee C\equiv \neg (A\wedge B)\to C\equiv A\wedge B\to C$ which becomes C :- A, B.