Swappa : Uni / Logica - Raccolta delle domande di Teoria

 :: 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

Esame del 12 settembre 2008

Esercizio 1

1. Fornire la definizione di f.b.f. in forma di Skolem
2. dare un esempio di f.b.f. in forma di Skolem
3. data una f.b.f., la sua forma di Skolem è unica?
4. Se è unica se ne dia una dimostrazione, altrimenti si fornisca un controesempio

SOLUZIONE

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

1. Vabeh dai lo lascio all'immaginazione
2. No, non lo è, perché dipende dall'ordine di estrazione dei quantificatori quando si crea la forma prenessa della fbf
3. Anche questo non è difficile...:)

Esercizio 5

1. Descrivere il principio di bivalenza per la logica proposizionale
2. Descrivere il principio di estensionalità per la logica proposizionale
3. Descrivere e discutere un esempio di connettivo estensionale
4. Descrivere e discutere un esempio di connettivo non estensionale
5. Dare la definizione di f.b.f. nella logica proposizionale
6. Descrivere e discutere un esempio di formula non ben formata

SOLUZIONE

1. Principio di bivalenza: ogni enunciato è sempre vero o falso
2. Principio di estensionalità: il vdv degli enunciati composti dipende solamente dal valore di verità degli enunciati che li compongono
3. L'AND, per esempio, e scrivo una fbf con un AND e relativa tabella di verità
4. 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.
5. 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
6. 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.

Esame del 4 giugno 2008

Esercizio 1

1. Dare la definizione di forma normale congiuntiva (FNC)
2. Dare la definizione di forma normale disgiuntiva (FND)
3. Fornire un esempio di una FNC e dell'equivalente formula FND

SOLUZIONE

1. La fbf P è in FNC sse:
   • P = P₁ AND P₂ AND P₃ AND ... AND P_N
   • Ogni P_n è una disgiunzione di letterali
2. La fbf P è in FND sse:
   • P = P₁ OR P₂ OR P₃ OR ... OR P_N
   • Ogni P_n è una congiunzione di letterali
3. Ma sì non è difficile:)

Esercizio 4

1. Dare la definizione di risolvente nella logica predicativa

SOLUZIONE

Mmm... nella logica predicativa, date due clausole C₁ e C₂, la clausola R è loro risolvente se:

• esistono due sostituzioni s₁ e s₂, la prima applicata a C₁ e la seconda a C₂, tali che le clausole non abbiano variabili in comune
• esistono due insiemi di letterali, uno tratto da C₁, l'altro da C₂, entrambi non vuoti, tali che la loro unione sia unficabile con l'mgu SIGMA. Questi insiemi sono {I₁...I_m} in C₁s₁, e {I'₁...I'_n} in C₂s₂
• R ha la forma ((C₁s₁ - {I₁...I_m} UNION C₂s₂ - {I'₁...I'_n})mgu

Esame del 10 aprile 2008

Esercizio 1

1. Definire il concetto di paradosso
2. Descrivere in dettaglio un esempio di paradosso
3. Determinare se la seguente frase è vera, falsa oppure è un paradosso. Giustificare la risposta: "Io dico sempre il falso"

SOLUZIONE

1. Un paradosso è un'affermazione che non può essere né vera, né falsa.
2. 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.
3. "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.

Esercizio 2

1. Fornire in modo dettagliato la definizione di struttura nella logica del prim'ordine
2. Fornire in modo dettagliato la definizione di ambiente nella logica del prim'ordine
3. Descrivere e discutere un esempio di struttura e di ambiente in cui la seguente formula P è vera: vabbeh non la scrivo
4. Descrivere e discutere un esempio di struttura e di ambiente in cui la formula P è falsa

SOLUZIONE

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

Esame del 22 febbraio 2008

Esercizio 2

Argomentare le risposte alle seguenti domande:

1. Enunciare il teorema di Church
2. Descrivere il concetto di semidecidibilità
3. Il calcolo proposizionale è decidibile, semidecidibile o indecidibile? Motivare la risposta
4. Il calcolo predicativo è decidibile, semidecidibile o indecidibile? Motivare la risposta

SOLUZIONE

1. 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
2. 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.

Esercizio 5

1. Si dia la definizione di insieme fuzzy e si illustri un esempio di insieme fuzzy e uno di insieme classico (ordinario)

Esercitazione del 20 dicembre 2007

Esercizio 1

Dare la definizione di conseguenza semantica e di equivalenza semantica nella logica proposizionale.

Dimostrare che:

1. (A => B) è conseguenza sem. di (~A OR B) ovvero che (~A OR B) |= (A => B)
2. facoltativo: (A AND B) non è conseguenza semantica di {A OR B, A OR ~ B}

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.

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.

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.

Esercizio 4

1. Si dia la definizione di clausola di Horn definita e di clausola goal
2. Si dia la definizione di programma logico
3. Si descrivano degli esempi di clausole di Horn definite, di clausole goal
4. 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.

SOLUZIONE

1. 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
2. Un programma logico è un insieme finito di clausole definite
3. ma no, dai...
4. no!

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.

---

Torna alla pagina di Logica Matematica