Logica Predicativa, dimostrazione
Buona serata a tutti... Prima di ogni cosa ringrazio questo forum del grande supporto che dà alla mia passione.
Sto dilettandomi a studiare i fondamenti della logica matematica, in internet ho trovato un pò di esercizi, e sono incappato in particolare a questo sulla LOGICA PREDICATIVA
"
Dimostrare la SODDISFACIBILITA' del seguente enunciato:
∀x ∀y(¬r(x, y) ∨ ¬r(y, x)) ∧ ∀x ∃y r(x, y) ∧ ∀x ∃y r(y, x)
con questa soluzione:
Bisogna trovare un’interpretazione che soddisfi l’enunciato. L’interpreta-
zione I tale che:
DI = {0, 1, 2}, rI = {(0, 1), (1, 2), (2, 0)}
ha questa caratteristica.
"
Qualcuno saprebbe darmi qualche delucidazione su come ottenere tale soluzione?? ne sarei molto curioso, grazie buona serata.
Sto dilettandomi a studiare i fondamenti della logica matematica, in internet ho trovato un pò di esercizi, e sono incappato in particolare a questo sulla LOGICA PREDICATIVA
"
Dimostrare la SODDISFACIBILITA' del seguente enunciato:
∀x ∀y(¬r(x, y) ∨ ¬r(y, x)) ∧ ∀x ∃y r(x, y) ∧ ∀x ∃y r(y, x)
con questa soluzione:
Bisogna trovare un’interpretazione che soddisfi l’enunciato. L’interpreta-
zione I tale che:
DI = {0, 1, 2}, rI = {(0, 1), (1, 2), (2, 0)}
ha questa caratteristica.
"
Qualcuno saprebbe darmi qualche delucidazione su come ottenere tale soluzione?? ne sarei molto curioso, grazie buona serata.
Risposte
devi semplicemente prendere 0,1,2 e farli "ruotare" come x,y in maniera appropriata.
occhio che nella seconda clausola e anche nella terza clausola la y dipende da x, quindi per skolem è da porsi come f(x).
ti faccio un esempio proprio per la seconda clausola:
devi chiederti se per ogni x (quindi per 0,1,2) esiste un y (che può essere 0,1,2) tale che r(x,y).
e cominci:
se x=0 c'è un y che mi verifica r(0,y)? sì, y=1.
se x=1 c'è un y che mi verifica r(1,y)? sì, y=2.
se x=2 c'è un y che mi verifica r(2,y)? sì, y=0.
bene, quindi la seconda clausola è verificata.
nello stesso modo svolgi la terza (che t'anticipo io essere vera, ma scrivila perchè solo così impari)
per la prima invece la questione è diversa, perchè anche y è "ruotabile" a piacimento. quindi devi pensarla così:
per ogni coppia x,y - quindi (0,0), (0,1), (0,2)...(2,2) - è vero che bla bla bla?
ti metti lì e provi.
ora, rileggendo meglio il tuo quesito non capisco se ciò che vuoi sapere è perchè questo modello soddisfi quell'insieme di clausole o come trovare, in questo caso particolare ma anche a livello generale, un modello che soddisfi le clausole.
se è la prima opzione allora ti ho appena risposto. se è la seconda, devi provare te piano piano a "pensare" se possa esistere un modello in cui vivono quelle 3 clausole oppure riuscire a ricavare la clausola vuota mediante istanziazione e risoluzione.
quale strada intraprendere? solo l'esperienza e il "naso" te lo può dire. devi ragionare in maniera avvocatesca, cercando di togliere ogni riferimento al mondo reale che ci possa essere in un esercizio (spesso sono dati in forma del tipo "se andrea è l'assassino allora beatrice è bionda") e basarti soltanto su quello che ti dicono le ipotesi, per non incorrere in tautologie o deduzioni che magari nel mondo reale sono presenti ma nelle ipotesi date non ci sono (se non capisci l'ultima frase saltala).
se "senti puzza di modello" si comincia sempre partendo con universi più piccoli possibile. ti accorgi subito che se il tuo universo fosse di un elemento solo, le 3 clausole non potrebbero valere tutte e 3 contemporaneamente.
allora poi provi con 2. e guardi un po'...il fatto che nel modello preposto ci siano 3 elementi può far supporre che anche con 2 il modello caschi, ma questo non è assolutamente detto.
spero d'esserti stato d'aiuto.
occhio che nella seconda clausola e anche nella terza clausola la y dipende da x, quindi per skolem è da porsi come f(x).
ti faccio un esempio proprio per la seconda clausola:
devi chiederti se per ogni x (quindi per 0,1,2) esiste un y (che può essere 0,1,2) tale che r(x,y).
e cominci:
se x=0 c'è un y che mi verifica r(0,y)? sì, y=1.
se x=1 c'è un y che mi verifica r(1,y)? sì, y=2.
se x=2 c'è un y che mi verifica r(2,y)? sì, y=0.
bene, quindi la seconda clausola è verificata.
nello stesso modo svolgi la terza (che t'anticipo io essere vera, ma scrivila perchè solo così impari)
per la prima invece la questione è diversa, perchè anche y è "ruotabile" a piacimento. quindi devi pensarla così:
per ogni coppia x,y - quindi (0,0), (0,1), (0,2)...(2,2) - è vero che bla bla bla?
ti metti lì e provi.
ora, rileggendo meglio il tuo quesito non capisco se ciò che vuoi sapere è perchè questo modello soddisfi quell'insieme di clausole o come trovare, in questo caso particolare ma anche a livello generale, un modello che soddisfi le clausole.
se è la prima opzione allora ti ho appena risposto. se è la seconda, devi provare te piano piano a "pensare" se possa esistere un modello in cui vivono quelle 3 clausole oppure riuscire a ricavare la clausola vuota mediante istanziazione e risoluzione.
quale strada intraprendere? solo l'esperienza e il "naso" te lo può dire. devi ragionare in maniera avvocatesca, cercando di togliere ogni riferimento al mondo reale che ci possa essere in un esercizio (spesso sono dati in forma del tipo "se andrea è l'assassino allora beatrice è bionda") e basarti soltanto su quello che ti dicono le ipotesi, per non incorrere in tautologie o deduzioni che magari nel mondo reale sono presenti ma nelle ipotesi date non ci sono (se non capisci l'ultima frase saltala).
se "senti puzza di modello" si comincia sempre partendo con universi più piccoli possibile. ti accorgi subito che se il tuo universo fosse di un elemento solo, le 3 clausole non potrebbero valere tutte e 3 contemporaneamente.
allora poi provi con 2. e guardi un po'...il fatto che nel modello preposto ci siano 3 elementi può far supporre che anche con 2 il modello caschi, ma questo non è assolutamente detto.
spero d'esserti stato d'aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo