Espressioni logiche – 4

di
Calcolo

 Se si applicano i connettivi logici a 3 clausole i risultati dipendono o meno dall’ordine di valutazione?

Dall’osservazione delle tabelle successive si può dedurre che

  • OR, AND, XOR, XNOR sono operatori associativi
  • NOR, NAND, non sono operatori associativi

OR

  p q r   p OR q   (p OR q) OR r   q OR r   p OR (q OR r)
+-------+--------+---------------+--------+---------------+
| 0 0 0 | 0      | 0             | 0      | 0             |
| 0 0 1 | 0      | 1             | 1      | 1             |
| 0 1 0 | 1      | 1             | 1      | 1             |
| 0 1 1 | 1      | 1             | 1      | 1             |
| 1 0 0 | 1      | 1             | 0      | 1             |
| 1 0 1 | 1      | 1             | 1      | 1             |
| 1 1 0 | 1      | 1             | 1      | 1             |
| 1 1 1 | 1      | 1             | 1      | 1             |
+-------+--------+---------------+--------+---------------+

  • OR: vero se almeno una clausola è vera
  • (p OR q) OR r = p OR (q OR r) = p OR q OR r

AND

  p q r   p AND q   (p AND q) AND r   q AND r   p AND (q AND r)
+-------+---------+-----------------+---------+-----------------+
| 0 0 0 | 0       | 0               | 0       | 0               |
| 0 0 1 | 0       | 0               | 0       | 0               |
| 0 1 0 | 0       | 0               | 0       | 0               |
| 0 1 1 | 0       | 0               | 1       | 0               |
| 1 0 0 | 0       | 0               | 0       | 0               |
| 1 0 1 | 0       | 0               | 0       | 0               |
| 1 1 0 | 1       | 0               | 0       | 0               |
| 1 1 1 | 1       | 1               | 1       | 1               |
+-------+---------+-----------------+---------+-----------------+

  • AND: vero se tutte le clausole sono vere
  • (p AND q) AND r = p AND (q AND r) = p AND q AND r

XOR

  p q r   p XOR q   (p XOR q) XOR r  q XOR r   p XOR (q XOR r)
+-------+---------+-----------------+--------+-----------------+
| 0 0 0 | 0       | 0               | 0      | 0               |
| 0 0 1 | 0       | 1               | 1      | 1               |
| 0 1 0 | 1       | 1               | 1      | 1               |
| 0 1 1 | 1       | 0               | 0      | 0               |
| 1 0 0 | 1       | 1               | 0      | 1               |
| 1 0 1 | 1       | 0               | 1      | 0               |
| 1 1 0 | 0       | 0               | 1      | 0               |
| 1 1 1 | 0       | 1               | 0      | 1               |
+-------+---------+-----------------+--------+-----------------+

  • XOR: vero se il numero di clausole vere è dispari
  • (p XOR q) XOR r = p XOR (q XOR r) = p XOR q XOR r

NOR

  p q r   p NOR q   (p NOR q) NOR r   q NOR r   p NOR (q NOR r)
+-------+---------+-----------------+---------+-----------------+
| 0 0 0 | 1       | 0               | 1       | 0               |
| 0 0 1 | 1       | 0               | 0       | 1               |
| 0 1 0 | 0       | 1               | 0       | 1               |
| 0 1 1 | 0       | 0               | 0       | 1               |
| 1 0 0 | 0       | 1               | 1       | 0               |
| 1 0 1 | 0       | 0               | 0       | 0               |
| 1 1 0 | 0       | 1               | 0       | 0               |
| 1 1 1 | 0       | 0               | 0       | 0               |
+-------+---------+-----------------+---------+-----------------+

  • Attenzione!
    (p NOR q) NOR r  <> p NOR (q NOR r)

NAND

  p q r   p NAND q   (p NAND q) NAND r   q NAND r   p NAND (q NAND r)
+-------+----------+-------------------+----------+-------------------+
| 0 0 0 | 1        | 1                 | 1        | 1                 |
| 0 0 1 | 1        | 0                 | 1        | 1                 |
| 0 1 0 | 1        | 1                 | 1        | 1                 |
| 0 1 1 | 1        | 0                 | 0        | 1                 |
| 1 0 0 | 1        | 1                 | 1        | 0                 |
| 1 0 1 | 1        | 0                 | 1        | 0                 |
| 1 1 0 | 0        | 1                 | 1        | 0                 |
| 1 1 1 | 0        | 1                 | 0        | 1                 |
+-------+----------+-------------------+----------+-------------------+

  • Attenzione!
    (p NAND q) NAND r <> p NAND (q NAND r)

XNOR

  p q r   p XNOR q   (p XNOR q) XNOR r   q XNOR r   p XNOR (q XNOR r)
+-------+----------+-------------------+----------+-------------------+
| 0 0 0 | 1        | 0                 | 1        | 0                 |
| 0 0 1 | 1        | 1                 | 0        | 1                 |
| 0 1 0 | 0        | 1                 | 0        | 1                 |
| 0 1 1 | 0        | 0                 | 1        | 0                 |
| 1 0 0 | 0        | 1                 | 1        | 1                 |
| 1 0 1 | 0        | 0                 | 0        | 0                 |
| 1 1 0 | 1        | 0                 | 0        | 0                 |
| 1 1 1 | 1        | 1                 | 1        | 1                 |
+-------+----------+-------------------+----------+-------------------+

  • XNOR: vero se il numero di clausole vere è dispari
  • (p XNOR q) XNOR r = p XNOR (q XNOR r) = p XNOR q XNOR r