Show that given logical proposition is tautology

$((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $

  1. I can apply the implication rule first and got

$\lnot((A \implies C) \land (B \implies C) \land \lnot C) \lor \lnot (A \lor B) $

  1. I applied the implication rule again and got

$ \lnot (( \lnot A \lor C) \land ( \lnot B \lor C) \land \lnot C) \lor \lnot (A \lor B) $

At this point I cannot move any further.

I know that I need to apply somewhere De Morgan's rule and distributivity. Any suggestions?

  • $\begingroup$ Thanks, I edited it right now $\endgroup$
    – zimimi
    Jun 29, 2015 at 10:33

2 Answers 2


Clearly, if the right hand side is true you have nothing to show.

Assume that the right hand side is false. Then $A$ or $B$ is true.

Use it to show that the in this case the left hand side is always false.

If $C$ is true this is obvious, if $C$ is false then use the fact that $A$ or $B$ must be true.

  • $\begingroup$ Could you do it with formula, exactly as I started $\endgroup$
    – zimimi
    Jun 29, 2015 at 10:38
  • $\begingroup$ You showld use the De Morgan's rule on the left hand side (more than once) and also on the right hand side. $\endgroup$ Jun 29, 2015 at 10:45

I'll deny the consequent and then show that the antecedent and such a denial leads to the empty set.

from the antecedent 1 Cac 
from the antecedent 2 Cbc
from the antecedent 3 Nc   
1 clausify          4 ANac
2 clausify          5 ANbc     
deny the consequent 6 Aab
3, 4 resolve        7 Na
6, 7 resolve        8 b
3, 5 resolve        9 Nb
8, 9 resolve       10 {}

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .