Calculadora de tablas de verdad, FNC, FND y polinomio de Zhegalkin

Cómo utilizar la calculadora

1. Introduzca en el campo función lógica (por ejemplo, x1 ∨ x2) o su vector (por ejemplo, 10110101)
2. Especifique las acciones a realizar mediante los interruptores
3. Especifique si la salida de la solución es requerida por el interruptor "Con solución"
4. Haga clic en el botón "Emitir una solución"

Símbolos utilizados

Como variables se utilizan las letras del alfabeto latino, así como números escritos después de la letra (índice de la variable). Así, los nombres de las variables serán: a, x, a1, B, X, X1, Y1, A123 y así sucesivamente.

Para registrar las operaciones lógicas puede utilizar los dos caracteres normales del teclado (*, +, !, ^, ->, =), y símbolos establecidos en la literatura (∧, ∨, ¬, ⊕, →, ≡). Si su teclado no tiene el símbolo de la operación deseada, utilice el teclado de la calculadora (si no está visible, pulse "Mostrar teclado"), donde están disponibles todas las operaciones lógicas y un conjunto de las variables más utilizadas. Para cambiar el orden de las operaciones se utilizan corchetes ().

Las denominaciones de las operaciones lógicas

• Y: & • ∧ *
• O: ∨ +
• NOT: ¬ !
• Exclusivo O (XOR): ⊕ ^
• Implicación: -> → =>
• Equivalencia: = ~ ≡ <=>
• Golpe de Schaeffer: ↑ |
• Flecha de Pierce: ↓

Qué puede hacer la calculadora

• Construir una tabla de verdad de la función
• Construir una tabla de verdad por un vector binario
• Construir una forma normal conjuntiva (FNC)
• Construir una forma normal disyuntiva (FND)
• Construir el polinomio de Zhegalkin (por los métodos de Pascal, triángulo y coeficientes indefinidos)
• Determinar si una función pertenece a cada una de las cinco clases de Post
• Construir K-Map (Mapa de Karnaugh)
• Minimizar FNC y FND
• Búsqueda de variables ficticias

¿Qué es una función booleana?

Función booleana f(x1, x2, ... xn) — es cualquier función de n variables x₁, x₂, ... x_n, en la que sus argumentos toman uno de dos valores: o bien 0 o bien 1, y la propia función toma valores 0 o 1. Es decir, es una regla por la que a un conjunto arbitrario de ceros y unos se le asigna el valor 0 o 1. Más información sobre las funciones booleanas en Wikipedia.

¿Qué es una tabla de verdad?

Tabla de verdad - es una tabla que describe una función lógica, es decir, que refleja todos los valores de la función para todos los valores posibles de sus argumentos. La tabla consta de n+1 columnas y 2n filas, siendo n el número de variables utilizadas. Las primeras n columnas contienen todos los valores posibles de los argumentos (variables) de la función, y la columna n+1 contiene los valores de la función que toma en un conjunto dado de argumentos.

A menudo existe una variante de la tabla en la que el número de columnas es igual a n + el número de operaciones lógicas. En dicha tabla también las primeras n columnas se rellenan con conjuntos de argumentos, y las restantes con valores de subfunciones incluidas en el registro de la función, lo que permite simplificar el cálculo del valor final de la función a expensas de los cálculos ya intermedios.

Operaciones lógicas

Una operación lógica es una operación sobre enunciados que permite hacer nuevos enunciados combinando otros más simples. La conjunción (∧ o &), la disyunción (∨ o |) se denominan comúnmente operaciones básicas, la implicación (→), la negación (¬), la equivalencia (=), el OR exclusivo (⊕).

Tabla de verdad de las operaciones lógicas

Cómo establecer una función lógica

Hay muchas formas de especificar una función booleana:

• tabla de verdad
• conjuntos característicos
• vector de valores
• Matriz de Gray
• fórmulas

Veamos algunas de ellas:

Para definir una función mediante un vector de valores, hay que escribir un vector de 2n ceros y unos, donde n es el número de argumentos de los que depende la función. Por ejemplo, una función de dos argumentos puede definirse de la siguiente manera 0001 (operación AND), 0111 (operación OR).

Para definir una función como fórmula, es necesario escribir una expresión matemática compuesta por los argumentos de la función y las operaciones lógicas. Por ejemplo, podemos especificar la siguiente función: a∧b ∨ b∧c ∨ a∧c

Formas de representar una función booleana

Se pueden utilizar fórmulas para obtener una enorme variedad de funciones, y con diferentes fórmulas se puede obtener la misma función. A veces puede ser muy útil saber cómo construir una función concreta, utilizando sólo un pequeño conjunto de operaciones dadas, o utilizando el menor número posible de operaciones arbitrarias. Veamos las formas básicas de definir funciones booleanas:

• Forma normal disyuntiva (FND)
• Forma normal conjuntiva (FNC)
• Forma normal algebraica (ANF, polinomio de Zhegalkin)

Forma normal disyuntiva (FND)

Una conjunción simple es una conjunción de un conjunto finito de variables, o de sus negaciones, en la que cada variable no aparece más de una vez. Una forma normal disyuntiva (FND) es una disyunción de conjunciones simples. Una forma normal disyuntiva perfecta (FND) es una FND con respecto a algún conjunto finito de variables dado, cada una de cuyas conjunciones incluye todas las variables de este conjunto. Por ejemplo, FND es la función ¬abc ∨ ¬a¬bc ∨ ac, pero no es una forma normal disyuntiva porque la última conjunción carece de la variable b.

Forma normal conjuntiva (FNC)

Una disyunción simple es una disyunción de una o más variables, o sus negaciones, con cada variable incluida no más de una vez. La forma normal conjuntiva (CNF) es una conjunción de disyunciones simples. Una forma normal conjuntiva perfecta (CNF) es una CNF con respecto a algún conjunto finito de variables dado, cada disyunción de la cual incluye todas las variables de este conjunto. Por ejemplo, la CNF es la función (a ∨ b) ∧ (a ∨ b ∨ c), pero no es una SNF porque la primera disyunción carece de la variable c.

Forma normal algebraica (FNA, polinomio de Zhegalkin)

Forma normal algebraica, el polinomio de Zhegalkin es una forma de representación de la función lógica en forma de polinomio con coeficientes de 0 y 1, donde la operación de conjunción se utiliza como producto y la OR exclusiva se utiliza como adición. Ejemplos de polinomios de Zhegalkin: 1, a, a⊕b, ab⊕a⊕b⊕1

Algoritmo para construir un FND para una función booleana

1. Construye una tabla de verdad para la función
2. Encuentra todos los conjuntos de argumentos en los que la función toma el valor 1
3. Escribe conjunciones simples para cada uno de los conjuntos según la siguiente regla: si en un conjunto la variable toma valor 0, entra en la conjunción con negación, en caso contrario sin negación
4. Combinar todas las conjunciones simples con una disyunción

Algoritmo de construcción de FNC para una función booleana

1. Construye una tabla de verdad para la función
2. Encuentra todos los conjuntos de argumentos en los que la función toma el valor 0
3. Escribe disyunciones simples para cada uno de los conjuntos según la siguiente regla: si en un conjunto la variable toma valor 1, entra en la disyunción con negación, en caso contrario sin negación
4. Combinar todas las disyunciones simples con una conjunción

Algoritmo para construir el polinomio de Zhegalkin de una función booleana

Existen varios métodos para construir el polinomio de Zhegalkin, en este artículo consideraremos el más conveniente y sencillo de todos.

1. Construye una tabla de verdad para la función
2. Añade una nueva columna a la tabla de verdad y escribe en las celdas 1, 3, 5... los valores de las mismas filas de la columna anterior de la tabla de verdad, y a los valores de las líneas 2, 4, 6... añade el módulo dos de las correspondientes líneas 1, 3, 5...
3. Añade una nueva columna a la tabla de verdad y sobrescribe los valores de las líneas 1, 2, 5, 6, 9, 10... y a las líneas 3, 4, 7, 8, 11, 12... añade los valores sobrescritos de forma similar al punto anterior.
4. Repite cada vez duplicando el número de elementos transferidos y añadidos hasta que la longitud sea igual al número de filas de la tabla.
5. Escribe conjuntos booleanos en los que el valor de la última columna es uno
6. Escribe los nombres de las variables correspondientes al conjunto en lugar de los de los conjuntos (para el conjunto cero escribe uno) y únelos utilizando la operación OR exclusiva.

Ejemplos de construcción de diferentes representaciones de funciones lógicas

Construyamos las formas normales perfectas disyuntiva y disyuntiva y el polinomio de Zhegalkin para la función de tres variables F = ¬ab∨¬bc∨ca

Construyamos una tabla de verdad para la función

---

Construcción de una forma normal disyuntiva:

Vamos a encontrar los conjuntos en los que la función toma un valor verdadero: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

Hagamos coincidir los conjuntos encontrados con conjunciones elementales para todas las variables, y si una variable del conjunto toma valor 0, se escribirá con negación:

K₁: { 0, 0, 1 } — ¬a¬bc
K₂: { 0, 1, 0 } — ¬ab¬c
K₃: { 0, 1, 1 } — ¬abc
K₄: { 1, 0, 1 } — a¬bc
K₅: { 1, 1, 1 } — abc

Combina conjunciones utilizando la disyunción y obtén una forma normal disyuntiva:

---

Construcción de una forma normal conjuntiva:

Encuentra los conjuntos en los que la función toma un valor falso: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

Hagamos coincidir los conjuntos encontrados con disyunciones elementales para todas las variables, y si una variable del conjunto toma valor 1, se escribirá con negación:

D₁: { 0, 0, 0 } — a∨b∨c
D₂: { 1, 0, 0 } — ¬a∨b∨c
D₃: { 1, 1, 0 } — ¬a∨¬b∨c

Combine las disyunciones con las conjunciones y obtenga una forma normal conjuntiva perfecta:

---

Construcción del polinomio de Zhegalkin:

Añade una nueva columna a la tabla de verdad y escribe en las líneas 1, 3, 5 y 7 los valores de las mismas líneas de la columna anterior de la tabla de verdad, y suma los valores de las líneas 2, 4, 6 y 8 módulo 2 con los valores de las líneas 1, 3, 5 y 7 correspondientes:

Añade una nueva columna a la tabla de verdad y escribe en las líneas 1 y 2, 5 y 6 los valores de las mismas líneas de la columna anterior en la tabla de verdad, y suma los valores de las líneas 3 y 4, 7 y 8 módulo 2 con los valores de las líneas 1 y 2, 5 y 6 correspondientes:

Añade una nueva columna a la tabla de verdad y escribe en las filas 1, 2, 3 y 4 los valores de las mismas filas de la columna anterior de la tabla de verdad, y suma los valores de las líneas 5, 6, 7 y 8 módulo 2 con los valores de las correspondientes líneas 1, 2, 3 y 4:

El resultado final es la siguiente tabla:

Escribe los conjuntos, en los que el vector resultante toma un valor unitario, y en lugar de las unidades en los conjuntos escribe los nombres de las variables correspondientes al conjunto (para el conjunto cero escribe uno):

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Combinando estas conjunciones mediante la operación exclusiva o, obtenemos el polinomio de Zhegalkin: c⊕b⊕bc⊕ab⊕abc