Assignment for discrete mathematics

Question

How can I prove that not every boolean function is equal to a boolean function constructed by only using ∧ and ∨?.Need help in proving it.

Answer 1

To see that $\{\land,\lor\}$ is not a functionally complete set, construct any boolean function using only these two connectives. Then no matter how you define this function in terms of $\land$ and $\lor$, this function must output true if all of its inputs are true. Hence, since there exists at least one boolean function that must output false if all of its inputs are true [Can you come up with a specific example?], it follows that $\{\land,\lor\}$ is not a functionally complete set, as desired. $~\blacksquare$

Answer 2

Here is a formal proof:

Choose $n$ and define the following subsets of functions from $\mathbb{B}^n$ to $\mathbb{B}$ (the set is finite, of course).

Let $\Phi_0 = \{ x \mapsto 1, x \mapsto 0 \} \cup \{ x \mapsto x_k \}_{k=1}^n$.

For $m >0$, let $\Phi_m = \{ f_1 \land\cdots \land f_k | f_i \in \Phi_j, j=0,...,m-1\} \cup \{ f_1 \lor\cdots \lor f_k | f_i \in \Phi_j, j=0,...,m-1\}$, where $f_1 \land\cdots \land f_k$ is defined by $(f_1 \land\cdots \land f_k)(x) = f_1(x) \land\cdots \land f_k(x)$, and similarly for $\lor$.

Let $\Phi = \cup_m \Phi_m$, this consists of all functions from $\mathbb{B}^n$ to $\mathbb{B}$ constructed using $\land, \lor$.

Define a partial order on $\mathbb{B}^n$ by $x \le y$ iff $x_i \le y_i$ for all $i$. We call a function $f:\mathbb{B}^n \to \mathbb{B}$ non-decreasing if $x \le y$ implies $f(x) \le f(y)$.

It is straightforward to see that the functions in $\Phi_0$ are non-decreasing, and by induction that the sets $\Phi_n$ are non-decreasing, and so all functions in $\Phi$ are non-decreasing.

It is clear that this holds for all $n$.

Now consider the function $i:\mathbb{B} \to \mathbb{B}$ defined by $i(x) = \lnot x$. We see that $i$ is not non-decreasing since $i(0)>i(1)$, hence cannot be constructed using $\land,\lor$.