We have $p\lor q\equiv (p\Rightarrow q)\Rightarrow q$. I am trying to show that there is no such formula representing "$\land$". I tried showing that if we could, we would then be able to deduce $\bot$, but without success. I also tried writing: $$f(p\Rightarrow q)=1+f(p)+f(p)f(q)\mod 2$$ where $f$ is a valuation, then given some formula $\varphi$ in terms of $p,q,\Rightarrow$ if I can show we cannot get: $$f(\varphi)=f(p)f(q)\mod 2$$ through a series of iterations, I would be done. Again unsuccessful (unless I go through a painful case bash). This is meant to be an easy question so I am obviously missing something silly - would appreciate a nudge.
Asked
Active
Viewed 45 times
2 Answers
2
Hint: Try proving by induction on length that any expression you can write in terms of $p,q,$ and $\Rightarrow$ is true for at least two different pairs of truth values for $(p,q)$.
(Alternatively, instead of thinking of it in terms of induction, you can think about the very last instance of $p$ or $q$ appearing in the expression. Whenever that last instance is true, the entire expression will be true. Of course, if you want to prove this completely rigorously, you will end up needing to use induction.)
Eric Wofsey
- 330,363
-
Just out of curiosity, do you actually think of it as an induction on length? It certainly can be, of course, but I think of it as a structural induction. – Brian M. Scott Dec 07 '16 at 01:01
-
I think it's better to think of it as a structural induction, but I said induction on length in this case to briefly but clearly indicate how induction can be used in this context (under the assumption that a student of this level might not know what "structural induction" means). – Eric Wofsey Dec 07 '16 at 01:04
-
I suspected as much, having done exactly the same thing a time or three. – Brian M. Scott Dec 07 '16 at 01:05
1
HINT: Show by induction that if $\varphi$ is built using only $\to$, then there are at least two valuations of $p$ and $q$ making $\varphi$ true.
Brian M. Scott
- 616,228