Natural deduction (negated implication)

In summary: Well, that just depends on how many steps it takes you to get a contradiction. No doubt you are more efficient at it than I am.
  • #1
Logic1
2
0
The proposition ¬(P→Q) is equivalent to ¬P^Q

Does someone maybe have an idea how you can prove (directly) ¬P^Q from ¬(P→Q) by means of natural deduction? I do not manage it.

Thanks in advance!
 
Physics news on Phys.org
  • #2
I would disagree with the problem. It's true that $\lnot(p\to q) \equiv (p\land\lnot q),$ but it is not true that $\lnot(p\to q)\equiv(\lnot p \land q)$. (A quick truth table will tell you this.) So you need to prove $\lnot(p\to q) \implies (p\land\lnot q)$ and you need to prove $(p\land\lnot q) \implies \lnot(p\to q)$.

Let's take the first one: $\lnot(p\to q) \implies (p\land\lnot q)$. What logical symbols $(\lnot, \land, \lor, \to, \equiv)$ are present/absent in the conclusion versus the premise? Well, we see that there's a $\to$ in the premise, but not in the conclusion, and there's a $\land$ in the conclusion that's not in the premise. So we might well need $\to$ elimination, as well as $\land$ introduction. You see how that can help you structure your proof?
 
  • #3
Thank Ackbach!

I made a typing error I think. I meant ¬(p→q)⟹(p∧¬q) of course.

To apply the ∧-introduction, I need to get P and ¬Q. But I do not see yet which steps I can start with to make the →-elimination possible (it's clearly not applicable immediately).
 
  • #4
Logic said:
Thank Ackbach!

I made a typing error I think. I meant ¬(p→q)⟹(p∧¬q) of course.

To apply the ∧-introduction, I need to get P and ¬Q. But I do not see yet which steps I can start with to make the →-elimination possible (it's clearly not applicable immediately).

Right, exactly. I would think about using $\lnot$ elimination. It's a powerful method, because you can construct sub-proofs by assuming anything you want. Don't forget contradiction elimination, where you can conclude anything you want from a contradiction. That's an important proof technique in subproofs. What outline do you have?
 
  • #5
Here's what I mean by outline, and this is what I would recommend for you to do. Basically, you're going to use $\land$ intro as the main organizing principle.

View attachment 7751
 

Attachments

  • Logic Problem 2018-02-09 Outline.png
    Logic Problem 2018-02-09 Outline.png
    3.3 KB · Views: 84
  • #6
Ackbach said:
Here's what I mean by outline, and this is what I would recommend for you to do. Basically, you're going to use $\land$ intro as the main organizing principle.

Is step 2 hypothesis for contradiction??
 
  • #7
solakis said:
Is step 2 hypothesis for contradiction??

Yep, that's right!
 
  • #8
Ackbach said:
Yep, that's right!

Then on the 6th step we should have ~~P and not on the 8th step
 
  • #9
solakis said:
Then on the 6th step we should have ~~P and not on the 8th step

Well, that just depends on how many steps it takes you to get a contradiction. No doubt you are more efficient at it than I am.
 

What is natural deduction?

Natural deduction is a method of deductive reasoning in logic that uses a set of rules to establish the validity of an argument. It is based on the idea that the truth of a statement can be determined by the truth of its premises and the validity of the logical rules used to derive it.

What is negated implication in natural deduction?

Negated implication is a logical operator that is used to express the negation of a conditional statement. In natural deduction, it is represented by the symbol ¬→ and is read as "not implies". It is used to show that if the antecedent of a conditional statement is false, then the entire statement is true.

What are the rules for negated implication in natural deduction?

The main rules for negated implication in natural deduction are the negation introduction and elimination rules. The negation introduction rule states that if we can prove a statement P implies a contradiction, then we can conclude that the negation of P is true. The negation elimination rule states that if we have a negated statement and we can prove a contradiction from its negation, then the original statement must be true.

How is negated implication used in proofs?

Negated implication is often used in proofs to show the validity of arguments. It is used to break down complex statements into simpler ones and to show the logical relationships between them. By using the rules of negated implication, we can establish the truth of a statement or refute its validity.

What are some common mistakes when using negated implication in natural deduction?

One common mistake when using negated implication in natural deduction is incorrectly applying the rules. It is important to carefully follow the rules and make sure they are applied correctly. Another mistake is assuming that a statement is true or false without sufficient evidence, which can lead to incorrect conclusions. It is also important to avoid mixing up the negation of a statement with its contrapositive, as they are not equivalent in natural deduction.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
808
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
849
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
0
Views
963
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Back
Top