Date due variabili logiche p e q le possibili funzioni in p e q sono 16
p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Sono necessarie 16 funzioni logiche (connettivi logici)?
No, sono sufficienti NOT, AND, OR
+----+-----------------------------------------------
| 6 | p XOR q = NOT p AND q OR p AND NOT q
| 9 | p ⇔ q = p XNOR q = NOT p AND NOT q OR p AND q
| 13 | p ⇒ q = NOT(p AND NOT q) = NOT p OR q
| .. | ...
+----+-----------------------------------------------
No, sono sufficienti NOT, AND
+----+-----------------------------------------------
| 0 | 0
| 1 | p AND q
| 2 | p AND NOT q
| 3 | p
| 4 | NOT p AND q
| 5 | q
| 10 | NOT q
| 12 | NOT p
| 13 | NOT(p AND NOT q)
| 14 | NOT (p AND q)
| 15 | 1
| .. | ...
+----+-----------------------------------------------
No, sono sufficienti NOT, OR
+----+-----------------------------------------------
| 0 | 0
| 1 | NOT(NOT p OR NOT q)
| 2 | NOT(NOT p OR q))
| 3 | p
| 4 | p OR NOT q
| 5 | q
| 10 | NOT q
| 12 | NOT p
| 13 | NOT p OR q
| 14 | NOT p OR NOT q
| 15 | 1
| .. | ...
+----+-----------------------------------------------
No, è sufficiente NAND
+----+-----------------------------------------------
| 0 | 0
| 3 | p
| 5 | q
| 7 | (p NAND p) NAND (q NAND q)
| 10 | q NAND q
| 12 | p NAND p
| 14 | p NAND q
| 15 | 1
| .. | ...
+----+-----------------------------------------------
No, è sufficiente NOR
+----+-----------------------------------------------
| 0 | 0
| 1 | (p NOR p) NOR (q NOR q)
| 3 | p
| 5 | q
| 10 | q NOR q
| 12 | p NOR p
| 15 | 1
| .. | ...
+----+-----------------------------------------------