PARTE 1

PARTE 1

Precedenze: ~ precede ∧ che precede ∨ che precede che ⇒ che precede ⇔ Γ|=A: ogni modello (interpretazione vera) di Γ è modello per A

Teo ded. Semantica: A è conseguenza semantica di B se e solo se B⇒A è una tautologia

Alternativo: Sia Γ un insieme di fbf. A è conseguenza semantica di Γ∪{B} se e solo se B⇒A è conseguenza semantica di Γ.

A è conseguenza semantica di Γ se e solo se Γ∪{∼A} è insoddisfacibile.

Equivalenze:

∼(∼A) ≡A A∧A ≡A A∨A ≡A A∧B ≡ B∧A A∨B ≡ B∨A

(A∧B)∧C ≡ A∧(B∧C)

(A∨B)∨C ≡A∨(B∨C) A∧(A∨B) ≡ A

A∨(A∧B) ≡A

A∧(B∨C) ≡ (A∧B)∨(A∧C) A∨(B∧C) ≡ (A∨B)∧(A∨C)

∼(A∧B) ≡ ∼A∨∼B

∼(A∨B) ≡ ∼A∧∼B A⇒B ≡ ∼A∨B A⇒B ≡ ∼(A∧∼B) B ≡ (∼A∧A)∨B B ≡ (∼A∨A) ∧B

Assiomi di L

A1. A⇒(B⇒A)

A2. (A⇒(B⇒C))⇒((A⇒B)⇒(A⇒C)) A3. (∼A⇒∼B)⇒((∼A⇒B)⇒A)

Completezza forte: Sia Γ un insieme di fbf, Γ|=A se e solo se Γ|-L A.

Deduzione sintattica: Sia Γ = Δ∪{B} un insieme di fbf. Γ|-L A se e solo se Δ|-L B⇒A.

PARTE 2

Prodotto di relazioni: associativo, compatibile con l’inclusione ma non commutativo. Relazione inversa:

inverto le frecce nel grafo e traspongo la matrice di incidenza. Seriale: se da ogni vertice parte almeno un arco, se in ogni riga della matrice c’è almeno un 1. Riflessiva: autoanello da ogni vertice, diagonale con 1 nella matrice di incidenza. Simmetrica: ogni arco ha doppia freccia (autoanello=doppia freccia), matrice incidenza simmetrica. Antisimmetrica: non ci sono archi con doppia freccia o sono autoanelli, matrice: se (i,k) è 0, (k,i) è 1 (fuori dalla diagonale principale). Transitiva: se a->b->c c’è anche una freccia diretta a-

>c, matrice: se (i,k) è 1, (k,j) è 1, allora anche (i,j) è 1.

Chiusure: rifl-simm. Sommo la matrice identica e la matrice trasposta. rifl-trans. Moltiplico tra di loro le matrici finchè non ne ho due uguali e le sommo. simm-trans. Sommo con la trasposta e poi moltiplico tra di loro finchè non ne ho due uguali. Rifl-simm-trans. Sommo con l’identica, poi agisco come al punto qui sopra. Se è rifl-simm-trans allora è relazione di equivalenza. Se è rifl-antisimm-trans allora è relazione di ordine. Reticolo: se per ogni coppia a,b esiste max e min

Funzioni

A è funzione se nella matrice di incidenza c’è un solo 1 su ogni riga.

Funzione iniettiva: una controimmagine sola in A. Se f(a1)=f(a2) allora a1=a2. Nella matrice: su ogni riga c’è un solo 1, e al più un 1 in ogni colonna. Nel grafo, se da ogni vertice esce un solo arco. Se è iniettiva ammette inversa dx. Funzione suriettiva: ogni B ha una controimmagine sola in A. Si verifica se in ogni riga della matrice c’è solo un 1 e in ogni colonna almeno un 1. Nel grafo, se da A esce un solo arco e ne arriva almeno uno in B. Se è suriettiva ammette inversa sx. F è biunivoca se è suriettiva e iniettiva. Se ammette inversa sx e dx queste coincidono.

PARTE 3

Precedenze: ~ ed i quantificatori (applicati nell’ordine in cui si trovano) precedono gli altri. Connettivi uguali si intendono associati a sinistra ed i quantificatori contigui si intendono

applicati nell’ordine in cui si trovano.

Termine libero se nessuna occorrenza di una variabile cade nel campo di un quantificatore.

Formula chiusa, senza occorrenze libere.

Interpretazione in <D,I>. Soddisfacibile se esiste almeno un assegnamento che la rende vera, vera se è vera per ogni assegnamento di valori alle variabili in D,I. Falsa se non esistono assegnamenti in D,I. Formule semanticamente equivalenti se: A|=B e B |=A.

Forma normale prenessa: quantificatori in testa.

Sostituzioni (i termini liberi cambiano variabile)

x A(x) B y (A[y / x] B)

x A(x) B y (A[y / x] B) x A(x) B y (A[y / x] B)

x A(x) B y (A[y / x] B)

x A(x) ⇒ B y (A[y / x] ⇒B)

x A(x) ⇒ B y (A[y / x] ⇒B)

B ⇒ x A(x) y (B ⇒ A[y / x])

B ⇒ x A(x) y (B ⇒ A[y / x]))

Forma di Skolem: sostituisco dalla fnp partendo dalla testa della formula i quant. Esistenziali con termini di arità n dove n è uguale al numero di quant. Universali che lo precedono (n=0 costante). Attenzione, se faccio una chiusura ora non sarà equivalente alla formula all’inizio.

Unificatori: sostituzioni possibili: variabili e funzioni con costanti. Non posso cambiare costanti o termini.

N.b. nella risoluzione se non deriviamo la clausola vuota non è detto che non sia insodd.

PARTE 4

Semigruppo: composizione interna binaria associativa. Monoide: elemento neutro (e) rispetto all’operazione binaria. Gruppo: ogni elemento ammette anche inverso rispetto al neutro. Se A è gruppo allora se ab=e ax=b xa=b ammettono una e una sola soluzione in A. Se vale la proprietà commutativa, il gruppo è detto gruppo abeliano.

Anello: due operazioni. <A,+> gruppo abeliano additivo. <A,*> semigruppo moltiplicativo. Valgono le distributive di + rispetto a *

Se il semigruppo moltiplicativo è un monoide, l’anello è unitario. In un anello lo zero è unico, è il neutro rispetto a +. Anello privo di divisori dello zero se non esistono a,b diversi da 0 tali che a*b=0. Leggi di cancellazione: se a*b=a*c e b*a=c*a con a diverso da 0 implica b diverso da c. Un anello è privo dei divisori dello zero se valgono le leggi di cancellazione. Corpo: anello i cui elementi diversi da 0 formano un gruppo rispetto a *. Campo: corpo in cui * gode della proprietà commutativa. Reticolo: insieme con due operazioni binarie che godono della proprietà commutativa ed associativa. Sottostrutture: tutte le precedenti applicate in un sottoinsieme H. Sottosemigruppo: a*b deve appartenere ancora ad H.

Sottogruppo: anche l’inverso di A deve app. ad H . Sottoanello: a-b e a*b deve appartenere ancora ad H.

Congruenza: considero un insieme A, una legge di arità n e una relazione di equivalenza  su A.

è compatibile se per ogni a¹, a²,..., aⁿ, b¹, b²,..., bⁿA, con (a¹,b¹), (a²,b²),..., (aⁿ,bⁿ)implicano((a¹,a²,...,aⁿ), (b¹,b²,...,bⁿ))Data una struttura algebrica A, una relazione di equivalenza si dice di congruenza se A è compatibile con ogni .

Omomorfismo: se vale per ogni a¹, a²,..., aⁿA¹, f (¹(a¹, a²,..., aⁿ)) = ²(f (a¹), f (a²),...,f (aⁿ)).

Monomorfismo se f è una funzione iniettiva, epimorfismo se f è suriettiva, isomorfismo se f è biunivoca.

Sottogruppo normale: per ogni hH e per ogni aA si ha a^-1haH (contiene tutti i coniugati dei suoi elementi). N.B. per dimostrare che un sottoinsieme di A sia sottogruppo normale bisogna anche verificare che sia sottogruppo.

Teorema di Lagrange: Se < A, × > è un gruppo finito di ordine n (cioè la sua cardinalità è n), un suo qualsiasi sottogruppo ha ordine m che divide n. In generale non vale l’inverso. Omomorfismo per gruppi:

Siano < A, × > un gruppo, < A’, * > una struttura algebrica ed f un omomorfismo di < A, × > in < A’, * >.

Posto T = f (A) A’, risulta: 1. < T, * > è un gruppo; 2. Nf è un sottogruppo normale di < A, × >; 3. < A / Nf , • > è isomorfo a < T, * >.

LABORATORIO:

list_of_descriptions.

name({*nome esercizio*}).

author({**}).

status(unsatisfiable).

description({*descrizione esercizio*}).

end_of_list.

list_of_symbols.

functions[(nome,arità), (nome,arità)].

predicates[(nome,arità), (nome,arità)].

end_of_list.

list_of_formulae(axioms).

formula(testo formula).

end_of_list.

list_of_formulae(conjectures).

formula(testo formula).

end_of_list.

end_of_problem.

Connettivi:

forall([variabile quantificata], formula) exists([variabile quantificata], formula) or(termine{,termine}∗ )

and(termine{,termine}∗ )

implies(antecedente, conseguente) not(formula)

Le costanti van definite come funz. di arità 0.