Formulario

Page 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, d iagonale 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…