Problem 5 - Logic / Predicate

Answer the following questions concerning logical formula.

1.

Transform the following formula to a clause set:

$$\forall X \left( p(X) \supset \exists Y (q(X, Y) \wedge r(Y)) \right).$$

2.

Show whether the following formula are valid, together with reasons:

(a)

$\forall X \exists Y p(X, Y) \supset \exists Y \forall X p(X, Y)$;

(b)

$\exists Y \forall X p(X, Y) \supset \forall X \exists Y p(X, Y)$;

(c)

$p(X) \supset \forall X p(X)$.

1.

Rewriting: $\forall X \left( p(X) \rightarrow \exists Y (q(X, Y) \wedge r(Y)) \right)$.

Prenex form: $\forall X \exists Y \left( p(X) \rightarrow (q(X, Y) \wedge r(Y)) \right)$.

Skolemized form: $\forall X \left( p(X) \rightarrow (q(X, h_1^1(X)) \wedge r(h_1^1(X))) \right)$.

Without universal quantifier: $p(X) \rightarrow (q(X, h_1^1(X)) \wedge r(h_1^1(X)))$.

Truth table:

$\neg$	$p(X)$	$\rightarrow$	$(q(X, h_1^1(X))$	$\wedge$	$r(h_1^1(X)))$
F	T	T	T	T	T
T	T	F	T	F	F
T	T	F	F	F	T
T	T	F	F	F	F
F	F	T	T	T	T
F	F	T	T	F	F
F	F	T	F	F	T
F	F	T	F	F	F

Disjonctive normal form:
$\neg ( (p(X) \wedge q(X, h_1^1(X)) \wedge \neg r(h_1^1(X)))$
$\vee (p(X) \wedge \neg q(X, h_1^1(X)) \wedge r(h_1^1(X)))$
$\vee (p(X) \wedge \neg q(X, h_1^1(X)) \wedge \neg r(h_1^1(X))) )$

De Morgan's law:
$(\neg p(X) \vee \neg q(X, h_1^1(X)) \vee r(h_1^1(X)))$
$\wedge (\neg p(X) \vee q(X, h_1^1(X)) \vee \neg r(h_1^1(X)))$
$\wedge (\neg p(X) \vee q(X, h_1^1(X)) \vee r(h_1^1(X)))$

Set notation:
$\{\neg p(X) , \neg q(X, h_1^1(X)) , r(h_1^1(X))\}$
$,\{\neg p(X) , q(X, h_1^1(X)) , \neg r(h_1^1(X))\}$
$,\{\neg p(X) , q(X, h_1^1(X)) , r(h_1^1(X))\}$

2.

See [HAM88] for a detailed answer to this question.