# A formula $\phi$ is logically equivalent to a another formula which contains only propositional variables and the connectives $\wedge$ and $\to$

Let $v_0$ be the valuation that assigns true ($T$) to every propositional variable.

I'm trying to show that any formula $\phi$ is logically equivalent to one with only propositional variables and the binary connectives $\wedge$ and $\to$ if and only if the natural extension of $v_0$, $v$ say, assigns the value $T$ to $\phi$.

If $\phi$ can be expressed in such a way then clearly $v(\phi)=T$ from the truth tables of $\wedge$ and $\to$. Now I have trouble proving the other way around formally. I think I can believe it is true looking at different truth tables but can't put my thoughts in order.

Could you tell me how you would go at it so I can get my head around it? I would be very grateful!

• Can you represent $p\vee q$ using only $\wedge$ and $\to$? – BrianO Nov 11 '15 at 0:14
• From scratch, no... But I can't prove it's impossible... and according to this theorem it should be possible – Kika Nov 11 '15 at 0:58
• Funny, it's always easier to figure out a proof of something when you know it's a theorem :) – BrianO Nov 11 '15 at 11:01

The other direction: Suppose that $v(\phi) = 1$. Write $\phi$ in conjunctive normal form, so it's a conjunction of clauses, each of which is a disjunction of propositional variables or their negations. Let $p_1, \dotsc, p_m$ be all the propositional variables appearing in $\phi$. The resulting formula $\phi_{cnf}$ is $$\phi_{cnf} = \bigwedge_{i=1}^n \bigvee_{j=1}^m a_{ij}$$ where each $a_{ij}$ is either $p_j$ or $\overline{p_j}$ (the negation of $p_j$). If $m = 1$ then each clause is just the single propositional variable or its negation.
Now, $\phi \iff \phi_{cnf}$, so $v(\phi_{cnf}) = 1$. Thus $v$ has to assign $1$ to every disjunction $\bigvee_{j=1}^m a_{ij}$, so in each disjunctive clause, at least one of the $a_{ij}$ must be $p_j$ and not $\overline{p_j}$ (otherwise $v$ would assign $0$ to that clause and hence to the whole formula). Each disjunction is therefore of the form $$\overline{p_{j_1}} \vee \cdots \vee \overline{p_{j_k}} \vee p_{j_{k+1}} \vee \cdots \vee p_{j_m}$$ for some permutation $j_1,\dotsc, j_m$ of $1,\dotsc,m$, and some $k$ with $0\le k < m$, so each can be written equivalently as $$(p_{j_1} \wedge \cdots \wedge p_{j_k}) \to (p_{j_{k+1}} \vee \cdots \vee p_{j_m}).$$ It remains only to show that $\vee$ can be expressed in terms of $\wedge$ and $\to$. Here's how: $$(p\vee q) \iff ((p\to q)\to q).$$