I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks you to show that NAND and NOR are the only binary connectives \$ such that {$} is functionally complete.

My proof strategy goes naturally as: 1. Suppose that \$ is functionally complete; 2. Show that either \$=| or \$=$\downarrow$.

By the assumption, since \$ is binary, it's truth function must be any one of 16 different combinations (including the AND-function, OR-function and so on...). But now I am stuck. It seems I have to show that each of the singletons {$} of the 14 left possible connectives defined be their truth functions (except from NAND and NOR) are functionally incomplete. I can see how to prove some set S of connectives is functionally complete, but not that it isn't. What would be the best approach for that? Am I in the right track?


Any functionally complete set of connectives must have at least one connective $\$$ such that $\top\$\top$ is equal to $\bot$ and one connective such that $\bot\$\bot$ is equal to $\top$. That means you only need to check the $4$ connectives that satisfy this condition, depending on what they return for $\top\$\bot$ and $\bot\$\top$.


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.