Jump to content

proof using contradiction


triclino

Recommended Posts

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]

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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]

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.