Istituzioni di logica - riassunto

Istituzioni di logica

(riassunto)

 ENUNCIATO = proposizione per la quale sia sensato chiedersi se sia vera o falsa

Enunciato semplice (o atomico)

o  Non contiene nessun altro enunciato

Enunciato composto

o  È possibile scomporlo in enunciati più semplici

 CONNETTIVI = permettono di ottenere enunciati composti da enunciati semplici

(“e”, “o”, “se”)

 FORMULA = espressione ottenuta da un insieme di simboli, chiamati lettere

proposizionali, mediante l’applicazione dei connettivi

Rappresentazione, in un linguaggio artificiale,

o Del contenuto concettuale degli enunciati del linguaggio naturale

o ⋀

p q

o  p → enunciato, “piove”

 ⋀ → connettivo, “e”

 q → enunciato, “c’è vento”

 L

Linguaggio proposizionale

Insieme i cui elementi si dicono lettere proposizionali

o  Con l’eventuale aggiunta di apici o indici

-formule = stringhe di simboli ottenute applicando un numero finito

L

o di volte le seguenti regole di formazione:

p∈ L

 Ogni è una formula, detta formula atomica

A A

 Se e sono formule, tali sono:

1 2

⋀

A A

 1 2

⋁

A A

 1 2

A → A

 1 2

¬ A

 1

Caratteri dei connettivi

o  ⋀ = e

 ⋁ = o

 → = se… allora

 ¬ = non

Le formule vengono indicate con lettere maiuscole dette metavariabili,

o con indici e apici F

 L’insieme di tutte le formule è indicato L

Convenzioni di notazione

o  Si utilizzano molte parentesi → per unicità di lettura

 Che serve a stabilire il connettivo principale in formule non

atomiche

 Per alleggerire la scrittura, l’uso delle parentesi non viene

rispettato alla lettera:

 Le parentesi esterne → omesse

p … p

 sta per:

1 n …

( )

p p …

⋀

( (¿ ))

p

 n−1 n

2 ¿

p

1

¿

 ⋀ ⋁

¬ lega più strettamente di e , che stringono

→

più strettamente di

 Quindi, in lettura, si parte dall’esterno

 →

Prima

 ⋁

,

Poi

 ¬

Ed infine

 ( (B

A ↔ B sta per A → B)⋀ → A)

 ↔ = connettivo chiamato bi-implicazione o

equivalenza materiale

 Una formula denota un’asserzione → che può essere vera o falsa

Noto il valore di verità dei suoi costrutti

o ⋀

A B A B

Si può determinare il valore di verità

o della formula stessa

T T T

 Ottica vero-funzionale

Definire il significato di un connettivo =

o F T F

specificare sotto quali condizioni è vero o falso

T F F

un enunciato che lo contiene come connettivo

principale F F F

Semantica bivalente

o  I valori di verità sono due:

 Vero T

 Falso F

Tavola di verità per il connettivo

o  Verifica di veridicità di un enunciato

 ⋀

Tavola di verità per il connettivo (congiunzione)

 ⋀ A B

A B è vera se e solo se sia che sono vere

 ⋁

Tavola di verità per il connettivo (disgiunzione)

 ⋁

A B è vera quando almeno uno degli enunciati è vero

⋁

A B A B

T T T

F T T

T F T

F F F

 ¬

Tavola di verità per il connettivo (negazione)

 A

¬ A è vera se e solo se è falsa

A ¬A

T F

F T

 →

Tavola di verità per il connettivo (implicazione)

 A B

A → B è falsa solamente quando è vera e è falsa

A B A →B

T T T

F T T

T F F

F F T

 →

Nell’implicazione ( ), l’enunciato è falso solo se:

 La conclusione è falsa e la premessa vera

 È invece vero anche se la premessa è falsa

 Stabilire la verità di una formula proposizionale

Fissiamo innanzitutto il fatto di accettare di avere solo 2 possibili valori

o di verità (T e F)

{ }

 2≔ 1,0 → insieme dei valori di verità

Si procede per gradi → partendo dalle formule atomiche, fino a quelle più

o complesse

 Atto di assegnamento → funzione matematica

 Che va dall’insieme delle formule atomiche → all’insieme di

valori di verità

 V : L→ 2

 V

Ovvero: prende in entrata formule atomiche

 E dà in uscita un valore di verità

 V → funzione di valutazione

 L → insieme del linguaggio proposizionale

{ }

 2 1,0

→ insieme dei valori di verità

Assegnato il valore di verità alle formule atomiche, il valore di verità

o delle formule composte è fissato automaticamente con le tavole di

verità per i connettivi

 Valori di verità dei connettivi

Valore di verità della NEGAZIONE

o  ( ) ≔1−V (

V ¬ A A)

 ¬ A

L’assegnamento di valore di verità di

 A

Si ottiene togliendo 1 al valore di verità di

Valore di verità della DISGIUNZIONE

o  ( ) ( ) ( )

⋁ ≔max ( )

V A B ⁡ V A , V B

 ⋁

A B

L’assegnamento di valore di verità di

 Si ottiene scegliendo il maggiore dei valori di verità attribuiti

A B

ad e

Valore di verità della CONGIUNZIONE

o ( ) (B)

V A , V

 ( )

⋀ ≔min

V A B ⁡¿

 ⋀

A B

L’assegnamento di valore di verità di

 Si ottiene scegliendo il minore dei valori di verità attribuiti

A B

ad e

Valore di verità della IMPLICAZIONE

o ( ) ( ) ( ))

≔

 (

V A → B max ⁡ 1−V A , V B

 A → B

L’assegnamento di valore di verità di

 Si ottiene scegliendo il massimo tra:

( )

 (1−V )

A , ciò che si ottiene sottraendo 1 dal valore

A

di verità di

 B

E il valore di verità di

Valore di verità della BI-IMPLICAZIONE

o ( )=1

 ( )=V (

V A ↔ B V A B)

se e solo se

 (

A ↔ B

Quindi, è vero se e solo se è uguale a

V A)

(

V B)

 A

Possibili definizioni relative ad una formula in base al valore di verità

TAUTOLOGIA (o verità logica)

o  ( )=1

A V A

Una formula è una tautologia qualora si abbia per

V

ogni possibile

 V

Se quindi è vera secondo ogni

CONTRADDIZIONE (o formula refutabile)

o  ( )=0

A V A

Una formula è refutabile qualora valga per ogni

V

possibile

 V

Se quindi è falsa secondo ogni

FORMULA SODDISFACIBILE

o  ( )=1

A V A

Una formula è soddisfacibile se e solo se per

V

almeno un

 V

Se quindi è vera per almeno 1

 ( V

Tavola di verità che calcoli per tutti i

V A)

Sono rilevanti solamente i valori di sulle lettere proposizionali che

V

o A

compaiono in

Se contiene lettere proposizionali

A n

o  n

Saranno prese in considerazione solo interpretazioni possibili

2

 Costruzione della tavola di verità

 Inserire prima gli enunciati atomici

 Poi i connettivi

 Infine inserire l’enunciato composto

Applicando via via le tavole di verità per ciascun connettivo di ogni sotto-

o formula, si ottiene il valore di verità della formula nel suo complesso

⋁

Esempio: p q → ¬r

o  3

Abbiamo 3 lettere proposizionali → quindi 2 interpretazioni

possibili ⋁ ⋁

p q r p q ¬r p q → ¬r

T T T T F F

F T T T F F

T F T T F F

F F T F F T

T T F T T T

F T F T T T

T F F T T T

F F F F T T

 Ad ogni assegnamento di verità alle lettere proposizionali

 Corrisponde un valore di verità della formula nel suo

complesso

 La formula è soddisfacibile → esiste almeno un assegnamento che

la rende vera

 V

Non è una tautologia perché non è vera per ogni

 Studio della correttezza delle INFERENZE (= schemi di ragionamento)

 La congiunzione ha:

 Come antecedente le premesse dell’inferenza

 Come conseguente, la conclusione dell’inferenza

Vi sono inferenze intuitivamente corrette ma non giustificabili con il

o calcolo proposizionale

 È necessario considerare più a fondo la struttura interna delle

proposizioni

⋀ ⋁

Ai connettivi , , , aggiungiamo due nuovi operatori, i

→ ¬

o quantificatori

 ∀ → quantificatore universale “per ogni”

 ∃ → quantificatore esistenziale “esiste”

 COSTANTI = elementi del dominio del discorso

 PREDICATI = proprietà di questi oggetti, o relazioni che posso intercorrere tra

questi

 In sostanza → i predicati permettono di esprimere proprietà e relazioni su

insiemi di oggetti

Quindi

o  x P

→ la costante gode di una proprietà

P( x)

 ∀ (x) x P

→ per ogni vale la proprietà

xP

 ∃ ) x P

→ esiste un che gode della proprietà

xP( x  U sta per

il predicato “essere uomo”

 M sta per il predicato “essere mortale”

 a

Invece sta per “Socrate”  U

sta per “essere uomo”

 M sta per “essere mortale”

 A sta per “essere animale”

 Linguaggio elementare (o di primo ordine) è composto di:

 ⋀ ⋁ → ¬

Connettivi proposizionali → , , ,

 ∀ ∃

2 quantificatori → , x , x , …

 Le variabili individuali → 0 1

a , a , …

 Le costanti individuali → 0 1

 P ,Q …

Le lettere predicative →

 f , g …

Le lettere funzionali →

DEFINIZIONI del LINGUAGGIO ELEMENTARE ⟨ ⟩

 L P, F,α , β

LINGUAGGIO ELEMENTARE → è una quadrupla :

È quindi costituito da 4 elementi

o è l’insieme dei simboli di predicato

P

o è una funzione che assegna ad ogni la sua arietà

α P

o  α : P→N

è l’insieme dei simboli di funzione

F

o è una funzione che assegna ad ogni la sua arietà

β F

o  β : F→ N

 Cos’è l’arietà?

Nel caso dei predicati ( )

P

o  Se si tratta di predicato nominale

 Il suo simbolo avrà arietà 1

 Perché per ottenere un enunciato è sufficiente 1 sola

specificazione

 Se si tratta di predicato verbale, il suo simbolo potrà avere:

 Arietà 2 → predicati che richiedono 2 specificazioni per

divenire enunciati

 Arietà 3 → predicati che richiedono 3 specificazioni per

divenire enunciati

 Le lettere proposizionali

 Rappresentano di per sé un enunciato

 Hanno quindi arietà 0

 Simboli di predicato secondo l’arietà:

 ARIETÀ 0

 Sono le lettere proposizionali

 Usati per formalizzare frasi composte da verbi

impersonali

 ARIETÀ 1

 Rappresentano proprietà d