OII 2017-11-16 – 5

Siano P, Q, R, S quattro variabili booleane, ossia variabili che possono assumere solo uno dei due valori 1 (VERO) e 0 (FALSO).
Ricordiamo che gli operatori booleani sono:

  1. not A, che si indica con ¬A, vale VERO se A è FALSO, e FALSO se A è VERO;
  2. A and B, che si indica con A B, vale VERO se sia A sia B sono VERO, e FALSO in tutti gli altri casi;
  3. A or B, che si indica con A B, vale FALSO se sia A sia B sono FALSO, e VERO in tutti gli altri casi.

In assenza di parentesi l’ordine di valutazione degli operatori è quello sopra riportato (prima il not, poi l’and, infine l’or).
Si consideri la seguente espressione logica:

(P∧Q)∧(R∧S)∨(¬P∧Q)

Quale delle seguenti espressioni logiche non è equivalente a quella riportata qui sopra?
Con equivalente si intende che assume gli stessi valori in funzione dei valori delle variabili booleane P, Q, R e S.

  1. (P∧Q)∧(R∧S)∨¬(P∨¬Q)
  2. ((P∧Q)∧(R∧S)∨¬P)∧((P∧Q)∧(R∧S)∨Q)
  3. ((P∧Q)∧(R∧S)∨¬P)∧((P∧Q)∧(R∧S)∨Q)∧(R∨¬R)
  4. (¬P∨¬Q)∧(R∧S)∨¬(P∨¬Q)

Soluzione 1

Considera la tabella di verità di ogni espressione

Soluzione 2

Elabora le espressioni (tramite le regole dell’algebra di Boole) finché si assomigliano tutte tranne una

(1): (P∧Q)∧(R∧S)∨(¬PQ)

= (P∧Q)∧(R∧S)∨¬P ∧ (P∧Q)∧(R∧S)∨Q : (2)

(3): ((P∧Q)∧(R∧S)∨¬P)∧((P∧Q)∧(R∧S)∨Q)∧(R∨¬R)

= ((P∧Q)∧(R∧S)∨¬P)∧((P∧Q)∧(R∧S)∨Q)∧1
= ((P∧Q)∧(R∧S)∨¬P)∧((P∧Q)∧(R∧S)∨Q) : (2)

quindi rimane la 4°…