Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But I'm confused on where to even start.

  1. Prove that ((p → q) ∧ ¬q) → ¬p is a tautology without using truth tables. Show intermediate steps and mention what law you are using.

  2. Prove that (p → r) ∧ (q → r) is logically equivalent to (p ∨ q) → r using only the logical equivalences. Show intermediate steps and mention what law you are using.

Thanks for any help!! These two links along with the one in my comment, denotes the laws for proving. All of these

First two rows from this one

  • $\begingroup$ It's just like (numerical) algebra, but with largely different rules. The solution will depend on what rules you are allowed to use, so perhaps if you post the complete list someone will be able to help. $\endgroup$ – David Feb 8 '16 at 23:38
  • $\begingroup$ i.stack.imgur.com/dEpCS.jpg The first row from this one $\endgroup$ – N. Spencer Feb 8 '16 at 23:48
  • $\begingroup$ For 1., it would help to have $(A\land B)\to C \equiv A\to (B\to C)$, which isn't hard to show (replace $\to$ with $\lor, \neg$, then use De Morgan, associativity). $\endgroup$ – BrianO Feb 9 '16 at 0:26

Well, the first step would be to express only with connectives $\{\wedge,\vee,\neg\}$.

To do this apply the equivalence $\;(x\to y) \;\equiv\; (\neg x \vee y)\;$ as often as required.

$$\begin{align}((p\to q)\wedge\neg q)\to\neg p \;& \equiv\; ((\neg p\vee q)\wedge \neg q)\to \neg p & \textsf{Implication Equivalence} \\ & \equiv\; \neg((\neg p\vee q)\wedge \neg q)\vee \neg p & \textsf{Implication Equivalence}\end{align}$$

When you do that, keep applying the Boolean rules until you reduce to $\top$ . I suggest starting with distribution.

$$\begin{align}\neg ((\neg p\vee q)\wedge \neg q)\vee \neg p & \equiv\; \neg((\neg p\wedge\neg q)\vee (q\wedge \neg q))\vee \neg p & \textsf{Distribution} \\ & \ddots \end{align}$$


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.