proof using contradiction

[triclino]

Prove using contradiction the following:

 

[p<=>(q <=>r)] =>[(p<=>q)=> r]

[shyvera]

Use the following rules:

 

[math]a\Leftrightarrow b\ \equiv\ (a\wedge b)\vee(\neg a\wedge \neg b)[/math]

 

[math]\neg(a\Leftrightarrow b)\ \equiv\ (a\wedge \neg b)\vee(\neg a\wedge b)[/math]

 

Thus: [math]\neg[(p\Leftrightarrow q)\Rightarrow r][/math]

 

[math]\implies\ (p\Leftrightarrow q)\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\vee(\neg p\wedge\neg q)]\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\wedge\neg r]\vee[(\neg p\wedge\neg q)\wedge\neg r][/math]

 

[math]\implies\ [p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)][/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}\vee\{[p\wedge(\neg q\wedge r)]\vee[\neg p\wedge(q\wedge r)]\}[/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[p\wedge(\neg q\wedge r)]\}\vee\{[\neg p\wedge(q\wedge r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ \{p\wedge[(q\wedge\neg r)\vee(\neg q\wedge r)]\}\wedge\{\neg p\wedge[(q\wedge r)\vee(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ [p\wedge\neg(q\Leftrightarrow r)]\wedge[\neg p\wedge(q\Leftrightarrow r)][/math]

 

[math]\implies\ \neg[p\Leftrightarrow(q\Leftrightarrow r)][/math]

[triclino]

Use the following rules:

 

[math]a\Leftrightarrow b\ \equiv\ (a\wedge b)\vee(\neg a\wedge \neg b)[/math]

 

[math]\neg(a\Leftrightarrow b)\ \equiv\ (a\wedge \neg b)\vee(\neg a\wedge b)[/math]

 

Thus: [math]\neg[(p\Leftrightarrow q)\Rightarrow r][/math]

 

[math]\implies\ (p\Leftrightarrow q)\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\vee(\neg p\wedge\neg q)]\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\wedge\neg r]\vee[(\neg p\wedge\neg q)\wedge\neg r][/math]

 

[math]\implies\ [p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)][/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}\vee\{[p\wedge(\neg q\wedge r)]\vee[\neg p\wedge(q\wedge r)]\}[/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[p\wedge(\neg q\wedge r)]\}\vee\{[\neg p\wedge(q\wedge r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ \{p\wedge[(q\wedge\neg r)\vee(\neg q\wedge r)]\}\wedge\{\neg p\wedge[(q\wedge r)\vee(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ [p\wedge\neg(q\Leftrightarrow r)]\wedge[\neg p\wedge(q\Leftrightarrow r)][/math]

 

[math]\implies\ \neg[p\Leftrightarrow(q\Leftrightarrow r)][/math]

 

Where is the contradiction

[shyvera]

You are assuming [math][p\Leftrightarrow(q\Leftrightarrow r)]\Rightarrow[(p\Leftrightarrow q)\Rightarrow r][/math] to be false. This is equivalent to [math][p\Leftrightarrow(q\Leftrightarrow r)]\wedge\neg[(p\Leftrightarrow q)\Rightarrow r].[/math] What I did was to show that [math]\neg[(p\Leftrightarrow q)\Rightarrow r][/math] would lead to [math]\neg[p\Leftrightarrow(q\Leftrightarrow r)][/math] which would make a contradiction with [math]p\Leftrightarrow(q\Leftrightarrow r).[/math]

[triclino]

Use the following rules:

 

[math]a\Leftrightarrow b\ \equiv\ (a\wedge b)\vee(\neg a\wedge \neg b)[/math]

 

[math]\neg(a\Leftrightarrow b)\ \equiv\ (a\wedge \neg b)\vee(\neg a\wedge b)[/math]

 

Thus: [math]\neg[(p\Leftrightarrow q)\Rightarrow r][/math]

 

[math]\implies\ (p\Leftrightarrow q)\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\vee(\neg p\wedge\neg q)]\wedge\neg r[/math]

 

[math]\implies\ [(p\wedge q)\wedge\neg r]\vee[(\neg p\wedge\neg q)\wedge\neg r][/math]

 

[math]\implies\ [p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)][/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}\vee\{[p\wedge(\neg q\wedge r)]\vee[\neg p\wedge(q\wedge r)]\}[/math]

 

[math]\implies\ \{[p\wedge(q\wedge\neg r)]\vee[p\wedge(\neg q\wedge r)]\}\vee\{[\neg p\wedge(q\wedge r)]\vee[\neg p\wedge(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ \{p\wedge[(q\wedge\neg r)\vee(\neg q\wedge r)]\}\wedge\{\neg p\wedge[(q\wedge r)\vee(\neg q\wedge\neg r)]\}[/math]

 

[math]\implies\ [p\wedge\neg(q\Leftrightarrow r)]\wedge[\neg p\wedge(q\Leftrightarrow r)][/math]

 

[math]\implies\ \neg[p\Leftrightarrow(q\Leftrightarrow r)][/math]

 

So now let us examine your proof:

 

According to your rule (which you must show how you get):

 

[math]\neg(a\Leftrightarrow b)\ \equiv\ (a\wedge \neg b)\vee(\neg a\wedge b)[/math]

 

To get :[math] \neg[p\Leftrightarrow(q\Leftrightarrow r)][/math]

 

You must have :[math] [p\wedge\neg(q\Leftrightarrow r)]\vee[\neg p\wedge(q\Leftrightarrow r)][/math]

 

Instead of [math] [p\wedge\neg(q\Leftrightarrow r)]\wedge[\neg p\wedge(q\Leftrightarrow r)][/math]

 

That you have in your proof