1

I'm taking an intro logic course this semester and my prof is hard to follow and not really great at clarifying things. I'm stuck on this question in my assignment, I'm just not sure how to start. I think I just need a jump start on how to tackle this sort of question.

So the question is, using basic inference rules, provide derivation to prove distributivity of $\lor$ over $\land$:

$P \lor (Q \land R) \vDash (P \lor Q) \land (P \lor R)$

$(P \lor Q) \land (P \lor R) \vDash P \lor (Q \land R)$

dyingatmidnight
  • 35

3 Answers3

4

You can prove them with Natural Deduction.

For $P∨(Q∧R) \vDash (P∨Q)∧(P∨R)$ :

1) $P∨(Q∧R)$ --- assumed

2) $P$ --- assumed [a] for $\lor$-elimination (or proof by cases)

3) $P \lor Q$ --- from 2) by $\lor$-introduction

4) $P \lor R$ --- from 3) by $\lor$-introduction

5) $(P∨Q)∧(P∨R)$ --- from 3) and 4) by $\land$-introduction

6) $Q \land R$ --- assumed [b] for $\lor$-elimination

7) $Q$ --- from 6) $\land$-elimination

8) $P \lor Q$ --- from 7) by $\lor$-introduction

9) $R$ --- from 6) $\land$-elimination

10) $P \lor R$ --- from 9) by $\lor$-introduction

11) $(P∨Q)∧(P∨R)$ --- from 8) and 10) by $\land$-introduction

Now, having derived $(P∨Q)∧(P∨R)$ from $P$ (see 2-5) and from $Q \land R$ (see 6-10) we can derive it from $P∨(Q∧R)$ by $\lor$-elimination, discharging assumptions [a] and [b] :

12) $(P∨Q)∧(P∨R)$ --- from 2), 5), 6) and 11) by $\lor$-elimination.

The above proof shows that :

$P∨(Q∧R) \vdash (P∨Q)∧(P∨R)$;

by completeness, we conclude with : $P∨(Q∧R) \vDash (P∨Q)∧(P∨R)$.

In the same way, we can proceed for : $(P∨Q)∧(P∨R) \vDash P∨(Q∧R)$.

You can easily modify the above proof according to this List of rules of inference :

  • steps 3 and 4 are Addition (or Disjunction Introduction)

  • step 5 is Adjunction (or Conjunction Introduction)

  • after step 5 we need Deduction theorem (or Conditional Introduction)

  • the same set of rules must be used for steps 6-11

  • finally, we have to apply in step 12 Case analysis.

Mauro ALLEGRANZA
  • 94,169
  • Oh gosh thank you!! The rules list you linked to are the ones we're using (We haven't gotten around to resolution yet). This is so much clearer than how my prof is explaining things. – dyingatmidnight Jan 22 '15 at 11:17
  • The only thing I'm fuzzy on is the use of Deduction theorem, that's one my prof has mentioned a lot but his examples on it aren't clear at all. – dyingatmidnight Jan 22 '15 at 11:25
  • @dyingatmidnight - the use of the Deduction th is easy explained; when you have derived the formula $\beta$ from the assumption $\alpha$, in symbols : $\alpha \vdash \beta$, you can use it in a new step deriving : $\alpha \rightarrow \beta$. In the above proof (2nd version) having derived (step 5) : $(P∨Q)∧(P∨R)$ form $P$, i.e. $P \vdash (P∨Q)∧(P∨R)$ we add step 5') : $P \rightarrow ((P∨Q)∧(P∨R))$ --- by DT. The same with 11') : $(Q \land R) \rightarrow ((P∨Q)∧(P∨R))$. Now, with 1) $P \lor (Q \land R)$, we are ready for Case analysis. – Mauro ALLEGRANZA Jan 22 '15 at 12:24
  • @dyingatmidnight - you can see this post for some comments on Ded Th. – Mauro ALLEGRANZA Jan 22 '15 at 12:29
  • so it turns out I was confusing Case Analysis with law of cases. Which doesn't seem to be the same thing. I'll try to upload a scan of the handout I have. – dyingatmidnight Jan 22 '15 at 14:23
  • http://i57.tinypic.com/1zy7urq.jpg I'm posting from my phone, sorry :) – dyingatmidnight Jan 22 '15 at 14:29
0

[Oops, didn't 't notice that this is a old question when it popped up: but I'll leave this here.]

To add to Mauro's answer, these are (as it happens) Questions 1 and 4 of the end-of-chapter Exercises for Chapter 21 of the second edition of my Intro to Formal Logic.

This version of the book isn't out yet BUT ...

The Exercises are available online AND also detailed worked answers with lots of hints about proof strategies.

For links, visit https://www.logicmatters.net/ifl/ifl2nd/ifl2-exercises-and-answers-2/

The relevant Exercises on propositional natural deduction are for Chs 20 to 23, and the worked answers run to over 40 pages. There is also a summary of the standard rules the book uses (you should then be able to adjust proof ideas easily to fit other reasonably closely related proof systems). Enjoy!

Peter Smith
  • 54,743
-1

Proving the Distributive Rule

x & (y V z) :: (x & y) V (x & z)

In order to prove the Distributive Rule, you must show that BOTH of the following statements are true:

                 Statement #1:     x  & (y V z) → (x & y) V (x & z)   

                                         AND

                   Statement #2:   (x & y) V (x & z) → x  & (y V z)

I show a separate proof for each of these statements:

Proof of Statement #1: x & (y V z) → (x & y) V (x & z)

x & (y V z) P x 1 Simp y V z 1 Simp ~ (x & y) AP ~ x V ~ y 4 DeM ~ y 2, 5 DS z 3, 6 DS x & z 2, 7 Conj ~ (x & y) → (x & z) 4-8 CP (x & y) V (x & z) 9 DeM

Proof of Statement #2: (x & y) V (x & z) → x & (y V z)

(x & y) V (x & z) P ~ x AP ~ x V ~ y 2 Add ~ x V ~ z 2 Add ~ ( x & y) 3 DeM ~ ( x & z) 4 DeM ~ ( x & y) & ~ ( x & z) 5, 6 Conj ~ ( ( x & y) V ( x & z) ) 7 DeM ~ (( x&y) V (x&z)) & ((x&y) V (x&z)) 1, 8 Conj x 2-9 IP ~ ( y V z) AP ~ y & ~ z 11 DeM ~ y 12 Simp ~ z 12 Simp ~ z V ~ x 14 Add ~ ( x & z) 15 DeM x & y 1 DS y 17 Simp y V z 18 Add ~ ( y V z) & ( y V z) 11, 19 Conj y V z 11 - 20 IP x & ( y V z) 10, 21 Conj

We can also prove the other Distributive Rule:

x V (y & z) :: (x V y) & (x V z)

In order to prove this Distributive Rule, you must show that BOTH of the following statements are true:

                 Statement #1:     x  V (y & z) → (x V y) & (x V z)   

                                         AND

                   Statement #2:   (x V y) & (x V z) → x  V (y & z)

I show a separate proof for each of these statements:

Proof of Statement #1: x V (y & z) → (x V y) & (x V z)

x V (y & z) P ~ ( x V y) AP ~ x & ~ y 2 DeM ~ x 3 Simp ~ y 3 Simp y & z 1, 4 DS y 6 Simp y & ~ y 5, 7 Conj x V y 2 - 8 IP ~ ( x V z) AP ~ x & ~ z 10 DeM ~ x 11 Simp ~ z 11 Simp y & z 1, 12 DS z 14 Simp z & ~ z 13, 15 Conj x V z 10 - 16 IP ( x V y ) & ( x V z) 9, 17 Conj

Proof of Statement #2: (x V y) & (x V z) → x V (y & z)

( x V y ) & ( x V z ) P x V y 1 Simp x V z 1 Simp ~ x AP y 2, 4 DS z 3, 4 DS y & z 5, 6 Conj ~ x → ( y & z ) 4 - 8 CP x V ( y & z ) 8 Impl

Rocco Anthony jerry
  • 1