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}$ (and ${\neg, \lor}$ ) are each minimal functionally complete subsets of ${\neg, \land, \lor, \to, \leftrightarrow}$ . Moreover, the binary connectives NOR and NAND are functionally complete on their own, and are called sole sufficient operators.

This mathematical logic-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: Mathematical logic stubs

Functional completeness

From Wikipedia, the free encyclopedia

Views

Navigation

interaction

Search