[Exercise 12.2] Prove that is is not possible to define the connective $\land$ in terms of $\lnot$ and ↔.
Suggestion: By induction on the complexity of formulae constructed by these connectives, prove that every truth table has an even number of rows that assign the respective formula as true.
I think i have already solved this exercise, so i would like to know if my solution is correct:
All the possible WFFs (Well Formed Formulae) constructed using $\lnot$ and ↔ are: $\lnot\ (a↔ b)$, $\lnot\ (\lnot a↔ b)$, $\lnot\ ( a↔ \lnot b)$, $\lnot\ (\lnot a $↔$ \lnot b)$, $\ (\lnot a↔ b)$, $\ ( a↔ \lnot b)$ and $\ ( \lnot a↔ \lnot b)$. Once all the truth-tables of the previous formulae have been verified, it is possible to determine that none of them match with the $a \land b$ operator truth-table , thus proving that the operator is not definable in terms of $\lnot$ and ↔.
In spite of the validity of my solution, i also would like to know how to actually solve this exercise using the concept of induction on the complexity of formulae, given the following definition:
Def. 2.4 (Complexity Degree of a WFF). For each formula on propositional logic we determine a natural number such that the following conditions hold:
1). Every atomic formula has complexity degree $0$.
2). If $A$ has a degree of complexity $n$, then$\ ( \lnot A )\ $ has a degree of complexity of $n+1$
3). If $A$ and $B$ have degrees of complexity $m$ and $n$, respectively, then$\ (A \land B )\ $, $\ (A \lor B )\ $, $\ (A \to B )\ $ and $\ (A ↔ B )\ $ have degrees of complexity $max$$\{m, n\}$$+1$, where $max$$\{m, n\}$ is the greatest value between $m$ and $n$.
Best Answer
First thing you should notice is that you also get $\top$ and $\bot$ since $a\leftrightarrow a =\top$. Also notice that $(\neg a\leftrightarrow b)\equiv \neg(a\leftrightarrow b)$. We also can restrict ourselves to having only two atomic propositions $a$ and $b$. Consider the levels of complexity up to $2$. At complexity $0$ we have $a$ and $b$, for complexity $1$ $\top$ $\bot$ $\neg a$ $\neg b$ and $a\leftrightarrow b$ at $2$ we get $\neg a \leftrightarrow b$ which are all the sentences you can get up to logical equivalence by using $\leftrightarrow$ and $\neg$. If we prove that we are done since none of them are equivalent to $a \wedge b$. we show that applying $\leftrightarrow$ and $\neg$ to any sentence or sentences equivalent to the ones listed above we get another sentence equivalent to the one listed above. Then by induction on the complexity of the formula we are done.
We see that the sentences are closed under $\neg$ meaning if I apply $\neg$ to any sentence I get one that is logically equivalent to one of the ones listed above. \begin{equation} \begin{matrix} \top && a&& b && (a\leftrightarrow b)\\ \bot && \neg a && \neg b && \neg(a \leftrightarrow b) \end{matrix} \end{equation} We also need to show they are closed under $\leftrightarrow$. This is a proof by case and there are $64$ pairs of sentences which would be silly to check all of them. The first trick is that $(\neg p\leftrightarrow q)\equiv \neg(p \leftrightarrow q)$ where $p$ and $q$ are not necessarily atomic formulas. So we just need to check that it's true for pairs in $\{\top,a,b,a\leftrightarrow b\}$ since we already establised the set is closed under negation. We are now left with $16$ pairs. Since $\leftrightarrow$ is symmetric and for each $p$ we have $p\leftrightarrow p\equiv \top$ this leaves us with $6$ cases. For any sentence $p$ one has $\top \leftrightarrow p \equiv p $ which covers all cases that have $\top$. For $a$ and $b$ it's immediate and finaly for $(a\leftrightarrow(a \leftrightarrow b))$ using truth tables you cans show that it's equivalent to $a\leftrightarrow b$. The same goes for $(b\leftrightarrow(b\leftrightarrow a))$