Operatori logici: le proprietà elementari con dimostrazioni

In questi appunti è presente un riassunto delle principali proprietà dei connettori logici, dimostrate attraverso l'impiego delle tavole di verità.

Cosa sono gli operatori logici e quali sono le principali proprietà

Gli operatori logici godono di alcune proprietà, proprio come le operazioni aritmetiche. Esse, anzichè in forma di equazioni, vengono date in forma di tautologia, la quale coinvolge due espressioni logiche collegate da una doppia implicazione. Il fatto che una doppia implicazione sia sempre verificata implica che le due espressioni coimplicate sono equivalenti e, quindi, intercambiabili.

Ecco la lista delle proprietà degli operatori logici:

• Proprietà 1: involutività di periodo
  [math]2[/math]
  della negazione
  [math] \overline{\overline{p}}\leftrightarrow p [/math]
• Proprietà 2: legge di contrapposizione dell'implicazione.
  [math](p\rightarrow q)\leftrightarrow(\overline{q}\rightarrow \overline{p})[/math]
• Proprietà 3: Idempotenza della congiunzione e della disgiunzione.
  
  [math]\begin{array}{cc}
  (p \wedge p)\leftrightarrow p,,,,;&(p \vee p)\leftrightarrow p
  \end{array} [/math]
• Proprietà 4: Teorema dell'assorbimento di Boole
  [math]\begin{array}{cc}
  [p\vee(p\wedge q)]\leftrightarrow p,,,,;&[p\wedge(p\vee q)]\leftrightarrow p
  \end{array}[/math]
• Proprietà 5: Proprietà commutativa della congiunzione e della disgiunzione
  
  [math]
  \begin{array}{cc}
  (p\wedge q)\leftrightarrow(q\wedge p),,,,;&(p\vee q)\leftrightarrow(q\vee p)
  \end{array}
  [/math]
• Proprietà 6: Proprietà associativa della congiunzione e della disgiunzione
  
  [math]
  \begin{array}{cc}
  [(p\wedge q)]\leftrightarrow[p\wedge(q\wedge r)],,,,;&[(p\vee q)\vee r]\leftrightarrow[p\vee(q\vee r)]
  \end{array}
  [/math]
• Proprietà 7: Proprietà distributiva della congiunzione rispetto alla disgiunzione e viceversa
  
  [math]\begin{array}{cc}
  [p\wedge(q\vee r)]\leftrightarrow[(p\wedge q)\vee(p\wedge r)],,,,;&[p\vee(q\wedge r)]\leftrightarrow[(p\vee q)\wedge(p\vee r)]
  \end{array}[/math]

Dimostrazioni delle proprietà degli operatori logici

Dimostrare una delle precedenti proprietà equivale al far vedere che essa è una tautologia. Per far ciò, occorre calcolarne la tavola di verità e far vedere che il risultato finale è una colonna contenente solamente il risultato
[math]V[/math]
per ogni interpretazione. Ci indica che la verità della proposizione studiata non dipende dall'interpretazione considerata, ma solo dalla struttura della formula stessa. Nel seguito vedremo alcune dimostrazioni scelte.

Dimostrazione della proprietà due

Vogliamo far vedere che vale
[math]((p \rightarrow q) \leftrightarrow(\overline{q} \leftarrow\overline{p}))[/math]
. Tracciamo a tale proposito la solita tabella, che in questo caso ha
[math]9[/math]
colonne e
[math]4[/math]
righe, e riempiamola con tutte le possibili interpretazioni.

Calcoliamo adesso i valori di verità degli operatori più interni, cioè riempiamo le colonne seconda, quinta e ottava secondo le colonne cui si riferiscono.
Poi si passa all'implicazione della colonna numero sette. Infine, calcoliamo i valori di verità assunti dalla doppia implicazione in ciascuna delle quattro interpretazioni disponibili, e concludiamo la dimostrazione osservando che si tratta di una tautologia, come volevasi dimostrare.

Dimostrazione della proprietà 6

Per dimostrare la prima formula della proprietà
[math]6[/math]
dovremo adoperare una tabella composta da
[math]11[/math]
colonne e ben
[math]8[/math]
righe. Ciò è dovuto al fatto che, essendo in questo caso le proposizioni semplici
[math]n=3[/math]
, il numero delle loro possibili interpretazioni è
[math]2^n=2^3=8[/math]
.

Disegniamo quindi la tabella e inseriamo le interpretazioni per

[math]p[/math]
,
[math]q[/math]
ed
[math]r[/math]
in tutti gli ordini concepibili.
Continuiamo come di consueto, calcolando prima le colonne delle congiunzioni interne, poi le colonne delle congiunzioni esterne.
Completiamo la dimostrazione calcolando la doppia implicazione, che come sempre capita per queste proprietà è l'operatore più esterno: otteniamo così la tautologia che ci aspettavamo.

Osservazioni sulle dimostrazioni precedentemente presentate

Per quanto appena dimostrato, dal momento che è la stessa cosa scrivere
[math]((p\wedge q)\wedge r)[/math]
[math](p\wedge(q\wedge r))[/math]
, si preferisce scrivere semplicemente
[math]p\wedge q \wedge r[/math]
. Tale cosa, che si fa anche con la disgiunzione, è lecita perchè non possono sorgere ambiguità. E' anche uso comune dare la definizione enunciata nel paragrafo seguente.



Definizione 1: Congiunzione e disgiunzione di n elementi

Siano date
[math]n[/math]
proposizioni
[math]p_1,p_2,...p_n[/math]
. Per quanto osservato, possiamo considerare senza ambiguità la congiunzione e la disgiunzione di tutte e
[math]n[/math]
le proposizioni. Esse vengono indicate con i simboli seguenti:

[math]
\begin{array}{cc}
\displaystyle
\bigwedge_{i=1}^n p_{i}=p_{1}\wedge p_{2}\wedge ... \wedge p_{n},\displaystyle \bigvee_{i=1}^n p_{i}=p_{1}\vee p_{2}\vee ...\vee p_{n}
\end{array}
[/math]

Per ulteriori informazioni sugli operatori logici vedi anche qui