# Solve it by using logical proposition

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?

• Thanks, I edited it right now Jun 29, 2015 at 10:33

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.

• Could you do it with formula, exactly as I started Jun 29, 2015 at 10:38
• You showld use the De Morgan's rule on the left hand side (more than once) and also on the right hand side. 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 {}