Logica Proposizionale Esercizio 7.
9 R&N
– ESERCITAZIONE –
Se l’unicorno è un animale mitico, è immortale, ma se non è mitico,
allora è un mammifero mortale. Se è immortale o un mammifero,
Dipertimento di Elettronica per l’Automazione allora ha un corno. L’unicorno è magico se ha un corno.
Università degli Studi di Brescia
Alessandro Saetti Scrivere le rappresentazioni logiche delle precedenti formule in modo
[email protected] tale che siano utilizzabili con la risoluzione unitaria.
Dimostrare per refutazione e tramite la strategia basata su insieme
Materiale per il Corso di Intelligenza Artificiale A di supporto quanto segue.
(Prof. Alfonso Gerevini)
• L’unicorno è mitico?
• L’unicorno è magico?
• L’unicorno ha un corno?
Esercizio 7.9 R&N (Soluzione) Esercizio 7.9 R&N (Soluzione)
Se l’unicorno e’ un animale mitico e’ immortale
Se l’unicorno e’ un animale mitico e’ immortale
¬mitico ∨ immortale
mitico → immortale
Se non e’ mitico allora e’ un mammifero mortale
Se non e’ mitico allora e’ un mammifero mortale
mitico ∨ ¬immortale
¬mitico → ¬immortale ∧ mammifero mitico ∨ mammifero
Se e’ immortale o e’ un mammifero allora ha un corno Se e’ immortale o e’ un mammifero allora ha un corno
immortale ∨ mammifero → cornuto ¬immortale ∨ cornuto
¬mammifero ∨ cornuto
L’unico e’ magico se ha un corno
L’unico e’ magico se ha un corno
cornuto → magico ¬cornuto ∨ magico
Esercizio Logica Proposizionale
Esercizio 7.9 R&N (Soluzione)
John lo sfregiato, Bill lo squartatore e Jack il duro vengono inter-
rogati con l’accusa di aver rubato la cassetta delle elemosina della
KB={¬mitico ∨ immortale, mitico ∨ ¬immortale, mitico ∨ mammifero,
parrocchia. Jack dice che il furto e’ stato commesso da Bill; Bill
¬immortale ∨ cornuto, ¬mammifero ∨ cornuto, ¬cornuto ∨ magico}
si professa innocente e John afferma di non aver compiuto il furto.
mitico∨mammifero, ¬mitico mitico∨¬immortale, ¬mitico
Sapendo che solo uno dei tre dice la verità, chi è il ladro.
1. S = {¬mitico} mammifero , ¬immortale
¬mammifero∨cornuto, mammifero
Scrivere le rappresentazioni logiche delle precedenti formule in modo
2. S = {¬mammifero, ¬immortale} cornuto tale che siano utilizzabili con la risoluzione unitaria.
Scoprire per refutazione e tramite la strategia di risoluzione basata
¬cornuto∨magico, cornuto
3. S = {¬immortale, cornuto} magico su insieme di supporto chi tra John, Jack e Bill ha commesso il
furto.
4. S = {¬immortale, magico} ?
Suggerimento:
La dimostrazione non ha portato ad alcuna contraddizione! Usare i letterali FurtoBill, FurtoJack, FurtoJohn, VeritaBill,
VeritaJack, VeritaJohn
Esempi Formule Logica del Primo Ordine
Logica del Primo Ordine
Rappresentare le seguenti formule in logica del primo ordine, usando
– ESERCITAZIONE – un vocabolario corretto (da definire)
Dipertimento di Elettronica per l’Automazione • Alcuni studenti studiano francese nella primavera del 2001
Università degli Studi di Brescia ∃x Studente(x) ∧ Studia(x,Francese,Primavera2001)
Alessandro Saetti
[email protected] • Tutti gli studenti che studiano francese passano l’esame
∀x, s Studente(x) ∧ Studia(x,Francese,s) → Passa(x,Francese,s)
Materiale per il Corso di Intelligenza Artificiale A
(Prof. Alfonso Gerevini) • Due studenti stuadiano greco nella primavera del 2001
∃x, y Studente(x) ∧ Studia(x,Greco,Primavera2001) ∧
Studente(y) ∧ Studia(y,Greco,Primavera2001) ∧ y = x
• Solo uno studente studia greco nella primavera del 2001
∃x Studente(x) ∧ Studia(x,Greco,Primavera2001) ∧
(∀y, y = x → ¬Studia(y,Greco,Primavera2001))
Esempi Formule Logica del Primo Ordine
• I poliziotti arrestano i ladri
Esercizi Formule Logica del Primo Ordine
∀x, y Poliziotto(x) ∧ Arresta(x, y) → Ladro(y)
e. Ogni persona che acquista una polizza assicurativa è previdente
• Tutti i poliziotti arrestano un ladro
(Predicati utili: Persona(.), Compra(.,.), Previdente(.))
∀x Poliziotto(x) → ∃y Ladro(y) ∧ Arresta(x, y)
• Tutti i ladri sono arrestati da un poliziotto f. Nessuna persona acquista una polizza costosa
∀x Ladro(x) → ∃y Poliziotto(y) ∧ Arresta(y, x) (Predicati utili: Persona(.), Compra(.,.), Polizza(.), Costosa(.))
• Esite un ladro che è arrestato da tutti i poliziotti
g. Esiste un agente che vende polizze a persone non assicurate
∃x Ladro(x) ∧ ∀y Poliziotto(y) → Arresta(y, x)
(Predicati utili: Agente(.), Vende(.,.,.), Polizza(.), Persona(.),
• Esiste un poliziotto che arresta tutti i ladri Assicurato(.))
∃x Poliziotto(x) ∧ ∀y Ladro(y) → Arresta(x, y)
Esercizi Formule Logica del Primo Ordine
Esercizi Formule Logica del Primo Ordine
• Esiste un agente che vende tutte le polizze a tutte le persone
non assicurate
• I politici possono ingannare qualche persona per tutto il tempo,
(Predicati utili: Agente(.), Vende(.,.,.), Polizza(.), Persona(.), o tutte le persone per qualche tempo, ma non possono ingannare
Assicurato(.)) tutte le persone per tutto il tempo
(Predicati utili: Politici(.), Persona(.), Inganna(.,.,.))
• Esiste un agente che vende tutte le polizze alle persone se e solo
se esse non sono assicurate
• Tutti i tedeschi parlano le stesse lingue
(Predicati utili: Agente(.), Vende(.,.,.), Polizza(.), Persona(.),
Assicurato(.)) (Predicati utili: Tedesco(.), Parla(.,.))
• Esiste un barbiere che rade tutti gli uomini che non si radono • Tutti i tedeschi parlano almeno una stessa lingua
da soli
(Predicati utili: Tedesco(.), Parla(.,.))
(Predicati utili: Barbiere(.), Rade(.,.), Uomo(.))
Esercizio Inferenza Logica del 1-Ordine Esercizio Inferenza Logica del 1-Ordine
Scrivere le rappresentazioni logiche delle seguenti formule in modo • Ogni persona lavora o come infermiere oppure come insegnante
tale che siano utilizzabili con la risoluzione generalizzata. ∀x Lavora(x,Insegnante) → ¬Lavora(x,Infermiere)
∀x ¬Lavora(x,Insegnante) → Lavora(x,Infermiere)
• Ogni persona lavora o come infermiere oppure come insegnante
• Tutti gli infermieri sono maschi
• Tutti gli infermieri sono maschi
∀x Lavora(x,Infermiere) → Maschio(x)
• Tutte le persone sono o maschi o femmine
• Tutte le persone sono o maschi o femmine ∀x ¬Machio(x)→Femmina(x)
∀x Maschio(x)→¬Femmina(x)
• Steve è un maschio e Roberta è una femmina
• Steve è un maschio e Roberta è una femmina
• Roberta non è una insegnante
Maschio(Steve), Femmina(Roberta),
• Roberta non è una insegnante (Contraddizione)
Dimostare per refutazione e tramite la strategia basata su insieme ¬Lavora(Roberta,Insegnante)
di supporto che Roberta insegna.
Esercizio Inferenza Logica del 1-Ordine Esercizio Inferenza Logica del 1-Ordine
• Ogni persona lavora o come infermiere oppure come insegnante 1. S = {¬Lavora(Roberta, Insegnante)}
¬Lavora(x,Insegnante) ∨ ¬Lavora(x,Infermiere) Lavora(x,Insegnante)∨Lavora(x,Infermiere), ¬Lavora(Roberta,Insegnante)
Lavora(x,Insegnante) ∨ Lavora(x,Infermiere) SOST({x/Roberta},Lavora(x,Infermiera))
• Tutti gli infermieri sono maschi 2. S = {¬Lavora(Roberta, Insegnante), Lavora(Roberta, Infermiera)}
¬Lavora(x,Infermiere) ∨ Maschio(x) ¬Lavora(x,Infermiera)∨Maschio(x), Lavora(Roberta,Infermiera)
SOST({x/Roberta},Maschio(x))
• Tutte le persone sono o maschi o femmine
3. S = {¬Lavora(Roberta, Insegnante), Lavora(Roberta, Infermiera), Maschio(Roberta)}
Machio(x)∨Femmina(x)
¬Maschio(x)∨¬Femmina(x) ¬Maschio(x)∨¬Femmina(x),Maschio(Roberta)
SOST({x/Roberta},¬Femmina(x))
• Steve è un maschio e Roberta è una femmina 4. S = {¬Lavora(Roberta, Insegnante), Lavora(Roberta, Infermiera)
Maschio(Steve), Femmina(Roberta), Maschio(Roberta), ¬Femmina(Roberta)}
Femmina(Roberta), ¬Femmina(Roberta)
• Roberta non è una insegnante (Contraddizione) F
¬Lavora(Roberta,Insegnante)
Per risoluzione unitaria derivo la clausola vuota!
Esempio su Circuiti Digitali (NOR) Esempio su Circuiti Digitali (NOR)
Scrivere la rappresentazione logica di un dispositivo C1 che imple- • Se due terminali sono connessi, allora hanno lo stesso segnale
menta la funzione logica NOR. Le regole da rappresentare sono le ∀t1 t2 Connesso(t1, t2)→(Segnale(t1)=Segnale(t2))
seguenti:
• Il segnale ad ogni terminale è 1 oppure 0 (1 = 0)
• Se due terminali sono connessi, allora hanno lo stesso segnale ∀t Segnale(t)=1 ↔ ¬Segnale(t)=0
1 = 0
• Il segnale ad ogni terminale è 1 oppure 0 (1 = 0)
• Il terminale A è connesso al terminale B sse il terminale B è
connesso al terminale A
• Il terminale A è connesso al terminale B sse il terminale B è
∀t1 t2 Connesso(t1, t2)↔Connesso(t2, t1)
connesso al terminale A
• L’output di una porta OR è 1 sse almeno uno dei suoi input è 1
• L’output di una porta OR è 1 sse almeno uno dei suoi input è 1 ∀g Tipo(g)=OR → Segnale(Out(1, g))=1 ↔
(Segnale(In(1, g))=1 ∨ Segnale(In(2, g))=1)
• L’output di una porta NOT è differente dall’input
• L’output di una porta NOT è differente dall’input
+ codifica dello specifico circuito ∀g Tipo(g)=NOT → Segnale(Out(1, g))=Segnale(In(1, g))
Esempio su Circuiti Digitali (NOR) Esercizio su Circuiti Digitali (OR+AND)
• Porte logiche: Scrivere la rappresentazione logica del seguente dispositivo C1.
Tipo(O1)=OR
Tipo(N1)=NOT C1
• Connessioni:
O1
Connesso(Out(1,O1),In(1,N1))
Connesso(In(1,C1),In(1,O1)) A1
Connesso(In(2,C1),In(2,O1))
Connesso(Out(1,N1),Out(1,C1))
Suggerimento:
• Segnali Input/Output:
Segnale(In(1,C1))=0 • L’output di una porta AND è 0 sse almeno uno degli input è 0
Segnale(In(2,C1))=1
Segnale(Out(1,C1))=1 (Contraddizione: E’ l’uscita pari a 0?) + codifica dello specifico circuito
Esercizio su Circuiti Digitali R&N
Scrivere la rappresentazione logica del seguente dispositivo C1.
C1
X1
X2
A2
O1
A1
Suggerimento:
• L’output di una porta XOR è 1 sse uno dei suoi input è differente
+ codifica dello specifico circuito
