Logica - formulario esame

Insiemi

∪ ∪• De Morgan: C(A B) = CA ∩ CB e C(A ∩ B) = CA CB (C = complementare)

∩ ∪• De Morgan generalizzata: C S (∪_i∈I Ai) = ∩_i∈I CAi e C(∩_i∈I Ai) = ∪_i∈I CAi∪ ∪ ∪ ∪ ∪ C) (C qui è un insieme)

• Distributività: A ∩ (B C) = (A ∩ B) (A ∩ C) e A (B ∩ C) = (A B) ∩ (A (B ∩ C))

Relazioni

Proprietà delle relazioni binarie

Una relazione binaria R su A si dice:

• Riflessiva se a R a per ogni a A
• Irriflessiva se ¬(a R a) per ogni a A
• Simmetrica se da a R b segue che b R a
• Antisimmetrica se da a R b e b R a segue che a = b
• Transitiva se da a R b e b R c segue che a R c

Relazione di equivalenza su A è: riflessiva, simmetrica e transitiva su A.

Classe di equivalenza di un elemento a A rispetto ad E [a]_E def = {x A | x E a}.

L'insieme quoziente è l'insieme di tutte le classi di equivalenza: A/E def = {[a]_E | a∈ A}.

Relazione d'ordine su A è una relazione riflessiva, antisimmetrica e transitiva su A. Ordine lineare o totale se a R b o b R a per ogni scelta di a, b A. Un ordine che non sia lineare si dice anche ordine parziale. Un elemento a A tale che b R a per ogni b A si dice massimo; un elemento a A tale che a R b per ogni b A si dice minimo.

Definizione (Ordine stretto). Un ordine stretto su A è una relazione irriflessiva su A.

Pre-ordine o quasi ordine su A è riflessiva e transitiva.

Funzioni

Composizione di due funzioni: f : A → B e g : B → C: g ◦ f : A → C, a → g(f(a))

Se f e g sono iniettive/suriettive/biezioni, allora g ◦ f è iniettiva/suriettiva/biezione

g ◦ f iniettiva se f è iniettiva; g ◦ f suriettiva se g è suriettiva; g ◦ f è una biezione se f è iniettiva e g è suriettiva.

Dimostrare la suriettività: si considera f(x) = y come un'equazione e la si risolve in favore di x.

Stringhe

Stringhe finite (su A) è una sequenza finita di simboli provenienti da A. L'insieme di tutte le stringhe finite su A si indica con A∗.

Stringa vuota è ε. La lunghezza di una stringa s è indicata con lh(s) ed è il numero di simboli che vi compaiono.

L'insieme delle stringhe su A di lunghezza n è il prodotto cartesiano Aⁿ.

Stringhe infinite (su A) è una sequenza infinita di simboli provenienti da A. L'insieme di tutte le stringhe infinite su A si indica con A^ℕ.