Resolver sistemas de ecuaciones lógicas cambiando variables.
El método de sustitución de variables se utiliza si algunas variables se incluyen en las ecuaciones solo en forma de una expresión específica y nada más. Entonces esta expresión se puede denotar mediante una nueva variable.
Ejemplo 1.
¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, x6, x7, x8 existen que satisfacen todas las condiciones que se enumeran a continuación?
(x1 → x2) → (x3→ x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de las variables x1, x2, x3, x4, x5, x6, x7, x8 para los que se satisface este sistema de igualdad. Como respuesta, debe indicar el número de dichos conjuntos.
Solución:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Entonces podemos escribir el sistema en forma de una sola ecuación:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. La conjunción es 1 (verdadera) cuando cada operando toma el valor 1. Es decir cada una de las implicaciones debe ser verdadera, y esto es cierto para todos los valores excepto (1 → 0). Aquellos. en la tabla de valores de las variables y1, y2, y3, y4, uno no debe estar a la izquierda de cero:
Aquellos. las condiciones se cumplen para 5 conjuntos y1-y4.
Porque y1 = x1 → x2, entonces el valor y1 = 0 se logra en un único conjunto x1, x2: (1, 0), y el valor y1 = 1 – en tres conjuntos x1, x2: (0,0), (0 ,1), (1.1). Lo mismo ocurre con y2, y3, y4.
Dado que cada conjunto (x1,x2) de la variable y1 se combina con cada conjunto (x3,x4) de la variable y2, etc., los números de conjuntos de las variables x se multiplican:
|
Número de conjuntos por x1…x8 |
||||
Sumemos el número de conjuntos: 1 + 3 + 9 + 27 + 81 = 121.
Respuesta: 121
Ejemplo 2.
¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2,... x9, y1, y2,... y9 hay que satisfacen todas las condiciones que se enumeran a continuación?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
en respuesta No hay necesidad enumere todos los diferentes conjuntos de valores de las variables x1, x2, ... x9, y1, y2, ... y9 para los cuales se satisface el sistema de igualdades dado. Como respuesta, debe indicar el número de dichos conjuntos.
Solución:
Hagamos un cambio de variables:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
El sistema se puede escribir como una sola ecuación:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
La equivalencia es verdadera sólo si ambos operandos son iguales. Hay dos conjuntos de soluciones para esta ecuación:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Porque zi = (xi ≡ yi), entonces el valor zi = 0 corresponde a dos conjuntos (xi,yi): (0,1) y (1,0), y el valor zi = 1 corresponde a dos conjuntos (xi,yi) ): (0,0) y (1,1).
Entonces el primer conjunto z1, z2,…, z9 corresponde a 2 9 conjuntos (x1,y1), (x2,y2),…, (x9,y9).
El mismo número corresponde al segundo conjunto z1, z2,…, z9. Entonces hay un total de 2 9 +2 9 = 1024 conjuntos.
Respuesta: 1024
Resolver sistemas de ecuaciones lógicas determinando visualmente la recursividad.
Este método se utiliza si el sistema de ecuaciones es bastante simple y el orden de aumento del número de conjuntos al sumar variables es obvio.
Ejemplo 3.
¿Cuántas soluciones diferentes tiene el sistema de ecuaciones?
¬x9 ∨ x10 = 1,
¿Dónde x1, x2,… x10 son variables lógicas?
No es necesario que la respuesta enumere todos los diferentes conjuntos de valores x1, x2,... x10 para los que se satisface este sistema de igualdades. Como respuesta, debe indicar el número de dichos conjuntos.
Solución:
Resolvamos la primera ecuación. Una disyunción es igual a 1 si al menos uno de sus operandos es igual a 1. Es decir las soluciones son los conjuntos:
Para x1=0, existen dos valores de x2 (0 y 1), y para x1=1 solo existe un valor de x2 (1), tal que el conjunto (x1,x2) es solución de la ecuación . Hay 3 juegos en total.
Sumemos la variable x3 y consideremos la segunda ecuación. Es similar al primero, lo que significa que para x2=0 existen dos valores de x3 (0 y 1), y para x2=1 solo existe un valor x3 (1), tal que el conjunto (x2 ,x3) es una solución de la ecuación. Hay 4 juegos en total.
Es fácil ver que al agregar otra variable, se agrega un conjunto. Aquellos. Fórmula recursiva para el número de conjuntos de (i+1) variables:
N i +1 = N i + 1. Luego, para diez variables obtenemos 11 conjuntos.
Respuesta: 11
Resolver sistemas de ecuaciones lógicas de varios tipos.
Ejemplo 4.
¿Cuántos conjuntos diferentes de valores de las variables lógicas x 1,..., x 4, y 1,..., y 4, z 1,..., z 4 hay que satisfacen todas las condiciones enumeradas a continuación? ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
en respuesta No hay necesidad Enumere todos los diferentes conjuntos de valores de las variables x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 para los que se satisface este sistema de igualdad.
Como respuesta, debe indicar el número de dichos conjuntos.
Solución:
Tenga en cuenta que las tres ecuaciones del sistema son iguales en diferentes conjuntos independientes de variables.
Veamos la primera ecuación. Una conjunción es verdadera (igual a 1) sólo si todos sus operandos son verdaderos (igual a 1). La implicación es 1 en todas las tuplas excepto (1,0). Esto significa que la solución a la primera ecuación serán los siguientes conjuntos x1, x2, x3, x4, en los que 1 no está ubicado a la izquierda de 0 (5 conjuntos):
De manera similar, las soluciones de la segunda y tercera ecuaciones serán absolutamente los mismos conjuntos y1,…,y4 y z1,…, z4.
Ahora analicemos la cuarta ecuación del sistema: x 4 ∧ y 4 ∧ z 4 = 0. La solución serán todos los conjuntos x4, y4, z4 en los que al menos una de las variables sea igual a 0.
Aquellos. para x4 = 0, todos los conjuntos posibles (y4, z4) son adecuados, y para x4 = 1, son adecuados los conjuntos (y4, z4), en los que hay al menos un cero: (0, 0), (0,1 ), (1, 0).
|
Número de juegos |
||||
El número total de conjuntos es 25 + 4*9 = 25 + 36 = 61.
Respuesta: 61
Resolver sistemas de ecuaciones lógicas mediante la construcción de fórmulas recurrentes.
El método de construcción de fórmulas recurrentes se utiliza para resolver sistemas complejos en los que el orden de aumento del número de conjuntos no es obvio y construir un árbol es imposible debido a los volúmenes.
Ejemplo 5.
¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2,... x7, y1, y2,... y7 hay que satisfacen todas las condiciones que se enumeran a continuación?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
La respuesta no necesita enumerar todos los diferentes conjuntos de valores de las variables x1, x2,..., x7, y1, y2,..., y7 para los que se satisface este sistema de igualdades. Como respuesta, debe indicar el número de dichos conjuntos.
Solución:
Tenga en cuenta que las primeras seis ecuaciones del sistema son idénticas y difieren sólo en el conjunto de variables. Veamos la primera ecuación. Su solución serán los siguientes conjuntos de variables:
Denotemos:
número de tuplas (0,0) en las variables (x1,y1) hasta A 1,
número de tuplas (0,1) en las variables (x1,y1) hasta B 1,
número de tuplas (1,0) en las variables (x1,y1) hasta C 1,
el número de tuplas (1,1) en las variables (x1,y1) hasta D 1 .
número de tuplas (0,0) en las variables (x2,y2) hasta A 2,
número de tuplas (0,1) en las variables (x2,y2) hasta B 2,
número de tuplas (1,0) en las variables (x2,y2) hasta C 2,
el número de tuplas (1,1) en las variables (x2,y2) hasta D 2 .
Del árbol de decisión vemos que
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Tenga en cuenta que el conjunto (0,0) de las variables (x2,y2) se obtiene de los conjuntos (0,1), (1,0) y (1,1) de las variables (x1,y1). Aquellos. A 2 =B 1 +C 1 +D 1.
El conjunto (0,1) de las variables (x2,y2) se obtiene de los conjuntos (0,1), (1,0) y (1,1) de las variables (x1,y1). Aquellos. B 2 =B 1 +C 1 +D 1.
Argumentando de manera similar, observamos que C 2 =B 1 +C 1 +D 1. D2 = D1.
Así, obtenemos fórmulas recurrentes:
A yo+1 = B yo + C yo + D yo
B yo+1 = B yo + C yo + D yo
C i+1 = B i + C i + D i
D i+1 = A i +B i + C i + D i
hagamos una mesa
| Conjuntos | Designación. | Fórmula |
Número de juegos |
||||||
| yo=1 | yo=2 | yo=3 | yo=4 | yo=5 | yo=6 | yo=7 | |||
| (0,0) | yo | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B yo | B yo+1 =B yo +C yo +D yo | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C yo | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | yo | D yo+1 =D yo | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
La última ecuación (x7 ∨ y7) = 1 la satisfacen todos los conjuntos excepto aquellos en los que x7=0 e y7=0. En nuestra tabla, el número de estos conjuntos es A 7.
Entonces el número total de conjuntos es B 7 + C 7 + D 7 = 127+127+1 = 255
Respuesta: 255
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.
- Conmutatividad de disyunción y conjunción:
un ˅ segundo ≡ segundo ˅ un
a^b ≡ b^a - Ley distributiva sobre disyunción y conjunción:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Negación de la negación:
¬(¬a) ≡a - Consistencia:
a ^ ¬a ≡ falso - Tercero exclusivo:
a ˅ ¬а ≡ verdadero - Leyes de De Morgan:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Simplificación:
a ˄ a ≡ a
un ˅ un ≡ un
a ˄ verdadero ≡ a
a ˄ falso ≡ falso - Absorción:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Reemplazo de implicación
a → b ≡ ¬a ˅ b - 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 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 Tareas del examen estatal unificado Junto con estas funciones, a menudo se encuentran implicaciones.
Veamos algunos tareas simples Relacionado con 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 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
- ¬ 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.
- 13579
- 97531
- 24678
- 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 en este caso.
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 | do | 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. Sólo dos cosas se desprenden de la verdad de su testimonio: 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 varias opciones, correspondiente 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 existen método general, a diferencia de la fuerza bruta, que permite solucionar 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. Otro truco útil La solución a 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 mesa completa En verdad, 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 cuales 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. Esto es lo que parece árbol completo soluciones 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 X i se puede combinar con cada solución para las variables Y j, entonces número total Hay 36 soluciones.
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 etapa inicial es posible establecer un 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. Una computadora puede hacer frente con bastante facilidad a tareas en las que el número de variables es de 20 a 30, pero tardará mucho en empezar a pensar en los problemas. tamaño más grande. 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. Usando funciones básicas 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 una función lógica correspondiente a una ecuación lógica o un sistema de ecuaciones.
En un programa de este tipo, es necesario crear un bucle en función del número de conjuntos, formar el conjunto en sí en el cuerpo del bucle en función del número del conjunto, calcular el valor de la función en este conjunto y, si este 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 tarea dificil Obtener un conjunto de valores variables por número determinado se reduce al conocido problema de convertir un número al sistema 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
///
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 dadas 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 variables de función divertido. 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 verdadera.
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 usa la función SolveEquations para resolver varios sistemas de ecuaciones lógicas. La función SolveEquations es parte de la clase ProgramCommon siguiente:
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
- ¿Cuál de las tres funciones es equivalente?
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X˄Y
- 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?
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 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.
- 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.
- 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:
- Si una palabra par termina en vocal, entonces siguiente palabra, si existe, debe comenzar con vocal.
- 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? - Mamá lavó a Masha con jabón.
- Un líder es siempre un modelo.
- La verdad es buena, pero la felicidad es mejor.
- Cuantas soluciones tiene la ecuación:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Enumere todas las soluciones de la ecuación:
(a → b) → c = 0 - ¿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 - Cuantas soluciones tiene la ecuación:
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1
Respuestas a los problemas:
- Las funciones b y c son equivalentes.
- El fragmento corresponde a la función b.
- 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) - 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)) - Oración b.
- La ecuación tiene 3 soluciones: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)
Métodos para resolver sistemas de ecuaciones lógicas.
Puedes resolver un sistema de ecuaciones lógicas, por ejemplo, usando una tabla de verdad (si el número de variables no es demasiado grande) o usando un árbol de decisión, habiendo simplificado primero cada ecuación.
1. Método de reemplazo de variables.
La introducción de nuevas variables permite simplificar el sistema de ecuaciones, reduciendo el número de incógnitas.Las nuevas variables deben ser independientes entre sí.. Luego de resolver el sistema simplificado, debemos volver a las variables originales.
Consideremos la aplicación de este método usando un ejemplo específico.
Ejemplo.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Solución:
Introduzcamos nuevas variables: A=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); mi=(X9 ≡ X10).
(¡Atención! Cada una de las variables x1, x2, ..., x10 debe incluirse en sólo una de las nuevas variables A, B, C, D, E, es decir. las nuevas variables son independientes entre sí).
Entonces el sistema de ecuaciones quedará así:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Construyamos un árbol de decisión para el sistema resultante:
Considere la ecuación A=0, es decir (X1≡ X2)=0. Tiene 2 raíces:
X1≡X2 |
||
En la misma tabla se puede ver que la ecuación A=1 también tiene 2 raíces. Organicemos el número de raíces en el árbol de decisión:
Para encontrar la cantidad de soluciones de una rama, debes multiplicar la cantidad de soluciones en cada nivel. La rama izquierda tiene 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 soluciones; la rama derecha también tiene 32 soluciones. Aquellos. todo el sistema tiene 32+32=64 soluciones.
Respuesta: 64.
2. Método de razonamiento.
La dificultad de resolver sistemas de ecuaciones lógicas radica en lo engorroso de un árbol de decisión completo. El método de razonamiento le permite no construir el árbol completo, sino comprender cuántas ramas tendrá. Veamos este método usando ejemplos específicos.
Ejemplo 1. ¿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
No es necesario que la respuesta enumere todos los diferentes conjuntos de valores de las variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 para los que se satisface este sistema de igualdad. Como respuesta, debe indicar el número de dichos conjuntos.
Solución :
La primera y segunda ecuaciones contienen variables independientes que están relacionadas por la tercera condición. Construyamos un árbol de soluciones para la primera y segunda ecuaciones.
Para representar un árbol de soluciones para un sistema de la primera y segunda ecuaciones, cada rama del primer árbol debe continuar con un árbol de variables. en . El árbol así construido tendrá 36 ramas. Algunas de estas ramas no satisfacen la tercera ecuación del sistema. Marquemos el número de ramas del árbol en el primer árbol."y" , que satisfacen la tercera ecuación:
Expliquemos: para satisfacer la tercera condición, cuando x1 = 0, debe ser y1 = 1, es decir, todas las ramas del árbol."INCÓGNITA" , donde x1=0 puede continuar con una sola rama del árbol"y" . Y sólo por una rama del árbol"INCÓGNITA" (derecha) todas las ramas del árbol encajan"y". Así, el árbol completo de todo el sistema contiene 11 ramas. Cada rama representa una solución del sistema de ecuaciones original. Esto significa que todo el sistema tiene 11 soluciones.
Respuesta: 11.
Ejemplo 2. ¿Cuántas soluciones diferentes tiene el sistema de ecuaciones?
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
¿Dónde x1, x2,…, x10 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 el número de dichos conjuntos.
Solución : Simplifiquemos el sistema. Construyamos una tabla de verdad para parte de la primera ecuación:
X1∧X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Presta atención a la última columna, coincide con el resultado de la acción. X1 ≡ X10.
X1≡X10 |
Después de la simplificación obtenemos:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Considere la última ecuación:(X1 ≡ X10) = 0, es decir x1 no debe coincidir con x10. Para que la primera ecuación sea igual a 1, la igualdad debe ser verdadera(X1 ≡ X2)=1, es decir x1 debe coincidir con x2.
Construyamos un árbol de soluciones para la primera ecuación:
Considere la segunda ecuación: para x10=1 y para x2=0 el soportedebe ser igual a 1 (es decir, x2 coincide con x3); para x10=0 y para x2=1 soporte(X2 ≡ X10)=0, lo que significa el soporte (X2 ≡ X3) debe ser igual a 1 (es decir, x2 coincide con x3):
Razonando de esta manera, construimos un árbol de decisión para todas las ecuaciones:
Por tanto, el sistema de ecuaciones tiene sólo 2 soluciones.
Respuesta: 2.
Ejemplo 3.
¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 existen que satisfacen todas las condiciones que se enumeran a continuación?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
Solución:
Construyamos un árbol de soluciones para la primera ecuación:
Considere la segunda ecuación:
- Cuando x1=0 : el segundo y tercer paréntesis serán iguales a 0; para que el primer paréntesis sea igual a 1, y1=1, z1=1 (es decir, en este caso, 1 solución)
- Cuando x1=1 : el primer paréntesis será igual a 0; segundo o el tercer paréntesis debe ser igual a 1; el segundo paréntesis será igual a 1 cuando y1=0 y z1=1; el tercer paréntesis será igual a 1 cuando y1=1 y z1=0 (es decir, en este caso, 2 soluciones).
Lo mismo ocurre con las ecuaciones restantes. Observemos el número resultante de soluciones para cada nodo del árbol:
Para saber el número de soluciones para cada rama, multiplique los números resultantes por separado para cada rama (de izquierda a derecha).
1 rama: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solución
Rama 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 soluciones
3ra rama: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 soluciones
4ta rama: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 soluciones
5ta rama: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 soluciones
Sumemos los números resultantes: hay 31 soluciones en total.
Respuesta: 31.
3. Aumento natural del número de raíces.
En algunos sistemas, el número de raíces de la siguiente ecuación depende del número de raíces de la ecuación anterior.
Ejemplo 1. ¿Cuántos conjuntos diferentes de valores de las variables lógicas x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 existen que satisfacen todas las condiciones que se enumeran a continuación?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
simplifiquemos primera ecuación:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Entonces el sistema tomará la forma:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
Etc.
Cada siguiente ecuación tiene 2 raíces más que la anterior.
4 ecuación tiene 12 raíces;
La ecuación 5 tiene 14 raíces.
La ecuación 8 tiene 20 raíces.
Respuesta: 20 raíces.
A veces el número de raíces crece según la ley de Fibonacci.
Resolver un sistema de ecuaciones lógicas requiere un enfoque creativo.
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 le permita decir cuántas soluciones tiene el sistema y cuáles son los conjuntos que dan las 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 la variable tiene un valor de 0 se bifurcará en dos ramas donde la variable recibirá los valores 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?
Puedes seleccionar varias maneras resolución de 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 paréntesis 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:
|
0 |
0 |
1 |
1 |
0 |
1 |
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 Estatal Unificado 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. 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 nuevas ecuación variable se escribirá en la forma: 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 ecuación dada 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:
(incógnita 1 → incógnita 2 )*(incógnita 2 → incógnita 3 )*…*(x m -1 → x m) = 1.
Supongamos que incógnita 1 – es cierto, entonces de la primera ecuación obtenemos que incógnita 2 También es cierto, desde el segundo. incógnita 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 incógnita 1 =0, entonces de la primera ecuación tenemos incógnita 2 =0 o incógnita 2 =1.
Cuando incógnita 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 incógnita 2 =0 entendemos eso incógnita 3 =0 o incógnita 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.
|
Árbol |
Número de soluciones |
|
|
x1 |
|
|
|
x2 |
||
|
x3 |
||
|
… |
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:
|
x1 |
x2 |
(x 1 → x 2) |
Creemos una tabla de verdad para dos ecuaciones:
|
x1 |
x2 |
x3 |
x1 → x2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |