Prove [(q ˄ (p ↔ ¬ q) ) → q] is a tautology using logic laws

Question

How to prove that this statement is tautology using logic laws

(q ˄ (p ↔ ¬ q) ) → q

Edit:

I got stuck here after trying to apply De Morgan's law:

(q ˄ (p ↔ ¬ q)) → q
¬ [q ˄ (p ↔ ¬ q)] ˅ q
¬ q ˅ ¬ (p ↔ ¬ q) ˅ q
¬ q ˅ (¬ p ↔ q) ˅ q
¬ q ˅ [(¬ p → q) ˄ (q → ¬ p)] ˄ q

When you say "logic laws" what laws exactly are you referring to? Depending on what laws you can you, you may or may not be able to prove the statement. — Colm Bhandal, Dec 15 '15 at 14:54
But what's to prove? $(q \land r)\to q$ is a tautology, for any $r$. — BrianO, Dec 15 '15 at 16:38
It is not necessary to "unpack" $↔$; using commutativity and associativity, you can rewrite the fourth line as : $(¬ q \lor q) \lor [¬ (p ↔ ¬ q)]$ and then apply $a \lor \lnot a \equiv T$ and $T \lor a \equiv T$ to conclude that the formula is equivalent to $TRUE$, i.e. a tautology. — Mauro ALLEGRANZA, Dec 15 '15 at 16:44

score 1 · Answer 1 · answered Dec 15 '15 at 14:56

1

Hint: The desired tautology has the form $(q\wedge r)\rightarrow q$

answered Dec 15 '15 at 14:56

paw88789

Mauro ALLEGRANZA · Accepted Answer · 2015-12-15T15:37:10.130

1

Long comment

You have to use the equivalence between $a \to b$ and $\lnot a \lor b$.

It must be :

$(q \land (p \leftrightarrow ¬ q) ) \to q$

is equivalent to :

$\lnot [q \land (p \leftrightarrow ¬ q) ] \lor q$.

Then, apply De Morgan's laws to get :

$\lnot q \lor \lnot (p \leftrightarrow ¬ q) \lor q$.

Now it is quite easy ... (see Table of Logical Equivalences)

edited Dec 15 '15 at 15:37

answered Dec 15 '15 at 14:59

Mauro ALLEGRANZA

I have edited my post. can you check what's wrong ? and if it's right how can i continue/simplify the last statement? – J.doe123 Dec 15 '15 at 16:41

score 0 · Answer 3 · answered Dec 15 '15 at 15:00

It very much depends on which logic laws you're allowed to do.

If you have the axiom schema $\phi\land\psi\rightarrow\phi$ it follows by substituting $q$ for $\phi$ and $(p \leftrightarrow \neg q)$ for $\psi$.

If on the other hand you're allowed to use truth tables, then it's just a matter of making a truth table and see it to be a tautology.

3 Answers3