Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I’m currently trying to learn more about Mathematical Logic and have reached a sticking point. I also have the solutions to the problems I’m working through and I usually don’t need to ask for help to understand a concept, but this problem is still giving me trouble. I’ll list the problem and solution and hopefully someone can just clarify a few things

Prove that $\{ \top, \bot, ¬, \leftrightarrow, + \}$ is not complete.

For anyone who doesn't know what the $+$ symbol means, I've listed it below. Let me know in the comments if any other symbol needs clarification.

( {$+$} symbol $\Rightarrow$ $(A \vee B) \wedge ¬(A \wedge B)$ )

As a hint, the book suggested to first recognized that all wff’s using these connectives and two sentence symbols A, B; has an even number of T’s among the four possibilities. (not sure what they mean here)

So the solution uses mathematical induction as a method of proof, but I'm just confused as to the meaning of the hint and how that will show that the set listed is not complete. Any help would be appreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

For completeness, it should be possible to construct arbitrary truth tables, esp. the truth tables for $\land$, which has one $\top$ and three $\bot$ in it. If the hint is right, this is not possible with the given connectives.

To show that any wff involving only $A$ and $B$ and these connectives evalutes to $\top$ in an even number of the four possible truth value combinations of $A,B$, we can use induction:

  • $\top$ is always true, i.e. in all $4$ cases.
  • $\bot$ is never true, i.e. in $0$ cases.
  • $\neg\phi$ is true in $4-2k=2(2-k)$ cases, if $\phi$ is true in $2k$ cases
  • $\phi\leftrightarrow\psi$, where $\phi$ is true in $2k$ cases and $\psi$ in $2m$ cases. If $\phi\land\psi$ is true in $r$ cases, then $\neg\phi\land\neg\psi$ is true in $4-2k-2m+r$ cases, hence $\phi\leftrightarrow\psi$ is true in $4-2k-2m+2r=2(2-k-m+r)$ cases.
  • $\phi+\psi\iff\neg(\phi\leftrightarrow\psi)$
share|improve this answer
    
This makes a lot of sense now, thanks! –  Amateur Math Guy Feb 10 '13 at 22:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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