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 $p$, $q…$) sono espressioni logiche;
  • se $e$ è un’espressione logica, allora \(\overline{e}\) è anch’essa un’espressione logica;
  • se $e_{1}$ ed $e_{2}$ sono espressioni logiche, allora anche \(e_{1}\wedge e_{2}\), \(e_{1}\vee e_{2}\), \(e_{1}\rightarrow e_{2}\), \(e_{1}\leftrightarrow e_{2}\), \(e_{1}\overline{\vee} e_{2}\) sono espressioni logiche.

Esempio 1: La scrittura \((p\vee\overline{q})\to \overline{p\wedge q}\) è un’espressione logica.
Infatti vi compaiono $p$ e $q$, che essendo proposizioni semplici sono espressioni logiche; vi compare anche \(\overline{q}\), ma essendo $q$ un’espressione logica, anche \(\overline{q}\) lo è. Per quanto appena detto, \(p\vee\overline{q}\) e \(p\wedge q\) sono rispettivamente una disgiunzione e una congiunzione di espressioni logiche, e quindi anch’esse rientrano in tale categoria. Dal momento poi che \(p\wedge q\) è espressione logica, lo è anche la sua negazione. Infine, tutta la formula \((p\vee\overline{q})\rightarrow\overline{p\wedge q}\) 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 è \(\rightarrow\), seguito dalla disgiunzione \(\vee\) e dalla negazione grande, che si trovano entrambe al secondo livello; la negazione piccola e la congiunzione \(\wedge\) 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 \((p\vee\overline{q})\to\overline{p\wedge q}\) 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 $p$ e $q$. Cominciamo a tale proposito col riscrivere le negazioni logiche nel modo seguente:
\[
\begin{aligned}
\overline{q} &:\neg q\\
\overline{p\wedge q} &: \neg(p\wedge q)
\end{aligned}
\]
Adesso l’espressione logica iniziale si presenta così: \([p\vee(\neg q)]\rightarrow[\neg(p\wedge q )]\). Tracciamo una tabella in cui ognuno dei simboli su indicati ad esclusione delle parentesi abbia la sua colonna, e in cui ci siano $2^n$ righe, essendo $n$ il numero delle diverse proposizioni semplici presenti; in tal caso, 9 colonne e 4 righe.
tabella1
Le possibili interpretazioni delle proposizioni $p,q$ sono 4: $(V,V),(V,F),(F,V),(F,F)$. Le righe della precedente tabella sono dedicate ciascuna a una delle interpretazioni; scriviamo allora i valori di verità di $p$ e di $q$ in ciascuna delle loro colonne:
tabella2
A questo punto procediamo dall’operatore più interno a quello più esterno. Come già visto nel corso dell’osservazione 1, l’ordine degli operatori in questo caso è, dal più interno al più esterno: $\neg,\wedge,\vee,\neg,\rightarrow$. 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è $q$:
tabella3
Allo stesso modo, riferendoci alle ultime due colonne di $p$ e $q$, riempiremo la colonna della congiunzione usando la sua tavola di verità:
tabella4
Tocca adesso alla disgiunzione $\vee$. Essa si riferisce alla $p$ della prima colonna e alla $q$ negata, i cui valori di verità sono rappresentati nella terza colonna. Usando allora la tavola di verità della disgiunzione, riempiamo la seconda colonna:
tabella5
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:
tabella6
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:
tabella7
La colonna indicata in rosso nell’ultima tabella è la soluzione del problema: essa rappresenta la tavola di verità relativa all’espressione logica \((p\vee \overline{q})\rightarrow\overline{p\wedge q}\) in tutte le sue possibili interpretazioni.

 

Commenti

commenti