Matematica Discreta I Lezione del giorno 29 settembre 2007 Elementi di Logica Elementare Proposizioni e predicati.

Matematica Discreta I

Lezione del giorno 29 settembre 2007 Elementi di Logica Elementare Proposizioni e predicati.

Si definisce proposizione logica una qualunque frase di senso compiuto che sia vera o falsa.

Esempio:

P = “7>5”

é una proposizione vera (P è il nome della proposizione, fra virgolette vi è il testo o enunciato della proposizione”).

Q = “Palermo è una città della Lombardia”

é una proposizione falsa.

R = “Ciao”

non è una proposizione.

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 una qualunque 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”

Talvolta si restringono i valori possibili delle 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 possibili che si possono attribuire alla variabile x sono appunto gli interi positivi.

Una proposizione si può considerare un predicato senza variabili: in tal senso tutto ciò che diremo

sui predicati si potrà applicare alle proposizioni.

Operazioni logiche.

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.

Se conveniamo che il simbolo 1 indica “vero”e il simbolo 0 indica “falso”, i possibili valori di verità della congiunzione PQ, in funzione di quelli di P e Q, sono i seguenti:

11=1 10=0 01=0 00=0

e si possono schematizzare in una tavola della verità come la seguente:

P Q PQ

1 1 1

1 0 0

0 1 0

0 0 0

oppure come la seguente (in cui alle righe si fanno corrispondere i valori di P, alle colonne quelli di Q, e nelle caselle all’incrocio quelli di PQ):

1 0 1

0

Analoghe tavole di verità si possono ottenere convenendo che V indichi “vero”, F indichi “falso”.

1 0

0 0