Booleano

True

Sintassi

true

Semantica

true è vero

False

Sintassi

false

Semantica

false è falso

Variabili

Sintassi

<NAME>

Semantica

x è una proposizione della quale non conosciamo il valore: può essere vero o falso.

Negazione

Sintassi

¬ <BOOL>

Semantica

Se x è vero, ¬x è falso
Se x è falso, ¬x è vero

x¬x
falsovero
verofalso

Esempi

¬true è falso
¬false è vero
¬(¬x) ha lo stesso valore di x

Congiunzione

Sintassi

<BOOL> ∧ <BOOL>

Semantica

Se x e y sono veri, x∧y è vero
Altrimenti x∧y è falso

xyx ∧ y
falsofalsofalso
falsoverofalso
verofalsofalso
veroverovero

Esempi

true∧x ha lo stesso valore di x
false∧x è falso
x∧x ha lo stesso valore di x
x∧¬x è falso
x∧y ha lo stesso valore di y∧x

Disgiunzione

Sintassi

<BOOL> ∨ <BOOL>

Semantica

Se x è vero o se y è vero, x∨y è vero
Altrimenti x∨y è falso.

xyx ∨ y
falsofalsofalso
falsoverovero
verofalsovero
veroverovero

Una disgiunzione non indica necessariamente un'alternativa.

Semantica equivalente

Se x e y sono falsi, x∨y è falso
Altrimenti x∨y è vero.

Esempi

false∨x ha lo stesso valore di x
true∨x è vero
false∨x ha lo stesso valore di x
x∨x ha lo stesso valore di x
x∨¬x è vero
x∨y ha lo stesso valore di y∨x

Implicazione

Sintassi

<BOOL> ⇒ <BOOL>

Semantica

Se y è vero, x⇒y è vero;
Se x è falso e y è falso, x⇒y è vero;
Se x è vero e y è falso, x⇒y è falso.

xyx ⇒ y
falsofalsovero
falsoverovero
verofalsofalso
veroverovero

Una implicazione non indica necessariamente una causalità.

Semantica equivalente

Se x è vero e y è falso, x⇒y è falso;
Altrimenti x⇒y è vero.

Esempi

false⇒x è vero
true⇒x ha lo stesso valore di x
x⇒true è vero
x⇒false ha lo stesso valore di ¬x
x⇒x è vero
x⇒¬x ha lo stesso valore di ¬x
x⇒y ha lo stesso valore di (¬y)⇒¬x

Equivalenza

Sintassi

<BOOL> ≡ <BOOL>

Semantica

Se x ha lo stesso valore di y, x≡y è vero;

Altrimenti x≡y è falso.

xyx ≡ y
falsofalsovero
falsoverofalso
verofalsofalso
veroverovero

Esempi

false≡x ha lo stesso valore di ¬x
true≡x ha lo stesso valore di x
x≡x è vero
x≡¬x è falso
x≡y ha lo stesso valore di y≡x

Esercizi

A1 Scrivere in Caml un tipo di dato boolean che definisce le formule booleane.
A2 Scrivere una funzione string_of_boolean che trasforma una formula booleana in una stringa.

Altri operatori

Operatori binari

1
xyx ? y
falsofalsofalso
falsoverofalso
verofalsofalso
veroverofalso
2
xyx ? y
falsofalsofalso
falsoverofalso
verofalsofalso
veroverovero
3
xyx ? y
falsofalsofalso
falsoverofalso
verofalsovero
veroverofalso
4
xyx ? y
falsofalsofalso
falsoverofalso
verofalsovero
veroverovero
5
xyx ? y
falsofalsofalso
falsoverovero
verofalsofalso
veroverofalso
6
xyx ? y
falsofalsofalso
falsoverovero
verofalsofalso
veroverovero
7
xyx ? y
falsofalsofalso
falsoverovero
verofalsovero
veroverofalso
8
xyx ? y
falsofalsofalso
falsoverovero
verofalsovero
veroverovero
9
xyx ? y
falsofalsovero
falsoverofalso
verofalsofalso
veroverofalso
10
xyx ? y
falsofalsovero
falsoverofalso
verofalsofalso
veroverovero
11
xyx ? y
falsofalsovero
falsoverofalso
verofalsovero
veroverofalso
12
xyx ? y
falsofalsovero
falsoverofalso
verofalsovero
veroverovero
13
xyx ? y
falsofalsovero
falsoverovero
verofalsofalso
veroverofalso
14
xyx ? y
falsofalsovero
falsoverovero
verofalsofalso
veroverovero
15
xyx ? y
falsofalsovero
falsoverovero
verofalsovero
veroverofalso
16
xyx ? y
falsofalsovero
falsoverovero
verofalsovero
veroverovero 

 1: false
 2: x ∧ y
 3: x ∧ ¬y
 4: x
 5: ¬x ∧ y
 6: y
 7: (x ∧ ¬y) ∨ (¬x ∧ y) = x xor y = ¬(x ≡ y)
 8: x ∨ y 
 9: ¬x ∧ ¬y = ¬(x ∨ y)
10: (¬x ∧ ¬ y) ∨ (x ∧ y) = ¬(x xor y) = x ≡ y
11: ¬y
12: x ∨ ¬y = y ⇒ x
13: ¬x
14: ¬x ∨ y = x ⇒ y
15: ¬(x ∧ y) = x ⇒ ¬y = ¬x ⇒ y
16: true

Operatori n-ari

Sia un operatore f che prende n variabili x1, x2,...xn. Mostriamo per induzione che si può esprimere questo operatore con ¬, ∧, ⇒, true e false.

Caso di base:
Se n=0, il tale caso f è vero o falso.
Caso d'induzione:
si può scrivere f(x1,x2,...,xn) come (x1 ⇒ f(true,x2,...,xn)) ∧(¬x1 ⇒ f(false,x2,...,xn)):
  • Se x1 è vero, abbiamo
    (true ⇒ f(true,x2,...,xn)) ∧ (¬true ⇒ f(false,x2,...,xn))
    equivalente a
    f(true,x2,...,xn) ∧ true
    equivalente a
    f(true,x2,...,xn))
  • Se x1 è falso, abbiamo (falso ⇒ f(true,x2,...,xn)) ∧ (¬false ⇒ f(false,x2,...,xn))
    equivalente a
    true ∧ f(false,x2,...,xn)
    equivalente a
    f(false,x2,...,xn))
f(true,x2,...,xn)) e f(false,x2,...,xn)) sono operatori che prendono n-1 variabili.
Dunque con l'ipotesa d'induzione si possono scrivere con ¬,∧, ⇒, true and false.
Dunque anche f(x1,x2,...,xn).

Esempio:
x1x2x3f(x1,x2,x3)
falsofalsofalsovero
falso falsoverovero
falso verofalsofalso
falso veroverovero
vero falsofalsovero
vero falsoverofalso
vero verofalsofalso
vero veroverovero
Abbiamo f(x1,x2,..,xn) equivalente (x1 ⇒ f1(x2,...,xn)) ∧(¬x1 ⇒ f2(x2,...,xn)) dove
x2x3f1(x2,x3)f2(x2,x3)
falsofalsoverovero
falsoverofalsovero
verofalsofalsofalso
veroveroverovero
Abbiamo f(x1,x2,x3) equivalente (x1 ⇒ ((x2 ⇒ f3(x3)) ∧(¬x2 ⇒ f4(x3)))) ∧(¬x1 ⇒ ((x2 ⇒ f5(x3)) ∧(¬x1 ⇒ f6(x3)))) dove
x3f3(x2,x3)f4(x2,x3)f5(x2,x3)f6(x2,x3)
falsofalsoverofalsovero
veroverofalsoverovero
Abbiamo f(x1,x2,x3) equivalente (x1 ⇒ ((x2 ⇒ x3)) ∧(¬x2 ⇒ ¬x3))) ∧(¬x1 ⇒ ((x2 ⇒ x3) ∧(¬x1 ⇒ true)))

Conclusioni

Gli operatori che abbiamo sono sufficienti.
Possiamo avere solo ¬, ∧ e ∨.
Anche ¬, ∧ sono sufficienti perché a∨b si può scrivere ¬(¬a∧¬b).
Anche ¬, ∨ sono sufficienti perché a∧b si può scrivere ¬(¬a∨¬b).
Anche ¬, ⇒ sono sufficienti perché a∧b si può scrivere ¬(a⇒¬b) e a∨b si può scrivere ¬a⇒b.

Valutazione

Tabella di verità

Formula f: ((x∧y)∨z)⇒(z⇒(x∧y))
Variabili: x, y e z
Sottoformule:
f1:x∧y
f2:f1∨z
f3:z⇒f1
f:f2⇒f3
xyzf1f2f3f
falsofalsofalsofalsofalsoverovero
falsofalsoverofalsoverofalsofalso
falsoverofalsofalsofalsoverovero
falsoveroverofalsoverofalsofalso
verofalsofalsofalsofalsoverovero
verofalsoverofalsoverofalsofalso
veroverofalsoveroveroverovero
veroveroveroveroveroverovero

Esercizi

A3 Scrivere una funzione eval che prende una formula e una valutazione delle variabili e restituisce il valore della formula per questa valutazione.
A4 Scrivere una funzione table che prende una formula e scrive la sua tabella di verità.

Soddisfacibilità

Definizione

Una formula è soddisfacibile se esiste una valutazione delle variabili che la rende vera.

Esempi

((x∧y)∨z)⇒(z⇒(x∧y)) è soddisfacibile.
x ∧¬x non è soddisfacibile.

Esercizi

A5 Scrivere una funzione sat che verifica se una formula è soddisfacibile.

Tautologia

Definizione

Una formula è una tautologia se tutte le valutazioni delle variabili la rendono vera.

Tautologia e Soddisfacibilità

f è una tautologia se e solamente se ¬f non è soddisfacibile.

Esempi

(x∧y)⇒(y∧x) è una tautologia.
((x∧y)∨z)⇒(z⇒(x∧y)) non è una tautologia.

Esercizi

A6 Scrivere una funzione taut che verifica se una formula è una tautologia.

*A7 Dare una valutazione delle variabili che rende la formula x⇒ (y ⇒ x) vera.

*A8 Dare una valutazione delle variabili che rende la formula x⇒ (y ⇒ x) falsa.

*A9 Dare una valutazione delle variabili che rende la formula ¬y⇒ (x ∧ y) vera.

*A10 Dare una valutazione delle variabili che rende la formula ¬y⇒ (x ∧ y) falsa.

*A11 Dare una valutazione delle variabili che rende la formula ((x⇒ y) ⇒ x) ⇒ x vera.

*A12 Dare una valutazione delle variabili che rende la formula ((x⇒ y) ⇒ x) ⇒ x falsa.

*A13 Dare la tabella di verità per la formula (x∨ ¬y) ⇒ (x ∧ y).

Laurent Théry

Last modified: Thu May 9 01:05:50 MEST 2002