2

I am new to logic. and here are my tryouts for deriving deriving "(p.q) v (p.r) from "p.(q v r)", and further I want to show that ”p.(q V r)” is equivalent to ”(p.q) V (p.r)”, by using natural deduction.

first try:

[1]......1. p.(q V r)

[1]......2. q V r ... .....................(1) CE

[1]......3. p ...............................(1) CE

[1]......4. ?

I need two "p" for the conclusion, how can I introduce another "p" and keep it in the conclusion?

or, second try:

[1]........1. p.(q V r)

[2]........2. - r .................................P

[1,2]......3. (p.q) ........................(1)(2) DE

[1]........4. - r > (p.q) ....................2 D

[1]........5. ?

  • is the dot a conjunction? So "p & (q v r) ⊢ (p&q) v (p&r)"? – Marc H. Apr 3 '18 at 9:49
  • yes, dot is conjunction. – agBerg Apr 3 '18 at 9:59
  • Are you allowed to use Logical replacement rules? If so there is a specific one that this example covers immediately. This would be proven by truth table. – Logikal Apr 5 '18 at 20:36
  • If you want a standard proof, you have to figure out what axioms you want to start with. The property you mention is known as distribution, and is commonly an axiom. There are also other methods, such as truth tables or Venn diagrams. – Acccumulation Apr 5 '18 at 20:40
3

First, we have to unpack the premise p ∧ (q ∨ r) using conjunction elimination to get the two conjuncts: p and (q ∨ r).

Then, we have to use proof by cases (i.e. disjunction elimination) to derive p ∧ q by conjunction introduction followed by (p ∧ q) ∨ (p ∧ r) by disjunction introduction, in the first case, and p ∧ r by conjunction introduction followed by (p ∧ q) ∨ (p ∧ r) by disjunction introduction, in the second case.

Having derived (p ∧ q) ∨ (p ∧ r) from both disjuncts of (q ∨ r), we can conclude that it follows from the premise, i.e. that :

(p ∧ q) ∨ (p ∧ r) is a logical consequence of p ∧ (q ∨ r).

1

Here is a proof done in Fitch:

enter image description here

0

The Fitch-style natural deduction proof checker and editor I am using for this answer is associated with the book forall x: Calgary Remix.

Here is the question:

first try:

1......1. p.(q V r)

1......2. q V r ... .....................(1) CE

1......3. p ...............................(1) CE

1......4. ?

I need two "p" for the conclusion, how can I introduce another "p" and keep it in the conclusion?

The solution below is similar to what Bram28 provided in lines 2-11:

Output from http://proofs.openlogicproject.org/

To get past line 3, we need to eliminate the disjunction, the ∨ symbol. This is an "or" statement. Either Q is true or R is true. So to eliminate the "or" we need to consider two cases. I drew thin blue boxes around the two cases, one for Q and one for R.

Regarding the question about needing two "p" for the conclusion, the extra "p" is added in lines 6 for the Q case and in line 9 for the R case.

Note how this was done in the Q case.

In line 4 I started a sub-proof by assuming Q. I need no justification for that assumption.

In line 5 I used the fact that in line 2 I already have P and in line 4 I have Q as an assumption. Since I have both of them I can introduce a conjunction, that is, an "and" statement. Now I have P ∧ Q, part of the conclusion I want.

After that I can introduce a disjunction, that is, an "or" statement to the P ∧ Q. What will I add? I can add anything I want. I already know this statement is true because one of the cases, P ∧ Q, is true. So I introduce the ∨ with precisely what I need to get the result I want: P ∧ R.

I've taken care of the two cases by constructing a sub-proof for each one and in each case I reached the desired conclusion. The proof will be complete once I claim that. In line 10 I state the conclusion from both sub-proofs. The justification of this is an elimination of the disjunction I started with in line 3 using sub-proofs in lines 4-6 and 7-9.

The proof checker confirms the solution.

We can go in the other direction as well. Bram28 does this in lines 12-23 of that proof. The last line of that proof introduces a biconditional by referencing as justification for the introduction the two sub-proofs on lines 2-11 and 12-23.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.