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à.

Esercizio 10 pagina 35

Esercizio 26 pagina 36

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)