# Show provability under a premise

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.

• 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. – DanielV Nov 8 '16 at 1:17
• 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$. – Mauro ALLEGRANZA Nov 8 '16 at 6:59

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