Алгебра логики в программировании

На этой странице вы узнаете

• Как расставлять приоритеты?
• Как связаны алгебра логики и программирование?
• Что делать с отрезками в задачах?

В статье «Алгебра логики» мы узнали, что алгебра есть не только в математике, но и в информатике. Наверное, многим могло показаться очень странным, что в информатике появился целый раздел алгебры, но в этой статье мы сможем «подружить» алгебру с информатикой. Сделаем мы это, конечно, с помощью программирования на Python.

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

Мы уже говорили, что алгебра логики оперирует истиной и ложью, которым также могут соответствовать числа 1 и 0.

В Python эта логика сохраняется. В нем есть логический тип данных bool, который может принимать значение True или False — истина и ложь соответственно. Которые также эквивалентны числам 1 и 0.

Еще мы разбирали в статье «Алгебра логики» такие логические операторы, как конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция. Давайте вспомним, что они из себя представляют.

Конъюнкция (логическое «и») – данный оператор проверяет, чтобы все функции в выражении были истинными. 

Он работает по принципу умножения: если хоть один элемент равен нулю, то все произведение равно нулю.

Рассмотрим на примере:

На картинке выше изображен торт, про который мы можем сказать:
«Торт украшен клубникой» и «на торте 3 свечи» – такое выражение будет истинным.
Но если мы скажем:
«Торт украшен клубникой» и «на торте 6 свечей» – такое выражение будет ложным.

Дизъюнкция (логическое «или») – логический оператор, проверяющий, что хотя бы один элемент из выражения истинный. 

Он по способу работы похож на сложение: если среди элементов есть единица, то все выражение будет истинным. 

Здесь можно составить такое выражение:

«Торт украшен клубникой» или «на торте все свечи синие» – такое выражение будет истинным, потому что среди элементов есть верный.

С отрицанием все работает еще проще.

Отрицание – логический оператор, который меняет значение элемента на противоположное, то есть меняет истину на ложь, и наоборот.

В примере с тортом можно сказать так:
«На торте не 6 свечей» – данное выражение истинно, ведь мы отрицаем ложное высказывание.

Импликация (следование) – логический оператор, который превращает выражение в ложное только в случае, когда из истины следует ложь.

Эквивалентность – логический оператор, проверяющий, чтобы оба элемента были либо ложными, либо истинными. 

То есть если первый элемент равен второму, то выражение будет истинным.

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

Как логические операторы записываются в программе Python и в чем их отличие?

Логические операторы в Python мы уже упоминали в статье «Основы программирования. Часть 2». Давайте их вспомним:

Есть одна проблема, связанная с последними двумя операторами.
Она заключается в том, что для импликации и эквиваленции нет специальных логических операторов, но для них можно использовать математические:

• Математическое сравнение на равенство работает так же, как логическая эквиваленция: вернет True, если значения будут одинаковые и False в противном случае.

• Математическое «меньше или равно» полностью соответствует логическому следованию: False будет возвращено только в том случае, если значение слева будет больше значения справа. А если вспомнить аналогию логических переменных и целых чисел, это произойдет только в ситуации 1 <= 0. В остальных случаях будет истина.

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

1. Эквиваленция и импликация будут иметь равный приоритет и выполняться в порядке очереди. Но относительно логических операторов их приоритет станет самым высоким.

2. Инверсия, конъюнкция и дизъюнкция будут иметь свой законный приоритет.

Как расставлять приоритеты? Как вы знаете, умение правильно расставлять приоритеты просто необходимо в обычной жизни, но, оказывается, оно также необходимо и в информатике, в частности, в алгебре логики. Чтобы получить верный ответ при решении логического выражения, нужно расставлять скобки. Это обязательно помнить, особенно при использовании математических операторов в Python.

Например:

• простое логическое уравнение только из конъюнкции, дизъюнкции и инверсии в лишних скобках не нуждается (кроме тех, конечно, что уже есть в уравнении):

• при появлении импликации и эквиваленции подключаем скобки, чтобы сохранить приоритет и этих, и других логических операторов:

Теперь мы понимаем, как правильно составить выражение для Python, так что пора научиться решать практические задания.

Решение практических задач

Как связаны алгебра логики и программирование? Между программированием и алгеброй логики установлен довольно приятный союз: — С одной стороны, в больших и запутанных программах может быть много логических зависимостей, распутать которые поможет знание алгебры логики. — С другой, не менее приятной, — программа сможет все решить за нас. Логические уравнения могут быть большими и запутанными. Законы логики помогут нам их сократить. Работать с сокращенным выражением будет проще. Но программа может отлично справиться и со сложным выражением, так что сокращать нам не придется.

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

А много нам и не надо:

1. Нужен перебор логических переменных по совсем небольшому диапазону — от 0 до 1.
2. Правильно записанное логическое уравнение, чтобы проверить его при каждом наборе истины и лжи.

Вопрос встает только о конкретной реализации. Python — очень гибкий язык. Для разных формулировок задачи он может предложить разные инструменты, которые сделают написание кода еще приятнее.

Начнем с обобщенной задачи — построение таблицы истинности. На этом примере можно показать, что математические операторы путают приоритет логических. Так что давайте составим таблицу истинности для уравнения A ≡ B ∧ C ⇒ A.

Перебор устроим с помощью вложенных циклов for. Они будут перебирать отдельные переменные, которые потом будут подставляться в логическое уравнение. Для удобства будем сохранять значение уравнения в отдельную переменную, затем выводить все на экран.

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

Да, промежуточных результатов при такой реализации у нас нет. А зачем они нам? Нам важен итоговый результат — мы его получили.

Есть ощущение, что этот код не очень красивый. Он однозначно рабочий, но все-таки слишком много вложенных циклов. Конечно, можно оставить так.

Чтобы сделать код более красивым и понятным, можно немного доработать его.

В статье «Комбинаторика в информатике» мы обсуждали такую вещь, как модуль itertools, который содержит функции для работы с различными комбинациями. Как раз наш случай — мы используем различные комбинации 1 и 0.

Сейчас нам пригодится функция product, которая создаст различные комбинации из указанных элементов. Изначально запишем их в отдельный массив для удобства:

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

Пожалуй, стоит подробнее рассказать про строку:
A, B, C = i.

Мы точно знаем, что i — это массив с 3 элементами, так как мы изначально задали создание наборов длиной 3. Если указать перед ним ровно столько же переменных, им можно присвоить соответствующие элементы массива в одну строку.

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

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

Другая наша возможная цель — проверить, будет ли выражение истинным всегда? Получим ли мы истину при любом наборе логических переменных?

Как и в прошлый раз, у нас есть не один вариант реализации. Будем анализировать выражение А ∧ (В ∨ С) ≡ В.

Первый вариант:

• перебор всех наборов — вложенными циклами или с помощью product;
• сохранение всех результатов уравнения от каждого набора;
• проверка, чтобы ни одно значение не было ложным — для сохранения всех результатов можно использовать список.

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

Второй вариант — функция all. Она возвращает True, если все значения внутри нее равны True — как раз наш случай. Чтобы записать программу максимально коротко, прямо внутри нее можно прописать и уравнение, и перебор его элементов:

Здесь в переменную result записывается логическое значение True, если для всех наборов А, В, С из комбинаций d длиной 3 результат логического уравнения равен True. Если же среди всех результатов есть хоть один False – функция all даст нам False.

Для похожей задачи — чтобы не все значения уравнения были ложными — можно использовать функцию any. Синтаксис абсолютно такой же, разница есть в принципе работы: any вернет True, если среди всех переданных значений есть хоть одно истинное значение.

Python — гибкий язык. Если вам важнее видеть алгоритм работы кода более явно — используйте вложенные циклы, массивы для хранения значений и будьте более, чем на 100% уверены в каждом шаге. Если же вы хотите использовать дополнительные инструменты для сокращения объема кода и, как следствие, более быстрого его написания — вам в помощь комбинации product из itertools и инструменты массовой проверки all и any.

Теперь попрактикуемся на примере, аналогичном №2 из ЕГЭ:

Задание. Логическая функция F задается выражением (x ∨ y) → (z ≡ x).Дан фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z.

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

Шаг 1. С помощью вложенных циклов for переберем все возможные комбинации переменных:

Шаг 2. Запишем выражение и приравняем его к новой переменной result:

Шаг 3. Теперь нужно вывести переменные:

Шаг 4. Запускаем программу, она выведет всю таблицу истинности.

Шаг 5. Нужно сопоставить таблицу истинности с фрагментом из условия.Убираем все строки которые точно не показаны на фрагменте: ложные функции, а также те строки, в которых набор единиц и нулей не представлен во фрагменте (1 1 1 или 0 0 0).

Шаг 6. У нас осталось три строки, которые и представлены на фрагменте:

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

У переменной х в двух строчках из трех представлены нули, это значит, что х – переменная 2, следовательно, оставшаяся переменная 3 – z. Эта комбинация и будет ответом!

Ответ: yxz

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

Отрезок – последовательность нескольких чисел, у которой есть начало и конец.

Что делать с отрезками в задачах? Когда в задаче на алгебру логики даны отрезки, нужно обязательно вспомнить о нескольких моментах: 1. Все отрезки нужно написать в код. 2. Нужно проверить большое количество чисел х на то, чтобы они соответствовали условию. 3. Длина отрезка вычисляется в python с помощью функции len(), но после нахождения длины отрезка функцией нужно отнять единицу от получившегося решения.

Теперь мы поняли, как работать с отрезками, и сможем решить задачу.

Разберем пример задания №15 из ЕГЭ на отрезки.

Задание. На числовой прямой даны два отрезка: P=[10, 29] и Q=[13, 18].Укажите наибольшую возможную длину отрезка A, для которого выражение

((x ∈ A) → (x ∈ P)) ∨ (x ∈ Q)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

Решение. Шаг 1. Запишем все отрезки в код:

Шаг 2.  С помощью вложенного цикла переберем х:

Шаг 3. Запишем наше выражение в условие if. Сделаем проверку: если этот х делает выражение ложным, удаляем этот х из отрезка А:

Шаг 4. Выводим длину А, не забывая отнять единицу:

Ответом будет число 19. 

Ответ: 19

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

При работе с кодом очень важно понимать, как устроена программа, в статье «Алгоритмы» вы сможете познакомиться с основами составления программ, что будет  полезно для многих следующих разделов информатики.

Термины

Цикл – конструкция, обеспечивающая многократное исполнение набора команд.

Вложенные циклы – цикл, в который вложен другой цикл.

Массив – структура данных, которые хранятся под определенными индексами.

Фактчек

• Для импликации и эквиваленции в Python используются математические операторы сравнения, что немного нарушает их общий приоритет. Сохранить его можно с помощью скобок.
• Значения истины и лжи в Python являются логическим типом данных, который может принимать значение True или False и соответствует 1 и 0.
• Функция all проверяет, все ли переданные ей значения истинны. Функция any проверяет, есть ли среди всех переданных значений хоть одно истинное.
• При работе с отрезками нужно обязательно указывать их в программе.
• Длина отрезка вычисляется с помощью функции len() в Python, но при ее вычислении нужно обязательно вычитать из конечного результата единицу.

Проверь себя

Задание 1.
Для выражения А ∨ В ∧ ¬(В ∧ А) выберите верную запись на языке Python (с сохранением порядка действий):

1. A and B or not B or A
2. A and B or not (B or A)
3. A or B and not B and A
4. A or B and not (B and A)

Задание 2.
Для выражения ¬А ⇒ В ≡ А ∧ В выберите верную запись на языке Python (с сохранением порядка действий):

1. not (А <= В == А and В)
2. not А <= В == (А and В)
3. ((not A) <=  B) == (A and B)
4. (not А) <= (В == (А and В))

Задание 3.
Чему будут равны значения функции при всех наборах переменных для уравнения: 

A ∧ B ⇒ C ∧ A ∨ C ∧ B?

1. 11111101
2. 11101111
3. 00000011
4. 11000111

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

1. ¬(A ∧ B) ∧ ¬(C ∧ ¬A)
2. ¬(A ∧ B) ∨ ¬(C ∧ ¬A)
3. A ∧ B ∧ ¬(C ∧ ¬A)
4. ¬(A ∧ B) ∨ ¬(C ∧ A)

Ответ: 1. — 4; 2. — 3; 3. — 1; 4. — 2.