metodi matematici per l’informatica · metodi matematici per l’informatica tutorato – lezione...
TRANSCRIPT
Corso per matricole congrue a 1 Docente: Margherita Napoli
Tutor: Amedeo Leo
METODI MATEMATICI PER L’INFORMATICA Tutorato – Lezione 2 – 17/03/2016
Applicazioni della logica proposizionale La logica ha una serie di applicazioni importanti, come la matematica e l'informatica. Le proposizioni
espresse nel linguaggio naturale sono spesso ambigue. Per questo, è necessario tradurle nel linguaggio
della logica.
Esempio: Puoi accedere a Internet dal campus solo se hai un account o non sei un ospite.
Come si traduce:
p: puoi accedere a Internet dal campus
solo se: ->
hai un account: q
sei un ospite: r
Quindi: (q V -r) -> p
Esempio: Se (hai più di 12 anni o sei accompagnato dai tuoi genitori) allora (puoi salire su quella giostra)
Proposizioni elementari:
p = hai più di 12 anni
q = sei accompagnato dai tuoi genitori
r = puoi salire su quella giostra
Traduzione: p ∨ q → r
Esempio: Non puoi andare sulle montagne russe se sei alto meno di 150cm o se hai meno di 16 anni.
Proposizioni elementari:
q: puoi andare sulle montagne russe
r: sei alto meno di 150cm
s: hai più di 16 anni
Traduzione: (r ∧ ¬s) -> ¬q
Regola generale:
Individua nella frase le parole chiave che corrispondono ai connettivi logici ed usa essi per identificare le
proposizioni elementari
Esempio: Puoi avere caffè gratis se sei maggiorenne ed è martedì
passo 1: individua connettivi logici (se, ed)
passo 2: identifica le proposizioni elementari (p caffè, q maggiorenne, r martedì)
passo 3: riscrivi la frase come una proposizione logica q ∧ r -> p
Esempio:
Si assuma di avere le seguenti proposizioni elementari:
p = Tu guidi a più di 130 km/h
q = Prendi la multa
Traduci ciascuna delle seguenti frasi:
Tu non guidi a più di 130 km/h (¬p)
Tu guidi a più di 130 km/h, ma non prendi la multa (p ∧ ¬q)
Se non guidi a più di 130 km/h allora non prendi la multa (¬p → ¬q)
Guidare a più di 130 km/h è sufficiente per prendere una multa (p → q)
Prendi la multa, ma non guidi a più di 130 km/h (q ∧ ¬p)
Rappresentazione di T e F in un computer I computer rappresentano le informazioni (dati e programmi) attraverso 1 e 0. La logica utilizza vero e falso,
cioè T e F. Un bit è sufficiente a rappresentare 1 (vero = T) e 0 (falso = F). Una variabile booleana può
corrispondere ad una proposizione. T ed F sono sostituite con 1 e 0.
Ricerche su Web I connettivi logici sono anche utilizzati nella ricerca di informazioni in rete. Poiché tali ricerche usano
tecniche della logica proposizionale, sono chiamate ricerche booleane. In tale ricerche, il connettivo AND è
usato per abbinare i record che contengono entrambi i termini di ricerca, il connettivo OR è usato per
abbinare uno o entrambi i termini, e il connettivo NOT viene utilizzato per escludere un particolare termine
di ricerca.
Esercizio 2 pagina 22 Puoi vedere il film sole se sei maggiorenne o hai il permesso di un genitore.
Puoi vedere il film : p
Sei maggiorenne : q
Hai il permesso di un genitore : r
Espressione: p -> (q V r)
Esercizio 8 pagina 22 p: L’utente inserisce una password valida
q: Accesso consentito
r: L’utente è registrato al sistema
a) L’utente è registrato al sistema, ma non inserisce una password valida.
Risposta: r ∧ ¬p
d) Se l’utente non inserisce una password valida, ma è registrato al sistema, allora l’accesso è
consentito.
Risposta: (¬p ∧ r ) -> q
Equivalenze proposizionali Nel ragionamento matematico riveste un ruolo importante la possibilità di sostituire una affermazione
(proposizione) con un’altra avente gli stessi valori di verità.
Una tautologia è una proposizione composta (ovvero un’espressione formata da proposizioni legate da
operatori logici) che è sempre vera per tutti i possibili valori delle proposizioni elementari che la
compongono.
Una contraddizione è una proposizione composta che è sempre falsa per tutti i possibili valori delle
proposizioni elementari che la compongono.
Una contingenza è una proposizione composta che non è né una tautologia né una contraddizione.
Le proposizioni p e q sono dette logicamente equivalenti se hanno gli stessi valori di verità (o
equivalentemente se p ↔ q è una tautologia). La notazione p ≡ q denota che p e q sono logicamente
equivalenti.
Esempi di equivalenze logiche Leggi di De Morgan:
(p q) p q
(p q) p q
La prima equivalenza ci dice che la negazione di una congiunzione è formata prendendo la disgiunzione
delle negazioni delle proposizioni componenti. Allo stesso modo, la seconda equivalenza ci dice che la
negazione di una disgiunzione è formata prendendo la congiunzione delle negazioni delle proposizioni.
Commutative laws:
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
Associative laws:
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributività:
p (q r) (p q) (p r)
Proprietà dell’implicazione:
p q p q
Esempio: Negare, utilizzando le leggi di De Morgan, la frase “L’estate in Messico è calda ed assolata”.
Soluzione: L’estate in Messico non è calda o non è assolata
Uso di equivalenze logiche
Le equivalenze possono essere usate per trasformare proposizioni o parti di esse per poter ottenere un
qualche risultato. Come mostrare equivalenze logiche:
Usare una tavola di verità
Usare equivalenze logiche già note
Soddisfacibilità proposizionale
Una proposizione è soddisfacibile se c'è una assegnazione di valori di verità alle sue variabili che la rende
vero. Quando tale assegnazione non esiste, cioè quando la proposizione è falsa per tutte le assegnazioni di
valori di verità alle sue variabili, la proposizione è insoddisfacibile (se e solo se la sua negazione è una
tautologia). Quando troviamo una particolare assegnazione di valori di verità che fa una proposizione vera,
abbiamo dimostrato che è soddisfacibile; tale assegnazione è chiamato una soluzione di questo problema
di soddisfacibilità.
Esercizi presenti sulla piattaforma relativi alla Logica Proposizionale
Esercizio 5 Verificare se la proposizione (p ∧ q) → (p → q) è una tautologia.
(p ∧ q) → (p → q) ≡
≡ ¬(p ∧ q) ∨ (p q) ≡ Per la proprietà dell’implicazione
≡ ¬(p ∧ q) ∨ (¬p V q) ≡ Per la proprietà dell’implicazione
≡ (¬p V ¬q) ∨ (¬p V q) ≡ Per le leggi di De Morgan
≡ (¬p V ¬p) V (¬q V q) ≡ Per le leggi associative e commutative dell’OR
≡ (Vero) V (Vero) ≡ Vero
Esercizio 8 Si supponga vera la proposizione p ∧ q. Per ciascuna delle seguenti proposizioni dire se possiamo
concludere che sia vera, se possiamo concludere che sia falsa o se non possiamo concludere nessuna delle
due cose (giustificare le risposte).
(a) p ∨ q. è vera: p ∧ q è vera se sono entrambe vere. (Vero) V (Vero) è Vero.
(b) ¬p ∨ ¬q. è falsa: per le leggi di De Morgan, corrisponde a ¬(p ∧ q). Poiché p ∧ q è Vero, la sua negazione
è Falsa.
(c) p ∨ ¬q. è vera: p ∧ q è vera, quindi sia p che q sono Vero. (Vero) V (Falso) è Vero.
Esercizio 9 Si supponga che la proposizione p ∧ q sia falsa. Per ciascuna delle proposizioni (a), (b) e (c) seguenti, dire se
possiamo concludere che sia vera, se possiamo concludere che sia falsa o se non possiamo concludere né
che sia vera né che sia falsa (giustificare le risposte).
(a) p ↔ q. non si può concludere nulla.
(b) ¬p ∨ ¬q. è vera: per le leggi di De Morgan, corrisponde a ¬(p ∧ q). Poiché p ∧ q è Falso, la sua
negazione è Vera.
(c) ¬p ∧ ¬q. non si può concludere nulla (anche con le leggi di De Morgan; fare la tavola di verità).
Cosa è stato fatto 1. Ripasso di teoria sulle applicazioni della logica proposizionale
2. Esercizi (pagina 22, numeri 2,8).
3. Ripasso di teoria sulle equivalenze proposizionali
4. Esercizi (pagine 35 e 36, numeri 10,26)
5. Esercizi assegnati sulla piattaforma relativi alla logica proposizionale (numeri 5,8,9)