From WikiChip
Difference between revisions of "boolean algebra/functional completeness"
< boolean algebra

m
m
Line 1: Line 1:
 +
{| class="wikitable" style="float: right;"
 +
! colspan="6" | Logic function classification
 +
|-
 +
! Func    !! Monotone Inc !! Self-dual !! Linear  !! 0-preserving !! 1-preserving
 +
|-
 +
| [[LOW]]  || '''✔'''      || '''✘'''  || '''✔''' || '''✔'''      || '''✘'''
 +
|-
 +
| [[HIGH]] || '''✔'''      || '''✘'''  || '''✔''' || '''✘'''      || '''✔'''
 +
|-
 +
| [[NOT]]  || '''✘'''      || '''✔'''  || '''✔''' || '''✘'''      || '''✘'''
 +
|-
 +
| [[AND]]  || '''✔'''      || '''✘'''  || '''✘''' || '''✔'''      || '''✔'''
 +
|-
 +
| [[OR]]  || '''✔'''      || '''✘'''  ||'''✘'''  || '''✔'''      || '''✔'''
 +
|-
 +
| [[XOR]]  || '''✘'''      || '''✘'''  ||'''✔'''  || '''✔'''      || '''✘'''
 +
|}
 
A set of logic operations is '''functionally complete''' in [[Boolean algebra]] provided every [[propositional function]] can be expressed entirely in terms of operations in the set - i.e. by combining the various logic operations in a set one could create every truth table. Two notable sets are [[NAND logic|'''{''' NAND '''}''']] and [[NOR logic|'''{''' NOR '''}''']]. Such sets are also called '''universal''' or '''complete''' sets.
 
A set of logic operations is '''functionally complete''' in [[Boolean algebra]] provided every [[propositional function]] can be expressed entirely in terms of operations in the set - i.e. by combining the various logic operations in a set one could create every truth table. Two notable sets are [[NAND logic|'''{''' NAND '''}''']] and [[NOR logic|'''{''' NOR '''}''']]. Such sets are also called '''universal''' or '''complete''' sets.
  
Line 8: Line 25:
  
 
== Determining Completeness ==
 
== Determining Completeness ==
{| class="wikitable" style="float: right;"
 
! Func    !! Monotone !! Self-dual !! Linear  !! 0-preserving !! 1-preserving
 
|-
 
| [[NOT]]  || '''✘'''  || '''✔'''  || '''✔''' || '''✘'''      || '''✘'''
 
|-
 
| [[AND]]  || '''✔'''  || '''✘'''  || '''✘''' || '''✔'''      || '''✔'''
 
|-
 
| [[OR]]  || '''✔'''  || '''✘'''  ||'''✘'''  || '''✔'''      || '''✔'''
 
|}
 
 
* Given a set of Boolean functions
 
* Given a set of Boolean functions
 
* Find at least one of each:
 
* Find at least one of each:

Revision as of 02:45, 24 November 2015

Logic function classification
Func Monotone Inc Self-dual Linear 0-preserving 1-preserving
LOW
HIGH
NOT
AND
OR
XOR

A set of logic operations is functionally complete in Boolean algebra provided every propositional function can be expressed entirely in terms of operations in the set - i.e. by combining the various logic operations in a set one could create every truth table. Two notable sets are { NAND } and { NOR }. Such sets are also called universal or complete sets.

Examples

The following are some examples of functionally complete sets:

Determining Completeness

From the table it can be seen that the following sets are functionally complete: { AND, NOT }, { OR, NOT }, { AND, OR, NOT }.

See also