Una proposizione è una frase alla quale è possibile attribuire un valore di verità (VERO o FALSO) secondo un criterio oggettivo. Le proposizioni le indicheremo con le lettere minuscole (p, q ecc…)

Esempio. La frase “5 è un numero dispari” è una proposizione vera, mentre la frase ”Roma è la capitale della Germania” è una proposizione falsa.

Esempio. Le frasi ”mi piacerebbe andare a Roma” (esprime un desiderio), ”che bel cane!” (esprime un’esclamazione), ”hai una penna?” (esprime una richiesta) non sono proposizioni.

I connettivi logici sono: ”non”, ”e”, ”o”, ”se. . . allora”, ”se e solo se” e servono per legare fra loro piu` proposizioni.

Le proposizioni possono essere atomiche o composte (ottenute combinando frasi attraverso connettivi logici).

Esempio. La frase ”Roma è la capitale d’Italia” è una proposizione atomica, mentre la frase ”se c’è il sole, allora esco” è una proposizione composta (ottenuta combinando due frasi attraverso il connettivo ”se. . . allora”).

Gli enunciati aperti o predicati sono delle frasi in cui compaiono delle variabili. Se alle variabili vengono assegnati dei valori il predicato diventa una proposizione.

L’insieme dei valori che possono assumere le variabili è detto dominio $D$. Mentre il sottoinsieme di $D$ che trasforma il predicato in proposizione vera è detto insieme di verità dell’enunciato aperto.

Esempio. Consideriamo l’enunciato aperto p(x): ”x è un numero naturale maggiore di 4”. Il dominio D = N, mentre l’insieme di verità
I ={x ∈N|x >4}.

Le espressioni logiche sono combinazioni di proposizioni, connettivi e parentesi.

Per determinare il valore di verità delle espressioni logiche utilizzeremo delle tabelle (tavole di verità ) in cui verranno attribuiti i valori di verità alle proposizioni di cui sono composte le espressioni stesse.

Due espressioni si dicono logicamente equivalenti se possiedono la medesima tavola di verità.