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!
 A: 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).
$$
