3336 Homework Assignment 3 Due Thursday, 02/07, 11:59pm 1. Consider the following hypotheses: x (p(x) q(x)) H2 :

Math.3336 Homework Assignment 3

Due Thursday, 02/07, 11:59pm

1. Consider the following hypotheses:

H1 : ∃x (p(x) ∧ q(x)) H2 : ∀x (q(x) → r(x)) Use rules of inference to prove that the following conclusion follows from these hypotheses:

C : ∃x (p(x) ∧ r(x)) Clearly label the inference rules used at every step of your proof.

2. Consider the following hypotheses:

H1 : ∀x (¬C(x) → ¬A(x)) H2 : ∀x (A(x) → ∀y B(y)) H3 : ∃x A(x) Use rules of inference to prove that the following conclusion follows from these hypotheses:

C : ∃x (B(x) ∧ C(x)) Clearly label the inference rules used at every step of your proof.

3.

Consider the following predicate quantified formula:

∃x ∀y (P (x, y) ↔ ¬P (y, y)) Prove the unsatisfiability of this formula using rules of inference.

1 4. Translate into English the statement

∀