Fondamenti dell'Informatica

Proprietà dell'algebra booleana

⊔M ⊓M, allora il poset è un reticolo completo;

Í ¹ ¹P(S)∀M ⊔M ∅ ⊓M ∅➢ Complementazione: Sia <S, un reticolo limitato. x’ è complemento di x se≤>x x’ = 0 x x’ = 1, quindi se per ogni elemento a del reticolo esiste un⊓ ∧ ⊔elemento b tale che a b = 0 (minimo) e a b = 1 (massimo);⊓ ⊔➢ Limitazione: Se esiste un elemento minimo e uno massimo il reticolo èlimitato. Se nel reticolo sono presenti elementi che hanno più di un complemento, allora il reticolo non è distributivo. Se il reticolo non è limitato, non è nemmeno complementato. 11Un reticolo nel quale valgono le proprietà di distributività, completezza, complementazione e limitazione è un’algebra booleana, su cui si basano tutti icalcolatori ad eccezione delle macchine quantistiche.

ALGEBRA BOOLEANA}B = <⊔, ‘, 0, 1, x>⊓, Vi è corrispondenza tra algebracINS = <∪,

, T, x>∩, ∅, booleana e teoria degli insiemi

ASSIOMI ALGEBRA BOOLEANA

Dicitura corrispondente

teoria insiemistica

Proprietà commutativa:

x y = y x

x y = y x

x⊔ = ⊔ x

x⊓ = ⊓ x

Proprietà distributiva:

x (y z) = (x y) z

x (y z) = (x y) z

x⊔ (⊔ y) z = (x⊔ ⊔ y) z

x⊓ (⊓ y) z = (x⊓ ⊓ y) z

Proprietà dello 0:

x 0 = x

x = x

x⊔ 0 = x

x⊓ 0 = 0

Proprietà dell’1:

x 1 = 1

x 1 = T

x⊔ 1 = x

x⊓ 1 = x

Complementarietà:

x x’ = 1

x x = T

c(x x’) = 0

x x =⊓ ∩ ∅

PRINCIPIO DI DUALITÀ

D D D D

Se x = y

x = y

dove x è il duale di x e y è il duale di y.

Quindi, se un enunciato è dimostrabile mediante gli assiomi delle algebre di Boole anche il suo duale lo è.

Esempi:

® D x = 0

x = 1

® D x = 1

x = 1

® D x y

(x y)⊔ ⊓®c c Dx x (x x ) = 0∩ ∪

Il principio di dualità permette di dimezzare gli assiomi definiti sopra.

LEGGI DI DE MORGAN

Formulate dal matematico Augustus De Morgan nell’Ottocento.

Stabiliscono una relazione di equivalenza tra gli operatori e∪ ∩.

➢ c c c1^ legge: (x y) = x y∩ ∪

➢ c c c2^ legge: (x y) = x y∪ ∩ 12

PORTE LOGICHE

Circuiti = <OR, AND, NOT, 0, 1, X>

➢ OR: : se passa corrente in uno dei due fili passa in uscita;

➢ AND: : se e solo se passa in entrambi i fili passa in uscita;

➢ NOT: : se passa in ingresso non passa in uscita;

➢ XOR: : passa in uscita se e solo se passa in un filo;

➢ NOR: : passa in uscita se non passa da nessun filo (not or);

➢ NAND: : passa solo se non passa da entrambi i fili (not and);

➢ XNOR: : passa solo se passa da entrambi i fili o da nessuno (not xor).

13

TABELLE DI VERITÀ

OPERATORE SIMBOLO INPUT A INPUT B RISULTATO

0 0 0

0 1 1

OR 1 0 1

1 1 1

0 0 0

0 1 0

AND 1 0 0

1 1 1

0 / 1

NOT 1 / 0

0 0 0

1. 1 XOR 1 0 11 1 00 0 10 1
2. 0 NOR 1 0 01 1 00 0 10 1
3. 1 NAND 1 0 11 1 00 0 10 1
4. 0 XNOR 1 0 01 1 1

Quando si stila una tavola di verità, la prima operazione da svolgere è la stesura della tabella: detto il numero di variabili da confrontare, la tabella dovrà avere 2 righe. È consigliabile procedere a partire dall'operatore più interno.

PROPRIETÀ SU INSIEMI INFINITI

Al matematico italiano Giuseppe Peano si deve la definizione, ancora oggi adoperata, dei numeri naturali, oltre che la formulazione del principio di induzione.

PRINCIPIO DI INDUZIONE (DEL 1° ORDINE)

Data una proprietà P(x), x ∈ X, per dimostrare secondo il principio di induzione che P vale su tutto X si procede come di seguito:

1. CASO BASE: si verifica la validità di P(0);
2. CASO PASSO:
   • HIPOTESI: P(x) ipotesi induttiva;
   • TESI: P(S(x)) si verifica la validità della tesi.

LOGICA PROPOSIZIONALE

Un qualsiasi linguaggio L si avvale di un insieme

finito di simboli, detto alfabeto, costituito da diverse componenti:

• VARIABILI PROPOSIZIONALI: p, q, r,…
• COSTANTI LOGICHE: ∧, ∨, ¬,
• SIMBOLI AUSILIARI: ( )
• Nient’altro è parte dell’alfabeto.

FORMULE BEN FORMATE (FBF) Le espressioni sintatticamente corrette della logica proposizionale (che servono a rappresentare degli enunciati sensati e non ambigui) sono chiamate formule ben formate (FBF) e sono definite nel seguente modo:

1. Tutte le variabili proposizionali sono fbf;
2. A B A B A B A B A A BÎ ® Î
3. Se , L, allora ( ), ( ), ( ), (¬ ) L, dove , sono metavariabili∧ ∨ sostituibili con una qualsiasi formula ben formata del linguaggio;
4. ÎNient’altro L.

OPERATORI LOGICI A meno della presenza di parentesi, l’ordine di precedenza degli operatori logici è:

• ®¬, ∧, ∨,

Nel caso vi sia un’espressione contenente più operatori logici dello stesso tipo ® adiacenti, ad

esempio p q r, è necessario dichiarare l'ordine di precedenza daadoperare. 15La riduzione degli operatori inclusi nel linguaggio può essere vantaggiosa in terminidi economia di scala, ma può comportare un aumento della lunghezza delleespressioni che vanno a sostituire gli operatori esclusi.

TEOREMI E DIMOSTRAZIONI
A è definita come espressione dimostrabile attraverso la logica proposizionale, quindi un teorema della logica proposizionale.

DIMOSTRABILITÀ
⊢: A: partendo dalle ipotesi si dimostra la tesi A servendosi di lemmi, ossia teoremi Γ⊢già noti in precedenza.
Un altro metodo di dimostrazione è quello per assurdo, nel quale si nega la tesi e siarriva alla contraddizione di almeno un'ipotesi.

TABLEAU
T,F FA,T
A: formule segnate
T-REGOLE F-REGOLE
¬,∧,∨,⊢A? FA...C /C /…/C1 2 n
È possibile dire che A è dimostrabile se si trova un tableau che inizia con FA

E taletableau è chiuso, ossia tutte le configurazioni contengono almeno una coppiacomplementare. Per risolvere un tableau solitamente si procede a partire dall'operatore più esterno.

TEOREMA DI CHURCH-ROSSER
Nell'ambito della logica proposizionale, il teorema di Church-Rosser afferma che, quando si applicano regole di riduzione ai termini, l'ordine in cui vengono scelte le riduzioni non fa differenza per il risultato finale, quindi se un tableau deve chiudersi giungerà alla chiusura.

SEMANTICA DELLA LOGICA PROPOSIZIONALE
Comprendere il significato dei simboli utilizzati all'interno di un linguaggio ed estendere tale concetto alle formule ben formate corrisponde ad esplicitare il sistema formale di una semantica.

• Variabili proposizionali: ogni variabile proposizionale può essere vera o falsa, ma non entrambe;
• FBF: Tautologiche o valide: sempre vere;
• Contraddizioni o invalide: sempre false;
• Soddisfacibili: talvolta vere, talvolta false.

Le interpretazioni che rendono vera la formula si dicono modelli, quelle che la rendono falsa sono note come contromodelli.

TEOREMA DI CORRETTEZZA E DI VALIDITÀ

Esiste una relazione di doppia implicazione tra tautologia e tableau chiuso, ossia ogni formula con tableau chiuso è una tautologia e tutte le tautologie hanno tableau chiuso.

Quando si ha di fronte un tableau aperto, per determinare se una formula è soddisfacibile o una contraddizione, si risolve il tableau partendo da T invece che da F. Se si ottiene un tableau chiuso allora la formula è una contraddizione, altrimenti è soddisfacibile.

TEOREMA DI DEDUZIONE

Se ho una dimostrazione di B a partire da A, allora e solo allora posso dimostrare che A implica B:

⊢ ®A B A B ⊢

⊢ ®B BΓ ⊢ Γ

Il simbolo ⊢ non è compreso nel linguaggio, è quindi metalinguistico. Attraverso ⊢, questo teorema, che lega a simbolo che invece è incluso

all'interno del linguaggio, si traduce un simbolo metalinguistico in uno linguistico. LOGICA PREDICATIVA (DEL 1° ORDINE) Una logica predicativa L ha un proprio alfabeto, un suo linguaggio, un apparato deduttivo a tableaux e una sua semantica. ALFABETO DI L Come nella logica proposizionale, anche nella logica predicativa ci si avvale di un alfabeto, ossia un insieme finito di simboli, costituito da diverse componenti: - VARIABILI INDIVIDUALI: x, y, z - COSTANTI LOGICHE: ∧, ∨, ¬ - QUANTIFICATORI: ∀, ∃ - Nient'altro alfabeto. SEGNATURA DI L (PARAMETRI) Ogni logica predicativa ha la propria segnatura. - COSTANTI INDIVIDUALI: a, b, c - FUNZIONI: f, g, h, n, k, w (gli indici rappresentano l'arietà; sono eseguibili solo su termini dello stesso tipo e ritornano un valore di tipo analogo a quello dei primi due) - PREDICATI: P, Q, R, ... (esprimono relazioni tra le espressioni alle quali vengono applicati o, nel

caso l'età sia 1, esprimono una proprietà dell'espressione a cui sono legati)FBF➢ È vero che ogni predicato, con la sua arietà, FBF;➢ A B A B A B A B A A BÈ vero che se , FBF, allora ( ), ( ), ( ), (¬ ) FBF, dove , sono sostituibili con una qualsiasi FBF;➢ È vero che se x è una variabile individuale, (∀x P(x)), (∃x P(x)) FBF;➢ È vero che se P , t , t ,... termini, allora P(t , t ,... t ) FBF;1 2 1 2 n➢ È vero che nient'altro FBF. 18Una FBF è chiusa se tutte le variabili sono quantificate, ossia se ogni variabile compare in una sottoformula preceduta da un quantificatore associato a tale variabile.TERMINI DEL LINGUAGGIO DI L➢ È vero che ogni variabile individuale termini;➢ È vero che ogni costante individuale termini;➢ f fÈ vero che se t , t ,... termini e linguaggio, allora (t , t ,... t ) termini;