Как решать логические формулы. Системы логических уравнений в задачах егэ по информатике

Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. В математике существуют определенные задачи, которые посвящены логике высказываний. Чтобы решить данного рода уравнения необходимо обладать неким багажом знаний: знания законов логики высказываний, знания таблиц истинности логических функций 1 или 2 переменных, методы преобразования логических выражений. Кроме того, необходимо знать следующие свойства логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Любую логическую функцию от \ переменных - \можно задать таблицей истинности.

Решим несколько логически уравнений:

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

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

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

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

Начнем решение с \[Х1\] и определим какие значения данная переменная может принимать: 0 и 1. Далее рассмотрим каждое их вышеприведенных значений и посмотрим, какое может быть при этом \[Х2.\]

Как видно из таблицы наше логическое уравнение имеет 11 решений.

Где можно решить логическое уравнение онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x9, y1, y2, ... y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 - два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Ответ: 1024

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x9 ∨ x10 = 1,

где x1, x2, … x10 - ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 (0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 (0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N i +1 = N i + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

Решение систем логических уравнений различного типа

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 , ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(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

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

Решение систем логических уравнений методом построения рекуррентных формул

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа № 18»

городского округа город Салават Республики Башкортостан

Системы логических уравнений

в задачах ЕГЭ по информатике

Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.

Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.

Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.

Успешность решения системы логических уравнений зависит от знания законов логики и от четкого применения методов решения системы.

Рассмотрим решение системы логических уравнений методом отображения.

(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?

((x 1  y 1 )  (x 2  y 2 ))  (x 1  x 2 )  (y 1  y 2 ) =1

((x 2  y 2 )  (x 3  y 3 ))  (x 2  x 3 )  (y 2  y 3 ) =1

((x 7  y 7 )  (x 8  y 8 ))  (x 7  x 8 )  (y 7  y 8 ) =1

где x 1 , x 2 ,…, x 8, у 1 ,у 2 ,…,у 8 - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение . Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1 , y1) и определив значение пары (x2 , y2) , мы найдем пару (x3 , y3 ), которая, в свою очередь, приведет к паре (x4 , y4 ) и так далее.

Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.

Таблица истинности:

Построение таблицы истинности трудоемко и неэффективно по времени, поэтому применяем второй способ - логические рассуждения. Произведение равно 1 тогда и только тогда, когда каждый множитель равен 1.

(x 1  y 1 )  (x 2  y 2 ))=1

(x 1  x 2 ) =1

(y 1  y 2 ) =1

Рассмотрим первое уравнение. Следование равно 1, когда 0 0, 0 1, 1 1, значит (x1 y1)=0 при (01), (10), то пара (x 2  y 2 ) может быть любой (00), (01), (10), (11), а при (x1 y1)=1, то есть (00) и (11) пара (x2 y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.

Общее количество пар 1+1+1+22=25

2) (23.160 Поляков К.Ю.) Сколько различных решений имеет система логических уравнений

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

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

...

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

x 7  y 7 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,y1), (x2,y2) первого уравнения.

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

(y 1  y 2 ) = 1

Решением второго уравнения являются пары (00), (01), (11).

Найдем решения первого уравнения. Если x1=0, то x2 , y2 - любые, если x1=1, то x2 , y2 принимает значение (11).

Составим связи между парами (x1 , y1) и (x2 , y2).

Составим таблицу для вычисления количества пар на каждом этапе.

Учитывая решения последнего уравнения x 7  y 7 = 1, исключим пару (10). Находим общее число решений 1+7+0+34=42

3)(23.180) Сколько различных решений имеет система логических уравнений

(x 1  x 2 )  (x 3  x 4 ) = 1

(x 3  x 4 )  (x 5  x 6 ) = 1

(x 5  x 6 )  (x 7  x 8 ) = 1

(x 7  x 8 )  (x 9  x 10 ) = 1

x 1  x 3  x 5  x 7  x 9 = 1

Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x3,x4) первого уравнения.

(x 1  x 2 )  (x 3  x 4 ) = 1

Исключим из решения пары, которые в следовании дают 0 (1 0), это пары (01, 00, 11) и (10).

Составим связи между парами (x1,x2), (x3,x4)

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.


Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ - логическое отрицание (инверсия)

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Операция И - логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Совершенная конъюнктивная нормальная форма

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

Методы решения систем логических уравнений

Решить систему логических уравнений можно, например, с помощью таблицы истинности (если количество переменных не слишком велико) или с помощью дерева решений, предварительно упростив каждое уравнение.

1. Метод замены переменных.

Ввод новых переменных позволяет упростить систему уравнений, сократив количество неизвестных. Новые переменные должны быть независимыми друг от друга . После решения упрощенной системы надо снова вернуться к первоначальным переменным.

Рассмотрим применение этого метода на конкретном примере.

Пример.

((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

Решение:

Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).

Тогда система уравнений будет выглядеть так:

(А ∧ В) ∨ (¬А ∧ ¬В)=0

(В ∧ C) ∨ (¬B ∧ ¬C)=0

(С ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Построим дерево решений полученной системы:

Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:

Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:

Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.

Ответ: 64.

2. Метод рассуждений.

Сложность решения систем логических уравнений состоит в громоздкости полного дерева решений. Метод рассуждений позволяет не строить все дерево полностью, но понять при этом, сколько оно будет иметь ветвей. Рассмотрим этот метод на конкретных примерах.

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

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

x1\/y1 =1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение :

Первое и второе уравнения содержат независимые переменные, которые связаны третьим условием. Построим дерево решений первого и второго уравнений.

Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:

Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.

Ответ: 11.

Пример 2. Сколько различных решений имеет система уравнений

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение : Упростим систему. Построим таблицу истинности части первого уравнения:

Обратите внимание на последний столбец, он совпадает с результатом действия X1 ≡ X10.

После упрощения получим:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Рассмотрим последнее уравнение: (X1 ≡ X10) = 0 , т.е. х1 не должно совпадать с х10. Чтобы первое уравнение было равно 1, должно выполняться равенство (X1 ≡ X2)=1, т.е. х1 должно совпадать с х2.

Построим дерево решений первого уравнения:

Рассмотрим второе уравнение: при х10=1 и при х2=0 скобка должна быть равна 1 (т.е. х2 совпадает с х3); при х10=0 и при х2=1 скобка (X2 ≡ X10)=0 , значит, скобка (X2 ≡ X3) должна быть равна 1 (т.е. х2 совпадает с х3):

Рассуждая таким образом, построим дерево решений для всех уравнений:

Таким образом, система уравнений имеет всего 2 решения.

Ответ: 2.

Пример 3.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?

(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

Решение:

Построим дерево решений 1-го уравнения:

Рассмотрим второе уравнение:

• При х1=0 : вторая и третья скобки будут равны 0; чтобы первая скобка была равна 1, должны у1=1 , z1=1 (т.е. в этом случае - 1 решение)
• При х1=1 : первая скобка будет равна 0; вторая или третья скобка должна быть равна 1; вторая скобка будет равна 1 при у1=0 и z1=1; третья скобка будет равна 1 при у1=1 и z1=0 (т.е. в этом случае - 2 решения).

Аналогично для остальных уравнений. Отметим полученное кол-во решений у каждого узла дерева:

Чтобы узнать кол-во решений для каждой ветви, перемножим полученные числа по отдельности для каждой ветви (слева напрво).

1 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 решение

2 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 решения

3 ветвь: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 решения

4 ветвь: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 решения

5 ветвь: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 решения

Сложим полученные числа: всего 31 решение.

Ответ: 31.

3. Закономерное увеличение количества корней

В некоторых системах количество корней очередного уравнения зависит от количества корней предыдущего уравнения.

Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Упростим первое уравнение: (x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тогда система примет вид:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

И т.д.

Каждое следующее уравнение имеет на 2 корня больше, чем предыдущее.

4 уравнение имеет 12 корней;

5 уравнение имеет 14 корней

8 уравнение имеет 20 корней.

Ответ: 20 корней.

Иногда количество корней растет по закону чисел Фибоначчи.

Решение системы логических уравнений требует творческого подхода.