Logica proposizionale

Note

La logica proposizionale è un linguaggio composto da un alfabeto di:

Lettere enunciative (ente atomico) al più numerabile
Connettivi:
Ausiliari:

Tra tutte le stringhe generabili su questo alfabeto, individuo le Formule Ben Formate (FBF):

Ogni lettera enunciativa è una FBF.
Se sono FBF, allora , , , , sono FBF.
Nient'altro è una FBF.

Sottoformule

Le sottoformule di una FBF sono sottostringhe di , che sono FBF. Dato si può costruire l'albero delle sue sottoformule.

Priorità degli operatori

Introduco una priorità sugli operatori, come in aritmetica:
E connettivi uguali si associano a sinistra.

Semantica

Note

Un interpretazione è una funzione: $è$ Che soddisfa:

Queste sono rappresentabili come tabelle di verità:

Un interpretazione è un assegnamento alle lettere enunciative (variabili) e la verità () o meno () di una formula dipende da questo assegnamento e dalle tabelle di verità.

Soddisfacibilità

Note

Una FBF si dice soddisfacibile se esiste un interpretazione tale che . In questo caso è chiamato un modello di e scriviamo . In caso contrario si dice insoddisfacibile.

I modelli di una formula sono le righe che rendono vera .

Una FBF con per ogni interpretazione si dice una tautologia, e la scriviamo .

Conseguenza semantica

Note

Una FBF si dice essere conseguenza semantica di un insieme di FBF () se ogni modello di è anche modello di .

Inoltre, per il teorema della deduzione semantica: Per il teorema del legame tra insoddisfacibilità e conseguenza semantica: $è$

Per verificare che :

Calcolo i modelli di
Verifico che questi siano anche modelli di

Dimostrazione

Sia un interpretazione:

Se non è modello di , allora non è modello di
Se è modello di , allora dall'ipotesi allora è modello di : , cioè non è modello di

Equivalenza semantica

Note

Due FBF e si dicono semanticamente equivalenti () se e hanno gli stessi modelli: Cioè hanno la stessa tabella di verità.

Tip

Data una tavola di verità, è possibile costruire il suo rappresentante nei seguenti metodi:

Forma normale congiuntiva

Guardiamo nella tabella di verità le righe con :

Forma normale disgiuntiva

Guardiamo nella tabella di verità le righe con :

È sempre possibile trasformare una FBF in un'equivalente che contiene solo i connettivi: Detti connettivi completi adeguati. L'equivalenza non è unica.