Completitud Funcional en Lógica Digital – Part 1

Se dice que un conjunto de operaciones es funcionalmente completo o universal si y solo si cada función de conmutación puede expresarse mediante operaciones en él. Un conjunto de funciones booleanas está funcionalmente completo si todas las demás funciones booleanas se pueden construir a partir de este conjunto y se proporciona un conjunto de variables de entrada, por ejemplo

Conjunto A = {+,*,’ (O, Y, complemento) } son funcionalmente completos.
El conjunto B = {+,’} está funcionalmente completo
Set C = {*,’} están funcionalmente completos

Teorema de integridad funcional de Post: importantes clases cerradas de funciones:

T ₀ : clase de todas las funciones que conservan 0, como f(0, 0, … , 0) = 0.
T ₁ – clase de todas las funciones que conservan 1, como f(1, 1, … , 1) = 1.
S: clase de funciones autodual, como f(x ₁ , … ,x _n ) = ¬ f(¬x ₁ , … , ¬x _n ).
M: clase de funciones monótonas, como: {x ₁ , … ,x _n } ≤ {x ₁ , … ,x _n }, if x _i ≤ y _i
if {x ₁ , … ,x _n } ≤ {x ₁ , … ,x _n }
entonces f(x ₁ , … ,x _n ) ≤ f(x ₁ , … ,x _n )
L – clase de funciones lineales, que se pueden presentar como: f(x ₁ , … ,x _n ) = a ₀ + a ₁ ·x ₁ + … + a _n ·x _n ; un _yo {0, 1}.

Teorema – Un sistema de funciones booleanas es funcionalmente completo si y sólo si para cada una de las cinco clases definidas T ₀ , T ₁ , S, M, L, existe un miembro de F que no pertenece a esa clase.

Estos son conjuntos mínimos de operadores funcionalmente completos:

Un elemento:
{↑}, {↓}.

dos elementos –
${\displaystyle \{\vee ,\neg \}}, {\displaystyle \{\wedge ,\neg \}},$ ${\displaystyle \{\to ,\neg \}}, {\displaystyle \{\gets ,\neg \}},$ ${\displaystyle \{\to ,\bot \}}, {\displaystyle \{\gets ,\bot \}},$ ${\displaystyle \{\to ,\nleftrightarrow \}}, {\displaystyle \{\gets ,\nleftrightarrow \}},$ ${\displaystyle \{\to ,\nrightarrow \}}, {\displaystyle \{\to ,\nleftarrow \}},$ ${\displaystyle \{\gets ,\nrightarrow \}}, {\displaystyle \{\gets ,\nleftarrow \}},$ ${\displaystyle \{\nrightarrow ,\neg \}}, {\displaystyle \{\nleftarrow ,\neg \}},$ ${\displaystyle \{\nrightarrow ,\top \}}, {\displaystyle \{\nleftarrow ,\top \}},$ ${\displaystyle \{\nrightarrow ,\leftrightarrow \}}, {\displaystyle \{\nleftarrow ,\leftrightarrow \}}.$

tres elementos –
${\displaystyle \{\lor ,\leftrightarrow ,\bot \}},$ ${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}},$ ${\displaystyle \{\lor ,\nleftrightarrow ,\top \}},$ ${\displaystyle \{\land ,\leftrightarrow ,\bot \}},$ ${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}},$ ${\displaystyle \{\land ,\nleftrightarrow ,\top \}}.$

Ejemplos de Completitud funcional –

¿Comprobar si la función F(A,B,C) = A’+BC’ está funcionalmente completa?
Explicación: comencemos poniendo todas las variables como ‘A’ para que se convierta en
F(A,A,A) = A’+A.A’ = A’—-(i)
F(B,B,B) = B’+ B.B’ = B’—(ii)
Ahora sustituya F(A,A,A) en lugar de la variable ‘A’ y F(B,B,B) en lugar de la variable ‘C’
F(F(A,A, A),B,F(B,B,B)) = (A’)’+B.(B’)’ = A+B—(iii)
de (i) y (ii) se deriva el complemento y de ( iii) se deriva el operador ‘+’, por lo que esta función es funcionalmente completa como se indica arriba si la función contiene {+,’} es funcionalmente completa .
¿Comprobar si la función F(A,B) = A’+B está funcionalmente completa?
Explicación: comencemos poniendo todas las variables como ‘A’ para que se convierta en
F(A,A) = A’+A = 1—-(i)
F(B,B) = B’+B = 1—(ii )
F(A,0) = A’+0 = A’—(iv)
Ahora sustituya F(A,0) en lugar de la variable ‘A’
F(F(A,0),B) = (A’) ‘+B = A+B—(iii)
de (iv) se deriva el complemento y de (iii) se deriva el operador ‘+’ por lo que esta función es funcionalmente completa como se indica arriba si la función contiene {+,’} es parcialmente funcionalmente completa .
¿Comprobar si la función F(A,B) = A’B está funcionalmente completa?
Explicación: comencemos poniendo todas las variables como ‘A’ para que se convierta en
F(A,A) = A’.A’ = 0—-(i)
F(A,0) = A’.0 = 0—( ii)
F(A,1) = A’.1 = A’—(iv)
Ahora sustituya F(A,1) en lugar de la variable ‘A’
F(F(A,1),B) = (A’ )’*B = A*B—(iii)
de (iv) se deriva el complemento y de (iii) se deriva el operador ‘*’, por lo que esta función es funcionalmente completa como se indica arriba si la función contiene {*,’} es parcialmente funcional completo _
Nota: si la función se vuelve funcionalmente completa al sustituir ‘0’ o ‘1’, entonces se conoce como parcialmente funcionalmente completa.
¿Comprobar si la función F(A,B) = A’B+AB’ (EX-OR) está funcionalmente completa?
Explicación: comencemos poniendo todas las variables como ‘A’ para que se convierta en
F(A,1) = A’.1 + A.0 = A’—-(i)
F(A’,B) = AB + A ‘B’–(ii)
F(A’,B’) = AB’ + A’B–(iii)
F(A,B’) = A’B’ + AB—(iv)
Entonces no hay forma de obtener {+,*,’} según la condición. Entonces EX-OR no está funcionalmente completo .
Considere las operaciones
f(X, Y, Z) = X’YZ + XY’ + Y’Z’ y g(X′, Y, Z) = X′YZ + X′YZ′ + XY
¿Cuál de las siguientes es ¿correcto?
(A) Tanto {f} como {g} están funcionalmente completos
(B) Solo {f} está funcionalmente completo
(C) Solo {g} está funcionalmente completo
(D) Ni {f} ni {g} están funcionalmente completos
Explicación: consulte GATE CS 2015 (Conjunto 1) | Pregunta 65

Referencias –
Teorema de integridad funcional de Post Completitud
funcional – Wikipedia

Este artículo es una contribución de Vaishali Bhatia . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto<, o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta