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.
Risoluzione: combinare tra loro le clausole. Oltre che con lo schema si considera l’insieme. Se Ris(s)=Ris2(s) allora l’insieme di clausole è soddisfacibile (non vale per I ordine)
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 ovvero ad ogni 1 della matrice fuori dalla diagonale principale corrisponde uno 0 in posizione simmetrica). 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.
Trasformazioni dei quantificatori:x A x A x A x A Forma normale prenessa: quantificatori in testa.
Sostituzioni (i termini liberi cambiano variabile). Se la formula non ha occorrenze libere non serve cambiare 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 quantificatori esistenziali con termini di arità n dove n è uguale al numero di quantificatori universali che lo precedono (n=0 costante).
Mantengo i quantificatori universali.
La chiusura della forma di Skolem non è equivalente alla chiusura della formula data.
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 insoddisfacibile. Quando inizio la risoluzione clausole diverse devono riferirsi a variabili diverse. Es. C1 contiene X, Y. C2 contiene X,X. C2 dovrà contenere S,S (se la variabile è la stessa all’interno della stessa clausola si mantiene)
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. Per dimostrare che è gruppo si può anche dimostrare che è sottogruppo di gruppi noti di cui sono note le proprietà. (Esempio gruppo lineare generale di matrici non singolari di ordine 2) per il criterio di caratterizzazione dei sottogruppi. (Dati X,Y G, X-1*Y G?)
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. Dato un gruppo basta dimostrare che il prodotto appartiene ancora al sottogruppo. 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 a1, a2,..., an, b1, b2,..., bnA, con (a1,b1), (a2,b2),..., (an,bn)implicano((a1,a2,...,an), (b1,b2,...,bn))Data una struttura algebrica A, una relazione di equivalenza si dice di congruenza se A è compatibile con ogni .
Omomorfismo: se vale per ogni a1, a2,..., anA1, f (1(a1, a2,..., an)) = 2(f (a1), f (a2),...,f (an)).
Monomorfismo se f è una funzione iniettiva, epimorfismo se f è suriettiva, isomorfismo se f è biunivoca.
Sottogruppo normale: per ogni hH e per ogni aA si ha a-1haH (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. Cardinalità: numero degli elementi.
Nucleo di un omomorfismo di gruppi è il sottoinsieme di X costituito dai punti che vengono portati dalla funzione nell'elemento neutro di Y.
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.
Teorema di 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. Il nucleo dell’omomorfismo è un sottogruppo normale di < A, × >;
3. < A / Nf , • > è isomorfo a < T, * >.
Un sottoanello I di < A, +, × > si dice ideale di < A, +, × > se per ogni iI e per ogni aA si ha iaI ed aiI.
