Tavole di verità di espressioni logiche complesse

Espressioni logiche

Definizione 1: Espressione logica.
Si definiscono espressioni logiche tutte e sole le combinazioni finite di simboli costruite secondo le regole seguenti:

• tutte le proposizioni semplici (come
  [math]p[/math]
  ,
  [math]q...[/math]
  ) sono espressioni logiche;
• se
  [math]e[/math]
  un'espressione logica, allora
  [math] \overline{e} [/math]
  è anch'essa un'espressione logica;
• se
  [math]e_{1}[/math]
  ed
  [math]e_{2}[/math]
  sono espressioni logiche, allora anche
  [math] e_{1}\wedge e_{2}[/math]
  ,
  [math]e_{1}\vee e_{2}[/math]
  ,
  [math] e_{1} \rightarrow e_{2}[/math]
  ,
  [math] e_{1}\leftrightarrow e_{2} [/math]
  ,
  [math] e_{1}\overline{\vee} e_{2} [/math]
  sono espressioni logiche.

Esempio 1: La scrittura è un'espressione logica.
Infatti vi compaiono e , che essendo proposizioni semplici sono espressioni logiche; vi compare anche , ma essendo un'espressione logica, anche lo è. Per quanto appena detto, e sono rispettivamente una disgiunzione e una congiunzione di espressioni logiche, e quindi anchesse rientrano in tale categoria. Dal momento poi che è espressione logica, lo è anche la sua negazione. Infine, tutta la formula risulta un'implicazione di espressioni logiche, cosicché essa stessa un'espressione logica, come volevasi dimostrare.

Osservazione 1: In ogni espressione logica si possono ordinare gli operatori dal più esterno al più interno. Per esempio, nell'espressione dell'esempio 1 abbiamo che l'operatore più esterno è

, seguito dalla disgiunzione e dalla negazione grande, che si trovano entrambe al secondo livello; la negazione piccola e la congiunzione sono invece gli operatori più interni.

Metodo risolutivo per le tavole di verità di espressioni logiche complesse

Metodo risolutivo: Si consideri ancora l'espressione logica dell'esempio 1. In questa sezione vogliamo scoprire come sia possibile calcolare il valore di verità da essa assunto in tutte le possibili interpretazioni delle proposizioni semplici e . Cominciamo a tale proposito col riscrivere le negazioni logiche nel modo seguente:

Adesso l'espressione logica iniziale si presenta così:

. Tracciamo una tabella in cui ognuno dei simboli su indicati ad esclusione delle parentesi abbia la sua colonna, e in cui ci siano righe, essendo il numero delle diverse proposizioni semplici presenti; in tal caso, 9 colonne e 4 righe.
Le possibili interpretazioni delle proposizioni sono 4: . Le righe della precedente tabella sono dedicate ciascuna a una delle interpretazioni; scriviamo allora i valori di verità di e di in ciascuna delle loro colonne:
A questo punto procediamo dall'operatore più interno a quello più esterno. Come già visto nel corso dell'osservazione 1, lordine degli operatori in questo caso , dal più interno al più esterno: . Ci che faremo sarà quindi adoperare la tavola di verità della negazione per riempire la terza colonna, negando gli elementi della colonna a cui essa si riferisce, cioè :
Allo stesso modo, riferendoci alle ultime due colonne di e , riempiremo la colonna della congiunzione usando la sua tavola di verità.
Tocca adesso alla disgiunzione . Essa si riferisce alla della prima colonna e alla negata, i cui valori di verità sono rappresentati nella terza colonna. Usando allora la tavola di verità della disgiunzione, riempiamo la seconda colonna:

Procedendo in modo del tutto simile, riempiamo la sesta colonna con le negazioni dei valori di verità relativi alla congiunzione, a loro volta rappresentati nell'ottava colonna:

Non resta adesso che ripetere il procedimento per l'ultimo operatore rimasto. In questo caso occorre riferirsi alle colonne numero 2 e 6, che sono quelle degli operatori immediatamente più interni all'implicazione:

La colonna indicata in rosso nell'ultima tabella è la soluzione del problema: essa rappresenta la tavola di verità relativa all'espressione logica

in tutte le sue possibili interpretazioni.