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

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 ri-

→ →

∈

spetto 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 tale che la

- 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 iniettive/suriettive/biezioni g ◦ f iniettiva/suriettiva/biezione

→ → →

- g ◦ f iniettiva f iniettiva; g ◦ f suriettiva g suriettiva; g ◦ f biezione f iniettiva e g suriettiva

→