Riassunto esame Informatica, prof. Gnudi, libro consigliato Progettazione dei database, Lorenzi

Algebra booleana / Logica

L'algebra booleana è un ramo dell'algebra che opera con variabili logiche che possono assumere i soli valori di verità 0 (falso) o 1 (vero). Essa è finalizzata al calcolo proposizionale (proposizione = frase alla quale può essere attribuito un valore di verità).

Operatori logici / Connettivi

• Congiunzione A AND B, ∧, ∩: V se entrambe sono V
• Alternativa A OR B, +, ∨: V se almeno una è V
• Alternativa esclusiva A XOR B, ⊕: V se una è V e l'altra è F
• Negazione NOT A, −, ¬
• Implicazione IF A THEN B, ⇒: Risolvo notA or B
• Coimplicazione A IFF B, ⇔, ≡, =: V se entrambe sono uguali
• NOT (A AND B): A NAND B
• NOT (A OR B): A NOR B

Tavola di verità

Esercizi

1) Se A=V, B=F, C=V quale è il valore di verità delle seguenti espressioni?

• A or (notB and C): V or (V and V) = V or V = VERO
• A and Falso: V and F = FALSO
• B or Vero: F or V = VERO
• A and B and C: V and F and V = F and V = FALSO
• Not (A and C): not (V and V) = not V = FALSO

2) Se A=V, B=V, C=F quale è il valore di verità delle seguenti espressioni?

• A xor (B or C): V xor (V or F) = V xor V = FALSO
• A xor B xor C: V xor V xor F = F xor F = FALSO
• (A and B) xor C: (V and V) xor F = V xor F = VERO

3) Costruire la tavola di verità delle seguenti espressioni

A or V = V; A and F = F; not not A = A (dipende da A)

4) Verificare che la tabella di verità A ⇒ B coincide con quella notA or B

5) Verificare che la tabella (A ⇒ B) · (B ⇒ A) coincide con quella A ≡ B

Proprietà degli operatori logici

• Identità / Elemento neutro: A OR 0 = A, A AND 1 = A
• Elemento nullo: A OR 1 = 1, A AND 0 = 0
• Idempotenza: A OR A = A, A AND A = A
• Involuzione: NOT (NOT A) = A
• Inversa / Complementare: A OR (NOT A) = 1, A AND (NOT A) = 0
• Commutativa: A OR B = B OR A, A AND B = B AND A
• Associativa: A OR (B OR C) = (A OR B) OR C, A AND (B AND C) = (A AND B) AND C
• Distributiva: A OR (B AND C) = (A OR B) AND (A OR C), A AND (B OR C) = (A AND B) OR (A AND C)
• Assorbimento: A OR (A AND B) = A, A AND (A OR B) = A
• Leggi di De Morgan: NOT (A OR B) = (NOT A) AND (NOT B), NOT (A AND B) = (NOT A) OR (NOT B)

Esercizi con De Morgan

Con le leggi di De Morgan si dimostra che AND, OR, NOT non sono indipendenti e sono utili per semplificare espressioni complesse. Bisogna scambiare gli operatori AND e OR e cambiare il valore di verità di tutti i termini.

• Not (A and B or C): notA or notB and notC
• Not (A or (B and notC)): notA and notB or C
• Not (N > 7 or (X > 0 and X < 5)): not (N > 7) and not (X > 0) or not (X < 5), N ≤ 7 and X ≤ 0 or X ≥ 5
• Not (X > 5 or N < 1000): not (X > 5) and not (N < 1000), X ≤ 5 and N ≥ 1000
• A and B: not not (A and B), not [(notA) or (notB)]

Tautologia e Contraddizione

Si dice tautologia una proposizione sempre vera per ogni valore di verità delle proposizioni che la costituiscono. Si dice contraddizione una proposizione sempre falsa per ogni valore di verità delle proposizioni che la costituiscono.

Funzioni booleane

Funzioni le cui variabili sono booleane e il valore è 0 o 1.

Esercizio

Ricavare le espressioni booleane per le seguenti funzioni:

1. Guardo dove la funzione è VERA e da lì costruisco l'espressione:
   • Riga 3 A=V B=F F(A,B) = A and (notB)
   • Riga 4 A=F B=F F(A,B) = (notA) and (notB)
2. La funzione è data dall'OR fra le due espressioni (perché vera in uno dei due casi):
   A and (notB) or (notA) and (notB)
3. Semplifico l'espressione con gli operatori booleani e le proprietà:
   • not {[notA or B] and [A or B]} (leggi di De Morgan)
   • not [B or (notA and A)] (proprietà distributiva)
   • not (B or Falso) = notB (B or Falso = B)

Rappresentazione dell'informazione

Un sistema di numerazione è caratterizzato da un insieme di cifre e da un insieme di regole che identificano le rappresentazioni e permettono di identificare in modo univoco i valori rappresentati. In un sistema di numerazione posizionale, il valore associato a ciascuna cifra del numero dipende dalla posizione di tale cifra e dalla base (ovvero dall'insieme di cifre utilizzato).

Esempio

In base dieci la rappresentazione di 5432,23 corrisponde al valore: (5 × 1000) + (4 × 100) + (3 × 10) + (2 × 1) + (2 × 0,1) + (3 × 0,01) = 5432,23

Sistema binario

• E' basato su due simboli: 0 e 1 (detti BIT - Binary Digit).
• La base viene rappresentata come (10)_B.
• Il massimo valore decimale rappresentabile con n cifre binarie è: 2ⁿ - 1.

Unità di misura delle memorie

• 1 Byte = 8 bit = 1B
• 1 KB = 1024 B = 2¹⁰ B
• 1 MB = 1024 KB = 2²⁰ B
• 1 GB = 1024 MB = 2³⁰ B

Da binario a decimale

• (101000)_B = 32 + 8 = 40
• (111111111)_B = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1023

Da decimale a binario

Esempio di conversione con divisione per 2:

• 35: 100011_B
• 50: 110010_B

Operazioni in sistema binario

Addizione

• (11 + 1)_B = (100)_B
• (101 + 11)_B = (1000)_B

Sottrazione

• (100 - 1)_B = (11)_B
• (100 - 11)_B = (1)_B

Moltiplicazione

• (1101 × 110)_B = (1001110)_B
• (111 × 100)_B = (11100)_B

Divisione

• (10011 : 11)_B = (110,1)_B
• (111 : 100)_B = (1,11)_B

Sistema esadecimale

• E' basato su 16 simboli: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
• La base viene rappresentata come (10)_H.
• Il massimo valore decimale rappresentabile con n cifre esadecimali è: 16ⁿ - 1.

Da binario a esadecimale

• (1110)_B = 14 = (E)_H
• (1111)_B = 15 = (F)_H
• (10000)_B = 16 = (10)_H
• (11111111)_B = (FF)_H
• (101010111100)_B = (ABC)_H
• (1111,101)_B = (F,A)_H

Da esadecimale a binario

• (7B)_H = (0111 1011)_B
• (E5F)_H = (1110 0101 1111)_B
• (7B,1A)_H = (0111 1011, 0001 1010)_B

Questi metodi possono essere applicati anche nel caso in cui si considerino basi b = 2^k, in questo caso le cifre binarie saranno da raggruppare in blocchi di k.

Esempi

• (111 001 011 111, 001 000)_B = (7137,1)
• (11 10 01 01 11 11, 00 10)_B = (321133,02)
• (76)_H = (111 110)_B

Esempi di rappresentazioni in base 2 e 16

Indirizzi IP

• Numero che identifica univocamente i dispositivi collegati con una rete informatica che utilizza lo standard IP (Internet Protocol).
• Sono composti da 4 numeri memorizzati con 4 Byte (ogni Byte è composto da 8 bit, quindi 32 bit totali).
• Ciascuno di questi numeri può variare da 0 a 255.
• Il numero massimo di indirizzi IP possibili è: 2³² = 4 Giga.
• Indirizzo IP più grande: (255. 255. 255. 255) = (FF . FF . FF . FF)_H = 4 Giga - 1
• La prima parte dell'indirizzo IP è riservata alla RETE, la seconda all'INTERFACCIA/HOST secondo una suddivisione in classi caratterizzata dai valori dei primi 3 bit.

Classi di indirizzi IP

• Classe A: 0111 1111. 1111 1111. 1111 1111. 1111 1111 = 128 RETI 16 000 000 HOST
• Classe B: 1011 1111. 1111 1111. 1111 1111. 1111 1111 = 16 000 RETI 64 000 HOST
• Classe C: 1101 1111. 1111 1111. 1111 1111. 1111 1111 = 2 000 000 RETI 256 HOST

Colori RGB (Red, Green, Blue)

• Nome di un modello di colori di tipo additivo che si basa su 3 colori: rosso, verde e blu.
• Tonalità dei 3 colori: da 0 a 255 (decimale), Da 00 a FF (esadecimale).

Esempio di colori RGB

• Rosso: 255 0 0 = FF 00 00
• Verde: 0 255 0 = 00 FF 00
• Blu: 0 0 255 = 00 00 FF
• Nero: 0 0 0 = 00 00 00
• Bianco: 255 255 255 = FF FF FF
• Giallo: 255 255 0 = FF FF 00

16 000 000 circa di colori RGB possibili, 256 gradazioni di grigio.

Rappresentazione interna

La rappresentazione interna di un numero riguarda un insieme limitato di valori.

Rappresentazione interna dei numeri interi

Interi senza segno

Con n cifre binarie l'intervallo di valori che si possono rappresentare è [ 0 ; 2ⁿ - 1].

Esercizi

1. Usando 10 bit per rappresentare gli interi senza segno, quali interi si possono rappresentare?
   10 bits → Gli interi senza segno che si possono rappresentare con 10 bit vanno da 0 a 2¹⁰ - 1, da 0 a 1023.
2. Usando 24 bit per rappresentare gli interi senza segno, quali interi si possono rappresentare?
   24 bits → Gli interi senza segno che si possono rappresentare con 24 bit vanno da 0 a 2²⁴ - 1, da 0 a 16 000 000~.

Interi con segno

Segno e valore assoluto: La prima cifra denota il segno (1 = - 0 = +).

Esempi su 10 cifre binarie:

• +0 : 0000000000
• -0 : 1000000000
• +1 : 0000000001
• -1 : 1000000001

Con n cifre binarie l'intervallo di valori che si possono rappresentare è [ -2^n-1 ; +2^n-1 - 1 ].

Esercizi

1. Usando 10 bit per rappresentare gli interi con segno in complemento a 2, quali interi si possono rappresentare?
   10 bits → Gli interi con segno che si possono rappresentare con 10 bit vanno da -2⁹ a +2⁹ - 1, da -512 a +511.
2. Dovendo rappresentare il valore -5395 qual è il tipo di intero adatto a rappresentarlo? (Da scegliere tra gli interi con segno a 8, 16, 32 bit)
   8 bits: 2⁸ = 256 (no); 16 bits: 2¹⁶ = 65 536 (sì).
   16 bits → Gli interi con segno che si possono rappresentare con 16 bit vanno da -2¹⁵ a +2¹⁵ - 1, da -32 768 a +32 767.

Convertire un numero intero con segno in complemento a 2

1. Convertire (-101010)_B in complemento a 2 su 8 cifre.
   • Aggiungo a sx un tot di zeri fino ad arrivare a 8 cifre: 00101010
   • Sostituisco ogni cifra c con la differenza 1-c: 11010101
   • Sommo 1: 11010101+1=11010110
     • 214 è il numero che sommato a 42 mi dà 256 (2⁸)
2. Convertire (+101010)_B in complemento a 2 su 8 cifre.
   • Poiché il numero è positivo, devo solo aggiungere gli zeri: 00101010

Nota: Il procedimento di conversione per numeri negativi include il complemento (cambiando ogni cifra) e l'aggiunta di 1 per ottenere il complemento a 2.