Образовательный портал Павла Добряка

4.5. Логические уравнения

Задачи на логические уравнения являются большой темой для изучения. На эту тему уходит 2 – 3 90-минутных занятия (больше только на последнюю программистскую задачу). Далее дается подборка разнообразных логических уравнений от простых к сложным. Для решения большинства уравнений будем использовать деревья решений и комбинаторику, поэтому тема логических уравнений находится на стыке трех разделов: «Логика», «Деревья и графы», «Комбинаторика».

Задача 4.5.1. Сколько различных решений имеет уравнение

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

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

 

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

 (J  ⌐K  ⌐M) ∧ (N  ⌐N) = 1

 

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

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

Примечание. Дерево является типичным способом решения уравнений. Если вы смотрите на уравнение и растерялись, не видите решений — это явный признак того, что надо строить дерево.

 

Задача 4.5.4. Сколько различных решений имеет система логических уравнений:

(x1 ≡ x2) ≡ (x3 ≡ x4) = 0

(x3 ≡ x4) ≡ (x5 ≡ x6) = 0

(x5 ≡ x6) ≡ (x7 ≡ x8) = 0

(x7 ≡ x8) ≡ (x9 ≡ x10) = 0

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

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

 

Задача 4.5.5. Сколько различных решений имеет система логических уравнений:

(x1 ≡ x2) → (x2 ≡ x3) = 1

(x2 ≡ x3) → (x3 ≡ x4) = 1

(x5 ≡ x6) → (x7 ≡ x8) = 1

Ошибка. Если вы ввели новые обозначения, как в предыдущей задаче, то вы неправы. Переменные в этой задаче не образуют изолированные группы.

Примечание: поиск закономерности в дереве с выведением формулы обсчета – типичный прием при решении систем уравнений.


Задача 4.5.6. Сколько различных решений имеет система логических уравнений:

⌐(x1 ≡ x2)  ⌐(x1 ≡ x3)  (x2 ≡ x3) = 0

⌐(x3 ≡ x4)  ⌐(x3 ≡ x5)  (x4 ≡ x5) = 0

⌐(x5 ≡ x6)  ⌐(x5 ≡ x7)  (x6 ≡ x7) = 0

⌐(x7 ≡ x8)  ⌐(x7 ≡ x9)  (x8 ≡ x9) = 0



Задача 4.5.7. Сколько различных решений имеет система логических уравнений:

(x1 x2) ∨ (⌐x1 ⌐x2) ∨ (⌐x3 x4) ∨ (x3 ⌐x4) = 1

(x3 x4) ∨ (⌐x3 ⌐x4) ∨ (⌐x5 x6) ∨ (x5 ⌐x6) = 1

(x5 x6) ∨ (⌐x5 ⌐x6) ∨ (⌐x7 x8) ∨ (x7 ⌐x8) = 1

(x13 x14) ∨ (⌐x13 ⌐x14) ∨ (⌐x15 x16) ∨ (x15 ⌐x16) = 1

 

Задача 4.5.8. Сколько различных решений имеет система логических уравнений:

x1 x2 x3 = 1

x2 x3 x4 = 1

x7 x8 x9 = 1

x8 x9 x10 = 1

Ошибка. Первый подвох заключается в приоритете операций. Вы помните, что в отсутствии скобок логическое «и» выполняется раньше логического «или», то есть сперва делаем второе действие, а потом – первое.

 

Задача 4.5.9. Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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

Примечание. Обратите внимание, что если система уравнений красива, то и дерево красиво, а при его обсчете появляются закономерности.

 

Задача 4.5.10. Сколь­ко существует решений у системы логических уравнений? 

(x1 ((x1 x2) → x3) (¬x1 y1) = 1

(x2 x3) ((x2 x3) → x4) (¬x2 y2) = 1

… 

(x6  x7)  ((x6  x7) → x8)  (¬x6  y6) = 1 

(x7  x8)  (¬x7  y7) = 1 

(¬x8 y8) = 1

 

Задача 4.5.11. Сколь­ко существует решений системы логических уравнений? 

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1

(⌐y1  y2) ∧ (⌐y2  y3) ∧ (⌐y3  y4) = 1

(x1 → y1) ∧ (x2 → y2) ∧ (x3 → y3) ∧ (x4 → y4) = 1

 

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

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

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

(x8 → x9)  (y8 → y9)  (y8 → x8) = 1

(y9 → x9) = 1



Задача 4.5.12. Сколь­ко существует решений системы логических уравнений? 

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5→ x6) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) ∧ (z4 → z5) ∧ (z5 → z6) = 1

x6 ∧ y6 ∧ z6 = 0

 

Задача 4.5.13. Сколь­ко существует решений у системы логических уравнений? 

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

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

((x8 ≡ y8) → (x9 ≡ y9)) ∧ (x8 → x9) ∧ (y8 → y9) = 1



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

(¬ (x1 ≡ x2) ∨ ¬ (y1 ≡ y2)) = 1

(¬ (x2 ≡ x3) ∨ ¬ (y2 ≡ y3)) = 1 

(¬ (x3 ≡ x4) ∨ ¬ (y3 ≡ y4)) = 1 

(¬ (x4 ≡ x5) ∨ ¬ (y4 ≡ y5)) = 1 

x5 ∨ y5 = 1 

 

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

 

(x1 x2) → (x3 x4) = 1

(x3 x4) → (x5 x6) = 1

(x5 x6) → (x7 x8) = 1

 

Задача 4.5.16. Сколько существует различных наборов значений логических переменных 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

 

Задача 4.5.17. Сколь­ко существует решений у системы логических уравнений? 

¬((¬x1 ∧ x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ x3) ∨ (x1 ∧ ¬x2 ∧ ¬x3)) = 1,

¬((¬x2 ∧ x3 ∧ ¬x4) ∨ (¬x2 ∧ x3 ∧ x4) ∨ (x2 ∧ ¬x3 ∧ ¬x4)) = 1,

...

¬((¬x8 ∧ x9 ∧ ¬x10) ∨ (¬x8 ∧ x9 ∧ x10) ∨ (x8 ∧ ¬x9 ∧ ¬x10)) = 1.

Следующая задача встречалась на ресурсах, посвященных подготовке к ЕГЭ. Маловероятно, что подобная задача встретится на реальном ЕГЭ, так как она очень сложна. Но стоит её решить, чтобы закрепить ряд приемов. После её решения вы будете способны решить любую систему логических уравнений.


Задача 4.5.18. Сколь­ко существует решений у системы логических уравнений? 

(x1 x2) ((x1 x2) → y1) = 1

(x2 x3) ((x2 x3) → y2) = 1

… 

(x6  x7)  ((x6  x7) → y6) = 1

(x7  x8)  (x7  y7) = 1

(x8  y8) = 1


Линейное изложение материала о логических уравнениях, где задачи приводятся от простых к сложным, может привести к тому, что ученик запутается в приемах решения («за деревьями не увидит леса»). Поэтому я рекомендую просмотреть «Приложение С», в котором приводится обзор приемов и логические уравнения сравниваются между собой. Кроме того, некоторые интересные и усложненные логические уравнения приводятся еще в двух параграфах последних глав книги -  «Комбинаторика при решении логических уравнений» и «Прогрессии и рекурсии в логических уравнениях». Когда вы дойдете до них, вы увидите, какие навыки остались в вашей долгосрочной памяти от изучения данного параграфа.