Тема: Преобразование логических выражений.

Тема: Преобразование логических выражений.

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù, Ú, ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение). В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù, Ú, ¬), что еще раз подчеркивает проблему.

Что нужно знать:

• условные обозначения логических операций
  • A, не A (отрицание, инверсия)
• Ù B, A и B (логическое умножение, конъюнкция)
• Ú B, A или B (логическое сложение, дизъюнкция)
• → B импликация (следование)
• ↔ B, эквиваленция (эквивалентность, равносильность)
• таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)
• операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
  1. → B = ¬ A Ú B или в других обозначениях A → B =
• операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:
  1. ↔ B = ¬ A Ù ¬ B Ú A Ù B или в других обозначениях A ↔ B =
• если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»
• логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
• логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
• в приведённых задачах операция импликация считается лево-ассоциативной, то есть операции импликации в цепочке выполняются слева направо (соблюдая принцип «операции с одинаковым приоритетом выполняются слева направо»):

• правила преобразования логических выражений (законы алгебры логики):

Пример задания:

1. -32. Сколько различных решений имеет система логических уравнений

(x₁ Ù y₁) º (Øx₂ Ú Øy₂)

(x₂ Ù y₂) º (Øx₃ Ú Øy₃)

.

(x₅ Ù y₅) º (Øx₆ Ú Øy₆)

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

Решение (метод битовых цепочек):

1. перепишем уравнения в более понятном виде:

1. заметим, что по закону де Моргана и выполним замену переменных

1. получаем систему

которая может быть записана в виде

и сворачивается в одно уравнение

1. это уравнение накладывает такое ограничение на битовую цепочку : соседние биты различны, что дает всего дав решения: и
2. теперь нужно перейти к исходным переменным, и
3. если , то имеем всего один вариант исходных переменных: , то есть единица в решении Z не увеличивает количество решений в исходных переменных
4. если , то имеем три варианта исходных переменных: , то есть каждый ноль в решении Z утраивает количество решений в исходных переменных
5. поскольку в каждом решении 3 нуля, каждое из двух решений Z даёт 3³ = 27 решений в исходных переменных; таким образом, всего решений 2 · 27 = 54
6. Ответ: 54.

Решение (оптимизированный метод отображений, А.Н. Носкин):

1. Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У. Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z.
2. Теперь перепишем систему с новыми однотипными переменными. ВНИМАНИЕ, сложность задачи будет заключаться во внимательной записи при замене переменных.

(z₁ Ù z₂) º (Øz₃ Ú Øz₄)

(z₃ Ù z₄) º (Øz₅ Ú Øz₆)

.

(z₉ Ù z₁₀) º (Øz₁₁ Ú Øz₁₂)

1. построим таблицу, в которой переберем все варианты z₁, z₂, z₃, z₄, поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2⁴); уберем из таблицы (желтая заливка) такие значения z₄, при которых первое уравнение не имеет решения.

1. анализируя таблицу, строим правило отображения пар переменных

(например паре Z₁Z₂=00 соответствует пара Z₃Z₄ = 11).

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

1. складываем все результаты: 9 + 9 + 9 + 27 = 54
2. Ответ: 54.