Lezione05.10.07_000 - Matematica E Informatica

Transcript

Matematica Discreta I Lezione del giorno 5 ottobre 2007 Se 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 1 0 0 0 0 2) Disgiunzione logica Dati due predicati P, Q, si chiama disgiunzione logica di P, Q il predicato che: - ha come nome PvQ (si legge P or Q) - ha come testo i testi di P e Q separati dalla congiunzione “o” (quindi ha come variabili le variabili di P e quelle di Q) - è falso solo per i valori delle variabili che rendono falsi sia P che Q, ed è vero per tutti gli altri valori delle variabili (quindi è vero per i valori delle variabili che rendono vero uno dei 2 predicati P, Q o entrambi) Esempio: Dati i 2 predicati P(x) = “x è un numero intero >10” Q(y) = “y è un numero razionale compreso fra 1 e 2” la loro congiunzione logica è il predicato [PQ](x,y)=”x è un numero intero >10 o y è un numero razionale compreso fra 1 e 2”. Tale nuovo predicato è falso solo per i valori di x che rendono falso P e i valori di y che rendono falso Q. Per esempio [PQ](14,3/2)=”14 è un numero intero >10 o 3/2 è un numero razionale compreso fra 1 e 2” è una proposizione vera in quanto P(14)= “14 è un numero intero >10” è una proposizione vera, pur essendo Q(5/2) = “5/2 è un numero razionale compreso fra 1 e 2” una proposizione falsa. Invece [PQ](9,5/2)=”9 è un numero intero >10 o 5/2 è un numero razionale compreso fra 1 e 2” è una proposizione falsa in quanto entrambe le proposizioni P(9), Q(5/2) sono false. La tavola di verità della disgiunzione logica PvQ è la seguente: P Q PvQ 1 1 1 1 0 1 0 1 1 0 0 0 oppure la seguente: 1 0 1 1 1 0 1 0 3) Negazione logica Dati un predicato P si chiama negazione logica di P, Q il predicato che: - ha come nome P (si legge not P) - ha un testo che è opposto di quello di P da un punto di vista logico (quindi ha le stesse variabili di P) - è vero per tutti i valori delle variabili per cui è falso P, ed è falso per tutti i valori delle variabili per cui è vero P Per esempio dato il predicato: P(x) = “x>6” (con campo di variabilità x=numero intero positivo) la sua negazione logica può essere P (x)=”non è vero che x>6” oppure, più elegantemente: P (x)=”x≤6”. La tavola di verità della negazione logica P è la seguente: P P 1 0 0 1 Implicazione logica Dati due predicati P, Q, nelle stesse variabili, diremo che P implica Q (oppure: da P segue Q, o ancora: se P allora Q) quando tutti i valori delle variabili che rendono vero P rendono vero anche Q. In questo caso scriveremo il simbolo PQ Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo): P(x) = “3