Logica proposizionale
Da Wikipedia, l'enciclopedia libera.
La logica proposizionale è un linguaggio formale con una semplice struttura sintattica, basata fondamentalmente su proposizioni elementari (atomi) e su connettivi logici di tipo "truth functional", che restituiscono il valore di verità di una proposizione in base al valore di verità delle proposizioni connesse (solitamente noti come AND, OR, NOT...). La semantica della logica proposizionale definisce il significato dei simboli e di qualsiasi proposizione che rispetti le regole sintattiche del linguaggio, basandosi sui valori di verità associati agli atomi. Data una interpretazione (o modello) di una proposizione (in generale di un insieme di proposizioni), e cioè una associazione tra le proposizioni elementari e le realtà rappresentate, possiamo generare un insieme infinito di proposizioni con significato definito che riguardino quella realtà (anche con un solo atomo, prendiamo ad esempio la proposizione NOT(NOT(NOT(...(NOT(P))))). Ciascuna proposizione si riferisce quindi ad uno o più oggetti della realtà rappresentata (anche astratta, ovviamente) e permette di descrivere o ragionare su quell'oggetto, utilizzando i due soli valori "Vero" e "Falso".
Indice |
[modifica] Sintassi
La definizione della struttura delle frasi (o sintassi) della logica proposizionale si fonda su due componenti;
- un alfabeto di simboli
- una grammatica generativa che opera sui simboli
[modifica] Alfabeto
L'alfabeto della logica proposizionale è costituito da:
- Un insieme numerabile di simboli di proposizione: P, Q, R, ...
- I simboli dei connettivi logici: ¬ (NOT), ∧ (AND), ∨ (OR), → (implicazione), ↔ (doppia implicazione}
- Le parentesi: (,) (hanno per lo più lo scopo di disambiguare il linguaggio)
[modifica] Grammatica generativa
La grammatica generativa della logica proposizionale, è definita attraverso regole di buona formazione delle formule, cioè regole ricorsive che consentono la creazione di formule di qualsivoglia lunghezza con struttura sintattica non ambigua. Consente cioè di creare frasi appartenenti al linguaggio e corrispondenti a precise regole, da cui il nome di formule ben formate.
L'insieme delle formule ben formate, brevemente fbf, è definito induttivamente nel seguente modo:
- un simbolo di proposizione è una fbf
- se A è una fbf lo è anche ¬A
- se A ed B sono fbf allora anche A ∧ B è una fbf
- se A ed B sono fbf allora anche A ∨ B è una fbf
- se A ed B sono fbf allora anche A → B è una fbf
- se A ed B sono fbf allora anche A ↔ B è una fbf
- niente altro è una fbf
La grammatica della logica proposizionale scritta in BNF è la seguente:
- f := l e L | NOT f | (f1 AND f2) | (f1 OR f2) | (f1 -> f2) | (f1 <-> f2)
[modifica] Semantica
La semantica della logica proposizionale è basata sulle tavole di verità e su una funzione di valutazione.
Le tavole di verità sono quelle note riguardo ai connettivi logici.
La funzione di valutazione va da dall'insieme P delle formule in {V,F} (vero, falso)
- v : P → {V,F}
ad ogni proposizione l e L si assegna un v(l)
- v(¬x) = V se v(x) = F
- v(¬x) = F se v(x) = V
eccetera, seguendo le proprietà delle tavole di verità.
