(a)  Vedi testi.


(b) Per definizione di conseguenza tautologica, vedi testi.

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

e un'affermazione vera.
Infatti, consideriamo nelle prime due colonne della seguente tabella
tutti i possibili assegnamenti di valori di verita' alle variabili p e q,
e nelle altre due colonne il valore di verita' di p -> (p -> q) e p -> q


 p  q  |  p -> (p -> q) | p -> q
----------------------------------
 0  0  |        1       |    1
 0  1  |        1       |    1
 1  0  |        0       |    0
 1  1  |        1       |    1

Ogni assegnamento che rende vera p -> (p -> q)  rende vera anche p -> q,
quindi p -> (p -> q) |= p -> q.

Un modo alternativo e' vedere che, per definizione di implicazione,
 p -> (p -> q)  puo' essere resa falsa solo per l'assegnamento p=1, q=1,
e che tale assegmento rende falsa anche p->q.

Un ulteriore modo alternativo e' utilizza il teorema di completezza. 
Taòe teorema ci garantiche che far vedere p -> (p -> q) |= p -> q equivale
a far vedere 
p -> (p -> q) |- p -> q
Questo corrisponde a mostrare che esiste una dimostrazione di p->q
che utilizza l'ipotesi p -> (p -> q). Mostriamo una tale dimostrazione
in deduzione naturale.

            [p]1    p -> (p -> q)
          -------------------------
   [p]1          p -> q
 --------------------------
           q
     ------------ (->I)(1)
         p -> q


(c)

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

Questa formula e' vera nella struttura data, poiche'
presi tre numeri naturali qualsiasi, se il terzo e' la somma del primo
e del secondo, allora e anche la somma del secondo e del primo,
visto che la somma e' commutativa.

---

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

Questa formula invece e' falsa nella struttura data.
Infatti
contiene una variabile libera e per almeno un ambiente rho'
(quello che assegna il valore 4 a z) abbiamo che

[[forall x. Q(x,x,z)]]rho' = 0

(infatti non e' vero che per qualsiasi numero la sua somma con
se stesso e' uguale a quattro...)

mentre in qualsiasi ambiente rho
[[(forall x. exists y. P(x,y))]]rho = 1
(ogni numero e' minore o uguale a qualche altro numero)

Abbiamo cosi', per definizione di implicazione,
 che

[[(forall x. exists y. P(x,y)) -> forall x. Q(x,x,z)]]rho' =1

e quindi non e' vera.
Non e' neanche soddisfacibile.