Logica proposizionale e Logica del primo ordine

Revisionato il 12/07/2026

di danieledeluca.1405

Publisher

Vota

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Logica proposizionale.- Il linguaggio della logica delle proposizioni, formule sintatticamente corrette. Valutazione di una formula, tautologie e contraddizioni. Deduzione ed equivalenza …

Esame Logica e algebra

Facoltà Ingegneria dell'informazione

Dal corso del Prof. Rodaro Emanuele

Università Politecnico di Milano

A.A. 2022-2023

44 pagine

Appunti esame

Scarica

Estratto del documento

Logica proposizionale

Paradosso di Russell

"Sia R l'insieme di tutti gli insiemi che non contengono se stessi":

R = { x : x ∉ x }

Se R ∈ R ⇒ R ∉ R

Se R ∉ R ⇒ R ∈ R

Paradosso!

Sintassi logica proposizionale

Alfabeto

Lettere enunciative: al più numerabile A₁,...,A_j,...
Connettivi: ¬, ∧, ∨, ⇒, ⇔
Simboli ausiliari: ), (;

Tra le stringhe su questo alfabeto (es. A₂ ⇒ ¬A₂ ∧ ∨ A₃) definiamo le formule bene formate:

Ogni lettera enunciativa è F.B.F.
Se α, B sono F.B.F., allora: (α⇒B), (α∧B), (α∨B), (α⇔B), (¬α) sono F.B.F.
Nient'altro è una F.B.F.

Esempio: ¬ non è una F.B.F. (¬⇒A)∧B, ma lo è (¬(A∧B)⇔(A⇒(B∨A))). Possiamo costruire l'albero di struttura della F.B.F.

Logica proposizionale: paradosso di Russell

"Sia R l'insieme di tutti gli insiemi che non contengono se stessi":

Se R ∈ R ⇒ R ∉ R

Se R ∉ R ⇒ R ∈ R

Paradosso!

Sintassi logica proposizionale: alfabeto

Lettere enunciative: al più numerabile A₁,...,A_j,...
Connettivi: ¬, ∧, ∨, ⇒, ⇔
Simboli ausiliari: ), (;

Tra le stringhe su questo alfabeto (es. A₁ ⇒ ¬A₂ ∧ ∨ A₃) definiamo le formule bene formate:

Ogni lettera enunciativa è F.B.F.
Se α, B sono F.B.F., allora: (α⇒B), (α∧B), (α∨B), (α⇔B), (¬α) sono F.B.F.
Nient'altro è una F.B.F.

Esempio: non è una F.B.F. (¬⇒A)∧B, ma lo è (¬(A∧B)⇔(A⇒(B∨A))). Possiamo costruire l'albero di struttura della F.B.F.

LEGGI LA SOTTOFORMULA: (A ⇒ (B∨A))

Interpretazione e semantica

Una interpretazione è una funzione:

ν: { _F F.B.F } ------> {0, 1}

Che soddisfa:

ν(A∧B) = min(ν(A), ν(B));
ν(¬A) = 1 - ν(A);
ν(A∨B) = max(ν(A), ν(B));
ν((A⇒B)) ...
ν((A⇔B)) ...

Più facendo lavorare con le tavole di verità su dispense:

μ(A)	μ(B)	μ(A∧B)	μ(¬A)	μ(¬B)	μ(A⇒B)	μ(B⇒A)	μ(A⇔B)
0	0	0	1	1	1	1	1
0	1	0	1	0	1	0	0
1	0	0	0	1	0	1	0
1	1	1	0	0	1	1	1

OSS: Una interpretazione è univocamente determinata dal valore sulle lettere enunciative e dalle precedenti regole.

Una F.B.F. α si dice soddisfacibile se esiste una interpretazione t.c. μ(α)=1, in questo caso μ è chiamato un modello di α.

OSS: In soldoni, i modelli di α sono le righe della T. di verità che vi rendono vera la F.B.F. α.

Esempio

A	B	¬A	¬A∨B	A⇒(¬A∨B)
0	0	1	1	1
0	1	1	1	1 ⇒ μ₁(A)=μ₁(B)=0
1	0	0	1	1 ⇒ μ₂(A)=0 μ₂(B)=1
1	1	0	1	1 ⇒ μ₃(A)=μ₃(B)=1

Dato un insieme Γ di F.B.F. Γ si dice soddisfacibile se esiste un modello γ per tutte le F.B.F. in Γ, in caso contrario Γ si dice insoddisfacibile.

Esempio

I modelli sono:

Γ={¬A, A⇒(¬A∨B)} μ₁, μ₂ di prima

Γ={¬A, B, A⇒(¬A∨B)} I modelli: μ₂(A)=0 μ₂(B)=1

Γ={¬A, A, B, A⇒(¬A∨B)} è insoddisfacibile

Tautologia

Una tautologia è una F.B.F. α t.c. per cui ogni interprete è un modello, lo scriviamo ⊢α

Es: ⊢ A∨(A⇒(¬A∨B))

OSS: Verificare se una F.B.F. è un problema decidibile ⇒ Algoritmo: costruisco la tabella di verità.

Anteprima

Vedrai una selezione di 10 pagine su 44