1
$\begingroup$

I'm in a Foundations of Computer Science course and it's all about logic and proofs. Some proofs are harder than others, and I'm completely stuck on this proof. It comes out of the textbook Texts and Monographs in Computer Science: A Logical Approach to Discrete Math by David Gries and Fred Schneider.

Apparently, the formatting is different than what you would typically see. I can only use axioms in this book, so that's what makes it quite difficult.

Thus to prove

($p \Rightarrow q) \land (q \equiv r) \Rightarrow (p\Rightarrow r)$

we need to use the following axioms:

Mutual implication: $(p \Rightarrow q) \land (q \Rightarrow p) \equiv (p\equiv q)$

Transitivity (a.): $(p \Rightarrow q)\land (q\Rightarrow r)\Rightarrow(p\Rightarrow r)$

Shunting: $p\land q \Rightarrow r\equiv p \Rightarrow (q \Rightarrow r)$

However, I think some manipulation needs to occur first because nothing matches except for shunting, but when I try that it doesn't seem to lead anywhere. That's all the problem statement says, but I'm sure other axioms are needed. Either way, I'm quite lost.

So far I have: $$\eqalign{ & {\bf{3}}.{\bf{72}}(3.80,3.82a,3.65) \cr & {\rm{Claim:}} \cr & \left( {p \Rightarrow q} \right) \wedge \left( {q \equiv r} \right) \Rightarrow \left( {p \Rightarrow r} \right) \cr & {\rm{Proof:}} \cr & \left( {p \Rightarrow q} \right) \wedge \left( {q \equiv r} \right) \Rightarrow \left( {p \Rightarrow r} \right) \cr & = \left\langle {3.59{\rm{, defn}}{\rm{. of implication, three times}}} \right\rangle \cr & \neg \left( {\left( {\neg p \vee q} \right) \wedge \left( {q \equiv r} \right)} \right) \vee \left( {\neg p \vee r} \right) \cr & = \left\langle {3.47a,{\rm{ De Morgan}}} \right\rangle \cr & \neg \left( {\neg p \vee q} \right) \vee \neg \left( {q \equiv r} \right) \vee \left( {\neg p \vee r} \right) \cr & = \left\langle {{\rm{3}}{\rm{.47b, De Morgan}}} \right\rangle \cr & \left( {\neg \neg p \wedge \neg q} \right) \vee \neg \left( {q \equiv r} \right) \vee \left( {\neg p \vee r} \right) \cr & = \left\langle {3.12,{\rm{ double negation}}} \right\rangle \cr & \left( {p \wedge \neg q} \right) \vee \neg \left( {q \equiv r} \right) \vee \left( {\neg p \vee r} \right) \cr} $$

And I'm lost from here.

$\endgroup$
  • $\begingroup$ Yeah, you'll need something other than those three axioms ... but not knowing what other axioms you have to work with, it's hard to provide some help :(. Do you have something to the effect of $(p \land q) \Rightarrow p$? $\endgroup$ – Bram28 Feb 17 '17 at 2:06
  • $\begingroup$ By prove, are you attempting to prove that the statement is true? If so; you could simply recognized that it is a tautology. $\endgroup$ – user400188 Feb 17 '17 at 2:38
  • $\begingroup$ I need to prove it to be true using previously proven axioms or match it to another previous axiom using textual substitution. To answer Bram, I do indeed have $(p \land q) \Rightarrow p$; it's called Weakening/Strengthening in my book. Would that be useful here? $\endgroup$ – Mark Schauer Feb 17 '17 at 4:06
  • $\begingroup$ But $(p \equiv q)$ is $(p \to q) \land (q \to p)$. $\endgroup$ – Mauro ALLEGRANZA Feb 17 '17 at 8:59
  • $\begingroup$ Thus, if you can unpack it, getting : $[(p \to q) \land (p \to q) \land (q \to p)] \to (p \to r)$. $\endgroup$ – Mauro ALLEGRANZA Feb 17 '17 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.