0
$\begingroup$

I'm working through Smullyan's "First-Order Logic." One exercise is to prove that $$\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}\supset r$$ I'm not sure how to make a nice-looking tableau with LaTeX but here goes: $$\sim(\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}\supset r)$$ $$\sim\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}$$ $$r$$ $$\sim[(p\supset r)\wedge (q\supset r)] \;\;|\;\; \sim(p\vee q)$$ Where I'm using | to represent a branching. The first branch will lead to the negation of both of the conditionals, which implies $\sim r$, which contradicts the 3rd line. The second branch, on the other hand, has the direct consequences $\sim p$ and $\sim q$. This doesn't contradict anything and I can't see anything else to which I could apply the inference rules. How do I complete the proof?

I feel like I'm making an obvious mistake so hints would be appreciated. Also anyone is certainly welcome to edit the question if they know how to make a nicer-looking tableau.

$\endgroup$
2
$\begingroup$

I think there is a problem with your tree: $$\sim(\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}\supset r)$$ $$\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}$$ $$\sim r$$

Isn't it this the correct step? If you continue with the tree you will find it closed.

$\endgroup$
0
$\begingroup$

So you wish to prove $\{[(p\supset r)\wedge (q\supset r)]\wedge(p\vee q)\}\supset r$ by showing that its negation is a contradiction.

Firstly, recall that the Tableau tree works by chaining conjunctions, branching disjuntions, and closing off contradictions (of statements earlier in the chain) .   The root statement is proven to be contradictory when all possible branches are closed.   Conditionals (Implications) are handled through equivalences.   $\def\to{\supset} A\to B\equiv \neg A\vee B$ and $\neg(A\to B)\equiv A\wedge\neg B$.   If needed, deMorgan's laws likewise handle negations of connections.   So do the thing. $$\begin{array}{c} \neg\Big(\big((p\to r)\wedge(q\to r)\wedge(p\vee q)\big)\to r\Big)\\ (p\to r)\wedge(q\to r)\wedge(p\vee q)\wedge\neg r\\ (\neg p\vee r)\wedge(\neg q\vee r)\wedge(p\vee q)\wedge\neg r\\\hline \begin{array}{ccccccc}&&&&&\neg r\\ &&&&&p\vee q\\ &&&&&\neg q\vee r\\ &&&&&\neg p\vee r\\\hline &&& \Box &&\vert & \require{cancel}\cancel \Box\\ & \Box &&\vert&\cancel \Box&\\ \cancel \Box &\vert & \cancel \Box \end{array}\end{array}$$ Replace the $\Box$ with the appropriate statements.

$\endgroup$

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.