ALGEBRA E LOGICA (Pareschi e Schoof) 2^{o} esonero Roma 2 maggio 2002, 14:00–15:45.

COGNOME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOME . . . . . . . . . . . . . . . . . . . . . . . .

Inserire le risposte negli spazi predisposti, accompagnandole con spiegazioni chiare ed essenziali. NON SI ACCETTANO RISPOSTE SCRITTE SU ALTRI FOGLI. Ogni esercizio vale 6 punti.

1. Sia P l’insieme dei numeri primi ≤ 17. Per p, q ∈ P definiamo p ≤ q quando ogni cifra binaria di p è minore o uguale alla cifra corrispondente di q.

(a) Dimostrare che si tratta di un ordinamento parziale.

(b) Determinare gli elementi minimali e massimali di P; determinare inf(3, 11) e sup(2, 5).

Abbiamo che P = {2, 3, 5, 7, 11, 13, 17}. In notazione binaria (base 2) l’insieme P è quindi uguale a {10, 11, 101, 111, 1011, 1101, 10001}. Gli elementi minimali sono 2, 5 e 17. Gli elementi massimali sono 7, 11, 13 e 17. Abbiamo che inf(3, 11) = 3, mentre sup(2, 5) = 7.

2. Determinare quanti sono i numeri 0 ≤ n < 2000 le cui cifre hanno somma uguale a 9.

Ogni numero con questa proprietà ha tre cifre o ha la prima cifra uguale a 1. Ci sono \binom{9+3−1}{9} = \binom{11}{2} numeri del primo tipo e \binom{8+3−1}{8} = \binom{10}{2} del secondo. Ci sono quindi \binom{11}{2} + \binom{10}{2} = 100 numeri con la proprietà richiesta.

3. Sia A = {a, b, c, d, e}. Determinare la chiusura transitiva della relazione R che consiste nelle coppie (a, b), (a, e), (b, c), (c, d), (d, b).

La matrice A associata alla relazione e le sue “potenze” A^{[2]} e A^{[3]} sono

A = ( \begin{matrix}0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,  A^{[2]} = ( \begin{matrix}0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,  A^{[3]} = ( \begin{matrix}0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Siccome le matrici A^{[4]} e A^{[5]} contengono solo ripetizioni, la chiusura transitiva di R è l’unione di R e l’insieme {(a, c), (b, d), (c, b), (d, c), (a, d), (b, b), (c, c), (d, d)}.

4. Siano x, y variabili booleane. L’operatore NAND è definito da x NAND y = \overline{(xy)}. Usando solo porte NAND costruire un circuito con input x e y e output \overline{x} e x + y.

Abbiamo che \overline{x} = x NAND x e xy = \overline{\overline{(xy)}} = \overline{(xy)} NAND \overline{(xy)} = (x NAND y) NAND (x NAND y).

5. I grafi.

Il grafo “cubo” Q_{3} è bipartito. Nelle altre versioni del compito, i due grafi sono sempre isomorfi, eccetto nel caso dei due grafi “ottagonali”. Essi non sono isomorfi perché un grafo contiene un vertice di grado 2 con due vertici vicini di grado 3, ma l’altro no.