[ALGORITMO] Logica booleana

[Eres]

Ci hanno dato un problema di logica per informatica che non capisco. Ecco il testo.

Show that the following sets of functions are complete for the set of binary Boolean functions.

* {AND, NOT}
* {OR, NOT}
* {NAND}
* {NOR}, where NOR := NOT o OR
* {XOR, AND}


You may use the fact that {AND, OR, NOT} is a complete set of binary functions.

Voi ci capite qualcosa? Io so solo che una funzione booleana prende uno o due dati bool come argomenti e restituisce vero o falso. Per esempio AND(A, B) è vero quando A e B sono entrambi veri; NOT(A) è vero quando A è falso. Non ho neanche idea di che cosa significhi NAND; forse NAND(A, B) = NOT(AND(A, B)), cioè OR(NOT(A), NOT(B)).
:master:

[adriana80]

NAND La sua uscita si porta a livello 0 solo se entrambi gli ingressi si portano a livello 1.
NOR una negazione delll OR
L'operatore XOR (detto anche OR esclusivo o somma modulo 2) restituisce 1 (vero) se e solo se un unico dei due operandi è 1, mentre restituisce 0 (falso) in tutti gli altri casi.

[Eres]

Piu' o meno le funzioni le conosco. Quello che non capisco e': che cosa devo fare? Non capisco che cosa intende con questa frase: Show that the following sets of functions are complete for the set of binary Boolean functions.

[pallinopinco]

Show that the following sets of functions are complete for the set of binary Boolean functions.

Credo che ti stiano chiedendo una dimostrazione formale, una di quelle che trovi sui testi di logica matematica.

[Eres]

Già, una doimosrazione. Ma di che cosa? In che senso "completi"?

[pallinopinco]

Senza scendere nei dettagli matematici (che data la natura del problema dovresti già conoscere) posso dirti che ti stanno chiedendo di dimostare che puoi esprimere qualsiasi funzione binaria con una sintesi NAND o con una sintesi NOR.

[Eres]

Quindi: partendo dal dato di fatto (espresso alla fine) che AND OR NOT sono tutte le funzioni booleane di cui potro' mai aver bisogno, devo dimostrare per ogni insieme di funzioni booleane che queste possono generare combinandosi le funzioni di cui prima. Giusto?

Ad esempio: AND e NOT bastano per genereare
AND, perche' AND(A,B) = AND(A,B)
NOT, perche' NOT(A) = NOT(A)
OR, perche' OR(A,B) = NOT(NOT(A), NOT(B))

E cosi' via per tutti i cinque insiemi di funzioni.
Dovrebbe essere comprensibile.

Grazie, ci provero'. Altrimenti, amen, tanto l'esercizio non dev'essere a tutti i costi risolto esattamente, basta che si da' un segno dell'impegno dato e di una certa competenza con queste entita' logiche.