0
$\begingroup$

With modus ponen as the inference rule, and the following axioms:

  1. $\varphi\rightarrow(\psi\rightarrow\varphi)$
  2. $(\varphi\rightarrow(\psi\rightarrow\chi))\rightarrow((\varphi\rightarrow\psi)\rightarrow(\varphi\rightarrow\chi))$
  3. $((\neg\varphi)\rightarrow(\neg\psi))\rightarrow(\psi\rightarrow\varphi)$

Let $\Gamma=\{p\wedge q,(\neg p)\vee q,p\vee r\}$. Is it true that $\Gamma\vdash r$?

Since the axioms are given purely in terms of $\neg$ and $\rightarrow$, I used basic logic equivalences to convert $\Gamma$ into $\Gamma=\{\neg(p\rightarrow\neg q),p\rightarrow q,\neg p\rightarrow r\}$. From this, I know I need a sequence of formulas derived from $\Gamma$ and the axioms to eventually arrive at $r$ (if $\Gamma\vdash r$ is true, I have not even entirely convinced myself that it is), but I don't really know where to start.

$\endgroup$
  • $\begingroup$ Suppose I asked you if $\{A \land B, A\} \vdash C$. Since $\{A \land B\} \vdash A$, this can be simplified to determining whether $\{A \land B \}\vdash C$. Use this principle to simplify your problem. $\endgroup$ – DanielV Nov 8 '16 at 1:17
  • 2
    $\begingroup$ You cannot : With $v(r)=$ f and $v(p)=v(q)=$ t the premises are satisfied and the conclusion is not. Thus $\Gamma \nvDash r$. $\endgroup$ – Mauro ALLEGRANZA Nov 8 '16 at 6:59
1
$\begingroup$

You cannot prove it.

A valuation $v$ such that :

$v(r)=$ f and $v(p)=v(q)=$ t

the premises are satisfied and the conclusion is not.

Thus

$\Gamma \nvDash r$.

$\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.