Cenni di logica e calcolo proposizionaleCenni di logica e calcolo proposizionale Corso di Laurea in...

Transcript of Cenni di logica e calcolo proposizionaleCenni di logica e calcolo proposizionale Corso di Laurea in...

Cenni di logica e calcolo proposizionale

Corso di Laurea in InformaticaUniversità degli Studi di Bari (sede Brindisi)

Analisi Matematica

S.Milella ([email protected]) Cenni di logica 1 / 10
Proposizioni

proposizione semplice := frase elementare di senso compiuto che può essere vera (V) ofalsa (F)

4 è un numero pari (V)

Milano è la capitale d’Italia (F)

La Milella è simpaticissima (?) Non è una proposizione semplice!

Le proposizioni semplici si possono combinare tra loro tramite i connettivi logici

¬ negazione∧ congiunzione∨ disgiunzione⇒ implicazione⇔ equivalenza

Le proposizioni composte sono il risultato di tali operazioni.

Proposizioni








Proposizioni








Proposizioni








Proposizioni








Proposizioni








Proposizioni composte

Esempi

A: Brindisi è in Puglia

¬A: Brindisi non è in PugliaA: torno a casa, B: leggo un libro

A ∧ B: torno a casa e leggo un libroA ⇒ B: se torno a casa allora leggo un libroA: 2 è un numero dispari, B: Roma è la capitale dell’Irlanda

A ⇔ B: 2 è un numero dispari se e solo se Roma è la capitale dell’Irlanda

Non tutte le frasi ottenute hanno senso nel linguaggio comune, ma sono tutteproposizioni logiche composte e, come tali, possono essere vere o false.

Proposizioni composte - Tavole di verità

Date due proposizioni semplici A e B, i valori di verità delle proposizioni composte siriassumono nelle seguenti tavole:

tavola di verità di ¬A (si legge non A)A ¬AV FF V

tavola di verità di A ∧ B (si legge A e B)A B A ∧ BV V VV F FF V FF F F

tavola di verità di A ∨ B (si legge A o B) ∨ non è esclusivoA B A ∨ BV V VV F VF V VF F F


tavola di verità di A ⇒ B (si legge A implica B oppure se A allora B)

A B A ⇒ BV V VV F FF V VF F V

Si dice anche che A è una condizione sufficiente per B e B è una condizionenecessaria per A.

tavola di verità di A ⇔ B (si legge A equivale a B oppure A se solo se B)

A B A ⇔ BV V VV F FF V FF F V


tavola di verità di A ⇒ B (si legge A implica B oppure se A allora B)

A B A ⇒ BV V VV F FF V VF F V

Si dice anche che A è una condizione sufficiente per B e B è una condizionenecessaria per A.

tavola di verità di A ⇔ B (si legge A equivale a B oppure A se solo se B)

A B A ⇔ BV V VV F FF V FF F V


contraddizione := proposizione composta sempre falsa

tautologia := proposizione composta sempre vera

Esempi

A ∧ (¬A) è una contraddizione, infatti

A ¬A A ∧ (¬A)V F FF V F

A ⇒ (A ∨ B) è una tautologia, infatti

A B A ∨ B A ⇒ (A ∨ B)V V V VV F V VF V V VF F F V




Esempi








Esempi






Osservazioni

¬(¬A) equivale ad A¬(A ∧ B) equivale a (¬A) ∨ (¬B)¬(A ∨ B) equivale a (¬A) ∧ (¬B)A ⇒ B equivale a (¬B) ⇒ (¬A)¬(A ⇒ B) equivale a A ∧ (¬B)i connettivi ∨ ed ∧ sono commutativi ed associativi

(da dimostrare con le tavole di verità)

Predicati e quantificatori

predicato:= frase contenente una o più variabili

Esempi

A(x): x è un numero razionale

A(x , y): x è maggiore di y

La verità o falsità di un predicato dipende dai valori attribuiti alle variabili:

A(√

2) è una proposizione falsa

A(3, 1) è una proposizione vera.

I predicati si trasformano in proposizioni semplici utilizzando i quantificatori:

∀ quantificatore universale (si legge per ogni)

∃ quantificatore esistenziale (si legge esiste)

Si fa uso anche del simbolo ∃| (si legge esiste un solo)



Esempi




A(√









Esempi




A(√








Esempi

Dato il predicato A(x): x ∈ R, x è pari

∀x A(x) (significa: per ogni x , x è un numero reale ed è pari) è una proposizionefalsa

∃x A(x) (significa: esiste almeno un numero reale pari) è una proposizione vera∃|x A(x) (significa: esiste un solo numero reale pari) è una proposizione falsa

Dato il predicato A(x , y): x + y = 2

∀x ∃y A(x , y) è una proposizione vera∃y ∀x A(x , y) è una proposizione falsa

Attenzione all’ordine dei quantificatori!


Esempi

Dato il predicato A(x): x ∈ R, x è pari

∀x A(x) (significa: per ogni x , x è un numero reale ed è pari) è una proposizionefalsa

∃x A(x) (significa: esiste almeno un numero reale pari) è una proposizione vera∃|x A(x) (significa: esiste un solo numero reale pari) è una proposizione falsa

Dato il predicato A(x , y): x + y = 2

∀x ∃y A(x , y) è una proposizione vera∃y ∀x A(x , y) è una proposizione falsa

Attenzione all’ordine dei quantificatori!


Osservazioni

Dato un predicato A(x)

la negazione della proposizione ∀x A(x) è ∃x ¬A(x)la negazione della proposizione ∃x A(x) è ∀x ¬A(x)la negazione della proposizione ∀x ∃y A(x , y) è ∃x ∀y ¬A(x , y)la negazione della proposizione ∃x ∀y A(x , y) è ∀x ∃y ¬A(x , y)

Cenni di logica e calcolo proposizionaleCenni di logica e calcolo proposizionale Corso di Laurea in...

Documents

Transcript of Cenni di logica e calcolo proposizionaleCenni di logica e calcolo proposizionale Corso di Laurea in...