LOGICA E ALGEBRA
Logica Proposizionale:
Una f.b.f. A è conseguenza semantica di un insieme Γ di f.b.f. , e si scrive Γ|=A, se ogni modello di Γ è un modello per A.
Teorema di deduzione semantica: Sia Γ un insieme di fbf. A è conseguenza semantica di Γ {B} se e solo se B A è conseguenza semantica di Γ.
Teorema: A è conseguenza semantica di Γ se e solo se Γ { A} è insoddisfacibile.
Una formula A è semanticamente equivalente a B (scriveremo A B) se tutti e soli i modelli di A sono modelli di B, in altre parole se A è conseguenza semantica di B e B è conseguenza semantica di A .
( A) A (A B) C A (B C) (A B) A B A A A A (A B) A A B A B A A A A (A B) A A B (A B) A A A A (A B) A B ( A A) B A B B A A (B C) (A B) (A C) B ( A A) B
A B B A A (B C) (A B) (A C) (A B) A B (A B) C A (B C)
SISTEMA L:
Assiomi di L: A1. A (B A) Inferenza di L: Modus Ponens (MP).
A2. (A (B C)) ((A B) (A C)) Da A e A B si riscrive B.
A3. ( A B) (( A B) A)
Teo di Correttezza e Completezza Forte: Sia Γ un insieme di fbf, Γ|=A se e solo se Γ|-L A.
SISTEMA R:
La risoluzione verifica se una formula A sia una tautologia (e quindi un teorema di L) o se sia deducibile da un insieme di formule Γ, provando rispettivamente l’insoddisfacibilità di A , o di Γ { Α}.
Una f.b.f. si dice in Forma A Clausole se è scritta come congiunzione di clausole. Le Clausole sono disgiunzioni di letterali. Letterali sono lettere enunciative o negazioni di lettere enunciative
Date le clausole C1, C2 ed R, R è una RISOLVENTE di C1 e C2 se esiste un letterale L C1 t.c. ~L C2 ed R=(C1 {L}) (C2 {~L}). Ossia date le clausole AB e AB la risolvente è A .
Un insieme di clausole Γ è insoddisfacibile se e solo se Γ|-r∷, dove ∷ indica la clausola vuota.
E quindi Γ|=A se e solo se Γ { A}|-r∷ (dopo aver ridotto in forma a clausole A e tutte le formule in Γ).
RELAZIONI E FUNZIONI
RELAZIONI:
Si chiama relazione R (n-aria o di arità n) fra gli n insiemi A1, A2, …, An un qualsiasi sottoinsieme di A1×A2×…×An.
Una qls relazione si può rappresentare con Matrice e Grafo di Incidenza. Prodotto tra relazioni si ottiene facendo prodotto tra matrici.
Una relazione binaria R su A che sia riflessiva, simmetrica e transitiva è relazione di equivalenza su A.
Siano Z l’insieme degli interi relativi ed n un intero maggiore di 1 fissato. La relazione R Z×Z definita ponendo (r,s) R se e solo se n divide r - s (scriveremo r s(mod n) per indicare che (r,s) R e n | m per dire che n divide m) è una relazione di equivalenza, detta relazione di congruenza modulo n.
Data una relazione di equivalenza ρ su un insieme A, per ogni a A, chiamiamo ρ -classe di a, l’insieme ρa={x A|
(a,x) ρ}-(denotata anche con [a]ρ).
L’insieme delle ρ -classi di A si dice insieme quoziente di A rispetto a ρ e si indica con A/ρ. Dunque A/ρ = {[a]ρ | a A}.
Notiamo che l’insieme quoziente di Z rispetto alla relazione di congruenza modulo n viene di solito indicato con Z/n e i suoi elementi vengono chiamati classi di resto modulo n; con considerazioni analoghe alle precedenti si prova che ci sono n classi distinte {0},{1},{2},...,{n - 1}, dove la generica classe {r} è formata dagli interi della forma nh+r.
Una relazione binaria R su A che sia riflessiva, antisimmetrica e transitiva è relazione d’ordine su A. Inoltre se per ogni coppia di elementi a, b di A si ha o (a,b) R o (b,a) R, R si dice relazione d’ordine totale. Se invece esistono due elementi in A tali che né (a,b) R né (b,a) R, tali elementi si dicono non confrontabili rispetto ad R.
FUNZIONI
Dati insiemi A e B finiti, f è una funzione se e solo se
Grafo: c’è uno e un solo arco uscente da ogni vertice che rappresenta un elemento di A, Matrice: c’è uno ed un solo 1 su ogni riga.
INIETTIVA: se ogni b B ha al più una controimmagine in A,ossia se f(a1) = f(a2) allora a1 = a2, o anche se a1 ≠ a2 allora f(a1) ≠ f(a2).
Grafo: da ogni vertice che rappresenta un elemento di A esce uno ed un solo arco e ad ogni vertice che rappresenta un elemento di B arriva al più un arco.
Matrice: su ogni riga c’è uno ed un solo 1 e su ogni colonna al più un 1.
SURIETTIVA: se ogni b B ha almeno una controimmagine in A, o anche se f(A) = B.
Grafo: da ogni vertice che rappresenta un elemento di A esce uno ed un solo arco e ad ogni vertice che rappresenta un elemento di B arriva almeno un arco.
Matrice: su ogni riga c’è uno ed un solo 1 e su ogni colonna almeno un 1.
BIUNIIVOCA: se è suriettiva ed iniettiva.
Grafo: da ogni vertice che rappresenta un elemento di A esce uno ed un solo arco e ad ogni vertice che rappresenta un elemento di B arriva uno e un solo arco.
Matrice: su ogni riga e su ogni colonna della matrice c’è uno ed un solo 1.
FATTORIZZAZIONE:
data f:A→B si ha che (a1,a2) ker(f) sse f(a1) = f(a2); ⁆ una funzione suriettiva h: A→A/ker(f) detta proiezione canonica. ⁆ poi un funzione iniettiva g: A/ker(f)→B cosi definita
([a],b) g sse (a,b) f
