Semiconductor & Computer Engineering
From WikiChip
Difference between revisions of "boolean algebra/functional completeness"
(init) |
|||
| Line 7: | Line 7: | ||
* '''{''' [[AND]], [[NOT]] '''}''', '''{''' [[OR]], [[NOT]] '''}''', '''{''' [[XOR]], [[AND]] '''}''', '''{''' [[MAJ]], [[NOT]] '''}''' | * '''{''' [[AND]], [[NOT]] '''}''', '''{''' [[OR]], [[NOT]] '''}''', '''{''' [[XOR]], [[AND]] '''}''', '''{''' [[MAJ]], [[NOT]] '''}''' | ||
| + | == Proving Completeness == | ||
| + | {| class="wikitable" style="float: right;" | ||
| + | ! Func !! Monotone !! Self-dual !! Linear !! 0-preserving !! 1-preserving | ||
| + | |- | ||
| + | | [[NOT]] || '''✘''' || '''✔''' || '''✔''' || '''✘''' || '''✘''' | ||
| + | |- | ||
| + | | [[AND]] || '''✔''' || '''✘''' || '''✘''' || '''✔''' || '''✔''' | ||
| + | |- | ||
| + | | [[OR]] || '''✔''' || '''✘''' ||'''✘''' || '''✔''' || '''✔''' | ||
| + | |} | ||
| + | * Given a set of Boolean functions | ||
| + | * Find at least one of each: | ||
| + | *# [[monotone Boolean function]] | ||
| + | *# [[self-dual Boolean function]] | ||
| + | *# [[linear boolean function]] | ||
| + | *# [[0-preserving Boolean function]] | ||
| + | *# [[1-preserving Boolean function]] | ||
| + | * Identify functional completeness. | ||
| − | {{ | + | From the table it can be seen that the following sets are functionally complete: '''{''' [[AND]], [[NOT]] '''}''', '''{''' [[OR]], [[NOT]] '''}''', '''{''' [[AND]], [[OR]], [[NOT]] '''}'''. |
Revision as of 18:35, 20 November 2015
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 }.
Examples
The following are some examples of functionally complete sets:
Proving Completeness
| Func | Monotone | Self-dual | Linear | 0-preserving | 1-preserving |
|---|---|---|---|---|---|
| NOT | ✘ | ✔ | ✔ | ✘ | ✘ |
| AND | ✔ | ✘ | ✘ | ✔ | ✔ |
| OR | ✔ | ✘ | ✘ | ✔ | ✔ |
- 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 }.