Esercizi di Logica

Esercizio 1

Descrivere il sistema formale per l'alfa-equivalenza

Esercizio 2

Fornire una derivazione (nello stile della Def.2.3 di [SM]) della formula ben formata (\x.xy)(zz)=_alfa(\w.wy)(zz) nel sistema formale per l'alfa-equivalenza a partire dall'insieme vuoto.

Esercizio 3

Fornire le definizioni di regola ammissibile e derivabile.
Dimostrare che nel sistema formale della alfa-equivalenza la seguente regola e' derivabile

       M =_alfa N    M' =_alfa N'  M" =_alfa N" 
     ------------------------------------------
                  M"MM' =_alfa N"NN'

Esercizio 4

Convincersi che le dimostrazioni delle proposizioni da 3.2 a 3.12 del testo [SM] dimostrano veramente quello che devono dimostrare.

Esercizio 5

Considerare le seguenti formule ben formate e dire se sono soddisfacibili, contraddittorie o tautologie.

not(p -> p)

p -> (p -> q)

(p -> p) -> not(p)

((p -> q) -> q) -> q

not(q -> not(q -> p))

(p -> r) -> ((q -> r) -> ((not(p)->q) -> r))

Dire se e' vero che

p -> (p -> q) |= p -> q

not(p -> p) |= (p -> q) -> (q -> p)

p -> (p -> q), not(p -> p) |= (p -> q) -> (q -> p)

Esercizio 6

Dimostrare che tutti gli assiomi del calcolo proposizionale sono tautologie.
Dimostrare che se le ipotesi della regola di inferenza del modus ponens sono tautologie, allora la conclusione e' una tautologia.

Esercizio 7
Giustificare il fatto che dimostrare

A,B |= C

e' equivalente a dimostrare che

not(A->not(B))->C

e' una tautologia

Esercizio 8
Dimostrare che, nel calcolo proposizionale, una regola di inferenza

        A₁ A₂ ... A_n  
      ----------------
             C

e' ammissibile se e solo se

 ( |= A₁, |= A₂ .... e  |= A_n) implica   |= C

Utilizzare questa proprieta' per dimostrare quindi che la regola

       not(A -> not(B))  
      ---------------------
               A

e' ammissibile.

Soluzione. (by luca98, josura e gabriele7)

Esercizio 9

Si prendano in considerazione le definizioni per le formule

A /\ B

A \/ B

A <-> B

date alla fine del secondo punto della Definizione 3.1 in [SM]
(dove /\ si legge "and", \/ si legge "or" e <-> si legge "equivalente a", oppure "se e solo se" oppure "doppia implicazione" ecc. )

Dimostrare che, dato un assegnamento proposizionale,

la formula A /\ B e' vera (il suo valore di verita' e' 1) se e solo se A e' vera e B e' vera
la formula A \/ B e' falsa (il suo valore di verita' e' 0) se e solo se A e' falsa e B e' falsa
la formula A <-> B e' vera (il suo valore di verita' e' 1) se e solo se A e B hanno lo stesso valore di verita' (cioe' entrambe 1 o entrambe 0).

Esercizio 10
DImostrare le proposizioni da 3.2 a 3.12 del testo [SM] utilizzando la deduzione naturale.

Esercizio 11
Considerare la deduzione naturale con le solo regole per l'implicazione, la negazione e l'assurdo.
Dimostrare che, definendo \/ e /\ come fatto alla fine del secondo punto nella definizione 3.1 [SM], tutte le regole della deduzione naturale per \/ e /\ sono derivabili o ammissibili.

Esercizio 12
Nella logica dei predicati, considerare la segnatura seguente, dove i simboli di funzione sono

{c⁰, k⁰, f¹, g²}

mentre i simboli di predicato (relazioni) sono

{P¹, Q²}

Fornire delle strutture (non banali) nelle quali le seguenti formule risultino vere e strutture nelle quali risultino false.

forall x.Q(x,x)

forall x. forall y.Q(x,y)

forall x. forall y. exists z. (P(x) -> Q(y,f(z)))

exists z. forall x. (P(x) \/ Q(k,z))

exists z. (P(g(z,c)) /\ (forall x. Q(x,f(g(z,k)))))

Esercizio 13

Considerare la segnatura dell'esercizio 12 e scrivere una grammatica di Chomsky che generi il linguaggio di tutte le formule ben formate di tale segnatura.
Dire di che tipo e' la grammatica fornita.

Esercizio 14
Fare qualche esercizio tra quelli proposti in [AU].

Esercizio 15
Consideriamo la segnatura che non abbia alcun simbolo di funzione e che abbia i seguenti simboli di predicato (relazione): {P,Q}, dove P e' binario e Q e' ternario.
Si consideri la struttura che ha come supporto l'insieme dei numeri naturali ed in cui P corrisponda alla relazione "≤" tra naturali e Q corrisponda alla seguente relazione ternaria tra numeri naturali: {(n,m,p) | n+m=p}.
Quali delle seguenti formule sono vere nella struttura data?

forall x. forall y. forall z.(Q(x,y,z) -> Q(y,x,z))

forall x. exists y. (Q(x,x,y) -> Q(y,x,y)) 

exists x. exists y. (P(x,y) \/ not(B(y,x,y)))

(forall x. exists y. P(x,y)) -> forall x. Q(x,x,c)

exists x. forall y. Q(x,y,x)

forall x. forall y. P(x,y)

exists x. exists y. P(x,y)

(forall x. exists y. not(P(x,y)) -> exists y. not(P(y,c)

Esercizio 16
Stabilire quali delle formule seguenti sono valide e quali soddisfacibili. Nel secondo caso, fornire un esempio di struttura che non ne e' un modello (in cui cioe' non siano vere).

(exists x.A(x) -> forall x.B(x)) -> forall x.(A(x) -> B(x))

(exists x.A(x) -> exists x.B(x)) -> forall x.(A(x) -> B(x))

(exists x.A(x) -> exists x.B(x)) -> exists x.(A(x) -> B(x))

(exists x.((A(x) -> B(x)))) -> (forall x.A(x) -> forall x. B(x))

(exists x.((A(x) -> B(x)))) -> (forall x.A(x) -> exists x. B(x))

(exists x.((A(x) -> B(x)))) -> (exists x.A(x) -> exists x. B(x))

(forall x.((A(x) -> B(x)))) -> (exists x.A(x) -> forall x. B(x))

(forall x.((A(x) -> B(x)))) -> (exists x.A(x) -> exists x. B(x))

(forall x.((A(x) -> B(x)))) -> (forall x.A(x) -> forall x. B(x))

(forall x.A(x) -> forall x. B(x)) -> (forall x.((A(x) -> B(x))))

(forall x.A(x) -> exists x. B(x)) -> (exists x.((A(x) -> B(x))))

(forall x.A(x) -> exists x. B(x)) -> (forall x.((A(x) -> B(x))))

Esercizio 17
Sia data la seguente formula della logica dei predicati con uguaglianza:

forall p. forall q.((P(p,a)/\not(p=a)) -> exists x. exists y.(f(x,y)=f(q,q)/\g(x,y)=p))

Stabilire se e' soddisfatta nelle seguenti interpretazioni:

Il supporto sono i numeri naturali dispari, 'a' corrisponde a 19, 'f' alla funzione esponente, 'g' al prodotto e P alla relazione '≤'.
Il supporto sono i numeri naturali, 'a' corrisponde a 1, 'f' alla funzione somma, 'g' al prodotto e P alla relazione '≤'.
Il supporto sono i numeri reali, 'a' corrisponde a 0, 'f' alla funzione somma, 'g' al prodotto e P alla relazione '≥'.

Esercizio 18
Dimostrare che il supporto di strutture che sono domini di PA contiene almeno un sottoinsieme numerabile di elementi.

Dimostrare nell'Aritmetica di Peano che 2+1=3.

Esercizio 19
(a) Fornire la definizione di sistema formale e di regola di inferenza ammissibile.

(b) Cosa significa, nel calcolo proposizionale (logica proposizionale), che una formula A e' conseguenza tautologica di un insieme di formule Gamma ( Gamma |= A) ?
E' vera la seguente affermazione? p -> (p -> q) |= p -> q dove p e q sono variabili proposizionali.
(c) Consideriamo la segnatura che non abbia alcun simbolo di funzione e che abbia i seguenti simboli di predicato (relazione): {P,Q}, dove P e' binario e Q e' ternario.
Si consideri la struttura che ha come supporto l'insieme dei numeri naturali ed in cui P corrisponda alla relazione "≤" tra naturali e Q corrisponda alla seguente relazione ternaria tra numeri naturali: {(n,m,p) | n+m=p}.
Quali delle seguenti formule sono vere nella struttura data?

forall x. forall y. forall z.(Q(x,y,z) -> Q(y,x,z))

(forall x. exists y. P(x,y)) -> forall x. Q(x,x,c)