2
$\begingroup$

This question is from Shoenfield's Mathematical Logic, chapter 1:

Show that if $H$ is a binary truth function such that every truth function is definable in terms of $H$, then $H$ is NAND or NOR.

The wording of the question is slightly modified; also, the question on the previous paragraph is slightly different wording from the question of the title but I think the meaning is the same (please correct me if I am wrong, and if this is the case please answer the question on the body rather than the title). Here, I use the definition:

an $n$-nary truth function $H$ is said to be definable in terms of the truth function $H_1,...,H_k$ if $H$ has a definition $H(a_1,...,a_n) = K$ where $K$ is built up from $H_1,...,H_k, a_1,...,a_n$ and commas and parenthesis.

Here is my attempt (following the book's suggestion): I first proved that if $H$ is singulary then every truth function definable in terms of $H$ is singulary. The book says in hint that I should prove that $H(T,T) =F$ and $H(F,F) = T$ and use the fact I first proved. Assuming that $H(T,T) =F$ and $H(F,F) = T$, I could show that $H$ had to be NAND or NOR. However, I am having hard time proving $H(T,T) =F$ and $H(F,F) = T$. If $H_\neg(a) = H(a,a)$ I would be done, but I do not know how. I tried looking at $H_\lor$ and $H_{\iff}$ but with no avail.

I realize that we can use Post's theorem on minimal funtionally complete sets, but as the chapter from which this problem arises does not mention it I wish to prove this following the book's hint.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

Suppose $H(T,T)=T$. Then no function arising from compositions of $H$ can return $F$ if all inputs are $T$, so $H$ is not functionally complete. Similarly, $H(F,F)=F$ implies functional incompleteness, so $H(T,T)=F$ and $H(F,F)=T$.

$\endgroup$
7
  • $\begingroup$ The question asks to show that only two functions are complete. From your answers it seems 2 other functions are also complete. i.e. $H(T,F) = T$ and $H(F, T) = F$ is also complete $\endgroup$
    – dEmigOd
    Feb 24, 2019 at 15:39
  • $\begingroup$ @dEmigOd OP only wanted to show $H(F,F)=T$ and $H(T,T)=F$, and I did that. $\endgroup$ Feb 24, 2019 at 15:40
  • $\begingroup$ @dEmigOd Also, $T$ or $F$ cannot be used as a literal value by themselves; only $H$ is allowed. $\endgroup$ Feb 24, 2019 at 15:42
  • $\begingroup$ the plus should be read as "and" not function calculation $\endgroup$
    – dEmigOd
    Feb 24, 2019 at 15:43
  • $\begingroup$ @dEmigOd You can't use AND! Only $H$ (which may be AND). $\endgroup$ Feb 24, 2019 at 15:44
0
$\begingroup$

Just a clarification. The H on the problem (d) is not the same as the H on the problem(c). It doesn't make sense to say that NAND and NORD are singulary.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .