Algoritmi e strutture dati appunti: Formulazione di proposizioni

Formulazione di proposizioni

Nella formulazione di un algoritmo compaiono momenti decisionali che contengono

una proposizione o predicato dal cui valore di verità dipende il prosieguo

dell’algoritmo.

Nei casi più semplici tali proposizioni sono atomiche (cioè non divisibili in

proposizioni più semplici). E’ questo l’esempio di proposizioni come:

vi sono altre cifre a sinistra delle ultime considerate

oppure

è finita la lista di numeri

In generale però tali proposizioni sono composte da proposizioni più semplici, unite

da connettivi (o operatori) logici. Ad esempio, l’algoritmo seguito dall’impiegato di

un ufficio postale nell’accettare conti corrente da parte degli utenti in coda potrebbe

contenere un passo del tipo:

accetta un altro conto corrente se l’utente ha già consegnato meno di 5 conti

corrente o non ci sono altri utenti in coda

o, alternativamente:

accetta un altro conto corrente se non accade che l’utente ha già consegnato

almeno 5 conti corrente e ci sono altri utenti in coda

Confrontando queste due descrizioni del comportamento prescritto all’impiegato non

è immediato stabilire se esse siano equivalenti. Il predicato su cui si basa la decisione

in questo caso è infatti composto da predicati atomici composti in modo diverso.

La verità di un predicato che contiene operatori logici può essere però facilmente

calcolata a partire dalla verità dei predicati componenti e dalle proprietà degli

operatori che li uniscono. Conoscendo tali proprietà è agevole costruire predicati

complessi, confrontarli per verificarne l’equivalenza o trasformarli per individuare la

formulazione più conveniente.

Gli operatori logici principali sono tre: OR, AND e NOT. Tali operatori consentono di

costruire proposizioni composte a partire da proposizioni elementari.

Gli operatori logici OR ed AND sono binari e cioè hanno due operandi, l’operatore

NOT è unario, cioè ha un solo operando.

Tabelle di verità e precedenze degli operatori fondamentali (vedi slides).

Esempio

Il primo predicato composto presentato sopra contiene i predicati elementari:

A: l’utente ha già consegnato meno di 5 conti corrente

B: ci sono altri utenti in coda

Tali predicati sono uniti dagli operatori logici OR e NOT in modo da formare

l’espressione:

A OR (NOT B)

Il secondo predicato composto presentato sopra contiene i predicati elementari:

A’: l’utente ha già consegnato almeno 5 conti corrente

B: ci sono altri utenti in coda

Tali predicati sono uniti dall’operatore logico NOT e AND in modo da formare

l’espressione:

NOT (A’ AND B)

dove questa volta le parentesi sono necessarie.

Osservando che il predicato elementare A’ è il contrario del predicato elementare A, i

passi che contengono i due predicati sono equivalenti se:

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

Costruendo le tabelle di verità dei due membri si verifica facilmente che essi sono

equivalenti

Operatori di relazione

Gli operatori di relazione sono operatori che permettono il confronto di entità la cui

natura può essere molto varia. Gli operatori di relazione più noti sono quelli che

permettono di confrontare quantità numeriche:

· uguale (simbolo ‘=’)

· diverso (simbolo ‘¹’)

· maggiore (simbolo ‘>’)

· minore (simbolo ‘<’)

· maggiore o uguale (simbolo ‘³’)

· minore o uguale (simbolo ‘£’)

In realtà gli operatori “uguale” e “diverso” si possono applicare a entità di qualunque

natura, mentre gli altri operatori si possono applicare a entità su cui sia definita una

relazione d’ordine.

Gli operatori di relazione permettono di esprimere predicati semplici (cioè

affermazioni che possono assumere uno dei due valori logici). Essi cioè, pur non

essendo operatori logici, consentono di costruire espressioni che possono essere usati

come argomenti di operatori logici.

Esempio

Assumendo che a, b e c siano le misure dei tre lati di un triangolo (si assume pertanto

che per essi sia verificata la disuguaglianza di Swartz), vogliamo scrivere le

condizioni che identificano se il triangolo è equilatero, isoscele o scaleno.

Il triangolo è equilatero se:

a=b AND b=c AND a=c

(in realtà per la proprietà transitiva dell’uguaglianza per per le proprietà dell’algebra

di Boole l’ultima clausola è inutile). Il triangolo è isoscele se:

(a=b AND a¹c) OR (b=c AND a¹c) OR (a=b AND b¹c)

(in realtà per le regole di precedenza le parentesi non sono necessarie, ma è

conveniente metterle per facilitare la lettura dell’espressione). In fine, il triangolo è

scaleno se:

a¹b AND a¹c AND b¹c

Se volessimo far scrivere ad un esecutore il risultato della verifica potremmo usare

l’algoritmo:

1. se a=b AND b=c AND a=c scrivi “equilatero”

2. se (a=b AND a¹c) OR (b=c AND a¹c) OR (a=b AND b¹c)

scrivi “isoscele”

3. se a¹b AND a¹c AND b¹c scrivi “scaleno”

dove l’esecutore esegue sempre tutti e tre i passi (cioè la sequenza dinamica coincide

sempre con la sequenza statica), ma per la natura delle condizioni stampa sempre una

sola tra le tre possibili scritte.

Tuttavia una formulazione alternativa dell’algoritmo potrebbe essere la seguente:

1. se a=b AND b=c AND a=c scrivi “equilatero” altrimenti

2. se a=b OR b=c OR a=c scrivi “isoscele” altrimenti

3. scrivi “scaleno”

dove la parola altrimenti significa ovviamente che se la condizione è vera l’esecutore

deve terminare l’esecuzione dell’algoritmo senza considerare i passi successivi.

Questa nuova formulazione risulta più sintetica e, una volta che ne sia stato compreso

il significato, più semplice. Essa infatti sfrutta il fatto di avere escluso al passo 1 che il

triangolo sia equilatero per semplificare al passo 2 la condizione che determina se il

triangolo e isoscele, e sfrutta il fatto di aver escluso al passo 2 che il triangolo sia

isoscele per concludere al passo 3 senza ulteriori controlli che è scaleno.

Al contrario, la prima formulazione dell’algoritmo, richiedendo sempre l’esecuzione

di tutti e tre i passi deve usare condizioni indipendenti.

Si noti infine che se invece di determinare prima se il triangolo e equilatero, poi se è

isoscele e infine se è scaleno si scegliesse di procedere al contrario, l’algoritmo

sarebbe:

1. se a¹b AND a¹c AND b¹c scrivi “scaleno” altrimenti

2. se (a=b AND a¹c) OR (b=c AND a¹c) OR (a=b AND b¹c)

scrivi “isoscele” altrimenti

3. scrivi “equilatero”

In questo caso la condizione al passo 2 non si è semplificata in quanto l’aver escluso

che il triangolo sia scaleno non dà alcuna informazione particolare.