Algebra Booleana PDF

Preview

Summary

Algebra booleana teoria, esempi e ambiti applicativi...

Description

-

-

-

ALGEBRA BOOLEANA Proposizioni: frase alla quale può essere attribuito un valore di verità: vero o falso, posso fare corrispondere a una frase un valore, ad es. a vero e a falso posso associare un valore, 1 o 0 - a tutte le proposizioni posso associare un valore Logica: in filosofia, lo studio delle funzioni proprie della struttura e dell’attività del pensiero di sè (L. formale - organizzazione di un ragionamento), oppure dei procedimenti seguiti dal pensiero in riferimento ai diversi contenuti cui può applicarsi (L. materiale) Logica matematica (o simbolica) è lo studio delle operazioni logiche che le formalizza in linguaggio matematico

ALGEBRA BOOLEANA - George Boole 1815-1864 In matematica, informatica ed elettronica, l'algebra di Boole è un ramo dell'algebra astratta che comprende tutte le algebre che operano con variabili booleane o logiche che possono assumere i soli valori di verità 0 o 1 → L'algebra booleana è finalizzata al calcolo proposizionale. - "Rossi (identificato da CF) è un dipendente dell'industria XXX (identificato da P.IVA - sai P.IVA che CF sono necessari per la proposizione) e il giorno x è residente a Milano" è vera se

A e B, Rossi appartiene all’intersezione dei due sistemi - legato al fatto che ho utilizzato il connettivo e (ad entrambi i sistemi), se sostituissi il connettivo o, il signor rossi apparterrebbe a … o … oppure a tutte e due senso inclusivo - "x è un numero divisibile per 4 o (in senso inclusivo OR) per 5" è vera se x = 4n oppure x = 5n con n numero intero quindi appartiene all’unione (≠ o in senso esclusivo XOR: unione - intersezione)

x = 4n oppure x = 5n con n numero intero quindi appartiene all’unione - "La popolazione dell'Italia non (vanno bene entrambi) è superiore a 100 milioni" è vera se la popolazione dell'Italia è minore o uguale a 100 milioni.

la popolazione dell'Italia è minore o uguale a 100 milioni. Calcolo proposizionale abbiamo delle proposizioni atomiche (sono quelle alle quali associo un valore di verità ma non sono composte da proposizioni più elementari), ad ognuna di queste associo un valore di verità: a vero faccio corrispondere il valore 1, a falso il valore 0 e quindi traduco una proposizione nell’operazione tra valori di verità Quali sono le operazioni che mi permettono di costruire un’operazione complessa?

AND: ∧, ∘, ⋂ OR: ∨, +, ⋃ XOR: ⊻, ⊕ (unione - intersezione) NOT: ￢, (complementare) → connettivi

A and B A or B A xor B A not A → proposizioni composte

Come le rappresento? uso le tavole delle operazioni - AND: quando entrambe sono vere, AND sarà vero (1) - SOLO in questo caso, negli altri casi è falsa - OR: quando sono entrambe false, OR sarà falso (0) - SOLO in questo caso, negli altri casi è vera - NOT: se a è falso, NOT è vero - se a è vero, NOT è falso

Esercizio A: Vero 1 B: Falso 0 C: Vero 1 qual è il valore di verità delle seguenti espressioni? - A or (not B and C) A+(- B ∘ C)

-

A and Falso

A∘0

-

B or Vero

B+1

-

A and B and C (0) not (A and C)

-

A∘B∘C - (A ∘ C)

A or (1 1) → ho OR, a meno che non siano entrambe false, è vero - in questo caso sarà Vero (1) Oppure, si poteva guardare anche solo “A or”, essendo vera, Vero (1) Ho un falso, sarà sicuramente Falso (0) (AND con falso è sempre falso CONTRADDIZIONE) Or è falso solo quando sono entrambi falsi, in questo caso quindi sarà Vero (1) (OR con una qualunque proposizione è sempre Vera - AUTOLOGIA) Almeno una delle tre è falsa, Falsa NOT (1) → Falso (0)

in Excel è possibile implementare gli operatori logici utilizzando le funzioni logiche: E (A1;B1) → operatore AND O (A1;B1) → operatore OR NON (A1) → operatore NOT dovrò costruire una tabella con tutte le possibili combinazioni (23=8, se fossero 4 sarebbe 24, copio due volte quelle già inserite e aggiungo in D 8 volte 1 e 8 volte 0)

→ inserisco le funzioni logiche per determinare se vero o falso E (A1;B1) → operatore AND O (A1;B1) → operatore OR NON (A1) → operatore NOT

→ formula per Vero (1) e Falso (0) posso trascinare in basso per estendere il risultato a tutte le altre combinazioni

Analogamente posso estendere questo ragionamento a tutte le altre funzioni

Proprietà Gli operatori introdotti godono di numerose proprietà: - Commutativa e associativa - Distributiva A and ( B or C ) = ( A and B ) or ( A and C ) - A or ( B and C ) = ( A or B ) and (A or C) - Involutiva: not not A = A - A and A = A A or A = A - A or (notA) = Vero A and (notA) = Falso

→ Verificare la proprietà distributiva → Legge di De Morgan

L'implicazione logica può essere vista anche come una relazione, due proposizioni sono in relazione se il risultato dell'operatore logico implicazione è VERO, questo aspetto è particolarmente evidente nel linguaggio comune dove l'implicazione è espressa nella forma “se A allora B”, così ad esempio ci risulta naturale la comprensione di: “se piove allora ci sono nuvole in cielo“ l'unica possibilità che tale affermazione sia falsa è quella di verificare che in un dato momento piova (vero) e NON ci siano nuvole in cielo (falso)

dalla tabella alla funzione booleana F: prodotto cartesiano di (0;1)x(0;1) → (0;1) → Proprietà distributiva

min 1.20 + slide

Applicazione dell’algebra booleana - nelle formule di excel - nella riga dei criteri nelle query di access - nei motori di ricerca - nei linguaggi di programmazione - nella progettazione dei circuiti logici - nella crittografia...