1

I am trying to prove that the set of five connectives:

$$\{ ¬, ∧, ∨, →, ↔\}$$

Is adequate (functionally complete) for all possible Boolean functions in propositional logic (only). I.e. EVERY Boolean function can be generated from these 5 operators.

This includes propositions with any number of atomic terms, i.e. the range from nullary operator on zero terms and 2 truth expressions $\{T,F\},$ through unary operator on one term and 4 truth functions, through binary+unary operators on two terms and 16 truth functions, all the way to <=n’ary operators on n terms generating 2^(2^n) functions, and presumably on to to infinite terms.

It is trivial to show that more minimal sets are producible. E.g. a set of ¬ and one of $\{ ∧, ∨, →\}$ is complete. As is the binary NAND or the binary NOR as singleton sets. These have all been shown to derive from the 5 operator set originally, then applying some law of logic to minimise that set one operator at a time.

However, I have been unable to prove the functional completeness of the (seemingly untrivial) 5 operator case for ANY Boolean Function with any number of terms.

Your help would be kindly appreciated.

Michael Hardy
  • 1
Drex
  • 69
  • If you have not problems with showing that, say, ${\lnot, \land}$ is functionally complete, then it is certainly much easier to show that the set ${\lnot, \land, \lor, \to, \leftrightarrow}$ is a cinch. – amWhy Jan 21 '18 at 23:05
  • You won't get the two nullary operators as compositions of unary and binary operators like the five in your question. The closest you'll get to the nullary operators would be the unary simulations $p\lor\neg p$ and $p\land\neg p$. – Andreas Blass Jan 21 '18 at 23:05
  • @amWhy If I understand the question correctly, the OP is able to prove completeness of ${\neg,\land}$ using the completeness of the $5$-element set of connectives. So I think what is needed is a pointer to the proof of completeness of ${\neg\land\lor}$ via disjunctive (or conjunctive) normal forms. – Andreas Blass Jan 21 '18 at 23:09
  • @AndreasBlass "I am trying to prove that the set of five connectives: ${¬,∧,∨,→,↔}$ is adequate for all possible Boolean functions in propositional logic (only). I.e. EVERY Boolean function can be generated from these 5 operators." ...."... I have been unable to prove the functional completeness of the (seemingly untrivial) 5 operator case for ANY Boolean Function with any number of terms." – amWhy Jan 21 '18 at 23:13
  • Yes, I was able to exhaustively manually show that for 2 Boolean variables, each of the 16 functions can be reduced to functions comprising of some/all of the 5-operators of the adequate set (or a more minimal set). This is also obvious for 1 or 0 variables, however moving upwards to 3 variables and potentially 256 different functions including many ternary ones, such an exhaustive proof is not possible. How should I proceed? – Drex Jan 21 '18 at 23:14
  • @amWhy "These [the 1- or 2-element complete sets] have all been shown to derive from the 5-operator set initially, then applying some law of logic to minimise that set one operator at a time." – Andreas Blass Jan 21 '18 at 23:52

1 Answers1

1

Let $f$ be an $n$ary boolean function, $n\ge1$. Among all boolean $n$ary functions expressible with the five operators, let $g$ be one that agrees with $f$ for the maximal number of possible inputs. (Such $g$ exists because there are only finitely many inputs). Then $g$ agrees with $f$ on all inputs. For if we assume otherwise, there exists an assignment of $n$ values $a_1,\ldots, a_n\in\{T,F\}$ to the input parameters such that $f(a_1,\ldots,a_n)\ne g(a_1,\ldots, a_n)$. For each $i$, $1\le i\le n$, define $\phi_i:=\neg X_i$ if $a_i=T$ and define $\phi_i:=X_i$ if $a_i=F$. Then $$\hat g(X_1,\ldots, X_n):= g(X_1,\ldots,X_n)\leftrightarrow(\phi_1\lor\ldots\lor \phi_n)$$ is built from the 5 operators and agrees with $f$ on more inputs than $g$ does, contradiction

Hagen von Eitzen
  • 374,180
  • I am slowly re-reading your proof , interpreting it line by line, in order that I can fully understand it, and why it implies that these 5 operators are functionally complete. I understand it until the mention of the ϕ's, then after that I can go no further. Why did defining these ϕ's to be X's (under certain logical conditions on the a's) imply the longer statement below it? I.e. How did the a's in the functions f and g become X's? And how did the biconditional association to the disjunction of ϕ's come about? I see the basic structure of the proof by contradiction. – Drex Jan 23 '18 at 20:57