0
$\begingroup$

For example $\{\land, \lnot\}$ apparently forms a functionally complete set as it can form any logical expression.

But I don't really know what this means or how you show it. Do we just show that some set is complete and then in the future if we have a new set, show that we can replicate the known operations with the new ones?

Do you have to find these strategically or is there a systematic way?

$\endgroup$
1
$\begingroup$

Do we just show that some set is complete and then in the future if we have a new set, show that we can replicate the known operations with the new ones?

Yeah, that's how we typically show that $\{ \land , \neg \}$ is complete: we already know that $\{ \land, \lor, \neg \}$ is functionally complete, and we just point out that $\lor$ can be rewritten in terms of $\land $ and $\neg$:

$$P \lor Q \Leftrightarrow \neg (\neg P \land \neg Q)$$

Also, here is a post explaining why $\{ \land , \lor, \neg \}$ is complete

$\endgroup$
  • $\begingroup$ How do you figure out how to write $\lor$ in terms of $\land$ and $\lnot$? $\endgroup$ – user539262 Mar 15 '18 at 20:50
  • $\begingroup$ @user539262 The DeMorgan's laws are well-known: $$\neg (P \lor Q) \Leftrightarrow \neg P \land \neg Q$$ ... so negating both sides that also means that $$P \lor Q \Leftrightarrow \neg(\neg P \land \neg Q)$$. You can use truth-tables that all of this is indeed the case $\endgroup$ – Bram28 Mar 15 '18 at 20:56
  • $\begingroup$ Is showing a relation from one operator to the next more of an art than a science? $\endgroup$ – user539262 Mar 15 '18 at 21:16
  • $\begingroup$ @user539262 Interesting question ... the binary operators have been studied extensively, so for those it is all pretty well known which can be reduced to which, and which not. And also note that something like DeMorgan's laws is completely intuitive: if it cannot be true that either $P$ or $Q$ are true then obviously both are false, and vice versa. So, grasping the intuitive meaning of the operators certainly helps the search for these kinsd of reductions. But if you gave me a couple of arbitrary ternary operators and asked me if I could make reductions, I would probably have a hard time, yes. $\endgroup$ – Bram28 Mar 15 '18 at 21:39
0
$\begingroup$

Here, once again - as the other page was marked as duplicate - a systematic way of showing completeness without relying on an already given complete set of operators.

I use the follwing notations: $$a \lor b = a + b,\, a \land b = a\cdot b = ab \mbox{ and } \neg a = \bar a, \, T = 1, F = 0$$

It is to be shown that $\forall n \in \mathbb{N}$ any truth function $f:\, \{0,1\}^n \rightarrow \{0,1\}$ can be written using only $\cdot$ and $\bar{}$.

  • $n = 1$: So, $f:\, \{0,1\} \rightarrow \{0,1\}$. $f(a) = a$ or $f(a) = \bar a$ or $f(a) = a\bar a$ or $f(a) = \overline{a \bar a}$ are doing the job.
  • $n \rightarrow n+1$: So, $f:\, \{0,1\}^{n+1} \rightarrow \{0,1\}$. Split $f(a_1,\ldots ,a_n, a_{n+1})$ into $$g_0(a_1,\ldots ,a_n) = f(a_1,\ldots ,a_n, 0) \mbox{ and } g_1(a_1,\ldots ,a_n) = f(a_1,\ldots ,a_n, 1)$$ According to induction hypothesis $g_0$ and $g_1$ can be expressed using only $\cdot$ and $\bar{}$. Now we have $$f(a_1,\ldots ,a_n, a_{n+1}) = \bar a_{n+1}g_0(a_1,\ldots ,a_n) + a_{n+1}g_1(a_1,\ldots ,a_n)= \overline{\overline{ \bar a_{n+1}g_0(a_1,\ldots ,a_n) + a_{n+1}g_1(a_1,\ldots ,a_n)}}= \overline{\overline{\bar a_{n+1}g_0(a_1,\ldots ,a_n)}\cdot \overline{a_{n+1}g_1(a_1,\ldots ,a_n)}}$$ So, we have written $f$ as an expression using only $\cdot$ and $\bar{}$.

Done.

$\endgroup$

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.