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!

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.