> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/300-logic/terms/functional-completness.md).

# functionally complete

Propositional logics commonly use a set of logical connectives consisting of 5 elements: negation, conjunction, disjunction, implication and bijection, i.e. $${NOT, AND, OR, IMPLY, IFF}$$.

Predicate logics commonly use the same symbols with addition of two quantifiers, $${NOT, AND, OR, IMPLY, IFF, EXISTS, FORALL}$$

Although $$IFF$$ connective can be constructed from $$IMPLY$$ conectives, it is often included in the basic set of logical connectives because it lowers complexity of compound formulae; basically, it can be regarded as a mere shorthand.

In fact, many connectives can be descibed in term of others. A **functionally complete** set of logical connectives (Boolean operators) is the one which can be used to produce all other logical connectives. Such a set can express all possible truth tables by combining its elements into a Boolean expression.

A well-known functionally complete set is $${AND,NOT}$$, consisting of binary conjunction and negation. Each of the singleton sets { NAND } and { NOR } is functionally complete.

IMPLY and AND connectives can be described in terms of OR connective - the minimum set of syymbols from which all other symbols can be constructed is