Ecuación en informática. Sistemas de ecuaciones lógicas en problemas del Examen Estatal Unificado en informática

Solución de sistemas ecuaciones lógicas Métodos tabulares para transformar expresiones lógicas.

Esta técnica se basa en el uso de tablas de verdad y está diseñada para estudiantes que saben convertir expresiones lógicas. Si los estudiantes no dominan estos métodos, pueden utilizarlos sin transformaciones. (Usaremos transformaciones). Para dominar este método de solución es imprescindible conocer las propiedades de las operaciones lógicas básicas: conjunción, disyunción, inversión, implicación y equivalencia.

Algoritmo para resolver sistemas de ecuaciones usando este método:

Transforma la ecuación lógica y simplifícala.

Determine la secuencia de resolución de ecuaciones en el sistema, ya que en la mayoría de los casos existe una solución secuencial de ecuaciones de arriba a abajo (como están ubicadas en el sistema), pero hay opciones cuando es más conveniente y más fácil comenzar a resolver desde abajo hacia arriba.

Construye una tabla de variables donde puedas establecer los valores iniciales de la primera variable (o de la última).

Escriba consistentemente las posibles opciones para la siguiente variable cuando todos significado del primero.

Después de resolver la ecuación anterior, pasando a la siguiente, asegúrese de prestar atención a qué variables se utilizan en las ecuaciones anteriores y posteriores, ya que los valores de las variables obtenidas al resolver las ecuaciones anteriores se pasan como opciones para las siguientes ecuaciones.

Preste atención a las cantidades resultantes de la solución cuando pase a la siguiente variable, porque Se puede identificar un patrón en el aumento de las decisiones.

Ejemplo 1.

¬ X1 ˅ X2=1

¬ X2 ˅ X3=1

¬ X3 ˅ X4=1

¬ X9 ˅ X10=1

Empecemos por X1 y veamos qué valores puede tomar esta variable: 0 y 1.

Luego consideraremos cada uno de estos valores y veremos cuál puede ser X2.

Respuesta: 11 soluciones

Ejemplo 2.

( X1X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1

( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1

(X8˄X9)˅(¬X8˄¬X9)˅(X8↔X10)=0

Transformemos usando la fórmula (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

Obtenemos:

( X1↔ X2) ˅ (X1↔ X3) =1

( X2↔ X3) ˅ (X2↔ X4) =1

( X8↔ X9 (X8↔ X10) =0

Para X1 =0 - 8 soluciones

Tomemos X1=1 y veamos qué valor puede tomar X2. Ahora para cada X2 consideraremos qué valores puede tomar X3, etc.

Para X1=1 – 8 soluciones

Total 8+8=16 soluciones

Respuesta. 16 soluciones

Ejemplo 3 .

¬ ( X1↔ X2)˄ ( X1X3) ˄ (¬X1˅¬X3 )=0

¬ ( X2↔ X3) ˄ (X2˅X4) ˄ (¬X2˅¬X4)=0

….

¬ ( X8↔ X9 (X8X10) ˄ (¬X8˅¬X10)=0

Después de las transformaciones (A˅ B) ˄(¬ A ˅¬ B)= ¬( A ↔ B)

obtenemos:

¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0

¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0

…..

¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0

Tomemos X1=0 y veamos qué valor puede tomar X2. Ahora para cada X2 consideraremos qué valores puede tomar X3, etc.

Tenemos 10 soluciones para X1=0

Hagamos lo mismo para X1=1. También obtenemos 10 soluciones.

Total:10+10=20

Respuesta: 20 soluciones.

Ejemplo 4.

(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1

(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Convirtamos usando fórmulas. (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B. Obtenemos:

(X1↔ X2) ˅ (X2↔ X3)=1

(X2↔ X3) ˅ (X3↔ X4)=1

(X3↔ X4) ˅ (X4↔ X5)=1

(X4↔ X5) ˅ (X5↔ X6)=1

(X5↔ X6) ˅ (X6↔ X7)=1

(X6↔ X7) ˅ (X7↔ X8)=1

(X7↔ X8) ˅ (X8↔ X9)=1

(X8↔ X9) ˅ (X9↔ X10)=0

Empecemos por el final, porque en la última ecuación las variables están determinadas de forma única.

Sea X10=0, entonces X9=1, X8=0, X7=0, X6=0, y las siguientes variables pueden tomar diferentes significados. Consideraremos cada uno.

Total de 21 soluciones para X10=0

Ahora considere para X10=1. También obtenemos 21 soluciones.

Total:21+21=42

Respuesta: 42 soluciones

Ejemplo 5.

( X1X2) ˅ (¬X1˄¬X2) ˅ (¬X3˄X4 (X3˄¬X4)=1

( X3˄X4) ˅ (¬X3˄¬X4) ˅ (¬X5X6) ˅ (X5˄¬X6)=1

( X5X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8 (X7˄¬X8)=1

( X7˄X8) ˅ (¬X7˄¬X8) ˅ (¬ X9X10 (X9˄¬X10) =1

Transformemos según las fórmulas:(¬ A ˄ B) ˅ ( A ˄ ¬ B)= A↔ ¬ B

( A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

( X1↔ X2) ˅ (X3 ↔ ¬X4)=1

( X3↔ X4 (X5 ↔ ¬X6)=1

( X5↔ X6) ˅ (X7 ↔ ¬X8)=1

( X7↔ X8 (X9 ↔ ¬X10)=1

Consideremos qué valores pueden tomar X1 y X2: (0,0), (0,1), (1,0), (1,1).

Consideremos cada opción y veamos qué valores pueden tomar X3, X4.

A partir de X7, X8, inmediatamente anotaremos el número de soluciones, ya que inmediatamente queda claro que cuando los valores son iguales (1,1) y (0,0), entonces las siguientes variables tienen 4 soluciones, y cuando son diferentes (0,1) y (1,0) – 2 soluciones.

Total: 80+80+32=192

Respuesta: 192 soluciones

Ejemplo 6.

(X1↔X2) ˅ (X2 ↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4 ↔X5)=1

….

(X8↔X9) ˅ (X9 ↔X10)=1

Tomemos X1=0 y veamos qué valor puede tomar X2. Ahora para cada X2 consideraremos qué valores puede tomar X3, etc.

Vemos un cierto patrón: el número de soluciones posteriores es igual a la suma de las dos anteriores.

Lo mismo para X1=1 obtenemos 89 soluciones.

Total: 89+89=178 soluciones

Respuesta: 178 soluciones

Resolvámoslo de una manera más.

(X1↔X2) ˅ (X2 ↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4 ↔X5)=1

….

(X8↔X9) ˅ (X9 ↔X10)=1

Introduzcamos el reemplazo:

t 1 =(X1↔X2)

t 2 =(X2↔X3)

t 3 =(X3↔X4)

t 4 =(X4↔X5)

t 5 =(X5↔X6)

t 6 =(X6↔X7)

t 7 =(X7↔X8)

t 8 =(X8↔X9)

t 9 =(X9↔X10)

Obtenemos:

t1t2=1

t2˅t3=1

t3˅t4=1

t4t5=1

t5t6=1

t6˅t7=1

t7˅t8=1

t8t9=1

t9t10=1

Echemost1=1 y usa las propiedades de disyunción:

PERO recordemos que

t 1 =(X1↔X2)

t 2 =(X2↔X3), etc.

Usemos la propiedad de equivalencia y asegurémonos, mirando la tabla, de que

Cuando T = 1, entonces se obtienen dos soluciones. Y cuando =0 hay una solución.

Por lo tanto, podemos contar el número de unos y multiplicarlos por 2+ el número de ceros. Contando, también usando un patrón..

Resulta que el número de unos = el número total anterior de soluciones T, y el número de ceros es igual al número anterior de unos.

Entonces. Lo conseguiremos. Como se dan dos soluciones, entonces 34 * 2 = 68 soluciones de uno + 21 soluciones de 0.

Total de 89 soluciones para T=1. De manera similar obtenemos 89 soluciones para T=0

Total 89+89=178

Respuesta: 178 soluciones

Ejemplo 7.

(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅¬(X3↔ X4)=1

(X3 ↔ X4 (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅¬(X5↔ X6)=1

(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅¬(X7↔ X8)=1

(X7 ↔ X8 (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅¬(X9↔ X10)=1

Introduzcamos el reemplazo:

t1=(X1 ↔ X2)

t2=(X3↔ X4)

t3=(X5↔ X6)

t4=(X7 ↔ X8)

t5=(X9↔ X10)

Obtenemos:

(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1

(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1

(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1

(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1

Consideremos qué pueden ser los T:

Total

t k ≠T K+1 ÉL k =T K+2

Obtenemos: 2 5 =32 para T

Total: 32+32=64

Respuesta: 64 soluciones.

Solución de la ecuación 1. Vaya a la forma de prefijo para escribir la ecuación, reemplazando los símbolos de las negaciones con ¬ 2. Construya el título de una tabla de verdad de un tipo especial 3. Complete las filas de la tabla de verdad para todas las combinaciones de A y B, sustituyendo 0 o 1 en lugar de X. 4. Genere una tabla de verdad para X = F (A,B) 5. Usando la tabla de verdad, determine el tipo de función X, si es necesario, usando los métodos de construcción de SCNF y SDNF, que se analizarán a continuación.

Construcción de una tabla de verdad de forma especial ¬((A+B)·(X A·B))=¬(B+¬(X A))

Tabla de verdad X=F(A, B) ABX Corresponde a la negación de la implicación B en A RESPUESTA:

Circuitos combinacionales de dispositivos lógicos Elementos básicos (GOST): 1 A B Disyunción A B Equivalencia y A B Conjunción M2 A B XOR

Circuitos combinacionales de dispositivos lógicos Elementos básicos (GOST): 1 A B Implicación y A B Elemento de Schaeffer y A B Coimplicación 1 A B Elemento de Webb

Ejemplo de circuito F 1 & 1 & & 1M2 B A

Resolver circuitos 1 Opción: convertir un circuito en una expresión lógica compleja y luego simplificarlo de acuerdo con las leyes de la lógica. Opción 2: construcción de una tabla de verdad y luego, si es necesario, construcción a través de SKNF o SDNF (ver más abajo). Consideremos la segunda opción, ya que es más sencilla y comprensible.

Construcción de la tabla de verdad AB A + B + · B B · A + A B A + · ·

Tabla de verdad F(A, B) ABX Corresponde a la negación de la implicación B en A RESPUESTA:

SDNF y SKNF (definiciones) Una conjunción elemental es una conjunción de varias variables, tomadas con o sin negación, y entre las variables puede haber otras idénticas. Una disyunción elemental se llama disyunción de varias variables, tomadas con o sin negación, y. entre las variables puede haber otras idénticas. Cualquier disyunción de conjunciones elementales Llamémosla forma normal disyuntiva (DNF) Llamemos a cualquier conjunción de disyunciones elementales forma normal conjuntiva (DNF)

SDNF y SCNF (definiciones) Una forma normal disyuntiva perfecta (PDNF) se denomina DNF en la que no hay conjunciones elementales idénticas y todas las conjunciones constan del mismo conjunto de variables, en la que cada variable aparece sólo una vez (posiblemente con negación). Una forma normal conjuntiva perfecta (PCNF) es una CNF en la que no hay disyunciones elementales idénticas y todas las disyunciones constan del mismo conjunto de variables, en la que cada variable aparece sólo una vez (posiblemente con negación).

Algoritmo para obtener SDNF de la tabla de verdad 1. Marque las filas de la tabla de verdad en cuya última columna hay 1. 2. Escriba para cada fila marcada la conjunción de todas las variables de la siguiente manera: si el valor de una variable en una fila dada es 1, luego incluya esta variable en la conjunción, si es igual a 0, entonces su negación. 3. Vincula todas las conjunciones resultantes en una disyunción. Algoritmo para obtener SCNF de la tabla de verdad 1. Marque las filas de la tabla de verdad en cuya última columna haya 0. 2. Escriba para cada fila marcada la disyunción de todas las variables de la siguiente manera: si el valor de una variable en una fila dada es 0, luego incluya esta variable en la conjunción, si es igual a 1, entonces su negación. 3. Vincula todas las disyunciones resultantes en una conjunción.

Ejemplo de construcción SKNF XY F(X,Y) Marcar ceros 2. Disyunciones: X + Y 3. Conjunción: (X + Y) · (X + Y)

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 ^ ¬а ≡ 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 elementos suficientemente conocidos. funciones 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 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 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 sólo se desprenden dos cosas: 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 varias 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:

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

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

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

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

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

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

La única diferencia es que la ecuación usa Y variables. Esta ecuación también tiene 6 soluciones. Dado que cada solución para las variables X i se puede combinar con cada solución para las variables Y j, entonces numero 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. recepción general 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 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, 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 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 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);

bool estático Fun53 (vars bool)

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?
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬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:
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.
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)

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.

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 ( cuenta) Google e inicia sesión: 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.

¡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 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 adecuado. hay 5 pares de este tipo. Número de soluciones para el 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 un 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].