1

Prove the following a tautology : (P ∧ ¬Q) ↔ ¬(P → Q)

I started with trying to seek a contradiction for (P ∧ ¬Q), but honestly I'm lost and don't know how to proceed. Any help would be appreciated.

David Hinton
  • 11
  • 1
  • 2
  • Prove using what: truth tables? boolean algebra? some deductive system? natural reasoning? For the latter you can reason as follows: if this is not a tautology then one of the sides of the equivalence is false while the other is true. This gives you two cases, one is that the left is true but the right is false. Then P is true and Q is false, see what it gives for the right side. Then do the other case. – Conifold Nov 02 '16 at 19:46
  • 1
    Maybe start on the right and see what happens when you distribute the negation? – Joseph Weissman Nov 02 '16 at 19:46
  • I'm unsure how formal/rigorous your proof needs to be. The basic method I would use is to use P->Q <-> ~P V Q, or prove it using truth tables. Then use boolean algebra with DeMorgan's law to make the right side of your equation equivalent to the left side. – Ameet Sharma Nov 02 '16 at 21:31
  • Though the actual formula is different, this is essentially a duplicate of http://philosophy.stackexchange.com/q/30139/2953. –  Nov 02 '16 at 23:13

1 Answers1

0

For left to right :

1) (P & ~ Q) --- premise

2) P --- by &-elim

3) ~ Q --- by &-elim

4) P → Q --- assumed [a]

5) Q --- by →-elim

6) Q & ~ Q --- contradiction !

7) ~ (P → Q) --- by ~-intro, discharging [a].

Thus far, we have proved :

(P & ~ Q) ⊢ ~ (P → Q).

Then by →-intro :

⊢ (P & ~ Q) → ~ (P → Q)

From right to left we need Double Negation :

1) ~ (P → Q) --- premise

2) ~ Q --- assumed [a]

3) P --- assumed [b]

4) ~ (P & ~ Q) --- assumed [c]

5) (P & ~ Q) --- from 2) and 3) by &-intro

6) contradiction from 4) and 5)

7) Q --- from 2) and 6) by Double Negation, discharging [a]

8) (P → Q) --- from 3) and 7) by →-intro, discharging [b]

9) contradiction from 1) and 8)

10) (P & ~ Q) --- from 4) and 9) by Double Negation, discharging [c].

Thus : ~ (P → Q) ⊢ (P & ~ Q) and then, by →-intro :

⊢ ~ (P → Q) → (P & ~ Q)

Mauro ALLEGRANZA
  • 36,790
  • 3
  • 36
  • 80