Functional completeness

From Wikipedia, the free encyclopedia

In logic, a set of logical connectives is functionally complete if all other possible connectives can be defined in terms of it.

Usually, in an exposition of classical logic, the following connectives are defined: conjunction ( $\land$ ), disjunction ( $\lor$ ), negation ( $\neg$ ), implication ( $\to$ ) and possibly bi-implication ( $\leftrightarrow$ ). This constitutes a functionally complete set. However, it is not a minimal functionally complete set, as implication and bi-implication may be defined as:

$A \to B := \neg A \lor B$

$A \leftrightarrow B := (A \to B) \land (B \to A)$

So ${\neg, \land, \lor}$ is also functionally complete. But then, $\lor$ can be defined as:

$A \lor B := \neg(\neg A \land \neg B)$

( $\land$ can also be defined in terms of $\lor$ in a similar manner.)

This cannot be further simplified, so ${\neg, \land}$ is a minimal functionally complete subset of ${\neg, \land, \lor, \to, \leftrightarrow}$ . However, the binary connectives NOR, NAND, and the ternary conditioned disjunction are functionally complete on their own, and are called sole sufficient operators.

This mathematics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "http://en.wikipedia.org../../../f/u/n/Functional_completeness.html"

Category: Mathematics stubs

Functional completeness

From Wikipedia, the free encyclopedia

Views

Navigation

Search