So far I have been using the given set to prove the functional completeness of other sets, but I don't know how to prove this one. That seems to be the case for similar questions too.Do I need to construct the truth table with every connective and build their equivalent with 3 given connectives?
Prove that the set {¬,∧,∨} is functionally complete.
boolean-algebralogic
Related Solutions
There is a result in Robert Reckhow's thesis that characterizes the adequate sets of connectives. The result says that for a set of connectives to be complete one needs the following:
- F and T (or formulas with these values),
- an odd connective (a connective is called odd if some fixing of its input variables with T and F except two input variables has odd number of Ts in its truth table),
- a non-monotone connective (a connective that turning an F to a T will make its value change from T to F).
These are necessary and sufficient conditions for a set of connectives to be adequate. If a set of connectives is not adequate then it lacks one of these. If you have an odd connective, you can fix the inputs with T and F to get either $\vee$ or $\wedge$. If you have a non-monotone connective, you can fix the inputs with T and F to get $\lnot$. Any boolean function can then be constructed from these as a CNF.
Note that even connectives are closed under composition as well as monotone connectives. So to prove that a set of connectives is inadequate, you typically need to show that either
- all of the connectives are monotone, or
- all of the connectives are even.
For your examples, the first one is a set of monotone connectives, the second one is a set of even connective. So they cannot be adequate.
Daniil wrote an excellent post, but just to add to that a little bit:
As Daniil pointed out, you can't capture any truth-functions that non-trivially depend on more than $1$ variable, such as $P \land Q$, with only a $\neg$. So, let's restrict ourselves to functions defined over one variable, $P$, and see if maybe we can capture all those using a $\neg$?
Unfortunately, the answer is still no. Again, as Daniil already pointed out, we can't capture any tautology or contradiction. That is, we can't capture the truth-function that always returns true (i.e. the function $f$ such that $f(T)=f(F)=T$), nor can we capture the truth-function that always returns false (i.e. the function $f'$ such that $f'(T)=f'(F)=F$)
So in this post I just wanted to show you how you can prove that result using induction. In particular, let's prove the following:
Claim
For any expression $\phi$ built up from $P$ and $\neg$ alone, it will be true that if $v$ is the valuation that sets $P$ to true (i.e. $v(P)=T$), and $v'$ is the valuation that sets $P$ to false (i.e. $v'(P)=F$), then either $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$ (in other words, $v(\phi)$ and $v'(\phi)$ will always opposite values, meaning that $\phi$ can not be a tautology or contradiction, for that would require that $\phi$ has the same value for any valuation)
Proof
We'll prove the claim by structural induction on the formation of $\phi$:
*Base: *
$\phi=P$. Then $v(\phi)=v(P)=T$, while $v'(\phi)=v'(P)=F$. Check!
Step:
If $\phi$ is not an atomic proposition, then there is only one possibility: $\phi$ is the negation of some other statement $\psi$, i.e. $\phi = \neg \psi$.
Now, by inductive hypothesis we can assume that $v(\psi)=T$ and $v'(\psi)=F$, or $v'(\psi)=T$ and $v(\psi)=F$
Well, if $v(\psi)=T$ and $v'(\psi)=F$, then $v(\phi)=v(\neg \psi)=F$ and $v'(\phi)=v'(\neg \psi) =T$. On the other hand, if $v(\psi)=F$ and $v'(\psi)=T$, then $v(\phi)=v(\neg \psi)=T$ and $v'(\phi)=v'(\neg \psi) =F$. So, we can conclude that $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$, as desired.
Best Answer
Hint: every Boolean formula can be written in CNF (conjunctive normal form) or DNF (disjunctive normal form), quite constructively.