… logica matematica

Progetto Eracle 2

Prof. Marialetizia Pedrinazzi

Prof. Daniela Strangis

Logica matematicaLogica matematica

Branca della matematica che si occupa Branca della matematica che si occupa del valore di verità delle proposizioni.del valore di verità delle proposizioni.

Una proposizione è un’affermazione a Una proposizione è un’affermazione a cui si può attribuire un valore di verità. cui si può attribuire un valore di verità.

Esempio: 2+3=4 è una proposizione Esempio: 2+3=4 è una proposizione falsa.falsa.

esercizi

Tanti matematici si sono occupatiTanti matematici si sono occupati

di tale problema, es. Aristoteledi tale problema, es. Aristotele

con i suoi sillogismi ha con i suoi sillogismi ha

organizzato e analizzato organizzato e analizzato

le forme del corretto le forme del corretto

ragionamento, il ragionamento ragionamento, il ragionamento

logico.logico.

Cosa succede se proviamo a Cosa succede se proviamo a combinare delle proposizioni fra loro? combinare delle proposizioni fra loro? Cosa succede al loro valore di verità?Cosa succede al loro valore di verità?

Le regole del calcolo fra proposizioniLe regole del calcolo fra proposizioni

costituiscono “l’algebra di Boole”,costituiscono “l’algebra di Boole”,

matematico inglese dell’800. matematico inglese dell’800.

Le operazioni fondamentali sono:Le operazioni fondamentali sono:

Somma logica +Somma logica +

Prodotto logico *Prodotto logico *

Negazione logicaNegazione logica

Disgiunzione esclusivaDisgiunzione esclusiva

L’algebra di Boole, segue le L’algebra di Boole, segue le regole della logica binaria, regole della logica binaria, cioè il risultato di una cioè il risultato di una qualsiasi operazione può qualsiasi operazione può assumere solo due valori:assumere solo due valori:

Valore vero Valore vero

Valore falsoValore falso

1

0

Proprietà Proprietà Essa si basa su alcuni assiomi da cui si ricavano Essa si basa su alcuni assiomi da cui si ricavano le seguenti proprietà:le seguenti proprietà:

Commutativa: a+b=b+aCommutativa: a+b=b+a

Associativa: (a+b)+c=a+(b+c)Associativa: (a+b)+c=a+(b+c)

Idempotenza a+a=aIdempotenza a+a=a

Assorbimento a+(a*b)=aAssorbimento a+(a*b)=a

Distributiva Distributiva

a*(b+c)=a*b+b*ca*(b+c)=a*b+b*c

Elemento neutro a+0=aElemento neutro a+0=a

Complemento a*(!a)=0Complemento a*(!a)=0

Leggi di De MorganLeggi di De Morgan

Leggi di De MorganLeggi di De Morgan

1.1. (a+b) = a*b(a+b) = a*b

2.2. (a*b) = a+b(a*b) = a+b

Costituisce il fondamento teorico Costituisce il fondamento teorico e pratico dei moderni e pratico dei moderni elaboratori.elaboratori.

Infatti, all’interno di questi il Infatti, all’interno di questi il valore 1 corrisponde ad un valore 1 corrisponde ad un valore di tensione altovalore di tensione alto

Il valore 0 corrisponde ad un Il valore 0 corrisponde ad un valore di tensione basso.valore di tensione basso.

Tale algebra trova un parallelo fra:Tale algebra trova un parallelo fra:

insiemistica, algebra delle insiemistica, algebra delle proposizioni, informatica.proposizioni, informatica.

Le operazioni fondamentali sono:Le operazioni fondamentali sono: Negazione logicaNegazione logica Prodotto logico *Prodotto logico * Somma logica + Somma logica + Disgiunzione esclusivaDisgiunzione esclusiva

Negazione: tabella di Negazione: tabella di veritàverità

AA Non ANon A

vv ff

ff vvAA Not ANot A

00 11

11 00

Negazione: not, nonNegazione: not, non

Insieme A

Insieme A

Negazione: esempiNegazione: esempi

A: 3 è un numero primoA: 3 è un numero primoNon A: non è vero che 3 è un numero primo Non A: non è vero che 3 è un numero primo

oppureoppure

Non A: 3 non è un numero primoNon A: 3 non è un numero primo

A: tutti gli italiani parlano l’italianoA: tutti gli italiani parlano l’italianoNon A: non tutti gli italiani parlano l’italiano Non A: non tutti gli italiani parlano l’italiano

oppure oppure

Non A: esiste almeno un italiano che non parla Non A: esiste almeno un italiano che non parla l’italianol’italiano

Es. 1Es. 1

Es. 2Es. 2

esercizi

Prodotto logico: Prodotto logico: *, *, and, et, and, et, ٨٨

Corrisponde all’intersezione fra due insiemi.Corrisponde all’intersezione fra due insiemi.

I insieme II insieme

Insieme intersezione

Prodotto logicoProdotto logico: tabella di : tabella di veritàverità

Prop. AProp. A Prop. BProp. B A and BA and B

00 00 00

00 11 00

11 00 00

11 11 11

La proposizione risultante è vera se e solo se entrambi sono vere.

Prodotto logicoProdotto logico: esempi: esempi

Esempio 1Esempio 1

A: 2 è un numero pari veraA: 2 è un numero pari vera

B: 6 è un numero dispari falsaB: 6 è un numero dispari falsa

A A ٨٨ B: 2 è un numero pari B: 2 è un numero pari andand 6 è 6 è un numero dispari un numero dispari falsafalsa

esercizi Adesso a voi altri Adesso a voi altri ……

Somma logica: Somma logica: +, U, or, +, U, or, o, velo, vel

Corrisponde a: unione di due Corrisponde a: unione di due insiemi:insiemi:

I insieme

II insieme

+ Insieme unione

I insieme

II insieme

Somma logicaSomma logica: tabella di : tabella di veritàveritàLa proposizione risultante è vera se almeno La proposizione risultante è vera se almeno una delle due è vera.una delle due è vera.

Prop. AProp. A Prop. BProp. B A or BA or B

00 00 00

00 11 11

11 00 11

11 11 11

Somma logica: esempiSomma logica: esempi

A: 2 è un numero pari A: 2 è un numero pari vera vera

B: 6 è un numero dispari falsaB: 6 è un numero dispari falsa

A V B: 2 è un numero pari A V B: 2 è un numero pari oo 6 è un num. dispari 6 è un num. dispari veravera

A: 3 è un numero pari falsaA: 3 è un numero pari falsaB: Roma è la capitale della Francia falsaB: Roma è la capitale della Francia falsa

A V B: 3 è un numero pari A V B: 3 è un numero pari oo Roma è la capitale Roma è la capitale della Francia falsadella Francia falsa

Es. 1Es. 1

Es. 2Es. 2

esercizi

Disgiunzione Disgiunzione esclusiva: esclusiva: xor, aut, o… o…xor, aut, o… o…

Disgiunzione esclusiva

I insieme

II insieme

Disgiunzione esclusivaDisgiunzione esclusiva

Prop. AProp. A Prop. BProp. B A xor BA xor B

00 00 00

00 11 11

11 00 11

11 11 00

La proposizione risultante è vera se e solo se una soltanto delle due proposizioni è vera

Disgiunzione esclusivaDisgiunzione esclusiva: : esempiesempi

““qui bisogna o vincere o morire!”qui bisogna o vincere o morire!”La proposizione: “2 o è pari o è dispari” è La proposizione: “2 o è pari o è dispari” è vera. Infatti, “2 è pari” è vera mentre “2 è vera. Infatti, “2 è pari” è vera mentre “2 è dispari” è falsa!dispari” è falsa!

La proposizione: “5 o è multiplo di 2 o è La proposizione: “5 o è multiplo di 2 o è multiplo di 3” è falsa. Infatti, “5 è multiplo di multiplo di 3” è falsa. Infatti, “5 è multiplo di 2” è falsa e “5 è multiplo di 3” è falsa. Poiché 2” è falsa e “5 è multiplo di 3” è falsa. Poiché entrambi sono false la risultante è falsa!entrambi sono false la risultante è falsa!

esercizi

RiepilogoRiepilogo delle operazioni delle operazioni

OPERATORI OPERATORI LOGICI LOGICI

FONDAMENTAFONDAMENTALILI

SIMBOLISMOSIMBOLISMO

Latino Latino Di HilbertDi Hilbert informaticoinformatico

Negazione Negazione logicalogica P = non PP = non P P = P P = P P = not PP = not P

Prodotto Prodotto logicologico P = P1 et P2P = P1 et P2 P= P1 P= P1 ٨٨ P2P2 P = P1 and P2P = P1 and P2

Somma logicaSomma logica P = P1 vel P2P = P1 vel P2 P = P1 V P2P = P1 V P2 P = P1 or P2P = P1 or P2

Disgiunzione Disgiunzione esclusivaesclusiva P = P1 aut P2P = P1 aut P2 P=P1 V P2P=P1 V P2 P = P1 xor P2P = P1 xor P2

Fine … adesso al Fine … adesso al lavoro!lavoro!

esercizi riassuntivi

Proposizioni: eserciziProposizioni: eserciziEsercizio 1) Stabilire quali delle seguenti frasi sono Esercizio 1) Stabilire quali delle seguenti frasi sono

proposizioni:proposizioni:a)a) Un quadrato ha 4 lati;Un quadrato ha 4 lati;b)b) Oggi il tempo è bello;Oggi il tempo è bello;c)c) Sono circa le due di pomeriggio;Sono circa le due di pomeriggio;d)d) 6 è un numero pari;6 è un numero pari;e)e) Che bella città!Che bella città!f)f) Nessuno è immortale.Nessuno è immortale.Esercizio 2) attribuire un valore di verità alle seguenti Esercizio 2) attribuire un valore di verità alle seguenti

proposizioni escludendo quelle che non lo sono:proposizioni escludendo quelle che non lo sono:a)a) Un rettangolo ha le diagonali isometriche;Un rettangolo ha le diagonali isometriche;b)b) 7 è divisore di 360;7 è divisore di 360;c)c) Il m.c.m. di 12 e 24 è 12;Il m.c.m. di 12 e 24 è 12;d)d) L’ Italia è bella;L’ Italia è bella;e)e) Il M.C.D. di 2 e 24 è 24;Il M.C.D. di 2 e 24 è 24;f)f) Oggi è una bella giornata;Oggi è una bella giornata;g)g) Mio figlio è bello;Mio figlio è bello;

Proposizioni: eserciziProposizioni: esercizi

Esercizio 3: costruire le Esercizio 3: costruire le possibili combinazioni di possibili combinazioni di verità di due proposizioni verità di due proposizioni completando la tabella a completando la tabella a fiancofianco

AA BB

F 0F 0 … … 00

F …F … V 1V 1

……. ….. …. F 0F 0

V …V … V ….V ….

Esercizio 4: costruire le possibili combinazioni di Esercizio 4: costruire le possibili combinazioni di verità di tre proposizioni costruendo una tabella verità di tre proposizioni costruendo una tabella analogamente all’esercizio precedenteanalogamente all’esercizio precedente

Negazione: eserciziNegazione: eserciziEsercizio 1) scrivere la negazione delle seguenti proposizioniEsercizio 1) scrivere la negazione delle seguenti proposizionia)a) 10 è multiplo di 510 è multiplo di 5b)b) Non uso la biciclettaNon uso la biciclettac)c) Non ho avuto nessun regaloNon ho avuto nessun regalod)d) Faccio i compiti per non essere bocciatoFaccio i compiti per non essere bocciatoe)e) Le api non si posano su fiori che non profumanoLe api non si posano su fiori che non profumano

Esercizio 2) date le seguenti proposizioni, scrivere le coppie formate da una Esercizio 2) date le seguenti proposizioni, scrivere le coppie formate da una proposizione e dalla sua negazioneproposizione e dalla sua negazione

a)a) Vedo neroVedo nerob)b) Non vado al mareNon vado al marec)c) Non devi passare col semaforo rossoNon devi passare col semaforo rossod)d) Devi fermarti col semaforo gialloDevi fermarti col semaforo gialloe)e) Vedo biancoVedo biancof)f) Non è vero che non vado al mareNon è vero che non vado al mareg)g) Devi passare col semaforo verdeDevi passare col semaforo verdeh)h) Non vedo neroNon vedo neroi)i) Vado in montagnaVado in montagnaj)j) Devi passare col semaforo rossoDevi passare col semaforo rossok)k) Vado in vacanzaVado in vacanzal)l) Non devo passare a nessun semaforoNon devo passare a nessun semaforo

Negazione: eserciziNegazione: esercizi

Esercizio 3: assegnate le seguenti proposizioni:Esercizio 3: assegnate le seguenti proposizioni:

A: 3 è soluzione di x+3=0A: 3 è soluzione di x+3=0

B: il M.C.D. di 6 e 8 è 24B: il M.C.D. di 6 e 8 è 24

C: il M.C.D. di 6 e 8 è 2C: il M.C.D. di 6 e 8 è 2

D: la Luna è un satellite di SaturnoD: la Luna è un satellite di Saturno

E: la balena è un mammiferoE: la balena è un mammifero

a)a) Determinare il valore di verità di ciascuna di Determinare il valore di verità di ciascuna di esse;esse;

b)b) Scrivete le nuove proposizioni non A, non B, Scrivete le nuove proposizioni non A, non B, ecc., determinando anche i relativi valori di ecc., determinando anche i relativi valori di verità.verità.

Esercizio 4: costruire la tabella di verità della Esercizio 4: costruire la tabella di verità della doppia negazione di una proposizionedoppia negazione di una proposizione

Esercizi sul prodotto logicoEsercizi sul prodotto logicoEsercizio 1) Scomporre le proposizioni composte date in proposizioni semplici:Esercizio 1) Scomporre le proposizioni composte date in proposizioni semplici:

Esempio: Spillo è il mio cane ed ha otto anni;Esempio: Spillo è il mio cane ed ha otto anni;Proposizione A: Spillo è il mio cane Proposizione A: Spillo è il mio cane Proposizione B: Spillo ha otto anniProposizione B: Spillo ha otto anni

a)a) Mara canta e non balla;Mara canta e non balla;b)b) Marco suona e canta;Marco suona e canta;c)c) D’estate lavoro e mi compro il motorinoD’estate lavoro e mi compro il motorinod)d) 4 è pari ed è multiplo di 2 4 è pari ed è multiplo di 2 Esercizio 2) Date le proposizioni seguenti Esercizio 2) Date le proposizioni seguenti A: 5 è numero primo; B: 6 è multiplo di 4; C: 4 è numero dispariA: 5 è numero primo; B: 6 è multiplo di 4; C: 4 è numero dispariattribuire il loro valore di verità quindi stabilire il valore di verità delle proposizioni attribuire il loro valore di verità quindi stabilire il valore di verità delle proposizioni

composte: composte: A A ٨٨ B; non A B; non A ٨٨ non B; A non B; A ٨٨ non Cnon C

Esercizio 3) Date le proposizioni seguenti:Esercizio 3) Date le proposizioni seguenti:A: 20 è minore di 10;A: 20 è minore di 10;B: 20 è maggiore di 10;B: 20 è maggiore di 10;C: 30 è multiplo di 5;C: 30 è multiplo di 5;D: 20 è multiplo di 4;D: 20 è multiplo di 4;E: 20 è un quadrato perfettoE: 20 è un quadrato perfettoScrivere in parole le seguenti proposizioni composte e assegna ad ognuna il valore di Scrivere in parole le seguenti proposizioni composte e assegna ad ognuna il valore di

verità: A verità: A ٨٨ B; non E B; non E ٨٨ non B; A non B; A ٨٨ non C; A non C; A ٨٨ non E; D non E; D ٨٨ non B; non D non B; non D ٨٨ non Enon EEsercizio 4) Date le proposizioni seguenti:Esercizio 4) Date le proposizioni seguenti:A: l’uomo è un mortale;A: l’uomo è un mortale;B: l’uomo è un mammifero;B: l’uomo è un mammifero;C: l’uomo ha due occhi;C: l’uomo ha due occhi;Scrivere in parole le seguenti proposizioni composte e assegna ad ognuna il valore di Scrivere in parole le seguenti proposizioni composte e assegna ad ognuna il valore di

verità: A verità: A ٨٨ B; non A B; non A ٨٨ non B; A non B; A ٨٨ non C; B non C; B ٨٨ non C; non C non C; non C ٨٨ non B; C non B; C ٨٨ non A; non(A non A; non(A ٨٨ B)B)

Esercizi sulla somma logicaEsercizi sulla somma logicaEsercizio 1: date le seguenti proposizioniEsercizio 1: date le seguenti proposizionia)a) 27 è il cubo di 327 è il cubo di 3b)b) -2 è soluzione dell’equazione 2x=0-2 è soluzione dell’equazione 2x=0c)c) In un triangolo la somma di due lati deve essere maggiore del In un triangolo la somma di due lati deve essere maggiore del

terzoterzod)d) Il triplo di 2 sommato con 5 è uguale a 10Il triplo di 2 sommato con 5 è uguale a 101.1. Assegnare i valori di verità alle proposizioniAssegnare i valori di verità alle proposizioni2.2. Scrivere le proposizioni composte:Scrivere le proposizioni composte:

A=a vel b, B=a vel c, C=a vel d, A=a vel b, B=a vel c, C=a vel d, D=b vel c, E=b vel d, F=c vel d D=b vel c, E=b vel d, F=c vel d

e determinare il valore di verità di ognuna di esse.e determinare il valore di verità di ognuna di esse.Esercizio 2: date le seguenti proposizioni: A=oggi fa caldo, B=oggi Esercizio 2: date le seguenti proposizioni: A=oggi fa caldo, B=oggi

vado al mare, traduci in simboli le seguenti proposizioni vado al mare, traduci in simboli le seguenti proposizioni composte.composte.

a)a) Oggi fa caldo e vado al mare A and BOggi fa caldo e vado al mare A and Bb)b) Oggi non fa caldo e vado al mareOggi non fa caldo e vado al mare …………… ……………c)c) Oggi non fa caldo e non vado al mareOggi non fa caldo e non vado al mare …………… ……………d)d) Oggi fa caldo o vado al mareOggi fa caldo o vado al mare …………… ……………e)e) Oggi non fa caldo o vado al mareOggi non fa caldo o vado al mare …………… ……………f)f) Oggi non fa caldo o non vado al mareOggi non fa caldo o non vado al mare …………… ……………

Esercizi sulla somma logicaEsercizi sulla somma logica

Esercizio 3: Esercizio 3: costruire la costruire la tabella di verità delle tabella di verità delle proposizioni indicate proposizioni indicate seguendo l’esempio seguendo l’esempio rappresentato in tabella: A rappresentato in tabella: A vel (nonB).vel (nonB).

AA BBNon Non

BBA vel A vel non Bnon B

00 00 11 11

00 11 00

11 00

11 11

1)1)Non A vel B, non A vel (nonB), A vel non (non Non A vel B, non A vel (nonB), A vel non (non B);B);

2)2) (A V nonA) V non B, A V(non A V B); A V( B (A V nonA) V non B, A V(non A V B); A V( B ٨٨ nonB); nonB);

(A (A ٨٨ B) V nonB B) V nonB

3)3)

;BVΛBA;BAV;AVB;B(AVB)Λ

Esercizi sulla disgiunzione esclusivaEsercizi sulla disgiunzione esclusiva

Esercizio 1: Esercizio 1: date le proposizioni sotto assegnare loro un valore di verità date le proposizioni sotto assegnare loro un valore di verità

P1=7 è pari; P2=7 è dispari; P3=5 è radice di 25; P1=7 è pari; P2=7 è dispari; P3=5 è radice di 25;

P4=5 è radice di 24P4=5 è radice di 24

quindi costruire le seguenti proposizioni composte: quindi costruire le seguenti proposizioni composte:

P1 XOR P2; P1 XOR P2; P1 XOR P3; P1 XOR P3; P1 XOR P4; P1 XOR P4;

P2 XOR P3; P2 XOR P3; P2 XOR P4; P2 XOR P4; P3 XOR P4.P3 XOR P4.

Esercizio 2: Esercizio 2: date le proposizioni: date le proposizioni:

P1=lavoro; P2=non guadagno; P3=mi diverto;P1=lavoro; P2=non guadagno; P3=mi diverto;

scrivi a parole le proposizioni compostescrivi a parole le proposizioni composte

P1 aut P2; P1 aut P2; P1 aut P3; P1 aut P3; P2 autP3; P2 autP3;

non P2 aut non P3non P2 aut non P3

Esercizio 3: Esercizio 3: date le proposizioni: date le proposizioni:

A=3 è pari; B=3 è dispari; C=3 non è numero primo;A=3 è pari; B=3 è dispari; C=3 non è numero primo;

Assegna un valore di verità alle seguenti proposizioni composteAssegna un valore di verità alle seguenti proposizioni composte

);(;;;; CBABACBCABA

Esercizi conclusiviEsercizi conclusivi

Esercizio 1) completare la seguente tabella come Esercizio 1) completare la seguente tabella come nell’esempio sviluppato nella prima riganell’esempio sviluppato nella prima riga

pp qq p and qp and q p or qp or q

2 è un numero 2 è un numero disparidispari

FF

5 è un numero 5 è un numero disparidispari

VV

2 e 5 sono numeri 2 e 5 sono numeri disparidispari

FF

2 o 5 sono 2 o 5 sono numeri disparinumeri dispari

VV

Milano si trova Milano si trova in Lombardiain Lombardia

vv

Milano si trova Milano si trova in Italiain Italia

vv

8+2=108+2=10

………………10 è dispari10 è dispari

…………

5 è un numero 5 è un numero primoprimo

…………....

6 è un multiplo 6 è un multiplo di 3di 3

…………..