Logical proof without truth table

Question

Problem

Proof following as tautology without using truth table.

$$ P(w,s,b) = ((w \wedge s \rightarrow b)\wedge (\neg w \rightarrow \neg s)\wedge (s) \rightarrow b $$

Attempt to proof

$$ (w \wedge s \rightarrow b) \iff \neg(w \wedge s) \vee b \iff (\neg w \vee \neg s) \vee b $$

$$ (\neg w \rightarrow \neg s) \iff (w \vee \neg s) $$

Now combining these we have

$$ (\neg w \vee \neg s \vee b)\wedge (s \wedge w) \to b $$ $$ \iff \neg ((\neg w \vee \neg s \vee b) \wedge (s \wedge w))\vee b $$ $$ \iff (w \wedge s \wedge \neg b) \vee (\neg s \vee \neg w \vee b) $$

Now not quite sure how should i proceed from here but if

let $$ A = (w \wedge s \wedge \neg b) $$ then we have $$ \neg A = \neg(w \wedge s \wedge \neg b) \iff \neg A = (\neg w \vee \neg s \vee b) $$

Meaning $$ (w \wedge s \wedge \neg b) \vee (\neg s \vee \neg w \vee b) \iff A \vee \neg A $$

and $A \vee \neg A$ is clearly tautology.

Is my proof correct?

Answer 1

It's correct but it could be made more elegant and easier to follow by trying to use the meanings of the logical operators, rather than treating it as a purely symbolic exercise in algebra.

Here's what I mean. In order to prove $P \Rightarrow Q$, you need to assume $P$, and derive $Q$.

So assume $((w \wedge s) \to b) \wedge (\neg w \to \neg s) \wedge s$. We need to derive $b$. Well:

• $s$ is true by assumption
• $\neg w \to \neg s$ is true by assumption, so $s \to w$ is true by contraposition.
• Hence $w$ is true, since $s$ and $s \to w$ are true.
• Hence $w \wedge s$ is true, since $w$ and $s$ are both true.
• Hence $b$ is true, since $(w \wedge s) \to b$ and $w \wedge s$ are true.

So we've derived $b$ from the assumption $((w \wedge s) \to b) \wedge (\neg w \to \neg s) \wedge s$.

Therefore $[((w \wedge s) \to b) \wedge (\neg w \to \neg s) \wedge s] \to b$ is true.

Answer 2

Your proof by logical algebra is correct.

Another method is that to show $\phi\land\psi\to\rho$ is a tautology it suffices to show that $\phi\land\psi\land\lnot\rho$ is a contradiction. This is called resolution.

$$\begin{align}P(w,s,b) &= ((w \wedge s \rightarrow b)\wedge (\neg w \rightarrow \neg s)\wedge s) \rightarrow b\\&=((\lnot w\lor\lnot s\lor b)\land(w\lor\lnot s)\land s)\to b \\\lnot P(w,s,b)&= (\lnot w\lor b\lor\lnot s)\land(w\lor\lnot s)\land s\land\lnot b\\&=(\lnot w\lor b)\land w\land s\land\lnot b\\&=\lnot w\land w\land s\land\lnot b\\&=\bot\\P(w,s,b)&=\top \end{align}$$