Logica proposizionale

Logica proposizionale

Il concetto di logica

Esistono tante logiche diverse, infinite. Assegnare una teoria formale equivale ad assegnare una logica, quindi i concetti di logica e teoria formale sono equivalenti.

Alfabeto

Consideriamo un insieme di simboli che chiamiamo alfabeto. Questo insieme lo indico con un insieme numerabile finito. Possono essere elementi dell'insieme alfabeto tutti quei simboli come , , , , ecc. Attraverso questi elementi possiamo costruire delle sequenze di simboli che hanno senso opportuno, cioè mi posso creare un linguaggio, ovvero mi posso creare delle regole per comporre gli elementi fra loro.

Formule ben formate (FBF)

Esistono formule che hanno senso e altre formule che invece non lo hanno. Le formule sono proprio delle sequenze di questi elementi. Queste formule le posso costruire a partire da un alfabeto e chiamo ben formate (FBF) tutte quelle formule che hanno un senso. In un linguaggio, le frasi possono essere classificate in corrette e non corrette.

Linguaggio

Avere un linguaggio vuol dire avere un alfabeto e delle formule ben formate che ci costruiamo proprio a partire da esso. Quindi un linguaggio è un alfabeto in cui si ha la capacità di costruire formule ben formate. Un linguaggio è un alfabeto in cui si ha la capacità di costruire FBF, cioè ci sono delle espressioni/formule di questo linguaggio che sono accettabili e altre formule no. Quindi ci deve essere un criterio che mi deve far capire quando una formula è ben formata e quando non lo è.

Grafico delle formule

Con questo grafico rappresentiamo tutte le parole che possono essere costruite a partire da un alfabeto senza tenere conto del significato (FNBF, formule non ben formate), cioè contiene tutte le possibili sequenze costruibili. L'insieme medio, quello blu, contiene invece tutte quelle parole con un senso, cioè contiene tutte le formule ben formate. L'insieme più piccolo contiene tutti gli elementi dell'alfabeto.

Teoria formale

Una teoria formale è costituita da un linguaggio (insieme finito e numerabile di FBF) e da un sistema deduttivo. Il sistema deduttivo è costituito da:

• Sistema di assiomi.
• Regole di inferenza.

Quando si fonda una teoria, ho un sistema deduttivo quando assegno gli assiomi e le regole di inferenza. In un sistema di assiomi (ci sono teorie in cui questo sistema è vuoto) gli assiomi sono un sottoinsieme numerato delle formule ben formate particolari che può essere vuoto, finito o infinito. Le regole di inferenza sono i sistemi dimostrativi, cioè dei modi logici con cui uno nella teoria procede per dimostrare il teorema e che mi permettono di introdurre il concetto di dimostrazione, infatti, queste regole mi consentono di dedurre e di dimostrare qualcosa. Sono anche dette regole di dimostrazione. Le regole di inferenza sono diverse a seconda della teoria in cui ci troviamo.

Livelli di lettura di una teoria formale

• Sintassi: A livello di sintassi ci preoccupiamo solo di scrivere parole che rispettano le regole del linguaggio senza tenere conto del significato. Quindi la sintassi è un insieme di regole per stabilire quali sequenze di simboli siano accettabili in un linguaggio o meno. La sintassi si occupa solo della forma della frase e non del loro contenuto. Il compito della sintassi è fornire delle regole per costruire le FBF.
• Semantica: A livello di semantica ci preoccupiamo di assegnare un significato a tutte le frasi sintatticamente corrette (cioè alle FBF). Il compito della semantica è assegnare un significato alle FBF. In un contesto semantico possiamo assegnare un significato VERO o FALSO a tutte le formule sintatticamente corrette.

Logica proposizionale

Per avere una logica proposizionale devo avere un linguaggio, un sistema deduttivo, gli assiomi e delle regole di inferenza. Avere una teoria formale è diverso da avere una teoria. Il termine formale dà luogo al concetto di teoria formale che è diverso dal concetto di teoria. Avere un linguaggio formale è diverso da avere un linguaggio. Esiste una teoria formale che è quella dei linguaggi formali dell'informatica. Studiare la teoria formale dei linguaggi formali vuol dire che i linguaggi formali sono una teoria formale in cui vi è un linguaggio e un sistema deduttivo. Il linguaggio formale è una teoria formale speciale costituita da un linguaggio e un sistema deduttivo.

Logica delle proposizioni

La logica proposizionale è un particolare tipo di logica che tenta di matematizzare e codificare la logica delle proposizioni. Una proposizione è un'affermazione che esprime un valore di verità, cioè un'affermazione che è VERA oppure è FALSA. In questo senso stiamo parlando a un livello semantico per la proposizione perché io assegno un valore di verità o di falsità. Per esempio:

• "5 è un numero dispari."
• "Roma è la capitale della Francia."

Sono due proposizioni che assumono un valore VERO oppure FALSO. Nel mio contesto astratto ho un alfabeto con cui formo delle parole e se ho una grammatica le parole le posso formare in maniera corretta. Per costruire un linguaggio bisogna fissare un alfabeto, cioè un insieme di simboli che ci serviranno a costruire delle "frasi" (che, in questo contesto, chiameremo formule). Le "frasi" non sono altro che delle sequenze finite (stringhe) di simboli che appartengono all'alfabeto che abbiamo fissato. Servirà poi una sintassi, cioè un insieme di regole per stabilire quali sequenze di simboli sono accettabili nel nostro linguaggio e quali no.

Calcolo proposizionale

Nel calcolo proposizionale (o logica) si devono manipolare delle proposizioni. Le proposizioni sono dei simboli che possiamo indicare con P, Q, R, ecc. In maniera astratta posso considerare le proposizioni come elementi di un insieme. Immaginiamo di avere un insieme numerabile di simboli che indicano le proposizioni.

A partire da queste proposizioni voglio costruire altre proposizioni che chiamo formule ben formate. L'alfabeto è composto dai simboli elementari, cioè dalle proposizioni atomiche. A partire dalle proposizioni atomiche si vogliono costruire le formule ben formate. Questo posso farlo servendomi dei simboli o connettivi. Le proposizioni si possono poi combinare tra loro mediante l'uso dei connettivi. Pertanto, il nostro alfabeto dovrà contenere:

• Simboli per indicare le proposizioni: P, Q, R, ...
• Simboli per indicare i connettivi: "non", "e", "o", "implica" o "freccia". Notazione: ¬, ∧, ∨, →
• Simboli accessori, come le parentesi: ( )

Posso costruire frasi utilizzando le proposizioni, i connettivi e le parentesi. Il simbolo ⊥ si chiama assurdo e serve per indicare la falsità.

Regole della sintassi

Ora stabiliamo le regole della sintassi, cioè spieghiamo come si costruiscono le formule ben formate. Quindi seguendo queste regole io saprò dire se una formula è ben formata oppure no. Le regole sono le seguenti:

• P, Q, R, ..., ⊥ sono FBF (sono proposizioni atomiche).
• Le altre FBF si ottengono combinando delle FBF già costruite mediante l'uso dei connettivi, nei modi seguenti: Se P e Q sono FBF, allora anche (¬P), (P ∧ Q), (P ∨ Q) e (P → Q) sono FBF.

Questa regola mi dice che per avere una formula ben formata devo avere le parentesi, quindi ¬P non è una FBF perché non ha le parentesi.

Per esempio, le seguenti sono FBF:

• (¬P → Q)

Invece, la seguente sequenza di simboli non è una FBF:

• ¬P Q

Questa sequenza non è una formula ben formata perché non è stata costruita ricorsivamente. Dietro alla costruzione delle FBF c'è il principio di induzione matematica dei numeri naturali.

Per esempio, la sequenza ¬(¬) → ) non è una FBF perché c'è un uso inappropriato delle parentesi:

• Per costruire la FBF giusta parto da ¬.
• Per ottenere ¬(¬) devo aggiungere le parentesi e quindi è una FBF.
• Per ottenere (¬(¬)) devo aggiungere ancora due parentesi quindi è una FBF.

A questo punto diciamo che per essere una FBF devo aggiungere queste parentesi e quindi la sequenza, per essere FBF, diventa: ((¬(¬)) → ⊥).

Convenzione delle parentesi

Per evitare l'uso di molte parentesi si usa una convenzione. Le regole che abbiamo stabilito conducono a un uso eccessivo delle parentesi. Per semplificare l'aspetto delle formule conviene stabilire delle priorità tra i vari simboli:

• P ∧ ¬ → deve essere interpretata come ((P ∧ (¬Q)) → R),
• invece, nella formula ¬P ∧ Q ∨ R → S non si possono togliere le parentesi, perché la formula verrebbe interpretata come (P → (Q ∨ R)).

A questo punto, nella logica delle proposizioni ho fissato un linguaggio e delle FBF. Avendo un linguaggio ora posso introdurre il concetto di semantica, cioè posso parlare di VERO o di FALSO. Il linguaggio è assegnato data la sintassi. Nella logica proposizionale, il linguaggio è dato da un insieme numerabile di simboli, che chiamo proposizioni, e da un insieme di simboli, che chiamo connettivi. Per costruire delle FBF si parte dalle proposizioni atomiche e operando con i connettivi intendo tutte le altre FBF.

Logica a due valori

In una logica si può parlare soltanto di VERO o di FALSO, ma si possono anche avere logiche a più di due valori. La logica proposizionale è una logica a due valori, cioè, data una proposizione si assegna un valore di verità o un valore di falsità. Dico che una proposizione è VERA quando ad essa si attribuisce il simbolo 1. Dico che una proposizione è FALSA se ad essa si attribuisce il simbolo 0. Il VERO e il FALSO sono soltanto due simboli. Assegnare un valore di verità o di falsità significa dare una funzione dall'insieme delle FBF in {0,1}:

• : FBF → {0,1}

Che associa ad ogni formula ben formata il suo valore di verità. Allora, quando io ho una semantica vuol dire che so attribuire ad ogni FBF un valore.

Ho una logica a più valori quando ho una funzione di verità che va da FBF in un insieme finito e numerabile di almeno tre simboli.

Dire che una proposizione è VERA vuol dire che la funzione di verità sulla proposizione che sto considerando vale 1. Dire che una proposizione è FALSA vuol dire che la funzione di verità sulla proposizione che sto considerando vale 0.

Quindi ad esempio poniamo:

Per ogni proposizione atomica A.

Se ho una formula che non è ben formata io non posso attribuire un valore di verità o di falsità.