Let $F$ be a formula and let $\delta$ be the distribution of truth values such that $\delta(P) = 1$ for any propositional variable $P$. Prove the following are equivalent:
- $F$ is equivalent to a formula using only $\land,\lor,\rightarrow$
- $F$ is equivalent to a formula without $¬$
- $F$ is satisifed by $\delta$
I already proved $1\implies 2$ and $2\implies 3$, but I'm stuck at $3\implies 1$. I tried constructing a formula to which $F$ is equivalent using an inductive reasoning, but I got stuck at the case where $F = ¬G$ for some $G$, where I don't have any idea to follow. I also tried contrapositive and tried to find what happens to a subformula of $F$, but I didn't know where to begin using this idea. Any idea?
Assume that $F$ is satisfied by $\delta.$
Considering only the atomic formulas occurring in $F,$ let $\mathcal A$ be the set of all truth-value assignments $\alpha$ such that $\alpha(F)=0.$
Given an assignment $\alpha\in\mathcal A,$ let $P_1,\dots,P_{m_\alpha}$ be the atomic formulas $P$ (occurring in $F$) for which $\alpha(P)=1,$ and let $Q_1,\dots,Q_{n_\alpha}$ be the atomic formulas $Q$ for which $\alpha(Q)=0;$ then $n_\alpha\gt0$ because of our assumption that $\delta(F)=1.$
If $m_\alpha\gt0$ let $$G_\alpha=(P_1\land\dots\land P_{m_\alpha})\to(Q_1\lor\dots\lor Q_{n_\alpha});$$ if $m_\alpha=0$ let $$G_\alpha=Q_1\lor\dots\lor Q_{n_\alpha}.$$ Let $G$ be the conjunction of all the formulas $G_\alpha (\alpha\in\mathcal A).$ You can easily verify that $G$ is equivalent to $F.$
In other words: Rewrite $F$ in conjunctive normal form. Observe that, because of the assumption that $\delta(F)=1,$ each conjunct has at least one positive literal, and that such a conjunct can be expressed using only the connectives $\land,\lor,\to.$