Appunti di Informatica

INFORMATICA

1. Algebra Booleana

venne inventata da George Boole, un matematico che voleva capire la verità di

L’algebra Booleana

una formula molto lunga, partendo dalla verità delle singole parti componenti; ci sono due possibilità:

1 (vero) e 0 (falso). Ogni variabile delle formule deve avere un dominio di definizione. Aveva diversi

obiettivi: riuscire ad estrarre le informazioni utili a risolvere un problema, essere in grado di

formalizzare e risolvere un problema analizzando tutti i casi possibili, saper ricavare il valore di verità

delle formule a partire da valori di verità noti.

Gli assiomi sono le regole che identificano questo tipo di algebra (non devono essere dimostrati,

xB,

perché sono così): consistenza (0,1∈B), chiusura (x,yB, x+yB), identità (0B tale che

x+0=x), inversione (xB, x+(-x)=1), commutatività (x,yB, x+y=y+x) e distributività (x,y,zB,

x+(y•z)=(x+y)•(x+z)). Vige anche il principio di dualità, secondo cui se T è un teorema dell’algebra

booleana, allora lo è anche il duale ottenuto da T rimpiazzando + con •, 0 con 1 e viceversa.

Gli operatori sono: B, +, •, -, 0, 1, e presentano diverse proprietà algebriche: associativa (x+(y+z) =

(x+y) + z, x•(y•z) = (x•y) • z), idempotenza (x+x = x, x • x = x), involuzione (--x = x), x•(-x) = 0 e

assorbimento (x+(x•y) = x, x•(x+y) = x).

L’algebra booleana si basa sulla logica, detta del primo ordine; ve ne sono diverse: la logica formale

(studio delle leggi e delle funzioni che caratterizzano la struttura del pensiero in sé), la logica

materiale (studio dei procedimenti seguiti dal pensiero in riferimento ai diversi contenuti cui può

applicarsi) e la logica matematica (studio della formalizzazione dei procedimenti e delle operazioni

logiche in linguaggio matematico). Una formula, invece, è un’espressione ben formata del linguaggio

alla quale può essere attribuito un valore di verità, vero o falso.

Una proposizione è una formula in cui sono presenti delle variabili; una volta che è stato assegnato,

il valore di verità deve essere sempre lo stesso; gli eventi futuri non sono proposizione, mentre per

quanto riguarda quelli temprali, devono essere specifici. Per quanto riguarda la circolarità, le frasi

possono essere vere, mentre alcune possono anche richiamarne altre. Le proposizioni possono

anche contenere connettivi, e vengono dette proposizioni composte; i connettivi possono essere:

  ; , ;  ;

NOT, NON, , -; AND, E, , •, OR, O, +, XOR, , IF...THEN, SE...ALLORA; IFF, SSE.

Le formule che non contengono connettivi vengono dette atomiche; se li contengono vengono dette

formule composte molecolari. Tutti i connettivi sono binari, tranne la negazione che è unario.

Una formula composta particolare, che viene interpretata sempre come vera, viene detta tautologia;

le formule sempre false, invece, vengono dette contraddizioni.

Ci sono diverse tavole di verità:

Le formule possono contenere anche delle variabili, che vengono indicate con le lettere minuscole.

Con riferimento alle Leggi di De Morgan, queste sono due regole valide per le operazioni

insiemistiche, che mettono in relazione le operazioni di unione, intersezione e complementazione.

Sono costituite da 2 leggi:

1) NOT (A AND B) = (NOT A) OR (NOT B)

2) NOT (A OR B) = (NOT A) AND (NOT B)

Le leggi di De Morgan sono utili per negare espressioni complesse; inoltre, mostrano che i 3

operatori AND, OR e NOT non sono indipendenti. È possibile esprimere AND attrvaverso OR e NOT:

A and B = not not (A and B) = not ((not A) or (not B)). Allo stesso modo, è possibile esprimere OR

tramite AND e NOT: A or B = not not (A or B) = not ((not A) and (not B)).

 

A B (-A • B) + (A • (-B))

Per quanto riguarda l’implicazione logica, questa avviene attraverso congiunzioni quali IF, THEN e

IFF. A implica B: A è condizione sufficiente per B, mentre B è condizione necessaria per A. NOT

➢ A OR NOT B. → →

L’equivalenza logica è .

➢ (A B) • (B A)

Un altro operatore è NAND, che comprende AND, OR e NOT.

not A = A nand A

➢ A and B = not not (A and B) = not (A nand b) = (A nand B) nand (A nand B)

➢ A or B = not not (Aor B) = not (not A and not B) = (not A) nand (not B) = (A nand A) nand (B

➢ nand B) A B A nand B

V V F

V F V

F V V

F F V

Gli operatori booleani possono essere usati: nelle formule di Excel, nella riga dei criteri nelle query

di Access, nei motori di ricerca in Internet, nei linguaggi di programmazione, nella progettazione dei

circuiti logici e nella crittografia. A B

0 0 0

0 1 1

1 0 1

1 1 1

2. Rappresentazione dell’informazione

Proprio perché l’informazione è qualcosa di astratto, per poterla utilizzare è necessario

rappresentarla; in un calcolatore viene rappresentata attraverso le cifre binarie. I sistemi di

principali sono 2: sistema decimale e sistema esadecimale.

rappresentazione

Il sistema decimale viene chiamato così perché i simboli sono 10, da 0 a 9; per poter scrivere un

numero si moltiplica ogni numero per 10, elevato alla sua posizione: si trova, così, il peso nascosto

associato alla sua posizione:

Per trasformare un numero in sistema decimale all’interno di un calcolatore, si separa la parte intera

dalla parte decimale, e si calcola il resto.

Per passare da base 2 a base 16 (sistema esadecimale) si raccolgono i numeri in gruppi da 4, e per

ogni gruppo si scrivono