Matematica Discreta Lezione del giorno 12 ottobre 2009 Elementi di Logica Matematica Proposizioni e predicati.

(1)

Matematica Discreta

Lezione del giorno 12 ottobre 2009 Elementi di Logica Matematica Proposizioni e predicati.

Si definisce proposizione logica (o brevemente proposizione) una frase di senso compiuto in cui sia contenuta un’affermazione che sia vera o falsa.

Esempio:

P = “7>5”

é un esempio di proposizione vera: P è il nome della proposizione, fra virgolette vi è il testo o enunciato della proposizione. Il nome della proposizione può essere una qualunque successione di caratteri alfabetici e numerici, per esempio P, Prop, P1 etc…..

Q = “Palermo è una città della Lombardia”

é una proposizione falsa.

R = “Ciao”

non è una proposizione (è un saluto ma non contiene un’affermazione).

Il valore di verità o falsità di una proposizione può anche non essere conosciuto:

P=”esiste vita intelligente al di fuori della terra”

é una proposizione (anche se non sappiamo attualmente se sia vera o falsa).

Si definisce predicato logico (o brevemente predicato) una frase di senso compiuto che contiene delle variabili (spesso indicate con lettere come x,y,z….) e che diventa una proposizione (vera o falsa) quando si fanno assumere valori concreti alle variabili.

Esempio:

P(x,y) = “la somma dei numeri interi x,y è >40” è un predicato nelle 2 variabili x,y (P è il nome del predicato, seguito dall’elenco, facoltativo, delle variabili; fra virgolette vi è il testo o enunciato del predicato).

Se facciamo per esempio assumere alle variabili rispettivamente i valori x=19, y=28, otteniamo la proposizione vera

P(9,8) = “la somma dei numeri interi 19,28 è >40”

mentre se facciamo per esempio assumere alle variabili rispettivamente i valori x=4, y=5, otteniamo la proposizione falsa

P(4,5) = “la somma dei numeri interi 4,5 è >40”

Per evitare che la scelta arbitraria dei valori delle variabili porti a frasi senza senso logico, talvolta si restringono i valori possibili che possono assumere le variabili in un predicato, indicando il campo di variabilità o universo (ossia indicando i valori permessi per le variabili).

Esempio:

Scrivendo

P(x) = “x<20” (campo di variabilità=numeri interi positivi)

si intende che nel predicato P gli unici valori leciti che si possono attribuire alla variabile x sono

appunto gli interi positivi.

(2)

Una proposizione si può in pratica considerare un predicato senza variabili: in tal senso tutto ciò che diremo sui predicati si potrà applicare alle proposizioni.

Operazioni logiche fra predicati.

Introdurremo delle operazioni logiche fra i predicati: sono operazioni che, dati alcuni predicati (operandi), operano su di essi per ottenere un nuovo predicato (risultato) i cui valori di verità o falsità dipendono da quelli dei predicati operandi.

1) Congiunzione logica

Dati due predicati P, Q, si chiama congiunzione logica di P, Q il predicato che:

- ha come nome PQ (si legge P and Q oppure P e Q)

- ha come testo i testi di P e Q separati dalla congiunzione “e” (quindi ha come variabili le variabili di P e quelle di Q)

- è vero solo per i valori delle variabili che rendono veri sia P che Q, ed è falso per tutti gli altri valori delle variabili (quindi è falso per i valori delle variabili che rendono falso uno dei 2 predicati P, Q o entrambi)

Esempio:

Dati i 2 predicati P(x,y) = “x>y”

Q(y,z) = “y<z

²

”

(con campo di variabilità= numeri interi positivi) la loro congiunzione logica è il predicato [PQ](x,y,z)=”x>y e y<z

²

”.

Tale nuovo predicato è vero solo per i valori di x,y che rendono vero P e i valori di y,z che rendono vero Q.

Per esempio

[PQ](5,3,2)=”5>3 e 3<2

²

” è una proposizione vera in quanto P(5,3)= “5>3”

Q(3,2) = “3<2

²

”

sono entrambe proposizioni vere.

Invece

[PQ](6,4,1)=”6>4 e 4<1

²

” è una proposizione falsa in quanto P(6,4)= “6>4”

é una proposizione vera, ma Q(4,1) = “4<1

²

”

é una proposizione falsa.

Analogamente [PQ](1,2,4) [PQ](2,4,2)

sono proposizioni false, la prima perché P(1,2) è falsa (pur essendo Q(2,4) vera), e la seconda

perché entrambe P(2,4), Q(4,2) sono false.