• Support PF! Buy your school textbooks, materials and every day products Here!

Logic Problem in a Proof

  • Thread starter Horse
  • Start date
  • #1
35
0

Homework Statement



Prove or disprove:

"If you can prove [tex] ( y \wedge \neg c ) \rightarrow Contradiction [/tex], then
[tex] y \rightarrow c [/tex] must be right."


Homework Equations



My teacher used the sign [tex] \wedge [/tex], instead of [tex] \vee [/tex], like:

"If [tex]( a \wedge b \wedge \neg c ) \rightarrow Contradiction [/tex], then [tex] a \wedge b \rightarrow c [/tex] must be right."

I feel it is not right.

The Attempt at a Solution



I proved in my replies:

"If you can prove [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] a \wedge b \rightarrow c [/tex] must be right."

I used the facts in my proof:

[tex] a \wedge \neg b = \neg ( a \rightarrow b ) = ( a \not \rightarrow b ) \not = \neg b \rightarrow \neg a \not = \neg a \not \rightarrow \neg b[/tex]
 
Last edited:

Answers and Replies

  • #2
20
1
I'm pretty sure you're either missing something or else you have mistyped it. (*) does not follow from the two contradictions given.
 
  • #3
35
0
I'm pretty sure you're either missing something or else you have mistyped it. (*) does not follow from the two contradictions given.
Let's simplify. I know for sure:


[tex]\neg ( a \rightarrow b ) = a \wedge \neg b [/tex]

So

[tex]( a \rightarrow b ) = \neg a \vee b[/tex]

If I want to prove [tex]( a \rightarrow b )[/tex], then the finding [tex] a \wedge \neg b \rightarrow Contradiction[/tex] will prove it. Please, notice that [tex] \neg ( a \rightarrow b ) \rightarrow Contradiction [/tex] because the two statements are equivalent. As [tex] \neg ( a \rightarrow b ) [/tex] and [tex] ( a \rightarrow b ) [/tex] cannot be true at the same time, the conclusion must be valid.


Let's compare its logic to the logic in the case:
The Argument:

[tex] a \wedge b \rightarrow c [/tex] (*)

Its contradictions:

[tex] \neg a \wedge b \wedge \neg c \rightarrow Contradiction[/tex]

[tex] a \wedge \neg b \wedge \neg c \rightarrow Contradiction[/tex]
We notice that the argument is:
[tex]a \wedge b \rightarrow c = \neg ( a \rightarrow \neg b ) \rightarrow c [/tex]

So [tex] \neg ( \neg ( a \rightarrow \neg b ) \rightarrow c ) \rightarrow Contradiction [/tex] must prove it, by the logic above this reply.

Let's write its part differently:

[tex] \neg ( \neg ( a \rightarrow \neg b ) \rightarrow c ) = \neg ( a \rightarrow \neg b ) \not \rightarrow c = a \wedge b \not \rightarrow c [/tex]

So I need to find that:

[tex] ( a \wedge b \not \rightarrow c ) \rightarrow Contradiction = ( \neg a \vee \neg b \rightarrow \neg c ) \rightarrow Contradiction[/tex]

Let's call [tex] d = \neg a \vee \neg b [/tex]. So

[tex] ( d \rightarrow \neg c ) \rightarrow Contradiction[/tex]

Let's use again:

[tex]( a \rightarrow b ) = \neg a \vee b[/tex]

So it becomes:
[tex] ( d \rightarrow \neg c ) \rightarrow Contradiction = ( \neg d \vee \neg c ) \rightarrow Contradiction [/tex]

It is equivalent to:

[tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex]

Conclusion

My teacher probably had something wrong. It should be right:

[tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex]
 
Last edited:
  • #4
35
0
New Problem

Prove [tex] a \vee b \rightarrow c [/tex]

Conjecture, according to my last proof:

"If you can prove [tex] ( a \vee b \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] a \vee b \rightarrow c [/tex] must be right."

It is similar to the last proof by contradiction:

"If you can prove [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] a \wedge b \rightarrow c [/tex] must be right."
 
Last edited:
  • #5
35
0


Prove [tex] a \vee b \rightarrow c [/tex]

Conjecture, according to my last proof:

"If you can prove [tex] ( a \vee b \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] a \vee b \rightarrow c [/tex] must be right."

It is similar to the last proof by contradiction:

"If you can prove [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] a \wedge b \rightarrow c [/tex] must be right."
Let's analyse them. Let [tex] p = a \vee b [/tex] and [tex] y = a \wedge b[/tex]. So the problems become:

"If you can prove [tex] ( p \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] p \rightarrow c [/tex] must be right."

"If you can prove [tex] ( y \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] y \rightarrow c [/tex] must be right."

I think the problem is now solved, because you can see it is basically of the same form.
 
  • #6
35
0


"If you can prove [tex] ( y \vee \neg c ) \rightarrow Contradiction [/tex], then
[tex] y \rightarrow c [/tex] must be right."
Does the following method work?

"If you can prove [tex] ( y \wedge \neg c ) \rightarrow Contradiction [/tex], then
[tex] y \rightarrow c [/tex] must be right."
 
Last edited:

Related Threads for: Logic Problem in a Proof

Replies
9
Views
8K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
398
Replies
2
Views
2K
  • Last Post
Replies
10
Views
4K
Top