# Math Help - Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

1. ## Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

Hi,

I am trying to answer the following exam question:
Let $\theta$ be $((p\wedge\neg q)\vee(\neg p\wedge q))$.
Show that $\theta\vdash(p\vee q)$ but that neither $\theta\vdash p$ nor $\theta\vdash q$

(Note: this question is using Propositional logic)

My current attempt is this:
1. Given $((p\wedge\neg q)\vee(\neg p\wedge q))$
2. Assume $\neg (p \vee q)$
3. Assume $p$
4. Using "OR introduction" $(p \vee q)$
5. Contradiction in lines 2 and 4
6. Derive $\neg p$ using Reductio Ad Absurdum
7. Assume $q$
8. Using "OR introduction" $(p \vee q)$
9. Contradiction in lines 2 and 8
10. Derive $\neg q$ using Reductio Ad Absurdum
11. Using "AND introduction" $(\neg p \wedge \neg q)$

I'm not sure where to go from here.

Can anyone help?

Thanks

2. ## Re: Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

It's simpler to have a direct proof rather than a proof by contradiction. You need to apply disjunction elimination (reasoning by cases) to $(p\wedge\neg q)\vee(\neg p\wedge q)$. If $p\wedge\neg q$ holds, then p and so $p\lor q$. The other case is similar.

3. ## Re: Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

I'm not sure if we're allowed to reason by cases in the exam.
The rules that we're allowed to use are:
1. (Given Statements Rule) Any $\sigma \in \Sigma$ may be deduced from $\Sigma$ in one step
2. (Top Rule) The statement $\top$ may be deduced from any $\Sigma$ in one step
3. ( $\wedge$-Introduction) If $\sigma$ and $\tau$ have been derived from $\Sigma$ then $(\sigma \wedge \tau)$ may be deduced from $\Sigma$ in one further step
4. ( $\vee$-Introduction) If $\tau$ has been deduced from $\Sigma$ then either $(\sigma \vee \tau)$, $(\tau \vee \sigma)$ may be deduced from $\Sigma$ in one further step
5. ( $\wedge$-Elimination) If $(\sigma \wedge \tau)$ has been deduced from $\Sigma$ the either $\sigma$ or $\tau$ may be deduced from $\Sigma$ in one further step
6. ( $\vee$-Elimination) If $(\sigma \vee \tau)$ and $\neg \sigma$ have been deduced from $\Sigma$ then $\tau$ may be deduced from $\Sigma$ in one further step
7. ( $\neg$-Elimination) If $\neg \neg \sigma$ has been deduced from $\Sigma$ then $\sigma$ may be deduced from $\Sigma$ in one further step
8. (Contradiction Rule) If $\sigma$ and $\neg \sigma$ have been deduced from $\Sigma$ then $\bot$ may be deduced from $\Sigma$ in one further step
9. (Reductio Ad Absurdum Rule) If $\bot$ has been deduced from $\Sigma \union {\sigma }$ then $\neg \sigma$ may be deduced from $\Sigma$ in one further step

Using these rules, could you possibly suggest how to approach the proof?

Thanks

4. ## Re: Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

What you have listed as disjunction elimination is in fact disjunctive syllogism, or modus tollendo ponens. A more standard disjunction elimination rule has the form

(taken from the book "Proofs and Types" by Girard, Lafont, Taylor, p. 72). This rule can be simulated in your system as follows.

Numbers in parentheses indicate where corresponding assumptions have been closed. Now you can proceed using reasoning by cases.

5. ## Re: Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

Originally Posted by emakarov
What you have listed as disjunction elimination is in fact disjunctive syllogism, or modus tollendo ponens. A more standard disjunction elimination rule has the form

(taken from the book "Proofs and Types" by Girard, Lafont, Taylor, p. 72). This rule can be simulated in your system as follows.

Numbers in parentheses indicate where corresponding assumptions have been closed. Now you can proceed using reasoning by cases.
I'm not too sure I understand what you said, but I think I may have derived a proof as follows:

1. Given $((p \wedge \neg q) \vee ( \neg p \wedge q))$
2. Assume $\neg (p \vee q)$
3. Assume $p$
4. $\vee$-Introduction $(p \vee q)$
5. $\bot$ from lines 2 and 4
6. $\neg p$ by RAA
7. Assume $(p \wedge \neg q)$
8. $p$ by $\wedge$-Elimination
9. $\bot$ from lines 6 and 8
10. $\neg (p \wedge \neg q)$ by RAA
11. $(\neg p \wedge q)$ by $\vee$-Elimination on lines 1 and 10
12. $q$ by $\wedge$-Elimination
13. $(p \vee q)$ by $\vee$-Introduction
14. $\bot$ from lines 2 and 13
15. $(p \vee q)$ by RAA

How does this seem to you?

Thanks

6. ## Re: Logic: Given ((p^¬q)v(¬p^q)) |- (p v q)

Originally Posted by dwally89
How does this seem to you?
Not bad. Strictly speaking, you need to first derive $\neg\neg(p\lor q)$ using RAA in step 15 and then derive $p\lor q$ using $\neg$-Elimination.

Originally Posted by dwally89
I'm not too sure I understand what you said
I think that tree representations of derivations are much simpler to understand than Fitch-style text that you are using. One writes premises above the line and the conclusion below the line. For example, $\wedge$-Introduction looks like

$\frac{\sigma\qquad\tau}{\sigma\land\tau}$

I used vertical dots $\vdots$ to hide some subderivations in post #4.

Your derivation can be simplified a little. In steps 2-9 you derive $\bot$ from $\neg(p\lor q)$ and $p\land\neg q$ (left picture):

You can move the subderivation $\frac{p\land\neg q}{p}$ as the arrow shows to get a shorter derivation on the right. If the result is substituted into your complete derivation, then you get exactly the picture from post #4 where $A = p\land\neg q$, $B = \neg p\land q$ and $C = p\lor q$.