|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.LogicaDomandeTeoria History
Hide minor edits - Show changes to output
Changed lines 124-125 from:
# '''facoltativo:''' (A AND B) non è conseguenza semantica di (A OR B, A OR ~B) to:
# '''facoltativo:''' (A AND B) non è conseguenza semantica di {A OR B, A OR ~ B}
%red%[-'''SOLUZIONE'''-]
Conseguenza semantica nella logica proposizionale: Γ |= P se tutti i modelli di Γ sono modelli di P.
Equivalenza semantica: P è equivalente a Q se tutti e soli i modelli di P sono modelli anche per Q, ovvero '''P |= Q''' e '''Q |= P'''.
Per dimostrare che (~A OR B) |= (A => B), basta fare la tavola di verità delle due, confrontarle, e dimostrare che sono uguali.
Per dimostrare che (A AND B) non è conseguenza semantica di {A OR B, A OR ~B}, occorre fare la tavola di A OR B e quella di A OR ~ B, vedere quali sono i modelli di ENTRAMBE le formule, e confrontarli con quelli evinti dalla tavola di A AND B. Added lines 145-159:
%red%[-'''SOLUZIONE'''-]
* L'universo di H di una fbf P, che si scrive H(P), è l'insieme formato da:
** le costanti che compaiono in P, e se non esistono ne introduco una
** l'applicazione di tutti i simboli di funzione che compaiono in P a tutti i termini che appaiono nell'universo (è ricorsiva)
* La base di H di una fbf P è l'insieme di tutte le formule ground (senza variabili) che si possono costruire a partire dai predicati di P, in cui inserisco come argomenti tutti gli elementi di H(P)
* L'interpretazione di Herbrand è una coppia (D'_h_', I'_h_') dove:
** D'_h_' è l'universo di H
** I'_h_'(c) = c, cioè ad ogni costante assegna se stessa
** I'_h_'(f(...)) = f(...), cioè la funzione è interpretata per se stessa
** i predicati sono a scelta
* Il modello di H è un'interpretazione di H che rende vera la P
Citiamo per inciso il '''Teorema di H''', che dice che una fbf P, chiusa e in forma di Skolem, è soddisfascibile sse esiste per essa un modello di H. Added lines 165-171:
%red%[-'''SOLUZIONE'''-]
# La clausola di Horn è una clausola in cui compare al più una formula atomica positiva. La clausola di Horn definita è la clausola di Horn in cui compare esattamente una formula atomica positiva. La clausola di Horn goal è quella in cui non compare nessuna formula atomica positiva
# Un programma logico è un insieme finito di clausole definite
# ma no, dai...
# no!
Changed lines 19-20 from:
to:
Changed lines 36-37 from:
to:
Changed lines 55-56 from:
to:
Changed lines 68-69 from:
to:
Changed lines 81-82 from:
to:
Changed lines 93-94 from:
to:
Changed lines 110-111 from:
to:
Added lines 103-106:
SOLUZIONE:\\
# Il teorema di Church afferma che la nozione di verità logica è '''indecidibile''', cioè non esiste un algoritmo che, data una fbf P della logica predicativa, termini sempre dicendo se è vera o falsa
# '''Semidecidibilità''' vuol dire che, data una fbf P, so applicare un algoritmo che, se termina, mi dice se è vera, ma se non termina, non so dire se sia falsa o semplicemente soddisfascibile.
Added lines 89-93:
# Una '''struttura''' è una coppia S = (D, I), dove D è il dominio e I un'assegnamento che fa le seguenti cose:
** ad ogni costante associa un elemento del dominio: I(c) IN D
** ad ogni funzione di arità > 0 associa una funzione di questo tipo: I(f): D'^k^' -> D
** ad ogni predicato associa una funzione del tipo I(A): D'^k^' -> {0,1}, quindi una funzione che va dal dominio al valore di verità
# Un''''ambiente''' di S è una funzione XI:VAR -> D, che va dall'insieme delle variabili al dominio D. In pratica è l'anagolo della struttura, ma per le variabili.
Added lines 77-81:
SOLUZIONE:\\
# Un paradosso è un'affermazione che non può essere né vera, né falsa.
# Prendiamo, ad esempio, ''"io sto mentendo"''. Se la frase è vera, cioè è vero che io sto mentendo, allora vuol dire che quello che dico è falso, e siccome ho detto "io sto mentendo", allora intendevo dire che dico la verità, e quindi non è vero che mento. Se la frase è falsa, allora vuol dire che sto dicendo la verità, ma se dico la verità, non posso affermare una frase falsa.
# "Io dico sempre il falso": se la frase fosse vera, allora anche quando dico "io dico sempre il falso" sarebbe falso, e quindi non è vero che dico sempre il falso. Se la frase fosse falsa, allora sarebbe vero il suo contrario, cioè "qualche volta dico il falso", e questa è una di quelle volte. Pertanto, è semplicemente una frase falsa e non un paradosso. Added lines 87-89:
Added lines 53-61:
SOLUZIONE:\\
# La fbf P è in FNC sse:
** P = P'_1_' AND P'_2_' AND P'_3_' AND ... AND P'_N_'
** Ogni P'_n_' è una disgiunzione di letterali
# La fbf P è in FND sse:
** P = P'_1_' OR P'_2_' OR P'_3_' OR ... OR P'_N_'
** Ogni P'_n_' è una congiunzione di letterali
# Ma sì non è difficile:) Added lines 64-69:
SOLUZIONE:\\
Mmm... nella logica predicativa, date due clausole C'_1_' e C'_2_', la clausola R è loro risolvente se:
* esistono due sostituzioni s'_1_' e s'_2_', la prima applicata a C'_1_' e la seconda a C'_2_', tali che le clausole non abbiano variabili in comune
* esistono due insiemi di letterali, uno tratto da C'_1_', l'altro da C'_2_', entrambi non vuoti, tali che la loro '''unione''' sia unficabile con l'mgu SIGMA. Questi insiemi sono {I'_1_'...I'_m_'} in C'_1_'s'_1_', e {I''_1_'...I''_n_'} in C'_2_'s'_2_'
* R ha la forma ((C'_1_'s'_1_' - {I'_1_'...I'_m_'} UNION C'_2_'s'_2_' - {I''_1_'...I''_n_'})mgu
Changed lines 19-20 from:
to:
SOLUZIONE:\\
# Una fbf in forma di Skolem è una fbf in forma normale prenessa, in cui le variabili legate dagli esistenziali vengono sostituite con:
* delle costanti, se non sono nello scope di nessun universale
* se invece si trovano nello scope di qualche universale, diventano funzioni delle variabili legate agli universali che lo precedono
# Vabeh dai lo lascio all'immaginazione
# No, non lo è, perché dipende dall'ordine di estrazione dei quantificatori quando si crea la forma prenessa della fbf
# Anche questo non è difficile...:) Changed lines 35-45 from:
to:
SOLUZIONE:\\
# Principio di bivalenza: ogni enunciato è sempre vero o falso
# Principio di estensionalità: il vdv degli enunciati composti dipende solamente dal valore di verità degli enunciati che li compongono
# L'AND, per esempio, e scrivo una fbf con un AND e relativa tabella di verità
# Il '''poiché''': In '''porto l'ombrello poiché piove''' la frase è vera, e i due enunciati sono veri. In '''il gatto miagola poiché Dario abbaia''', supponendo che i due siano veri, la frase nel suo complesso è falsa.
# Definizione di fbf nella logica proposizionale:
** le lettere atomiche, T e F sono delle fbf
** se P è una fbf, anche ~P lo è
** se P e Q sono fbf, allora anche P AND Q, P OR Q e P => Q lo sono
** nient'altro è una fbf
# descrivere e discutere un esempio di formula ''non'' ben formata: OR A non è ben formata perché la definizione dice P OR Q, e non OR Q.
Changed line 63 from:
!!!Esame del 20 dicembre 2007 to:
!!!Esercitazione del 20 dicembre 2007 Added lines 70-103:
!!!!Esercizio 4
Una f.b.f. P è in forma OR-NOT-OR se e solo se...
...mmm...
!!!Esame del 7 novembre 2007
!!!!Esercizio 2
Definire l'universo di Herbrand, la base di Herbrand, l'interpretazione ed il modello di Herbrand. Fornire un esempio per ogni definizione data.
!!!!Esercizio 4
# Si dia la definizione di clausola di Horn definita e di clausola goal
# Si dia la definizione di programma logico
# Si descrivano degli esempi di clausole di Horn definite, di clausole goal
# Si descriva un semplice programma logico P e una clausola logica G tale che ?-G si possa dimostrare da P. Si mostri l'albero SLD della refutazione.
!!!Esame del 3 luglio 2007
!!!!Esercizio 2
Sia P una f.b.f. costituita da formule atomiche e il solo connettivo OR; dimsotrare per induzione strutturale che P è soddisfascibile
!!!!Esercizio 5
Provare che l'insieme (=>, F) è funzionalmente completo, sapendo che l'insieme (XOR, ~, OR) lo è. Si ricorda che A XOR B = (~A AND B) OR (A AND ~B).
!!!Esame del 13 aprile 2007
!!!!Esercizio 2
Sia P una fbf. Dimostrare per induzione strutturale (caso base e conenttivi ~, AND e OR) che ~P non è conseguenza semantica di P, ovvero che nessun modello di P può anche essere modello di ~P. (Suggerimento: per ogni caso, sia quello base che i tre ricorsivi, ipotizzare che esista un'interpretazione di P, ovvero v(P)=1, e dimostrare che v(~P)= 0).
!!!!Esercizio 5
Provare che l'insieme (=>, F) è funzionalmente completo, sapendo che l'insieme (OR, ~) lo è.
!!!Esame del 20 febbraio 2007
!!!!Esercizio 5
Si enunci e si dimostri il teorema di deduzione semantica per la logica proposizionale. Si enunci il teorema di compattezza per la logica proposizionale.
Changed lines 60-69 from:
to:
!!!!Esercizio 5
# Si dia la definizione di insieme fuzzy e si illustri un esempio di insieme fuzzy e uno di insieme classico (ordinario)
!!!Esame del 20 dicembre 2007
!!!!Esercizio 1
Dare la definizione di conseguenza semantica e di equivalenza semantica nella logica proposizionale.
Dimostrare che:
# (A => B) è conseguenza sem. di (~A OR B) ovvero che (~A OR B) |= (A => B)
# '''facoltativo:''' (A AND B) non è conseguenza semantica di (A OR B, A OR ~B)
Added lines 1-63:
(:title Logica - Raccolta delle domande di Teoria:)
%titolo%''':: Logica - Raccolta delle domande di Teoria ::'''
!!!Abstract
In questa pagina c'è la raccolta delle domande di teoria apparse nei compiti precedenti, sperando che la storia si ripeta:D
!!!Esercitazione del 20 dicembre 2006
Si enuncino i teoremi di correttezza, completezza finita e completezza forte del calcolo dei sequenti per la logica proposizionale. Si dia la dimostrazione del teorema di correttezza per le regole (AND R), (SIM L) e (OR L).
[[Soluzione -> Attach:Teoria-20.12.2006.pdf]]
!!!Esame del 12 settembre 2008
!!!!Esercizio 1
# Fornire la definizione di f.b.f. in forma di Skolem
# dare un esempio di f.b.f. in forma di Skolem
# data una f.b.f., la sua forma di Skolem è unica?
# Se è unica se ne dia una dimostrazione, altrimenti si fornisca un controesempio
SOLUZIONE:...
!!!!Esercizio 5
# Descrivere il principio di bivalenza per la logica proposizionale
# Descrivere il principio di estensionalità per la logica proposizionale
# Descrivere e discutere un esempio di connettivo estensionale
# Descrivere e discutere un esempio di connettivo ''non'' estensionale
# Dare la definizione di f.b.f. nella logica proposizionale
# Descrivere e discutere un esempio di formula ''non'' ben formata
SOLUZIONE:...
!!!Esame del 4 giugno 2008
!!!!Esercizio 1
# Dare la definizione di forma normale congiuntiva (FNC)
# Dare la definizione di forma normale disgiuntiva (FND)
# Fornire un esempio di una FNC e dell'equivalente formula FND
!!!!Esercizio 4
# Dare la definizione di risolvente nella logica predicativa
!!!Esame del 10 aprile 2008
!!!!Esercizio 1
# Definire il concetto di paradosso
# Descrivere in dettaglio un esempio di paradosso
# Determinare se la seguente frase è vera, falsa oppure è un paradosso. Giustificare la risposta: ''"Io dico sempre il falso"''
!!!!Esercizio 2
# Fornire in modo dettagliato la definizione di ''struttura'' nella logica del prim'ordine
# Fornire in modo dettagliato la definizione di ''ambiente'' nella logica del prim'ordine
# Descrivere e discutere un esempio di struttura e di ambiente in cui la seguente formula P è vera: ''vabbeh non la scrivo''
# Descrivere e discutere un esempio di struttura e di ambiente in cui la formula P è falsa
!!!Esame del 22 febbraio 2008
!!!!Esercizio 2
Argomentare le risposte alle seguenti domande:
# Enunciare il teorema di Church
# Descrivere il concetto di semidecidibilità
# Il calcolo proposizionale è decidibile, semidecidibile o indecidibile? Motivare la risposta
# Il calcolo predicativo è decidibile, semidecidibile o indecidibile? Motivare la risposta
----
[[Torna alla pagina di Logica Matematica -> Logica Matematica]]
|
|
