# 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?

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.

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}