0
$\begingroup$

I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique".

I thought about writing down the truth table for a NOT, since it has just one input.

$\endgroup$
  • $\begingroup$ Yes, NOT is an example of a Boolean function with one input. There are three others. It sounds like you're confused by the wording of the question. Just delete the word "unique": it's a badly worded way of saying "And don't write down the same answer twice!", which you weren't going to do anyway. $\endgroup$ – David Richerby Oct 20 '14 at 16:15
  • $\begingroup$ @DavidRicherby Which would be the 3 others functions with one input? $\endgroup$ – nbro Oct 20 '14 at 16:23
  • $\begingroup$ @DavidRicherby Are they perchance True, False and A? $\endgroup$ – nbro Oct 20 '14 at 16:34
  • $\begingroup$ True and False, yes. I don't know what you mean by A but, if it's a Boolean function with one argument and it's different from True, False and NOT then it's the right answer. $\endgroup$ – David Richerby Oct 20 '14 at 16:44
1
$\begingroup$

This task is simple enough if you already know exactly what a function is and how to construct a truth table; you just have to write down every possible combination of assignments to all variables and functions, e.g., $x = 0$, $f(0) = 0$, and so on. If it isn't obvious, it might be beneficial to walk through a more drawn-out reasoning, which might also be more useful whenever you want to count and/or enumerate all possible functions where the number of functions is bigger, and the functions might not be that relatable (like for example how the negation function is relatable).

First of all we can count how many functions there are.

Given sets $A$ and $B$, there are $|B|^{|A|}$ functions $f : A \rightarrow B$.

So since we have $\mathbb B = \{0, 1\}$, $^*$ and we are concerned with functions $f : \mathbb B \rightarrow \mathbb B$, we have $2^2 = 4$ functions.

The next step is to make a truth table. But first, let's look at what a function is:

A function $f : X \rightarrow Y$ is a subset of the Cartesian product $X × Y$ subject to the following condition: every element of $X$ is the first component of one and only one ordered pair in the subset.

So we must find all sets that are subject to these constraints. An example of a set that is not a function is:

$S = \{(1,0), (1,1)\} \subset \mathbb B × \mathbb B$

since $1$ is the first component of two ordered pairs, ie. the value $1$ maps to two different values. Moreover, we don't have a mapping for the value $0$, ie. $f(0)$ is undefined.

Since we are dealing with a domain of size two, and since we have one and only one ordered pair for each member of the domain, all sets (functions) that we are considering are on the form:

$f = \{(0,\_),(1,\_)\}$

where $\_$ is either $0$ or $1$.

So then we list all possible enumerations of two ordered boolean values, and put them in the pair as the second component with the $0$ as the first component and the $1$ as the first component, respectively:

$0,0$

$1,1$

$1,0$

$0,1$

Plugging these in, we get:

$f_1 = \{(0,0),(1,0)\}$ ($f(x) = 0$)

$f_2 = \{(0,1),(1,1)\}$ ($f(x) = 1$)

$f_3 = \{(0,1),(1,0)\}$ ($f(x) = \neg x$)

$f_4 = \{(0,0),(1,1)\}$ ($f(x) = x$)

(As a sanity check, we confirm that we ended up with 4 functions, as expected.)

As a truth table:

$$\begin{array} {|c|c|c|c||c|} \hline x & f_1(x) & f_2(x) & f_3(x) & f_4(x)\\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ \hline \end{array} $$


* Or $\mathbb B = \{F,T\}$, if you prefer.

| cite | improve this answer | |
$\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.