2

This is the definition of $ \bf PL $

Let $ S = S _ { \bf PL } $, the set of logical symbols for $ \bf PL $, be the union of the following three sets:

$ Con = \{ \neg , \lor , \land , \rightarrow , \leftrightarrow \} $ is the set of connectives;

$ Props = \{ P _ 1 , P _ 2 , P _ 3 , \dots \} $ is the (countably infinite) set of propositional variables; and

$ \{ ( , ) \} $, the left and right parentheses.

And here are the deduction rules.

enter image description here

I tried to start by assuming $ Q $.

Deduction verifying $ \neg ( Q \rightarrow ( P \lor Q ) ) $

  1. $ Q ^ * \qquad \qquad \qquad $ Hypothetical
  2. $ ( P \lor Q ) ^ * \qquad \qquad (VI) $ on $ ( 1 ) $
  3. $ Q \rightarrow ( P \lor Q ) \qquad ( \rightarrow I ) $ on $ ( 1 , 2 ) $

But I can't find a falsehood. How can I continue?

I doubt I am already doing wrong in step 3. $ Q ^ * $ is already used for constructing $ ( P \lor Q ) ^ * $. If I want to construct $ Q \rightarrow ( P \lor Q ) $, I have to assume $ Q ^ { ** } $ before, isn't it?

Community
  • 1
yashirq
  • 505
  • I cannot understand what you meant after "I tried to start by assuming Q" – Astyx Oct 18 '16 at 18:00
  • 2
    It seems to me that your deduction rules lack some weakening rules before all the axioms will be useful. And a cut rule or something similar that will allow a proof tree to branch and contain more than one axiom. – hmakholm left over Monica Oct 18 '16 at 18:01
  • @Astyx Actually ¬(Q →(P ∨ Q)) is a conclusion. We are not given anything. So have to start by assuming something is true, like ((Q →(P ∨ Q)), or (P ∨ Q) or even ¬P. Here I assume Q to get start. I know it looks weird, but that's how the way it looks like that I learn from my class. – yashirq Oct 18 '16 at 18:05
  • 1
    Do you know any equivalent of $Q \implies P$ ? – Astyx Oct 18 '16 at 18:08
  • @Henning That's what all the rules I have so far :( – yashirq Oct 18 '16 at 18:08
  • @Astyx No. Verify ¬(Q →(P ∨ Q)) is a falsehood. That's all the information I have. – yashirq Oct 18 '16 at 18:10
  • yashirq Just curious: have you learned that from $A$ and $\lnot A$ you can derive $\bot$? Are you familiar with the symbol $\bot$: contradiction (by definition, always false)? – amWhy Oct 18 '16 at 19:14
  • @amWhy: That seems to be the $\neg E$ rule (except it has a subsequent explosion step built in, becasue the logical vocabulary here doesn't include $\bot$). – hmakholm left over Monica Oct 19 '16 at 13:00

1 Answers1

2

Your step $(3)$ is fine. Having assumed $Q$, you derive $Q\lor P$ correctly in step (2). Then, you are justified by concluding (deriving) that $Q\rightarrow (P \lor Q)$ through $\to$ Introduction.

From $(3)\quad Q\to(P \lor Q))$ $\quad (\to I)\quad$ on $(1,2)\;\;$ [at which you've discharged the assumption Q]

you can use $\lnot\lnot\,$I to conclude $$(4)\quad\lnot\lnot (Q\to (P\lor Q))\equiv \lnot (\lnot( Q\to (P\lor Q)))\qquad (\lnot\lnot I)\quad \text{ on } (3)$$

In other words, given your final comment about what you are seeking to do ("Verify ¬(Q →(P ∨ Q)) is a falsehood."),

you will have proven that it is NOT the case that $\lnot(Q\to(P\lor Q))$ is true. In other words, you will have proven that $\lnot(Q\to (P\lor Q))$ is indeed, false.

amWhy
  • 209,954
  • I thought ¬(Q→(P∨Q)) is a conclusion so we can't use it to compare with ¬¬(Q→(P∨Q)). But if we can use ¬(Q→(P∨Q)), why do we still have to do step 4? I think step 3 is enough. Q→(P∨Q) is already contradict with ¬(Q→(P∨Q)) – yashirq Oct 19 '16 at 00:13
  • Is it because of the parentheses? – yashirq Oct 19 '16 at 00:14
  • One of the reasons I asked you in the comments below your question about deriving a contradiction ($\bot$), was whether, if you assumed (assumption) that $\lnot(Q \rightarrow (P\lor Q))\quad(4)$, after which you can use $\land$Introduction to write (in the subproof following the assumption, to write (5) $;\big(Q\rightarrow(P \lor Q)\big) \land \lnot\big(Q\rightarrow (P\lor Q)\big)$. The subsequent line in the subproof (step 6) would be $\bot$, after which you would need to conclude $\lnot\Big(\lnot(Q\rightarrow (P\lor Q))\Big)$ – amWhy Oct 19 '16 at 15:41
  • But the deduction rules you list do not seem to recognize $\bot$, $\lnot I$, nor $\lnot$E. In any case, the four step proof I give you above is shorter, and follows only the deduction rules you listed in your question. – amWhy Oct 19 '16 at 15:44
  • The solution is posted today. Basically, step 1,2,3 are fine. We can regard $¬(Q→(P∨Q))$ as a premise. So what we need to do is to add $¬(Q→(P∨Q))$ as step 1. Then we do step 5, (Q→(P∨Q))∧¬(Q→(P∨Q)). Done. – yashirq Oct 20 '16 at 01:49