Proprietà elementari degli operatori logici

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 forma tipica 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.
Proprietà 1: Involutività di periodo 2 della negazione.
\[
\overline{\overline{p}}\leftrightarrow p
\]
Proprietà 2: Legge di contrapposizione dell’implicazione.
\[
(p\rightarrow q)\leftrightarrow(\overline{q}\rightarrow\overline{p})
\]
Proprietà 3: Idempotenza della congiunzione e della disgiunzione.
\[
\begin{array}{cc}
(p\wedge p)\leftrightarrow p\,\,\,\,; & (p\vee p)\leftrightarrow p
\end{array}
\]
Proprietà 4: Teorema dell’assorbimento di Boole.
\[
\begin{array}{cc}
[p\vee(p\wedge q)]\leftrightarrow p\,\,\,\,; & [p\wedge(p\vee q)]\leftrightarrow p
\end{array}
\]
Proprietà 5: Proprietà commutativa della congiunzione e della disgiunzione.
\[
\begin{array}{cc}
(p\wedge q)\leftrightarrow(q\wedge p)\,\,\,\,; & (p\vee q)\leftrightarrow(q\vee p)
\end{array}
\]

Proprietà 6: Proprietà associativa della congiunzione e della disgiunzione.
\[
\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}
\]

Proprietà 7: Proprietà distributiva della congiunzione rispetto alla disgiunzione e viceversa.
\[
\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}
\]

 

Dimostrazioni

Dimostrare una di tali proprietà è equivalente 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 V 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à 2: Vogliamo far vedere che vale \((p\rightarrow q)\leftrightarrow(\overline{q}\leftarrow\overline{p})\). Tracciamo a tale proposito la solita tabella, che in questo caso ha 9 colonne e 4 righe, e riempiamola con tutte le possibili interpretazioni di ? e ?.
tabella1
Calcoliamo adesso i valori di verità degli operatori più interni, cioè riempiamo le colonne seconda, quinta e ottava secondo le colonne cui si riferiscono:
tabella2
Tocca adesso all’implicazione della colonna numero sette:
tabella3
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.
tabella4
Dimostrazione della proprietà 6: Per dimostrare la prima formula della proprietà 6 dovremo adoperare una tabella composta da 11 colonne e ben 8 righe; ciò è dovuto al fatto che, essendo in questo caso le proposizioni semplici $n=3$, il numero delle loro possibili interpretazioni è $2^n=2^3=8$. Disegnamo quindi la tabella e inseriamo le interpretazioni per $p$, $q$ ed $r$ in tutti gli ordini concepibili:
tabella5
Continuiamo come di consueto, calcolando prima le colonne verdi delle congiunzioni interne, poi le colonne rosse delle congiunzioni esterne:
tabella6
Completiamo la dimostrazione calcolando la doppia implicazione, che come sempre capita per queste proprietà è l’operatore più esterno: otteniamo così
tabella7
cioè la tautologia che ci aspettavamo.

 

Osservazioni

Osservazione 1: Per quanto appena dimostrato, dal momento che è la stessa cosa scrivere \((p\wedge q)\wedge r\) oppure \(p\wedge(q\wedge r)\), si preferisce scrivere semplicemente $p\wedge q\wedge r$. Tale cosa, che si fa anche con la disgiunzione, è lecita perché non possono sorgere ambiguità. È anche uso comune dare le seguenti definizioni:

Definizione 1: Congiunzione e disgiunzione di $n$ elementi.
Siano date $n$ proposizioni $p_1,p_2,…p_n$. Per quanto osservato, possiamo considerare senza ambiguità la congiunzione e la disgiunzione di tutte e $n$ le proposizioni; esse vengono indicate con i simboli seguenti:
\[
\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}
\]

 

Commenti

commenti