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

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 2n 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 derivan ideas que permiten expresar una conjunción mediante negación y disyunción y, en consecuencia, expresar una 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?

X1	x2	X3	x4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

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 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 variables Y. 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 tal 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:

///

/// programa para contar el número de soluciones

/// ecuación lógica (sistema de ecuaciones)

///

///

/// 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:

X1	x2	X3	x4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

¿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)

El uso de ecuaciones está muy extendido en nuestra vida. Se utilizan en muchos cálculos, construcción de estructuras e incluso deportes. El hombre utilizó ecuaciones en la antigüedad y desde entonces su uso no ha hecho más que aumentar. En matemáticas, hay ciertos problemas que tienen que ver con la lógica proposicional. Para resolver este tipo de ecuación, es necesario tener ciertos conocimientos: conocimiento de las leyes de la lógica proposicional, conocimiento de las tablas de verdad de funciones lógicas de 1 o 2 variables, métodos para convertir expresiones lógicas. Además, es necesario conocer las siguientes propiedades de las operaciones lógicas: conjunción, disyunción, inversión, implicación y equivalencia.

Cualquier función lógica de \variables - \puede especificarse mediante una tabla de verdad.

Resolvamos varias ecuaciones lógicas:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Comencemos la solución con \[X1\] y determinemos qué valores puede tomar esta variable: 0 y 1. A continuación, consideraremos cada uno de los valores anteriores y veremos qué puede ser \[X2.\].

Como puede verse en la tabla, nuestra ecuación lógica tiene 11 soluciones.

¿Dónde puedo resolver una ecuación lógica en línea?

Puedes resolver la ecuación en nuestro sitio web https://site. El solucionador en línea gratuito le permitirá resolver ecuaciones en línea de cualquier complejidad en cuestión de segundos. Todo lo que necesitas hacer es simplemente ingresar tus datos en el solucionador. También puedes ver instrucciones en vídeo y aprender a resolver la ecuación en nuestro sitio web. Y si aún tienes preguntas, puedes hacerlas en nuestro grupo VKontakte http://vk.com/pocketteacher. Únete a nuestro grupo, siempre estaremos encantados de ayudarte.

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 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í 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 variables Y. 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?

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, donde J, K, L, M, N son variables lógicas?

Solución.

La expresión (N ∨ ¬N) es cierta para cualquier N, por lo tanto

J ∧ ¬K ∧ L ∧ ¬M = 0.

Apliquemos la negación a ambos lados de la ecuación lógica y usemos la ley de De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Obtenemos ¬J ∨ K ∨ ¬L ∨ M = 1.

Una suma lógica es igual a 1 si al menos uno de sus enunciados constituyentes es igual a 1. Por lo tanto, la ecuación resultante se satisface con cualquier combinación de variables lógicas, excepto en el caso en que todas las cantidades incluidas en la ecuación sean iguales a 0. Cada una de las 4 variables pueden ser iguales a 1 o 0, por lo tanto todas las combinaciones posibles son 2·2·2·2 = 16. Por lo tanto, la ecuación tiene 16 −1 = 15 soluciones.

Resta señalar que las 15 soluciones encontradas corresponden a cualquiera de los dos valores posibles de la variable lógica N, por lo que la ecuación original tiene 30 soluciones.

Respuesta: 30

¿Cuántas soluciones diferentes tiene la ecuación?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

¿Dónde J, K, L, M, N son variables lógicas?

No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de J, K, L, M y N para los que se cumple esta igualdad. Como respuesta, debe indicar el número de dichos conjuntos.

Solución.

Usamos las fórmulas A → B = ¬A ∨ B y ¬(A ∨ B) = ¬A ∧ ¬B

Consideremos la primera subfórmula:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Consideremos la segunda subfórmula.

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Consideremos la tercera subfórmula.

1) M → J = 1 por lo tanto,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Combinemos:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 por lo tanto 4 soluciones.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Combinemos:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L por lo tanto 4 soluciones.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Respuesta: 4 + 4 = 8.

Respuesta: 8

¿Cuántas soluciones diferentes tiene la ecuación?

((K ∨ L) → (L ∧ M ∧ N)) = 0

¿Dónde K, L, M, N son variables lógicas? La respuesta no necesita enumerar todos los diferentes conjuntos de valores de K, L, M y N para los que se cumple esta igualdad. Como respuesta debe indicar el número de dichos conjuntos.

Solución.

Reescribamos la ecuación usando una notación más simple para operaciones:

((K + L) → (L M N)) = 0

1) de la tabla de verdad de la operación “implicación” (ver el primer problema) se deduce que esta igualdad es verdadera si y solo si al mismo tiempo

K + L = 1 y L M N = 0

2) de la primera ecuación se deduce que al menos una de las variables, K o L, es igual a 1 (o ambas juntas); así que consideremos tres casos

3) si K = 1 y L = 0, entonces la segunda igualdad se cumple para cualquier M y N; como hay 4 combinaciones de dos variables booleanas (00, 01, 10 y 11), tenemos 4 soluciones diferentes

4) si K = 1 y L = 1, entonces la segunda igualdad es válida para M · N = 0; hay 3 combinaciones de este tipo (00, 01 y 10), tenemos 3 soluciones más

5) si K = 0, entonces L = 1 (de la primera ecuación); en este caso, la segunda igualdad se cumple cuando M · N = 0; hay 3 combinaciones de este tipo (00, 01 y 10), tenemos 3 soluciones más

6) en total obtenemos 4 + 3 + 3 = 10 soluciones.

Respuesta: 10

¿Cuántas soluciones diferentes tiene la ecuación?

(K ∧ L) ∨ (M ∧ N) = 1

Solución.

La expresión es verdadera en tres casos, cuando (K ∧ L) y (M ∧ N) son iguales a 01, 11, 10, respectivamente.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N son iguales a 1, y K y L son cualquier cosa menos simultáneamente 1. Por lo tanto, hay 3 soluciones.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 solución.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 soluciones.

Respuesta: 7.

Respuesta: 7

¿Cuántas soluciones diferentes tiene la ecuación?

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0

¿Dónde X, Y, Z, P son variables lógicas? No es necesario que la respuesta enumere todos los diferentes conjuntos de valores para los que se cumple esta igualdad. Como respuesta, solo necesita indicar el número de dichos conjuntos.

Solución.

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

El OR lógico es falso sólo en un caso: cuando ambas expresiones son falsas.

Por eso,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Por lo tanto, sólo hay una solución para la ecuación.

Respuesta 1

¿Cuántas soluciones diferentes tiene la ecuación?

(K ∨ L) ∧ (M ∨ N) = 1

¿Dónde K, L, M, N son variables lógicas? No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de K, L, M y N para los que se cumple esta igualdad. Como respuesta, solo necesita indicar el número de dichos conjuntos.

Solución.

La And lógica es verdadera sólo en un caso: cuando todas las expresiones son verdaderas.

K ∨ L = 1, METRO ∨ norte = 1.

Cada ecuación da 3 soluciones.

Considere la ecuación A ∧ B = 1, si tanto A como B toman valores verdaderos en tres casos cada uno, entonces en total la ecuación tiene 9 soluciones.

Por tanto la respuesta es 9.

Respuesta: 9

¿Cuántas soluciones diferentes tiene la ecuación?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

¿Dónde A, B, C, D son variables lógicas?

No es necesario que la respuesta enumere todos los diferentes conjuntos de valores A, B, C, D para los que se cumple esta igualdad. Como respuesta, debe indicar el número de dichos conjuntos.

Solución.

El "O" lógico es verdadero cuando al menos una de las afirmaciones es verdadera.

(D ∧ ¬D)= 0 para cualquier D.

Por eso,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, lo que nos da 3 posibles soluciones para cada D.

(D ∧ ¬ D)= 0 para cualquier D, lo que nos da dos soluciones (para D = 1, D = 0).

Por lo tanto: soluciones totales 2*3 = 6.

Total de 6 soluciones.

Respuesta: 6

¿Cuántas soluciones diferentes tiene la ecuación?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

¿Dónde K, L, M, N son variables lógicas? No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de K, L, M y N para los que se cumple esta igualdad. Como respuesta, solo necesita indicar el número de dichos conjuntos.

Solución.

Apliquemos la negación a ambos lados de la ecuación:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

El OR lógico es verdadero en tres casos.

Opción 1.

K ∧ L ∧ M = 1, entonces K, L, M = 1 y ¬L ∧ M ∧ N = 0. N es arbitrario, es decir, 2 soluciones.

Opcion 2.

¬L ∧ M ∧ N = 1, entonces N, M = 1; L = 0, K cualquiera, es decir, 2 soluciones.

Por tanto la respuesta es 4.

Respuesta: 4

A, B y C son números enteros para los cuales la afirmación es verdadera.

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

¿A qué es igual B si A = 45 y C = 43?

Solución.

Tenga en cuenta que esta declaración compleja consta de tres simples.

1) ¬(A = B); (A > B) → (B > C); (B > A) → (C > B);

2) estas declaraciones simples están conectadas por la operación ∧ (Y, conjunción), es decir, deben ejecutarse simultáneamente;

3) de ¬(A = B)=1 se sigue inmediatamente que A B;

4) supongamos que A > B, entonces de la segunda condición obtenemos 1→(B > C)=1; esta expresión puede ser verdadera si y sólo si B > C = 1;

5) por lo tanto tenemos A > B > C, sólo el número 44 corresponde a esta condición;

6) por si acaso, marquemos también la opción A 0 →(B > C)=1;

esta expresión es cierta para cualquier B; Ahora miramos la tercera condición y obtenemos

esta expresión puede ser verdadera si y sólo si C > B, y aquí tenemos una contradicción, porque no existe tal número B para el cual C > B > A.

Respuesta: 44.

Respuesta: 44

Construir una tabla de verdad para una función lógica.

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

en la que la columna de valores del argumento A es la representación binaria del número 27, la columna de valores del argumento B es el número 77, la columna de valores del argumento C es el número 120. El número en la columna se escribe de arriba a abajo, desde el más significativo al menos significativo (incluido el conjunto cero). Convierta la representación binaria resultante de los valores de la función X al sistema numérico decimal.

Solución.

Escribamos la ecuación usando notación más simple para operaciones:

1) esta es una expresión con tres variables, por lo que habrá líneas en la tabla de verdad; por lo tanto, la representación binaria de los números utilizados para construir las columnas A, B y C de la tabla debe constar de 8 dígitos.

2) convertir los números 27, 77 y 120 al sistema binario, sumando inmediatamente hasta 8 dígitos de ceros al comienzo de los números

3) Es poco probable que pueda escribir inmediatamente los valores de la función X para cada combinación, por lo que es conveniente agregar columnas adicionales a la tabla para calcular resultados intermedios (consulte la tabla a continuación)

X0

A	EN	CON
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) complete las columnas de la tabla:

A	EN	CON					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

el valor es 1 solo en aquellas líneas donde A = B

el valor es 1 en aquellas líneas donde B o C = 1

el valor es 0 solo en aquellas líneas donde A = 1 y B + C = 0

el valor es el inverso de la columna anterior (0 se reemplaza por 1 y 1 se reemplaza por 0)

el resultado de X (última columna) es la suma lógica de las dos columnas y

5) para obtener la respuesta, escribe los bits de la columna X de arriba a abajo:

6) convierte este número al sistema decimal:

Respuesta: 171

¿Cuál es el mayor entero X para el cual la afirmación (10 (X+1)·(X+2)) es verdadera?

Solución.

Una ecuación es una operación de implicación entre dos relaciones:

1) Por supuesto, aquí puedes aplicar el mismo método que en el ejemplo 2208, pero necesitarás resolver ecuaciones cuadráticas (no quiero...);

2) Tenga en cuenta que por condición solo nos interesan los números enteros, por lo que podemos intentar transformar de alguna manera la expresión original, obteniendo una declaración equivalente (¡no nos interesan en absoluto los valores exactos de las raíces!);

3) Considere la desigualdad: obviamente, puede ser un número positivo o negativo;

4) Es fácil comprobar que en el dominio la afirmación es verdadera para todos los números enteros , y en el dominio - para todos los números enteros (para no confundirse, es más conveniente utilizar desigualdades no estrictas y , en lugar de y );

5) Por tanto, para números enteros se puede sustituir por una expresión equivalente.

6) el dominio de verdad de una expresión es la unión de dos intervalos infinitos;

7) Consideremos ahora la segunda desigualdad: es obvio que también puede ser un número positivo o negativo;

8) En la región, la afirmación es verdadera para todos los números enteros, y en la región, para todos los números enteros, por lo tanto, para los números enteros se puede reemplazar con una expresión equivalente.

9) el dominio de verdad de la expresión es un intervalo cerrado;

10) La expresión dada es verdadera en todas partes, excepto en las áreas donde y ;

11) Tenga en cuenta que el valor ya no es adecuado, porque allí y , es decir, la implicación da 0;

12) Al sustituir 2, (10 (2+1) · (2+2)), o 0 → 0 que satisface la condición.

Entonces la respuesta es 2.

Respuesta: 2

¿Cuál es el mayor número entero X para el cual la afirmación es verdadera?

(50 (X+1)·(X+1))?

Solución.

Apliquemos la transformación de implicación y transformemos la expresión:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

El OR lógico es verdadero cuando al menos una afirmación lógica es verdadera. Resueltas ambas desigualdades y teniendo en cuenta que vemos que el mayor número entero para el que se satisface al menos una de ellas es 7 (en la figura, la solución positiva de la segunda desigualdad se muestra en amarillo y la primera en azul).

Respuesta: 7

Indique los valores de las variables K, L, M, N, en los que la expresión lógica

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

FALSO. Escribe la respuesta como una cadena de 4 caracteres: los valores de las variables K, L, M y N (en ese orden). Entonces, por ejemplo, la línea 1101 corresponde al hecho de que K=1, L=1, M=0, N=1.

Solución.

Duplica la tarea 3584.

Respuesta: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Solución.

Apliquemos la transformación de implicaciones:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Apliquemos la negación a ambos lados de la ecuación:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Transformemos:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Por lo tanto, M = 0, N = 0, ahora considere (¬K ∧ L ∨ M ∧ L):

del hecho de que M = 0, N = 0 se sigue que M ∧ L = 0, entonces ¬K ∧ L = 1, es decir, K = 0, L = 1.

Respuesta: 0100

Especifique los valores de las variables K, L, M, N en los que la expresión lógica

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

FALSO. Escribe tu respuesta como una cadena de cuatro caracteres: los valores de las variables K, L, M y N (en ese orden). Entonces, por ejemplo, la línea 1101 corresponde al hecho de que K=1, L=1, M=0, N=1.

Solución.

Escribamos la ecuación usando una notación de operaciones más simple (la condición "la expresión es falsa" significa que es igual al cero lógico):

1) de la formulación de la condición se deduce que la expresión debe ser falsa solo para un conjunto de variables

2) de la tabla de verdad de la operación “implicación” se deduce que esta expresión es falsa si y sólo si al mismo tiempo

3) la primera igualdad (el producto lógico es igual a 1) se cumple si y sólo si y ; de esto se sigue (la suma lógica es igual a cero), lo cual sólo puede suceder cuando ; Así, ya hemos definido tres variables.

4) de la segunda condición, , para y obtenemos .

Duplica la tarea

Respuesta: 1000

Especifique los valores de las variables lógicas P, Q, S, T, en las que la expresión lógica

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) es falso.

Escribe la respuesta como una cadena de cuatro caracteres: los valores de las variables P, Q, S, T (en ese orden).

Solución.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Apliquemos la transformación de implicación:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Respuesta: 0100

Especifique los valores de las variables K, L, M, N en los que la expresión lógica

(K → M) ∨ (L ∧ K) ∨ ¬norte

FALSO. Escribe tu respuesta como una cadena de cuatro caracteres: los valores de las variables K, L, M y N (en ese orden). Entonces, por ejemplo, la línea 1101 corresponde al hecho de que K=1, L=1, M=0, N=1.

Solución.

El OR lógico es falso si y sólo si ambas afirmaciones son falsas.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Apliquemos la transformación de implicación para la primera expresión:

¬K ∨ M = 0 => K = 1, M = 0.

Considere la segunda expresión:

(L ∧ K) ∨ ¬N = 0 (ver el resultado de la primera expresión) => L ∨ ¬N = 0 => L = 0, N = 1.

Respuesta: 1001.

Respuesta: 1001

Especifique los valores de las variables K, L, M, N en los que la expresión lógica

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

verdadero. Escribe tu respuesta como una cadena de cuatro caracteres: los valores de las variables K, L, M y N (en ese orden). Entonces, por ejemplo, la línea 1101 corresponde al hecho de que K=1, L=1, M=0, N=1.

Solución.

El "Y" lógico es verdadero si y sólo si ambas afirmaciones son verdaderas.

1) (K → M) = 1 Aplicar la transformación de implicación: ¬K ∨ M = 1

2) (K → ¬M) = 1 Aplicar la transformación de implicación: ¬K ∨ ¬M = 1

De ello se deduce que K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Apliquemos la transformación de implicación: K ∨ (M ∧ ¬L ∧ N) = 1 del hecho de que K = 0 obtenemos.

Este material contiene una presentación que presenta métodos para resolver ecuaciones lógicas y sistemas de ecuaciones lógicas en la tarea B15 (No. 23, 2015) del Examen Estatal Unificado en informática. Se sabe que esta tarea es una de las más difíciles entre las tareas del Examen Estatal Unificado. La presentación puede resultar útil a la hora de impartir lecciones sobre el tema "Lógica" en clases especializadas, así como al prepararse para el Examen Estatal Unificado.

Descargar:

Avance:

Para utilizar vistas previas de presentaciones, cree una cuenta de Google e inicie sesión en ella: https://accounts.google.com

Títulos de diapositivas:

Solución de la tarea B15 (sistemas de ecuaciones lógicas) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18 de noviembre de 2013, Saratov

¡¡¡La tarea B15 es una de las más difíciles del Examen Estatal Unificado de Informática!!! Se prueban las siguientes habilidades: convertir expresiones que contienen variables lógicas; describir en lenguaje natural el conjunto de valores de variables lógicas para las cuales un conjunto dado de variables lógicas es verdadero; Cuente el número de conjuntos binarios que satisfacen las condiciones dadas. Lo más difícil es porque... No existen reglas formales sobre cómo hacer esto, requiere conjeturas.

¡Sin lo que no puedes prescindir!

¡Sin lo que no puedes prescindir!

Conjunción de símbolos: A /\ B , A  B , AB , A &B, A y B disyunción: A \ / B , A + B , A | B , A o B negación:  A , A, no A equivalencia: A  B, A  B, A  B exclusivo “o”: A  B , A xor B

Método de reemplazo de variables ¿Cuántos conjuntos diferentes de valores de variables lógicas x1, x2, ..., x9, x10 existen que satisfacen todas las condiciones enumeradas a continuación: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ​​(¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​​​(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 La respuesta no necesita enumerar todos los diferentes conjuntos x1, x2, …, x9, x10 para los cuales este sistema de igualdades se mantiene. Como respuesta, debe indicar el número de dichos conjuntos (versión de demostración 2012)

Solución Paso 1. Simplifique cambiando variables t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Después de la simplificación: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Considere una de las ecuaciones: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Obviamente, =1 solo si una de las variables es 0 y la otra es 1 .Usemos la fórmula para expresar la operación XOR mediante conjunción y disyunción: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Paso 2. Análisis del sistema ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .A. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), entonces cada valor de tk corresponde a dos pares de valores x2k-1 y x2k, por ejemplo: tk =0 corresponde a dos pares - (0 ,1) y (1, 0) , y tk =1 – pares (0,0) y (1,1).

Paso 3. Contando el número de soluciones. Cada t tiene 2 soluciones, el número de ts es 5. Por tanto. para las variables t hay 2 5 = 32 soluciones. Pero a cada t le corresponde un par de soluciones x, es decir el sistema original tiene 2*32 = 64 soluciones. Respuesta: 64

Método de eliminación de parte de las soluciones ¿Cuántos conjuntos diferentes de valores de variables lógicas x1, x2,..., x5, y1,y2,..., 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; y5→ x5 =1. La respuesta no necesita enumerar todos los diferentes conjuntos x1, x2, ..., x5, y 1, y2, ..., y5 para los que se cumple este sistema de igualdad. La respuesta debe indicar el número de dichos conjuntos.

Solución. Paso 1. Solución secuencial de las ecuaciones x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 La primera ecuación es la conjunción de varias operaciones de implicación, igual a 1, es decir cada una de las implicaciones es cierta. La implicación es falsa sólo en un caso, cuando 1  0, en todos los demás casos (0  0, 0  1, 1  1) la operación devuelve 1. Escribamos esto en forma de tabla:

Paso 1. Solución secuencial de ecuaciones T.o. Se obtuvieron 6 conjuntos de soluciones para x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Razonando de manera similar, llegamos a la conclusión de que para y1, y2, y3, y4, y5 existe el mismo conjunto de soluciones. Porque estas ecuaciones son independientes, es decir no tienen variables comunes, entonces la solución de este sistema de ecuaciones (sin tener en cuenta la tercera ecuación) será 6 * 6 = 36 pares de “X” e “Y”. Considere la tercera ecuación: y5→ x5 =1 La solución son los pares: 0 0 0 1 1 1 El par no es una solución: 1 0

Comparemos las soluciones obtenidas, donde y5 =1, x5=0 no es adecuada. hay 5 de estos pares Número de soluciones al sistema: 36-5= 31. Respuesta: ¡¡¡Se necesitaba 31 Combinatoria!!!

Método de programación dinámica ¿Cuántas soluciones diferentes tiene la ecuación lógica x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, donde x 1, x 2,…, x 6 son 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 las cantidades de dichos conjuntos.

Solución Paso 1. Análisis de la condición A la izquierda de la ecuación se escriben secuencialmente las operaciones de implicación, la prioridad es la misma. Reescribamos: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 ¡NB! ¡Cada variable posterior depende no de la anterior, sino del resultado de la implicación anterior!

Paso 2. Revelando el patrón Consideremos la primera implicación, X 1 → X 2. Tabla de verdad: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 De un 0 obtuvimos 2 unidades, y de 1 obtuvimos un 0 y un 1. Solo hay un 0 y tres unos, este es el resultado de la primera operación.

Paso 2. Revelar un patrón Al conectar x 3 con el resultado de la primera operación, obtenemos: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 De dos 0 – dos 1, de cada 1 (hay 3) un 0 y un 1 (3+3)

Paso 3. Derivación de la fórmula T.o. puedes crear fórmulas para calcular el número de ceros N i y el número de unos E i para una ecuación con i variables: ,

Paso 4. Completar la tabla Completemos la tabla de izquierda a derecha para i = 6, calculando el número de ceros y unos usando las fórmulas anteriores; la tabla muestra cómo se construye la siguiente columna a partir de la anterior: número de variables 1 2 3 4 5 6 Número de ceros N i 1 1 3 5 11 21 Número de unos E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Respuesta: 43

Método que utiliza simplificaciones de expresiones lógicas ¿Cuántas soluciones diferentes tiene la ecuación ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 donde J, K, L, M, N son variables lógicas? No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de J, K, L, M y N para los que se cumple esta igualdad. Como respuesta, debe indicar el número de dichos conjuntos.

Solución Observa que J → K = ¬ J  K Introduzcamos un cambio de variables: J → K=A, M  N  L =B Reescribamos la ecuación teniendo en cuenta el cambio: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Obviamente, A  B para los mismos valores de A y B 6. Considere la última implicación M → J =1 Esto es posible si: M= J=0 M=0, J=1 M=J=1

Solución porque A  B, entonces cuando M=J=0 obtenemos 1 + K=0. Sin soluciones. Cuando M=0, J=1 obtenemos 0 + K=0, K=0, y N y L son cualquiera, 4 soluciones: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Solución 10. Cuando M=J=1 obtenemos 0+K=1 *N * L, o K=N*L, 4 soluciones: 11. El total tiene 4+4=8 soluciones Respuesta: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Fuentes de información: O.B. Bogomolova, D.Yu. Usenkov. B15: nuevas tareas y nuevas soluciones // Informática, No. 6, 2012, p. 35 – 39. K.Yu. Poliakov. Ecuaciones lógicas // Informática, No. 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [recurso electrónico]. http://kpolyakov.narod.ru/school/ege.htm, [recurso electrónico].