Semiconductor & Computer Engineering
From WikiChip
Difference between revisions of "boolean algebra/functional completeness"
m |
m |
||
| Line 16: | Line 16: | ||
| [[XOR]] || '''✘''' || '''✘''' ||'''✔''' || '''✔''' || '''✘''' | | [[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 '''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 '''complete''' sets. |
== Examples == | == Examples == | ||
Revision as of 11:46, 4 December 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 complete sets.
Examples
The following are some examples of functionally complete sets:
Determining Completeness
- Given a set of Boolean functions
- Find at least one of each:
- Identify functional completeness.
From the table it can be seen that the following sets are functionally complete: { AND, NOT }, { OR, NOT }, { AND, OR, NOT }.
