stan.author
(0 punti)
5' di lettura

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
[math] (p\vee\overline{q}) \to \overline{p\wedge q} [/math]
è un'espressione logica.
Infatti vi compaiono
[math]p[/math]
e
[math]q[/math]
, che essendo proposizioni semplici sono espressioni logiche; vi compare anche
[math] \overline{q} [/math]
, ma essendo
[math]q[/math]
un'espressione logica, anche
[math] \overline{q} [/math]
lo è.
Per quanto appena detto,
[math] p\vee\overline{q} [/math]
e
[math] p\wedge q [/math]
sono rispettivamente una disgiunzione e una congiunzione di espressioni logiche, e quindi anchesse rientrano in tale categoria. Dal momento poi che
[math] p\wedge q [/math]
è espressione logica, lo è anche la sua negazione. Infine, tutta la formula
[math] (p\vee\overline{q}) \rightarrow \overline{p\wedge q}[/math]
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 è

[math] \rightarrow [/math]
, seguito dalla disgiunzione
[math] \vee [/math]
e dalla negazione grande, che si trovano entrambe al secondo livello; la negazione piccola e la congiunzione
[math] \wedge [/math]
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
[math] (p\vee\overline{q})\to\overline{p\wedge q}[/math]
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
[math]p[/math]
e
[math]q[/math]
. Cominciamo a tale proposito col riscrivere le negazioni logiche nel modo seguente:

[math] \begin{aligned} \overline{q} &: \neg q\ \overline {p\wedge q} &: \neg (p\wedge q) \end{aligned}[/math]

Adesso l'espressione logica iniziale si presenta così:

[math] [p\vee(\neg q)]\rightarrow[\neg(p\wedge q)] [/math]
. Tracciamo una tabella in cui ognuno dei simboli su indicati ad esclusione delle parentesi abbia la sua colonna, e in cui ci siano
[math]2^n[/math]
righe, essendo
[math]n[/math]
il numero delle diverse proposizioni semplici presenti; in tal caso, 9 colonne e 4 righe.
Le possibili interpretazioni delle proposizioni
[math]p,q[/math]
sono 4:
[math](V,V),(V,F),(F,V),(F,F)[/math]
. Le righe della precedente tabella sono dedicate ciascuna a una delle interpretazioni; scriviamo allora i valori di verità di
[math]p[/math]
e di
[math]q[/math]
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:
[math]\neg,\wedge,\vee,\neg,\rightarrow [/math]
. 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è
[math]q[/math]
:
Allo stesso modo, riferendoci alle ultime due colonne di
[math]p[/math]
e
[math]q[/math]
, riempiremo la colonna della congiunzione usando la sua tavola di verità.
Tocca adesso alla disgiunzione
[math]\vee[/math]
. Essa si riferisce alla
[math]p[/math]
della prima colonna e alla
[math]q[/math]
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

[math] (p\vee \overline{q}) \rightarrow\overline{p\wedge q} [/math]
in tutte le sue possibili interpretazioni.