Matematica III - l'algebra booleana

UGUAGLIANZE NOTEVOLI E TEOREMA DI DE MORGAN

Quelle riportate di seguito sono le cosiddette uguaglianze notevoli, proprietà che riguardano l'insieme vuoto, universo e il complemento.

negazione dello 0 e dell'1 = ¬0 1 1 0

convoluzione = a ⊕ a

elementi neutri a+0 = a a·1 = a

assorbimento del complemento + = +a ab a b.

Nell'algebra tradizionale era lecito e dunque consentito operare in questo modo: + = + = x y x z → y z

Ma nell'algebra booleana e nella manipolazione delle espressioni booleane occorre tener presente che non vale il principio di eliminazione così come applicato nei passaggi algebrici tradizionali, infatti esso vale unicamente se:

{ + = + x y x z → y z

· = · x y x z . Mediante questo teorema è possibile dimostrare che la somma negata di a e b è

Uno dei teoremi più importanti dell'algebra booleana è il teorema di De Morgan.

uguale al prodotto di a negato e b negato. Dualmente il prodottonegato di a e b è uguale alla somma di a negato e b negato.

TABELLE DI VERITÀ

In un’algebra finita una funzione può esser definita in forma tabellare, fornendo il valore della variabiledipendente per tutte le finite combinazioni di valori, delle n variabili indipendenti. Tali combinazioni sono equivalenti aiin cui una funzione è definita. Poiché l’algebra ha due valori, ciascun punto rappresenta una disposizione conpunti n.ripetizione di 2 valori su n posti. Il numero complessivo di numeri P sarà dunque dato da P = 2, poiché stabilisce una corrispondenza di valoriLa tabella che definisce una funzione si dice tabella di veritàdi verità della proposizione risultante e quelli delle proposizioni componenti.

Ä :ESEMPI ED ESERCIZI RICAVARE UNA FUNZIONE DALLA TABELLA DI VERITÀ

Supponiamo di voler verificare, tramite la tabella di verità,

Quando esiste la funzione analizzando, prendi multa volta per volta i valori di tre condizioni:

1. a) oltre il limite di velocità;
2. b) vigile assente;
3. c) semaforo rosso.

CONSIDERAZIONI INIZIALI

Prima di cominciare l'esercizio, dobbiamo preoccuparci di impostare il problema. Per semplicità, ad ogni condizione abbiamo assegnato una lettera, la stessa che compare nell'elenco scritto sopra. Quando si approccia ad un esercizio di questa tipologia, bisognerebbe domandarsi quanti valori al massimo la funzione può assumere. Per farlo, bisogna utilizzare la formula sopra scritta P = 2^{numero condizioni}, da cui P = 2³ = 8.

AVVERTENZE

Quando una condizione assume valore 0, significa che la stiamo presupponendo falsa, viceversa se assume valore 1, la stiamo presupponendo vera. Nel caso della prima riga della tabella potremmo tradurre le tre condizioni in questa proposizione: se la condizione di aver oltrepassato il limite di velocità è falsa, se è falsa la condizione b) e se è falsa la condizione c).

falso che il vigile è assente e se è falso che c'era il semaforo rosso, la funzione prendiMulta può essere considerata come (rendendo meglio: se non ho oltrepassato il limite di velocità, se il vigile è presente e se il semaforo non è vera? prendiMulta può essere considerata vera?) Bisogna analizzare tutte le possibili combinazioni di valori per riempire la tabella e arrivare a completarla: