Question

Use logical equivalences to simplify (p → q) → (¬p → ¬q) until you have at most one occurrence of each variable p, q remaining. Identify all logical equivalences by name.

a) De Morgan's laws
b) Modus tollens
c) Modus ponens
d) Contraposition

Answer 1

The expression (p → q) → (¬p → ¬q) is simplified using logical equivalences to (p ∧ ¬q) → (¬p ∧ q), which is the simplest form with one occurrence of each variable p and q.

Step-by-step explanation:

The question asks to use logical equivalences to simplify (p → q) → (¬p → ¬q) using named logical frameworks such as De Morgan's laws, contraposition, and others. To simplify this expression, we'll apply logical equivalences step by step:

• The implication p → q is logically equivalent to ¬p ∨ q (implication).
• Similarly, ¬p → ¬q is equivalent to p ∨ ¬q (implication).
• Now, using the initial expression, we replace the implications following the rules above, turning (p → q) → (¬p → ¬q) into (¬p ∨ q) → (p ∨ ¬q).
• Next, we apply the contraposition equivalence to the new expression and obtain (¬(p ∨ ¬q)) → (¬(¬p ∨ q)),
• Applying De Morgan's laws, we simplify to (¬p ∧ q) → (p ∧ ¬q).
• This expression is the simplest form with one occurrence of each variable p and q without further simplification.

Therefore, the simplified expression of (p → q) → (¬p → ¬q) is (¬p ∧ q) → (p ∧ ¬q) using logical equivalences such as implication, contraposition, and De Morgan's laws.