Métodos de resolución de sistemas de ecuaciones lógicas. Métodos para resolver sistemas de ecuaciones lógicas.

Noskin Andrey Nikolaevich,
profesor de TI
categoría de calificación más alta,
Candidato de Ciencias Militares, Profesor Asociado
Liceo GBOU No. 1575, Moscú

Método de mapeo optimizado para resolver el problema 23 del Examen Estatal Unificado KIM en informática y TIC

Una de las tareas más difíciles del Examen Estatal Unificado KIM es el problema 23, en el que es necesario encontrar el número de conjuntos diferentes de valores de variables lógicas que satisfacen la condición especificada.
Esta tarea es quizás la más difícil del Examen Estatal Unificado KIM en informática y TIC. Como regla general, no más del 5% de los examinados lo afrontan (1).
Un porcentaje tan pequeño de estudiantes que completaron esta tarea se explica por lo siguiente:
- los estudiantes pueden confundir (olvidar) los signos de las operaciones lógicas;
- errores matemáticos en el proceso de realización de cálculos;
- errores de razonamiento al buscar una solución;
- errores en el proceso de simplificación de expresiones lógicas;
- Los profesores recomiendan resolver este problema después de completar todo el trabajo, ya que la probabilidad de
los errores son muy grandes y el “peso” de la tarea es sólo un punto principal.
Además, algunos profesores tienen dificultades para resolver este tipo de problemas y por ello intentan resolver problemas más sencillos con los niños.
Lo que también complica la situación es que en este bloque hay una gran cantidad de tareas diferentes y es imposible elegir una solución modelo.
Para corregir esta situación, la comunidad pedagógica está ultimando los dos métodos principales para resolver problemas de este tipo: la resolución mediante cadenas de bits (2) y el método de mapeo (3).
La necesidad de refinar (optimizar) estos métodos se debe al hecho de que las tareas cambian constantemente tanto en estructura como en el número de variables (solo un tipo de variables X, dos tipos de variables X e Y, tres tipos: X, Y , Z).
La dificultad para dominar estos métodos de resolución de problemas se confirma por el hecho de que en el sitio web de K.Yu. Polyakov, existen 38 análisis de este tipo de problemas (4). Algunos análisis proporcionan más de un tipo de solución a un problema.
Recientemente, en el Examen Estatal Unificado KIM en informática, ha habido problemas con dos tipos de variables X e Y.
He optimizado el método de visualización y animo a mis alumnos a utilizar el método mejorado.
Esto da resultados. El porcentaje de mis alumnos que afrontan esta tarea varía hasta el 43% de los que aprueban. Como regla general, cada año entre 25 y 33 personas de todos los grados 11 toman el examen estatal unificado de informática.
Antes de la aparición de los problemas con dos tipos de variables, los estudiantes utilizaban con mucho éxito el método de mapeo, pero después de la aparición de Y en la expresión lógica, comencé a notar que las respuestas de los niños ya no coincidían con las pruebas. Resultó que no tenían muy claro cómo crear una tabla de asignaciones con un nuevo tipo de variable. Entonces se me ocurrió que, por conveniencia, la expresión completa debería reducirse a un tipo de variable, como les conviene a los niños.
Daré esta técnica con más detalle. Por conveniencia, lo consideraré usando el ejemplo del sistema de expresiones lógicas dado en (4).
¿Cuántas soluciones diferentes tiene un sistema de ecuaciones lógicas?

(x1 ^ y 1)=(¬x 2 V ¬ y 2 )
(x2 ^ y 2)= (¬ X 3 V ¬ y 3 )
...
(x5 ^ y 5) = (¬ X 6 V ¬ y 6 )

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

5. Complete la tabla calculando el número de pares de variables para los cuales el sistema tiene solución.

6. Suma todos los resultados: 9 + 9 + 9 + 27 = 54
7. Respuesta: 54.
La metodología optimizada anterior para resolver el problema 23 del Examen Estatal Unificado KIM permitió a los estudiantes recuperar la confianza y resolver con éxito este tipo de problemas.

Literatura:

1.FIPI. Recomendaciones metodológicas para docentes, elaboradas a partir de un análisis de errores típicos de los participantes en el Examen Estatal Unificado de 2015 en CIENCIAS DE LA INFORMACIÓN y TIC. Modo de acceso: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

Hay varias formas de resolver sistemas de ecuaciones lógicas. Esto es reducción a una ecuación, construcción de una tabla de verdad y descomposición.

Tarea: Resolver un sistema de ecuaciones lógicas:

Consideremos método de reducción a una ecuación . Este método implica transformar ecuaciones lógicas para que sus lados derechos sean iguales al valor de verdad (es decir, 1). Para hacer esto, use la operación de negación lógica. Luego, si las ecuaciones contienen operaciones lógicas complejas, las reemplazamos por operaciones básicas: “Y”, “O”, “NO”. El siguiente paso es combinar las ecuaciones en una sola, equivalente al sistema, usando la operación lógica “Y”. Después de esto, debes transformar la ecuación resultante basándose en las leyes del álgebra lógica y obtener una solución específica para el sistema.

Solución 1: Aplicar inversión a ambos lados de la primera ecuación:

Imaginemos la implicación a través de las operaciones básicas “O” y “NO”:

Dado que los lados izquierdos de las ecuaciones son iguales a 1, podemos combinarlos usando la operación "Y" en una ecuación que sea equivalente al sistema original:

Abrimos el primer corchete según la ley de De Morgan y transformamos el resultado obtenido:

La ecuación resultante tiene una solución: A =0, B=0 y C=1.

El siguiente método es construir tablas de verdad . Dado que las cantidades lógicas tienen solo dos valores, simplemente puede revisar todas las opciones y encontrar entre ellas aquellas para las que se satisface un sistema de ecuaciones determinado. Es decir, construimos una tabla de verdad común para todas las ecuaciones del sistema y encontramos una recta con los valores requeridos.

Solución 2: Creemos una tabla de verdad para el sistema:

La línea para la cual se cumplen las condiciones de la tarea está resaltada en negrita. Entonces A=0, B=0 y C=1.

Forma descomposición . La idea es fijar el valor de una de las variables (igualarlo a 0 o 1) y así simplificar las ecuaciones. Luego puedes fijar el valor de la segunda variable, y así sucesivamente.

Solución 3: Sea A = 0, entonces:

De la primera ecuación obtenemos B = 0, y de la segunda, C = 1. Solución del sistema: A = 0, B = 0 y C = 1.

En el examen de informática, muy a menudo es necesario determinar el número de soluciones de un sistema de ecuaciones lógicas, sin encontrar las soluciones mismas, también existen ciertos métodos para ello; La forma principal de encontrar el número de soluciones de un sistema de ecuaciones lógicas esreemplazando variables. Primero, debe simplificar cada una de las ecuaciones tanto como sea posible según las leyes del álgebra lógica y luego reemplazar las partes complejas de las ecuaciones con nuevas variables y determinar el número de soluciones para el nuevo sistema. Luego, regrese al reemplazo y determine la cantidad de soluciones para él.

Tarea:¿Cuántas soluciones tiene la ecuación (A →B) + (C →D) = 1? Donde A, B, C, D son variables lógicas.

Solución: Introduzcamos nuevas variables: X = A →B e Y = C →D. Teniendo en cuenta las nuevas variables, la ecuación quedará escrita como: X + Y = 1.

La disyunción es verdadera en tres casos: (0;1), (1;0) y (1;1), mientras que X e Y son implicaciones, es decir, es verdadera en tres casos y falsa en uno. Por tanto, el caso (0;1) corresponderá a tres posibles combinaciones de parámetros. Caso (1;1) – corresponderá a nueve posibles combinaciones de parámetros de la ecuación original. Esto significa que el total de soluciones posibles a esta ecuación es 3+9=15.

La siguiente forma de determinar el número de soluciones de un sistema de ecuaciones lógicas es árbol binario. Veamos este método usando un ejemplo.

Tarea:¿Cuántas soluciones diferentes tiene el sistema de ecuaciones lógicas?

El sistema de ecuaciones dado es equivalente a la ecuación:

(X 1 → X 2 )*(X 2 → X 3 )*…*(x m -1 → x m) = 1.

pretendamos que X 1 – es cierto, entonces de la primera ecuación obtenemos que X 2 También es cierto, desde el segundo. X 3 =1, y así sucesivamente hasta x m= 1. Esto significa que el conjunto (1; 1;…; 1) de m unidades es una solución del sistema. Déjalo ahora X 1 =0, entonces de la primera ecuación tenemos X 2 =0 o X 2 =1.

Cuando X 2 cierto, obtenemos que el resto de variables también lo son, es decir, el conjunto (0; 1; ...; 1) es una solución del sistema. En X 2 =0 entendemos eso X 3 =0 o X 3 =, y así sucesivamente. Continuando con la última variable, encontramos que las soluciones de la ecuación son los siguientes conjuntos de variables (solución m +1, cada solución contiene m valores de las variables):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Este enfoque queda bien ilustrado mediante la construcción de un árbol binario. El número de soluciones posibles es el número de ramas diferentes del árbol construido. Es fácil ver que es igual a m +1.

En caso de dificultades en el razonamiento. investigación y construcciónde soluciones con las que puedes buscar una solución usando tablas de verdad, para una o dos ecuaciones.

Reescribamos el sistema de ecuaciones en la forma:

Y creemos una tabla de verdad por separado para una ecuación:

Creemos una tabla de verdad para dos ecuaciones:

Cómo resolver algunos problemas de las secciones A y B del examen de informática

Lección 3. Lógicas. Funciones lógicas. Resolver ecuaciones

Una gran cantidad de problemas del Examen Estatal Unificado están dedicados a la lógica proposicional. Para resolver la mayoría de ellos basta con conocer las leyes básicas de la lógica proposicional, el conocimiento de las tablas de verdad de funciones lógicas de una y dos variables. Daré las leyes básicas de la lógica proposicional.

1. Conmutatividad de disyunción y conjunción:
   un ˅ segundo ≡ segundo ˅ un
   a^b ≡ b^a
2. Ley distributiva sobre disyunción y conjunción:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negación de la negación:
   ¬(¬a) ≡a
4. Consistencia:
   a ^ ¬а ≡ falso
5. Tercero exclusivo:
   a ˅ ¬а ≡ verdadero
6. Leyes de De Morgan:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Simplificación:
   a ˄ a ≡ a
   un ˅ un ≡ un
   a ˄ verdadero ≡ a
   a ˄ falso ≡ falso
8. Absorción:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Reemplazo de implicación
   a → b ≡ ¬a ˅ b
10. Reemplazo de identidad
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Representación de funciones lógicas.

Cualquier función lógica de n variables - F(x 1, x 2, ... x n) puede especificarse mediante una tabla de verdad. Una tabla de este tipo contiene 2 n conjuntos de variables, para cada una de las cuales se especifica el valor de una función en este conjunto. Este método es bueno cuando el número de variables es relativamente pequeño. Ya para n > 5 la representación se vuelve poco visible.

Otra forma es definir la función mediante alguna fórmula utilizando funciones conocidas bastante simples. Un sistema de funciones (f 1, f 2,… f k) se llama completo si cualquier función lógica puede expresarse mediante una fórmula que contenga solo funciones f i.

El sistema de funciones (¬, ˄, ˅) está completo. Las leyes 9 y 10 son ejemplos que demuestran cómo la implicación y la identidad se expresan a través de la negación, la conjunción y la disyunción.

De hecho, un sistema de dos funciones –negación y conjunción o negación y disyunción– también es completo. De las leyes de De Morgan se desprenden ideas que permiten expresar la conjunción mediante negación y disyunción y, en consecuencia, expresar la disyunción mediante negación y conjunción:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradójicamente, un sistema que consta de una sola función está completo. Hay dos funciones binarias: anticonjunción y antidisyunción, llamadas flecha de Peirce y trazo de Schaeffer, que representan un sistema hueco.

Las funciones básicas de los lenguajes de programación suelen incluir identidad, negación, conjunción y disyunción. En los problemas del Examen Estatal Unificado, junto con estas funciones, a menudo se encuentran implicaciones.

Veamos algunos problemas simples que involucran funciones lógicas.

Problema 15:

Se da un fragmento de la tabla de verdad. ¿Cuál de las tres funciones dadas corresponde a este fragmento?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Función número 3.

Para resolver el problema, es necesario conocer las tablas de verdad de funciones básicas y recordar las prioridades de las operaciones. Permítanme recordarles que la conjunción (multiplicación lógica) tiene mayor prioridad y se ejecuta antes que la disyunción (suma lógica). Durante los cálculos, es fácil notar que las funciones con los números 1 y 2 en el tercer conjunto tienen el valor 1 y por esta razón no corresponden al fragmento.

Problema 16:

¿Cuál de los números dados cumple la condición?

(los dígitos, comenzando por el dígito más significativo, están en orden descendente) → (número - par) ˄ (dígito bajo - par) ˄ (dígito alto - impar)

Si hay varios de estos números, indique el mayor.

1. 13579
2. 97531
3. 24678
4. 15386

La condición la cumple el número 4.

Los dos primeros números no cumplen la condición porque el dígito más bajo es impar. Una conjunción de condiciones es falsa si uno de los términos de la conjunción es falso. Para el tercer número, no se cumple la condición del dígito más alto. Para el cuarto número, se cumplen las condiciones impuestas a los dígitos inferior y superior del número. El primer término de la conjunción también es verdadero, ya que la implicación es verdadera si su premisa es falsa, como es el caso aquí.

Problema 17: Dos testigos dieron el siguiente testimonio:

Primer testigo: Si A es culpable, entonces B es aún más culpable y C es inocente.

Segundo testigo: Dos son culpables. Y uno de los restantes es definitivamente culpable y culpable, pero no puedo decir quién exactamente.

¿Qué conclusiones sobre la culpabilidad de A, B y C se pueden sacar del testimonio?

Respuesta: Del testimonio se deduce que A y B son culpables y C es inocente.

Solución: Por supuesto, la respuesta se puede dar basándose en el sentido común. Pero veamos cómo se puede hacer esto de manera estricta y formal.

Lo primero que hay que hacer es formalizar las declaraciones. Introduzcamos tres variables lógicas: A, B y C, cada una de las cuales tiene el valor verdadero (1) si el sospechoso correspondiente es culpable. Entonces el testimonio del primer testigo viene dado por la fórmula:

A → (B ˄ ¬C)

El testimonio del segundo testigo viene dado por la fórmula:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

El testimonio de ambos testigos se supone verdadero y representa la conjunción de las fórmulas correspondientes.

Construyamos una tabla de verdad para estas lecturas:

La evidencia sumaria es cierta sólo en un caso, lo que lleva a una respuesta clara: A y B son culpables y C es inocente.

Del análisis de este cuadro también se desprende que el testimonio del segundo testigo es más informativo. De la veracidad de su testimonio se desprenden sólo dos opciones posibles: A y B son culpables y C es inocente, o A y C son culpables y B es inocente. El testimonio del primer testigo es menos informativo: hay 5 opciones diferentes correspondientes a su testimonio. En conjunto, el testimonio de ambos testigos da una respuesta clara sobre la culpabilidad de los sospechosos.

Ecuaciones lógicas y sistemas de ecuaciones.

Sea F(x 1, x 2,…x n) una función lógica de n variables. La ecuación lógica se ve así:

F(x 1, x 2, …x n) = C,

La constante C tiene el valor 1 o 0.

Una ecuación lógica puede tener de 0 a 2 n soluciones diferentes. Si C es igual a 1, entonces las soluciones son todos aquellos conjuntos de variables de la tabla de verdad para las cuales la función F toma el valor verdadero (1). Los conjuntos restantes son soluciones de la ecuación con C igual a cero. Siempre puedes considerar solo ecuaciones de la forma:

F(x 1 , x 2 , …x n) = 1

De hecho, déjese dar la ecuación:

F(x 1, x 2, …x n) = 0

En este caso, podemos ir a la ecuación equivalente:

¬F(x 1 , x 2 , …x n) = 1

Considere un sistema de k ecuaciones lógicas:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

Fk (x 1 , x 2 , …x n ) = 1

La solución de un sistema es un conjunto de variables en las que se satisfacen todas las ecuaciones del sistema. En términos de funciones lógicas, para obtener una solución a un sistema de ecuaciones lógicas, se debe encontrar un conjunto en el que la función lógica Ф sea verdadera, que represente la conjunción de las funciones originales F:

Ф = F 1 ˄ F 2 ˄ … F k

Si el número de variables es pequeño, por ejemplo, menos de 5, entonces no es difícil construir una tabla de verdad para la función Ф, que nos permita decir cuántas soluciones tiene el sistema y cuáles son los conjuntos que dan soluciones.

En algunos problemas de USE sobre cómo encontrar soluciones a un sistema de ecuaciones lógicas, el número de variables llega a 10. Entonces, construir una tabla de verdad se convierte en una tarea casi imposible. Resolver el problema requiere un enfoque diferente. Para un sistema arbitrario de ecuaciones, no existe ningún método general distinto de la enumeración que permita resolver este tipo de problemas.

En los problemas propuestos en el examen, la solución suele basarse en tener en cuenta las particularidades del sistema de ecuaciones. Repito, aparte de probar todas las opciones para un conjunto de variables, no existe una forma general de resolver el problema. La solución debe construirse en función de las características específicas del sistema. A menudo resulta útil realizar una simplificación preliminar de un sistema de ecuaciones utilizando leyes lógicas conocidas. Otra técnica útil para resolver este problema es la siguiente. No nos interesan todos los conjuntos, sino sólo aquellos en los que la función Ф tiene el valor 1. En lugar de construir una tabla de verdad completa, construiremos su análogo: un árbol de decisión binario. Cada rama de este árbol corresponde a una solución y especifica un conjunto en el que la función Ф tiene el valor 1. El número de ramas en el árbol de decisión coincide con el número de soluciones del sistema de ecuaciones.

Explicaré qué es un árbol de decisión binario y cómo se construye utilizando ejemplos de varios problemas.

Problema 18

¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 hay que satisfacen el sistema de dos ecuaciones?

Respuesta: El sistema tiene 36 soluciones diferentes.

Solución: El sistema de ecuaciones incluye dos ecuaciones. Encontremos el número de soluciones para la primera ecuación, dependiendo de 5 variables: x 1, x 2, ... x 5. La primera ecuación puede considerarse a su vez como un sistema de 5 ecuaciones. Como se ha demostrado, el sistema de ecuaciones en realidad representa la conjunción de funciones lógicas. Lo contrario también es cierto: una conjunción de condiciones puede considerarse como un sistema de ecuaciones.

Construyamos un árbol de decisión para la implicación (x1→ x2), el primer término de la conjunción, que puede considerarse como la primera ecuación. Así es como se ve una representación gráfica de este árbol:

El árbol consta de dos niveles según el número de variables de la ecuación. El primer nivel describe la primera variable X 1 . Dos ramas de este nivel reflejan los valores posibles de esta variable: 1 y 0. En el segundo nivel, las ramas del árbol reflejan solo aquellos valores posibles de la variable X 2 para los cuales la ecuación es verdadera. Dado que la ecuación especifica una implicación, una rama en la que X 1 tiene el valor 1 requiere que en esa rama X 2 tenga el valor 1. Una rama en la que X 1 tiene el valor 0 produce dos ramas con los valores de X 2 igual a 0 y 1 El árbol construido define tres soluciones, en las que la implicación X 1 → X 2 toma el valor 1. En cada rama, se escribe un conjunto correspondiente de valores de variables, que dan una solución a la ecuación.

Estos conjuntos son: ((1, 1), (0, 1), (0, 0))

Sigamos construyendo el árbol de decisión sumando la siguiente ecuación, la siguiente implicación X 2 → X 3. La especificidad de nuestro sistema de ecuaciones es que cada nueva ecuación del sistema utiliza una variable de la ecuación anterior, agregando una nueva variable. Dado que la variable X 2 ya tiene valores en el árbol, en todas las ramas donde la variable X 2 tiene un valor de 1, la variable X 3 también tendrá un valor de 1. Para tales ramas, la construcción del árbol continúa al siguiente nivel, pero no aparecen nuevas ramas. La única rama donde la variable X 2 tiene el valor 0 se bifurcará en dos ramas donde la variable X 3 recibirá los valores 0 y 1. Por lo tanto, cada adición de una nueva ecuación, dadas sus características específicas, agrega una solución. Primera ecuación original:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
tiene 6 soluciones. Así es como se ve el árbol de decisión completo para esta ecuación:

La segunda ecuación de nuestro sistema es similar a la primera:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

La única diferencia es que la ecuación usa Y variables. Esta ecuación también tiene 6 soluciones. Dado que cada solución para las variables Xi se puede combinar con cada solución para las variables Y j, el número total de soluciones es 36.

Tenga en cuenta que el árbol de decisión construido proporciona no solo el número de soluciones (según el número de ramas), sino también las soluciones mismas escritas en cada rama del árbol.

Problema 19

¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existen que satisfacen todas las condiciones que se enumeran a continuación?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Esta tarea es una modificación de la tarea anterior. La diferencia es que se suma otra ecuación que relaciona las variables X e Y.

De la ecuación X 1 → Y 1 se deduce que cuando X 1 tiene el valor 1 (existe una de esas soluciones), entonces Y 1 también tiene el valor 1. Por lo tanto, hay un conjunto en el que X 1 e Y 1 tienen los valores 1. Cuando X 1 es igual a 0, Y 1 puede tener cualquier valor, tanto 0 como 1. Por lo tanto, cada conjunto con X 1 igual a 0, y hay 5 de esos conjuntos, corresponde a los 6 conjuntos con Y variables. Por tanto, el número total de soluciones es 31.

Problema 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Solución: Recordando las equivalencias básicas, escribimos nuestra ecuación como:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

La cadena cíclica de implicaciones significa que las variables son idénticas, por lo que nuestra ecuación es equivalente a la ecuación:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Esta ecuación tiene dos soluciones cuando todos los X i son 1 o 0.

Problema 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Solución: Al igual que en el problema 20, pasamos de implicaciones cíclicas a identidades, reescribiendo la ecuación en la forma:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Construyamos un árbol de decisión para esta ecuación:

Problema 22

¿Cuántas soluciones tiene el siguiente sistema de ecuaciones?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X10)) = 0

Respuesta: 64

Solución: Pasemos de 10 variables a 5 variables introduciendo el siguiente cambio de variables:

Y 1 = (X 1 ≡ X 2); Y2 = (X3 ≡ X4); Y3 = (X5 ≡ X6); Y4 = (X7 ≡ X8); Y5 = (X9 ≡ X10);

Entonces la primera ecuación tomará la forma:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

La ecuación se puede simplificar escribiéndola como:

(Y 1 ≡ Y 2) = 0

Pasando a la forma tradicional, escribimos el sistema después de simplificaciones en la forma:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

El árbol de decisión de este sistema es simple y consta de dos ramas con valores de variables alternas:

Volviendo a las variables X originales, observe que para cada valor en la variable Y hay 2 valores en las variables X, por lo que cada solución en las variables Y genera 2 5 soluciones en las variables X. Las dos ramas generan 2 * 2. 5 soluciones, por lo que el número total de soluciones es 64.

Como puede ver, cada problema de resolución de un sistema de ecuaciones requiere su propio enfoque. Una técnica común es realizar transformaciones equivalentes para simplificar ecuaciones. Una técnica común es construir árboles de decisión. El enfoque utilizado recuerda en parte a la construcción de una tabla de verdad con la particularidad de que no se construyen todos los conjuntos de valores posibles de variables, sino sólo aquellos en los que la función toma el valor 1 (verdadero). A menudo, en los problemas propuestos no es necesario construir un árbol de decisión completo, ya que ya en la etapa inicial es posible establecer el patrón de aparición de nuevas ramas en cada nivel posterior, como se hizo, por ejemplo, en el problema 18. .

En general, los problemas que implican encontrar soluciones a un sistema de ecuaciones lógicas son buenos ejercicios matemáticos.

Si el problema es difícil de resolver manualmente, puedes confiar la solución a la computadora escribiendo un programa apropiado para resolver ecuaciones y sistemas de ecuaciones.

No es difícil escribir un programa así. Un programa de este tipo hará frente fácilmente a todas las tareas propuestas en el Examen Estatal Unificado.

Por extraño que parezca, la tarea de encontrar soluciones a sistemas de ecuaciones lógicas es difícil para una computadora, y resulta que una computadora tiene sus límites. La computadora puede resolver con bastante facilidad problemas en los que el número de variables es de 20 a 30, pero tardará mucho en empezar a pensar en problemas de mayor tamaño. El hecho es que la función 2 n, que especifica el número de conjuntos, es una exponencial que crece rápidamente a medida que n aumenta. Tan rápido que una computadora personal común y corriente no puede realizar una tarea que consta de 40 variables en un día.

Programa en lenguaje C# para la resolución de ecuaciones lógicas.

Escribir un programa para resolver ecuaciones lógicas es útil por muchas razones, aunque solo sea porque puede usarlo para verificar la exactitud de su propia solución a los problemas del Examen Estatal Unificado. Otra razón es que dicho programa es un excelente ejemplo de una tarea de programación que cumple con los requisitos para las tareas de categoría C en el Examen Estatal Unificado.

La idea de crear un programa es simple: se basa en una búsqueda completa de todos los conjuntos posibles de valores de variables. Dado que para una determinada ecuación lógica o sistema de ecuaciones se conoce el número de variables n, también se conoce el número de conjuntos: 2 n que deben clasificarse. Utilizando las funciones básicas del lenguaje C# (negación, disyunción, conjunción e identidad), no es difícil escribir un programa que, para un conjunto dado de variables, calcule el valor de la función lógica correspondiente a una ecuación lógica o un sistema de ecuaciones. .

En dicho programa, necesita construir un bucle basado en el número de conjuntos, en el cuerpo del bucle, usando el número del conjunto, forme el conjunto en sí, calcule el valor de la función en este conjunto, y si esto El valor es 1, entonces el conjunto da una solución a la ecuación.

La única dificultad que surge al implementar el programa está relacionada con la tarea de generar el propio conjunto de valores de variables en función del número establecido. La belleza de este problema es que esta tarea aparentemente difícil en realidad se reduce a un problema simple que ya ha surgido muchas veces. De hecho, basta con comprender que el conjunto de valores variables correspondientes al número i, compuesto por ceros y unos, representa la representación binaria del número i. Entonces, la compleja tarea de obtener un conjunto de valores variables mediante un número determinado se reduce a la tarea familiar de convertir un número a binario.

Así es como se ve una función en C# que resuelve nuestro problema:

///

///

/// función lógica - método,

/// cuya firma es especificada por el delegado del DF

///

/// número de variables

/// número de soluciones

estático int SolveEquations(DF divertido, int n)

conjunto bool = nuevo bool [n];

int metro = (int)Math.Pow(2, n); //número de conjuntos

int p = 0, q = 0, k = 0;

//Búsqueda completa por número de conjuntos

para (int i = 0; i< m; i++)

//Formación del siguiente conjunto - set,

//especificado por la representación binaria del número i

para (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Calcular el valor de la función en el conjunto.

Para entender el programa espero que las explicaciones de la idea del programa y los comentarios en su texto sean suficientes. Sólo me centraré en explicar el título de la función dada. La función SolveEquations tiene dos parámetros de entrada. El parámetro divertido especifica una función lógica correspondiente a la ecuación o sistema de ecuaciones que se está resolviendo. El parámetro n especifica el número de variables divertidas. Como resultado, la función SolveEquations devuelve el número de soluciones de la función lógica, es decir, el número de aquellos conjuntos en los que la función se evalúa como verdadero.

Es común para los escolares cuando alguna función F(x) tiene un parámetro de entrada x que es una variable de tipo aritmético, cadena o lógica. En nuestro caso, se utiliza un diseño más potente. La función SolveEquations se refiere a funciones de orden superior: funciones de tipo F(f), cuyos parámetros pueden ser no solo variables simples, sino también funciones.

La clase de funciones que se pueden pasar como parámetro a la función SolveEquations se especifica de la siguiente manera:

delegado bool DF(bool vars);

Esta clase posee todas las funciones a las que se les pasa como parámetro un conjunto de valores de variables lógicas especificadas por la matriz vars. El resultado es un valor booleano que representa el valor de la función en este conjunto.

Finalmente, aquí hay un programa que utiliza la función SolveEquations para resolver varios sistemas de ecuaciones lógicas. La función SolveEquations es parte de la clase ProgramCommon a continuación:

programa de clase común

delegado bool DF(bool vars);

vacío estático principal (argumentos de cadena)

Console.WriteLine("Y funciones - " +

ResolverEcuaciones(FunAnd, 2));

Console.WriteLine("La función tiene 51 soluciones - " +

ResolverEcuaciones(Diversión51, 5));

Console.WriteLine("La función tiene 53 soluciones - " +

ResolverEcuaciones(Diversión53, 10));

bool estático FunAnd(bool vars)

devolver vars && vars;

bool estático Fun51 (vars bool)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

bool estático Fun53 ​​(vars bool)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Así es como se ven los resultados de la solución para este programa:

10 tareas para el trabajo independiente

1. ¿Cuál de las tres funciones es equivalente?
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X˄Y
2. Se muestra un fragmento de la tabla de verdad:

¿A cuál de las tres funciones corresponde este fragmento?

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. El jurado está formado por tres personas. La decisión se toma si el presidente del jurado vota a favor, apoyado por al menos uno de los miembros del jurado. De lo contrario, no se toma ninguna decisión. Construir una función lógica que formalice el proceso de toma de decisiones.
5. X gana a Y si cuatro lanzamientos de moneda resultan en cara tres veces. Defina una función lógica que describa el pago de X.
6. Las palabras de una oración están numeradas comenzando desde uno. Una oración se considera correctamente construida si se cumplen las siguientes reglas:
   1. Si una palabra par termina en vocal, entonces la siguiente palabra, si existe, debe comenzar con vocal.
   2. Si una palabra impar termina en consonante, entonces la siguiente palabra, si existe, debe comenzar con consonante y terminar con vocal.
      ¿Cuál de las siguientes oraciones está correctamente construida?
   3. Mamá lavó a Masha con jabón.
   4. Un líder es siempre un modelo.
   5. La verdad es buena, pero la felicidad es mejor.
7. Cuantas soluciones tiene la ecuación:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Enumere todas las soluciones de la ecuación:
   (a → b) → c = 0
9. ¿Cuántas soluciones tiene el siguiente sistema de ecuaciones?
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Cuantas soluciones tiene la ecuación:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Respuestas a los problemas:

1. Las funciones b y c son equivalentes.
2. El fragmento corresponde a la función b.
3. Sea la variable lógica P el valor 1 cuando el presidente del jurado vota “a favor” de la decisión. Las variables M 1 y M 2 representan las opiniones de los miembros del jurado. La función lógica que especifica tomar una decisión positiva se puede escribir de la siguiente manera:
   P ˄ (M 1 ˅ M 2)
4. Deje que la variable lógica P i tome el valor 1 cuando el i-ésimo lanzamiento de moneda caiga en cara. La función lógica que especifica el pago X se puede escribir de la siguiente manera:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Oración b.
6. La ecuación tiene 3 soluciones: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Institución educativa presupuestaria municipal

"Escuela secundaria nº 18"

distrito urbano de la ciudad de Salavat de la República de Bashkortostán

Sistemas de ecuaciones lógicas.

en los problemas del examen estatal unificado en informática

La sección "Fundamentos del álgebra de la lógica" de las tareas del Examen Estatal Unificado se considera una de las más difíciles y difíciles de resolver. El porcentaje medio de tareas completadas sobre este tema es el más bajo y es del 43,2.

Basado en la especificación KIM de 2018, este bloque incluye cuatro tareas de diferentes niveles de dificultad.

La tarea 23 tiene un nivel de dificultad alto, por lo que tiene el porcentaje de finalización más bajo. Entre los graduados preparados (81-100 puntos), el 49,8% completó la tarea; los graduados moderadamente preparados (61-80 puntos) completaron el 13,7% el grupo restante de estudiantes no completó esta tarea.

El éxito en la resolución de un sistema de ecuaciones lógicas depende del conocimiento de las leyes de la lógica y de la aplicación precisa de los métodos para resolver el sistema.

Consideremos resolver un sistema de ecuaciones lógicas usando el método de mapeo.

(23.154 Polyakov K.Yu.) ¿Cuántas soluciones diferentes tiene el sistema de ecuaciones?

((X1  y1 )  (X2  y2 ))  (X1  X2 )  (y1  y2 ) =1

((X2  y2 )  (X3  y3 ))  (X2  X3 )  (y2  y3 ) =1

((X7  y7 )  (X8  y8 ))  (X7  X8 )  (y7  y8 ) =1

Dónde X1 , X2 ,…, X8, en1 , y2 ,…,y8 - variables lógicas? No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de variables para los que se cumple esta igualdad. Como respuesta, debe indicar el número de dichos conjuntos.

Solución. Todas las ecuaciones incluidas en el sistema son del mismo tipo y cada ecuación incluye cuatro variables. Conociendo x1 e y1, podemos encontrar todos los valores posibles de x2 e y2 que satisfagan la primera ecuación. Razonando de manera similar, a partir de los x2 e y2 conocidos podemos encontrar x3, y3 que satisface la segunda ecuación. Es decir, conociendo el par (x1, y1) y determinando el valor del par (x2, y2), encontraremos el par (x3, y3), que, a su vez, conducirá al par (x4, y4). etcétera.

Encontremos todas las soluciones a la primera ecuación. Esto se puede hacer de dos maneras: construir una tabla de verdad, mediante el razonamiento y la aplicación de las leyes de la lógica.

Mesa de la verdad:

Construir una tabla de verdad requiere mucho trabajo y tiempo, por lo que utilizamos el segundo método: el razonamiento lógico. El producto es igual a 1 si y sólo si cada factor es igual a 1.

(X1  y1 )  (X2  y2 ))=1

(X1  X2 ) =1

(y1  y2 ) =1

Veamos la primera ecuación. La consecuencia es igual a 1 cuando 0 0, 0 1, 1 1, lo que significa (x1 y1)=0 para (01), (10), entonces el par (X2  y2 ) puede ser cualquiera (00), (01), (10), (11), y cuando (x1 y1) = 1, es decir (00) y (11) el par (x2 y2) = 1 toma el mismos valores (00) y (11). Excluyamos de esta solución aquellos pares para los cuales la segunda y tercera ecuaciones son falsas, es decir, x1=1, x2=0, y1=1, y2=0.

Número total de pares 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) ¿Cuántas soluciones diferentes tiene el sistema de ecuaciones lógicas?

(X 1  (X 2  y 2 ))  (y 1  y 2 ) = 1

(X 2  (X 3  y 3 ))  (y 2  y 3 ) = 1

...

( X 6  ( X 7  y 7 ))  ( y 6  y 7 ) = 1

X 7  y 7 = 1

Solución. 1) Las ecuaciones son del mismo tipo, por lo que usando el razonamiento encontraremos todos los pares posibles (x1,y1), (x2,y2) de la primera ecuación.

(X1  (X2  y2 ))=1

(y1  y2 ) = 1

La solución a la segunda ecuación son los pares (00), (01), (11).

Encontremos soluciones a la primera ecuación. Si x1=0, entonces x2, y2 - cualquiera, si x1=1, entonces x2, y2 toma el valor (11).

Hagamos conexiones entre los pares (x1, y1) y (x2, y2).

Creemos una tabla para calcular el número de pares en cada etapa.

Teniendo en cuenta las soluciones de la última ecuación. X 7  y 7 = 1, excluyamos el par (10). Encuentra el número total de soluciones 1+7+0+34=42

3)(23.180) ¿Cuántas soluciones diferentes tiene un sistema de ecuaciones lógicas?

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Solución. 1) Las ecuaciones son del mismo tipo, por lo que usando el razonamiento encontraremos todos los pares posibles (x1,x2), (x3,x4) de la primera ecuación.

(X1  X2 )  (X3  X4 ) = 1

Excluyamos de la solución los pares que en la secuencia dan 0 (1 0), estos son los pares (01, 00, 11) y (10).

Hagamos conexiones entre pares (x1,x2), (x3,x4)

Sea una función lógica de n variables. La ecuación lógica se ve así:

La constante C tiene el valor 1 o 0.

Una ecuación lógica puede tener desde 0 hasta diferentes soluciones. Si C es igual a 1, entonces las soluciones son todos aquellos conjuntos de variables de la tabla de verdad para las cuales la función F toma el valor verdadero (1). Los conjuntos restantes son soluciones de la ecuación con C igual a cero. Siempre puedes considerar solo ecuaciones de la forma:

De hecho, déjese dar la ecuación:

En este caso, podemos ir a la ecuación equivalente:

Considere un sistema de k ecuaciones lógicas:

La solución de un sistema es un conjunto de variables en las que se satisfacen todas las ecuaciones del sistema. En términos de funciones lógicas, para obtener una solución a un sistema de ecuaciones lógicas, se debe encontrar un conjunto en el que la función lógica Ф sea verdadera, que represente la conjunción de las funciones originales:

Si el número de variables es pequeño, por ejemplo, menos de 5, entonces no es difícil construir una tabla de verdad para la función, que nos permita decir cuántas soluciones tiene el sistema y cuáles son los conjuntos que proporcionan soluciones.

En algunos problemas de USE sobre cómo encontrar soluciones a un sistema de ecuaciones lógicas, el número de variables llega a 10. Entonces, construir una tabla de verdad se convierte en una tarea casi imposible. Resolver el problema requiere un enfoque diferente. Para un sistema arbitrario de ecuaciones, no existe ningún método general distinto de la enumeración que permita resolver este tipo de problemas.

En los problemas propuestos en el examen, la solución suele basarse en tener en cuenta las particularidades del sistema de ecuaciones. Repito, aparte de probar todas las opciones para un conjunto de variables, no existe una forma general de resolver el problema. La solución debe construirse en función de las características específicas del sistema. A menudo resulta útil realizar una simplificación preliminar de un sistema de ecuaciones utilizando leyes lógicas conocidas. Otra técnica útil para resolver este problema es la siguiente. No nos interesan todos los conjuntos, sino sólo aquellos en los que la función tiene el valor 1. En lugar de construir una tabla de verdad completa, construiremos su análogo: un árbol de decisión binario. Cada rama de este árbol corresponde a una solución y especifica un conjunto en el que la función tiene el valor 1. El número de ramas del árbol de decisión coincide con el número de soluciones del sistema de ecuaciones.

Explicaré qué es un árbol de decisión binario y cómo se construye utilizando ejemplos de varios problemas.

Problema 18

¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 hay que satisfacen el sistema de dos ecuaciones?

Respuesta: El sistema tiene 36 soluciones diferentes.

Solución: El sistema de ecuaciones incluye dos ecuaciones. Encontremos el número de soluciones para la primera ecuación, dependiendo de 5 variables - . La primera ecuación puede considerarse a su vez como un sistema de 5 ecuaciones. Como se ha demostrado, el sistema de ecuaciones en realidad representa la conjunción de funciones lógicas. La afirmación inversa también es cierta: una conjunción de condiciones puede considerarse como un sistema de ecuaciones.

Construyamos un árbol de decisión para la implicación (): el primer término de la conjunción, que puede considerarse como la primera ecuación. Así es como se ve una representación gráfica de este árbol

El árbol consta de dos niveles según el número de variables de la ecuación. El primer nivel describe la primera variable. Dos ramas de este nivel reflejan los valores posibles de esta variable: 1 y 0. En el segundo nivel, las ramas del árbol reflejan solo aquellos valores posibles de la variable para los cuales la ecuación se evalúa como verdadera. Dado que la ecuación especifica una implicación, una rama que tiene el valor 1 requiere que en esta rama haya un valor de 1. Una rama que tiene el valor 0 genera dos ramas con valores iguales a 0 y 1. La ecuación construida El árbol especifica tres soluciones, en las cuales la implicación toma el valor 1. En cada rama, se escribe un conjunto correspondiente de valores de variables, que dan una solución a la ecuación.

Estos conjuntos son: ((1, 1), (0, 1), (0, 0))

Sigamos construyendo el árbol de decisión agregando la siguiente ecuación, la siguiente implicación. La especificidad de nuestro sistema de ecuaciones es que cada nueva ecuación del sistema utiliza una variable de la ecuación anterior, agregando una nueva variable. Dado que la variable ya tiene valores en el árbol, en todas las ramas donde la variable tiene un valor de 1, la variable también tendrá un valor de 1. Para tales ramas, la construcción del árbol continúa al siguiente nivel, pero no aparecen nuevas ramas. Una sola rama donde una variable tiene un valor de 0 se bifurcará en dos ramas donde la variable recibirá valores de 0 y 1. Así, cada adición de una nueva ecuación, dada su especificidad, suma una solución. Primera ecuación original:

tiene 6 soluciones. Así es como se ve el árbol de decisión completo para esta ecuación:

La segunda ecuación de nuestro sistema es similar a la primera:

La única diferencia es que la ecuación usa Y variables. Esta ecuación también tiene 6 soluciones. Dado que cada solución variable se puede combinar con cada solución variable, el número total de soluciones es 36.

Tenga en cuenta que el árbol de decisión construido proporciona no solo el número de soluciones (según el número de ramas), sino también las soluciones mismas escritas en cada rama del árbol.

Problema 19

¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existen que satisfacen todas las condiciones que se enumeran a continuación?

Esta tarea es una modificación de la tarea anterior. La diferencia es que se suma otra ecuación que relaciona las variables X e Y.

De la ecuación se deduce que cuando tiene un valor de 1 (existe una de esas soluciones), entonces tiene un valor de 1. Por lo tanto, hay un conjunto en el que y tiene valores de 1. Cuando es igual a 0, puede tienen cualquier valor, tanto 0 como 1. Por lo tanto, cada conjunto con , igual a 0, y hay 5 de esos conjuntos, corresponde a los 6 conjuntos con variables Y. Por lo tanto, el número total de soluciones es 31.

Problema 20

Solución: Recordando las equivalencias básicas, escribimos nuestra ecuación como:

La cadena cíclica de implicaciones significa que las variables son idénticas, por lo que nuestra ecuación es equivalente a la ecuación:

Esta ecuación tiene dos soluciones cuando todas son 1 o 0.

Problema 21

Cuantas soluciones tiene la ecuación:

Solución: Al igual que en el problema 20, pasamos de implicaciones cíclicas a identidades, reescribiendo la ecuación en la forma:

Construyamos un árbol de decisión para esta ecuación:

Problema 22

¿Cuántas soluciones tiene el siguiente sistema de ecuaciones?