PUERTA | CS 2013 | Pregunta 59

¿Cuál de los siguientes está(n) funcionalmente completo(s)?

(A)

f(a, b, c) = (a + b)(a + c)

(B)

f(a, b, c) = a’b’ + b’c + c’a’

(C)

f(a, b, c) = a’ + bc

(D)

Ninguna de las anteriores

Respuesta: (D)
Explicación:

Una función se considera funcionalmente completa si no pertenece a TO,T1,L,M,S que son

Propiedad 1 (TO): Decimos que la función booleana f conserva cero, si en la entrada 0 produce 0. Por la entrada 0 nos referimos a una entrada de este tipo, donde cada variable de entrada es 0 (esta entrada generalmente corresponde a la primera fila de la tabla de verdad). Denotamos la clase de cero

conservando las funciones booleanas como TO y escribiendo f € TO.

Propiedad 2 (T1): de manera similar a TO, decimos que la función booleana f conserva uno, si en 1 entrada, produce 1. La entrada 1 es la entrada donde todas las variables de entrada son 1 (esta entrada generalmente corresponde a la última fila de la tabla de verdad). Denotamos la clase de uno que conserva las funciones booleanas como T1 y escribimos f = T1.

Propiedad 3 (L): Decimos que la función booleana f es lineal si una de las siguientes dos afirmaciones se cumple para f:

• Por cada valor 1 de f, el número de 1 en la entrada correspondiente es impar, y por cada valor 0 de f, el número de 1 en la entrada correspondiente es par.

o

• Por cada valor 1 de f, el número de 1 en la entrada correspondiente es par, y por cada valor 0 de f, el número de 1 en la entrada correspondiente es impar.

Si una de estas afirmaciones se cumple para f, decimos que f es lineal1. Denotamos la clase de funciones booleanas lineales con L y escribimos f € L.

Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior