Question

Give a natural deduction proof from assumption ¬(φ → ψ) to conclusion φ ∧ ¬ψ.

Answer 1

To prove the statement φ ∧ ¬ψ from the assumption ¬(φ → ψ), we can use a proof by contradiction. Assuming that ¬(φ ∧ ¬ψ) is true, we show that it leads to a contradiction.

Step-by-step explanation:

In order to prove the statement φ ∧ ¬ψ from the assumption ¬(φ → ψ), we can use a proof by contradiction. Assuming that ¬(φ ∧ ¬ψ) is true, we will show that it leads to a contradiction.

1. Assume ¬(φ → ψ) (Assumption)
2. Assume φ ∧ ¬ψ (Assumption for contradiction)
3. From 2, we have ¬ψ (Simplification)
4. From 2, we have φ (Simplification)
5. From 1 and 4, we have ¬(φ → ψ) (Reiteration)
6. From 1 and 3, we have ¬φ (Modus Tollens)
7. From 5 and 6, we have ¬ψ (Disjunction Elimination)
8. From 4 and 7, we have φ ∧ ¬ψ (Conjunction Introduction)
9. From 1 and 8, we have ⊥ (Contradiction)
10. From 1, 8, and 9, we have φ ∧ ¬ψ (Proof by contradiction)

Therefore, from the assumption ¬(φ → ψ), we can conclude φ ∧ ¬ψ.