MMI (Metodi Matematici per l'Informatica) - Fondamenti - Appunti

NEGAZIONE NOT

= ( )

CONGIUNZIONE AND

= ( )

DISGIUNZIONE OR

= ( )

DISGIUNZIONE ESCLUSIVA XOR

= ( )

TABELLE DI VERITA’

NEGAZIONE

¬ p

p F

T T

F NEGATO

Restituisce il valore di una proposizione ma

CONGIUNZIONE

q p ^ q

p T T

T F F

T T F

F F F

F “E”

Restituisce vero quando ‘p’ ‘q’ sono vere

DISGIUNZIONE

q p v q

p T T

T F T

T T T

F F F

F “OPPURE”

Restituisce vero quando ‘p’ ‘q’ sono vere

DISGIUNZIONE ESCLUSIVA

q p q

p ⊕

T F

T F T

T T T

F F F

F “O” “O”

Restituisce vero quando ‘p’ ‘q’ sono vere

ma non entrambe

IMPLICAZIONE

q p q

p →

T T

T F F

T T T

F F T

F IPOTESI / CONDIZIONE SUFFICIENTE

‘p’ è detta CONCLUSIONE / CONDIZIONE

‘q’ è detta

NECESSARIA

Non presuppone vi sia una relazione tra p e q

PROPOSIZIONI CONDIZIONALI :

Dall’implicazione possiamo dedurre delle

q p INVERSO

è detta

→

¬p ¬q OPPOSTO

è detta

→

¬q ¬p CONTRO­NOMINALE

è detta

→

EQUIVALENZA

q p q

p ↔

T T

T F F

T T F

F F T

F “SE E SOLO SE” le due proposizioni hanno valori di verità

equivalenti

EQUIVALENZE PROPOSIZIONALI

Le Equivalenze Proposizionali sono utilizzate per semplificare proposizioni composte.

Sostituiscono una proposizione con un’altra avente lo stesso valore di verità. Esistono alcune

equivalenze proposizionali ben definite:

TAUTOLOGIA T

= “ Proposizione composta con valore di verità sempre vero. Si indica con ”

¬

( p v p )

Esempio:

CONTRADDIZIONE = “ Proposizione composta con valore di verità sempre falso. Si indica

F

con ” ¬

( p ^ p )

Esempio:

CONTINGENZA = “ Proposizione composta che non può essere definita né TAUTOLOGIA né

CONTRADDIZIONE ”

EQUIVALENZA LOGICA = “ Proposizioni composte / elementari con valore di verità

equivalente ” ( p q )

≡

T F

p = e q = allora

Esempio: PROPRIETA’ DI EQUIVALENZA:

Possiamo definire delle “leggi” o

NOME RAPPRESENTAZIONE LOGICA

¬(p v q) ¬p ^ ¬q

≡

DE MORGAN ¬(p ^ q) ¬p v ¬q

≡

p ^ T p

≡

IDENTITA’ p v F p

≡

p v T p

≡

DOMINAZIONE p ^ F p

≡

p v p p

≡

IDEMPOTENZA p ^ p p

≡

¬(¬(p)) p

DOPPIA NEGAZIONE ≡

p v q q v p

≡

COMMUTATIVA p ^ q q ^ p

≡

(p v q) v r p v (q v r)

≡

ASSOCIATIVA (p ^ q) ^ r p ^ (q ^ r)

≡

p v (q ^ r) (p v q) ^ (p v r)

≡

DISTRIBUTIVA p ^ (q v r) (p ^ q) v (p ^ r)

≡

p v ¬p T

≡

p ^ ¬p F

≡

p q T

ALTRE ≡

⊕

p q ¬(p v q)

≡

→

p q (p q)^(q p)

≡

↔ → →

PREDICATI E QUANTIFICATORI

LOGICA PROPOSIZIONALE = “ Proposizioni elementari e le loro combinazioni logiche ”

Nella logica proposizionale ogni proposizione deve essere ripetuta esaustivamente, con oggetti

diversi.

VARIABILE PROPOSIZIONALE = “ Oggetto generalizzato appartenente ad un insieme.

Evitano l’utilizzo di numerosi oggetti”

ASSERZIONI = “ Proposizione nella logica proposizionale con valori definiti. Possono definire

una per un gruppo di oggetti”

proprietà Esempio:

“ è amico di non è un’asserzione

X Y”

“ è amico di è un’asserzione

Andrea Anna”

QUANTIFICATORI UNIVERSALI

Queste proprietà vengono espresse con l’utilizzo dei (tutti gli

ED ESISTENZIALI

oggetti) (almeno un oggetto).

LOGICA PREDICATIVA = “ Modella gli oggetti e le loro proprietà, dette anche PREDICATI.

Utilizza variabili e quantificatori”

COSTANTE = “ Modella uno specifico oggetto, ad esempio ANDREA oppure ANNA”

VARIABILE PREDICATIVA = “ Rappresenta un oggetto di tipo specificato”

PREDICATO = “ Rappresenta le proprietà o la relazione tra gli oggetti”

Esempio:

P

(x,y): “ X è amico di Y”