Question

1. Show that (p → q) ∨ (q → r) and p → (q ∨ r) are not logically equivalent.

2. Prove that [p ∧ (p → q)] → q is a tautology using (a) truth table (b) logical equivalences.
3. Determine whether the given compound proposition is satisfiable: (p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q).
4. Determine the truth value of each of these statements if the universe of discourse for all variables consists of all real numbers.
(a) ∀x∃y(x 2 = y)
(b) ∃x∀y(xy = y)
(c) ∃x∃y(x + 2y = 5)
(d) ∀x∀y(x + y > 0)

Answer 1

To show that (p → q) ∨ (q → r) and p → (q ∨ r) are not logically equivalent, we can construct a truth table for both propositions. The truth table shows that they do not have the same truth value in all cases, which means they are not equivalent.

p q r p → q q → r (p → q) ∨ (q → r) q ∨ r p → (q ∨ r)

T T T T T T T T

T T F T F T T T

T F T F T T T T

T F F F T T T T

F T T T T T T T

F T F T F T T T

F F T T T T T T

F F F T T T F F

As we can see from the truth table, there are two cases where the propositions have different truth values: when p is false and q is true, and when p, q, and r are all false. Therefore, (p → q) ∨ (q → r) and p → (q ∨ r) are not logically equivalent.

To prove that [p ∧ (p → q)] → q is a tautology, we can use a truth table or logical equivalences.

(a) Truth table:

p q p → q p ∧ (p → q) [p ∧ (p → q)] → q

T T T T T

T F F F T

F T T F T

F F T F T

As we can see from the truth table, the proposition [p ∧ (p → q)] → q is true in all cases, which means it is a tautology.

(b) Logical equivalences:

[p ∧ (p → q)] → q

= ¬[p ∧ (p → q)] ∨ q (implication)

= ¬p ∨ ¬(p → q) ∨ q (de Morgan's law)

= ¬p ∨ ¬(¬p ∨ q) ∨ q (implication)

= ¬p ∨ (p ∧ ¬q) ∨ q (de Morgan's law)

= (¬p ∨ p ∨ q) ∧ (¬p ∨ ¬q ∨ q) (distributive law)

= (¬p ∨ q) ∧ (¬p ∨ T) (complement and identity)

= ¬p ∨ q (simplification)

Since ¬p ∨ q is a tautology,