Semiconductor & Computer Engineering
From WikiChip
Difference between revisions of "boolean algebra/functional completeness"
m (→Proving Completeness) |
|||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | A set of logic operations | + | {{ba title|functional completeness}} |
| + | {| 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 are said to be '''functionally complete''' 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 == | ||
| Line 8: | Line 26: | ||
== Determining Completeness == | == Determining Completeness == | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
* Given a set of Boolean functions | * Given a set of Boolean functions | ||
* Find at least one of each: | * Find at least one of each: | ||
| − | *# [[monotone Boolean function]] | + | *# [[monotone increasing Boolean function|monotone increasing]] |
| − | *# [[self-dual Boolean function]] | + | *# [[self-dual Boolean function|self-dual]] |
| − | *# [[linear boolean function]] | + | *# [[linear boolean function|linear]] |
| − | *# [[0-preserving Boolean function]] | + | *# [[0-preserving Boolean function|0-preserving]] |
| − | *# [[1-preserving Boolean function]] | + | *# [[1-preserving Boolean function|1-preserving]] |
* Identify functional completeness. | * Identify functional completeness. | ||
From the table it can be seen that the following sets are functionally complete: '''{''' [[AND]], [[NOT]] '''}''', '''{''' [[OR]], [[NOT]] '''}''', '''{''' [[AND]], [[OR]], [[NOT]] '''}'''. | From the table it can be seen that the following sets are functionally complete: '''{''' [[AND]], [[NOT]] '''}''', '''{''' [[OR]], [[NOT]] '''}''', '''{''' [[AND]], [[OR]], [[NOT]] '''}'''. | ||
| + | |||
| + | == See also == | ||
| + | * [[gate universality]] | ||
Latest revision as of 23:05, 7 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 are said to be functionally complete 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[edit]
The following are some examples of functionally complete sets:
Determining Completeness[edit]
- 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 }.