13. Логические операции. Таблицы истинности

Логические операции. Правила их записи и приоритеты

Алгебра логики по сравнению с более древней и сложной формальной логикой всегда имела козырь в рукаве в виде простоты её понимания, поскольку в её рамках переменные могли принимать только два значения, а именно «истинно» или «ложно», или же 1 или 0 соответственно. Однако алгебра логики чуть менее привычна для обычного человека, чем формальная логика. Тем не менее это не помешало ей развиться в серьёзную науку, имеющую набор своих инструментов и использующуюся для доказательства ряда теорем.

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

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

Конечно, существуют модели, которые могут давать больше возможных результатов. Например, выражение «Рядом со мной находится ручка» может давать несколько возможных значений в зависимости от того, насколько близко находится ручка. Можно определить значение этого выражения так, чтобы оно принадлежало непрерывному промежутку: от 0 до 1. Причём значение 1 будет соответствовать ситуации, когда ручка абсолютно близко, а 0 — когда ручка настолько далеко, что мы можем забыть о ней.

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

Как мы говорили ранее, в алгебре логики используются три логические операции, а именно И, ИЛИ и НЕ.

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

Здесь можно провести аналогию с арифметикой. Например, значение выражения 3 + 3 ∙ 3 можно определить двумя способами. В первом мы просто выполняем по порядку все действия, не делая различий между ними. 3 + 3 = 6, 6 ∙ 3 = 18.

Но что будет, если мы поменяем местами умножение и сложение: 3 ∙ 3 + 3? Теперь результат равен уже 12. Если же необходимо получить в первом случае 12, то мы бы написали 3 + (3 ∙ 3), то есть задали бы скобками приоритет действий. Вроде бы здесь всё нормально, с этим можно продолжать работать. Но в реальности закрепилась другая логика: сначала выполняются действия умножения и деления, а потом уже сложение и вычитание.

Мы привыкли читать слова слева направо: КОТ — животное. Но есть языки, в которых пишут и читают справа налево, тогда запись «КОТ» — это электрическое явление.

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

В алгебре логики точно так же существуют свои приоритеты выполнения операций. Перечислим их в порядке убывания:

• выражение в скобках;

• операция НЕ, то есть отрицание;

• операция И — логическое умножение. Эту операцию также называют конъюнкцией (от лат. conjunctio — «союз, связь»);

• операция ИЛИ — логическая сумма. Другое название — дизъюнкция (от лат. disjunctio — «разобщение»);

• импликация;

• эквивалентность.

Рассмотрим выражениеОно будет равносильно такому выражениюведь логическое умножение выполняется раньше сложения.

Так что наличие скобок не поменяет результат выражения. Это как в рассмотренном ранее примере: 3 + 3 ∙ 3 = 3 + 3 ∙ 3.

Можно представить это выражение с помощью арифметических операций: –A + B ∙ C. В таком виде, исходя из правил очерёдности действий:

1. вначале нужно произвести инверсию числа A;

2. затем перемножить числа B и С;

3. а затем сложить результаты этих операций.

В алгебре логики необходимо руководствоваться такими же правилами.

В случае, если подряд идут одноранговые действия, напримерто они выполняются слева направо, и выражение можно записать так:

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

Таблицы истинности. Построение таблиц истинности для логических выражений

Перед тем как перейти к таблицам истинности, необходимо ещё раз отметить, что операция НЕ является унарной (от лат. unus — «один»). Это значит, что она выполняется над единственным значением. По аналогии с математическим понятием модуля числа (это тоже унарная операция, так как на вход подаётся единственное значение).

Операции ИЛИ и И являются бинарными, то есть выполняются над двумя значениями по аналогии с арифметическими операциями сложения и умножения. Слово «бинарный» происходит от латинского binarius — «двойной».

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

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

Таблица истинности операции НЕ:

Как видно из таблицы, отрицание истинного утверждения даст нам ложь. А отрицание ложного выражения даст истину. С точки жизненной логики это не такая очевидная вещь. Так, можно отрицать тот факт, что конфету съел Миша — сказать, что конфету съел Вася. Но на самом деле конфету съел Юра. Получается, что мы отрицали ложное выражение ложным. Есть ли здесь противоречие? Нет. В алгебре логики отрицанием выражения «Конфету съел Миша» будет «Конфету съел НЕ Миша». Может возникнуть логичный вопрос: кто же тогда съел конфету? Но в алгебре логики нас это уже не интересует, важен тот факт, что это был не Миша.

Таблица истинности операции ИЛИ:

Для примера здесь можно рассмотреть выражение «Я съел конфету или я съел пирожное». Чтобы получить истину в результате, достаточно, чтобы было истинным хотя бы одно из простых выражений. Если же я съел и то, и другое, то выражение также примет истинное значение. Ложным оно будет, только если я не ел ни конфету, ни пирожное.

Таблица истинности операции И:

Для операции И, наоборот, чтобы выполнялась истинность, нужно одновременное выполнение истинности обоих утверждений. Достаточно хотя бы одной лжи, чтобы получилась ложь. Например, выражение «Я сделал уроки И пойду гулять» будет ложным и если уроки не сделаны, и даже если они сделаны, но вместо прогулки я пойду в магазин или останусь дома.

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

Булево значение в программировании

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

Хоть данный тип данных достаточно примитивен, то есть может принимать в качестве значения только 0 или 1, он широко используется во всех современных языках программирования. Например, если нам нужно знать, нарушалось ли какое-то условие при проверке массива данных, тогда достаточно использовать логическую переменную, которая по умолчанию принимает значение истинности, а любое нарушение результата проверки меняет значение на ложь.

Рассмотрим пример. Ученик за домашнее задание может получить максимальный балл тогда, когда он сделал всю работу верно, при этом соблюдены сроки сдачи домашнего задания. В этом случае мы можем составить такое логическое выражение: «Ученик сдал домашнее задание вовремя, И задание выполнено верно». Результат такого выражения может принимать значение «Истина» или «Ложь». В случае истины ученику выставляется максимальный балл, иначе — не выставляется. Учителю важно понимать, можно ли за работу ученика выставить максимальный балл. В этом случае можно составить таблицу истинности, используя операцию И:

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

Усложним пример. Теперь для получения максимальной оценки за информатику можно выполнить различные условия. Например, сдать вовремя все верно выполненные домашние работы или же победить в конкурсе по программированию. В этом случае логическое выражение, описывающее результат по предмету, будет представлено совокупностью более простых логических выражений: «Ученик сдал вовремя все домашние работы, И они выполнены верно, ИЛИ ученик победил на конкурсе по программированию». Заменим простые логические выражения на буквенные обозначения:

• Ученик сдал вовремя все домашние работы — A.

• Все работы выполнены верно — B.

• Победил в конкурсе по программированию — C.

Составим итоговое логическое выражение по правилам алгебры логики:Ещё это можно записать какДля представления результатов этого выражения также составим таблицу истинности, но теперь заменим истинное значение на 1, а ложное — на 0. Также в таблице отразим промежуточные вычисления, а именно выражение

Обратите внимание, что количество комбинаций входных данных, по сравнению с прошлой таблицей, увеличилось: вместо 4 их стало 8. Можно сделать вывод, что количество входных комбинаций логического выражения рассчитывается по формуле 2ᴺ, где 2 — количество возможных значений одного логического выражения, а N — количество логических выражений, объединённых в результат.

Глядя на эту таблицу, мы с уверенностью можем сказать, в каком случае ученик получает максимальный балл по информатике, а в каком — нет. В тех строках, где C = 1, то есть ученик победил на конкурсе, нам не важно знать, сколько работ он сдал и в какой срок. По условиям задачи ему будет выставлен максимальный балл. Если же C = 0 и ученик не победил в конкурсе, то мы будем смотреть на результат выражения A ∧ B. Оно будет истинно тогда, когда оба входных значения будут истинны, то есть ученик сдал все работы вовремя, при этом они все выполнены верно, и тогда уже не важно, победил он или нет. Конечно же, возможен результат, когда ученик и все работы вовремя сдал, и в конкурсе победил. Но учитель не может выставить балл выше максимального, поэтому в таком случае ученик получит просто максимальный балл.

Примеры таблиц истинности более сложных логических операций

Набор логических функций И, ИЛИ, НЕ является функционально полным набором или базисом алгебры логики:

• И (∧, также: х , ∙, *, &);

• ИЛИ (∨, также: +, |);

• НЕ (¬,).

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

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

Для демонстрации работы этой операции можно привести такой пример: «Число А не равно числу В». Таблица истинности для этой функции имеет вид:

Таким образом, если числа А и В равны, то условие не соблюдается и логическое выражение становится ложным. Если же числа А и В не равны, то условие будет соблюдено, а на выходе получится истина.

Операция «строгая дизъюнкция» выражается через логические операции И, ИЛИ, НЕ любой из двух логических формул:

1. A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B);

2. A ⊕ B = (A ∨ B) ∧ (¬A ∨ ¬B).

Первую формулу можно прочитать так: «если не B, то обязательно A или же наоборот, если не A, то обязательно B». Вторая формула может быть интерпретирована так: «или A, или B, но при этом обязательно или не A, или не B». Действительно, если в первой скобке истинно A, то во второй скобке уже не может быть истинным не A, значит, истинным будет не B.

Также можно сказать, что строгая дизъюнкция означает, что входные значения выражения обязательно должны быть неравны друг другу.

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

Логическая операция «импликация». Выражение, начинающееся со слов «если», «когда», «коль скоро» и продолжающееся словами «то», «тогда», называется условным высказыванием, или операцией «импликация».

Рассмотрим такой пример: если число делится на 4, то оно делится и на 2 тоже. Обозначим выражение F.

Возьмём число 6. Оно не делится на 4, но делится на 2, в этом случае импликация будет истинна. Если же взять число 8, то оно делится и на 4, и на 2, здесь импликация также истинна. Число 7, к примеру, не делится ни на 4, ни на 2, то есть можно сказать, что если число не делится на 4, то оно не делится и на 2 — это выражение истинно. Но мы не сможем найти число, которое бы делилось на 4 и при этом не делилось на 2 — здесь импликация будет давать ложь.

1. 6 : 4 — нет, 6 : 2 — да, F = 1;

2. 8 : 4 — да, 8 : 2 — да, F = 1;

3. 7 : 4 — нет, 7 : 2 — нет, F = 1;

4. x : 4 — да, x : 2 — да, F = 0.

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

Из ложного выражения следует что угодно

Существует исторический анекдот, который иногда называют теоремой о том, что из ложного утверждения следует что угодно.

Однажды на лекции Бертрана Рассела его студент усомнился в данном утверждении и попросил представить доказательство того, что если 2 + 2 = 5, то лектор — Папа Римский.

Рассел предложил такой ход рассуждений:

1. Предположим, что 2 + 2 = 5.

2. Вычтем из обеих частей по 2, получим 2 = 3.

3. Переставим правую и левую части: 3 = 2.

4. Вычтем из обеих частей по 1, 2 = 1.

Папа Римский и я — нас двое. Так как 2 = 1, то Папа Римский и я — одно лицо. Следовательно, я — Папа Римский.

Ещё можно привести такой пример, который также обозначает импликацию: «Число A не может быть больше числа B». То есть логическое выражение будет истинно тогда, когда A либо меньше, либо равно B.

Таблица истинности импликации имеет вид:

Импликацию можно обозначить по-разному:

Эти выражения эквивалентны и читаются одинаково: «Y равен импликации A и B». Операция «импликация» выражается через логические функции ИЛИ, НЕ в виде логической формулы:или

Данные формулы можно прочитать так: «Результат импликации равен логической сумме инверсного значения A и B». Вторую формулу можно прочитать так: «Отрицание импликации равно логическому произведению A и инверсного B».

Логическая операция «эквивалентность» (равнозначность). Этой логической операции соответствуют логические связки «если и только если», «тогда и только тогда, когда».

Здесь можно рассмотреть такой пример: «Я получу пятёрку по информатике тогда и только тогда, когда я сделаю домашнее задание». Если я сделал домашнее задание, то и оценка должна быть пятёркой. Но при этом я не получу пятёрку, если не сделаю задание. Если же я сделал задание, но пятёрку не получил, то результат выражения будет ложным, как и в случае, если я получил пятёрку, но при этом задание не выполнил — такое тоже невозможно.

Другой пример — логическое выражение «Число A равно числу B ». Таблица истинности для этой операции имеет вид:

На выходе мы получим истину тогда, когда входные значения равны. Можно сказать, что эквивалентность — это одновременная импликация в обе стороны. Эквивалентность A и B — это то же самое, что и (A → B) ∧ (B → A).

Операция «эквивалентность» обозначается по-разному. Выражения A ~ B, A ↔ B или A ≡ B обозначают одно и то же, и можно сказать, что A эквивалентно B, если и только если они равнозначны. Логическая операция «эквивалентность» выражается через логические функции И, ИЛИ, НЕ в виде логических формул:

Совершенная дизъюнктивная форма и совершенная конъюнктивная форма логических выражений

Итак, мы уже умеем составлять таблицу истинности для логического выражения. Но можно ли сделать наоборот: восстановить логическую функцию, зная таблицу истинности? Да, это возможно. Посмотрим, как это делается.

Возьмём, например, такую таблицу истинности:

Эта таблица показывает, что существует некоторое логическое выражение F, которое зависит от входных параметров A и B так, как показано в таблице.

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

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

2. Далее необходимо для каждой выделенной строки записать логическое выражение по следующему правилу: выражение формируется как логическое произведение входных значений. При этом, если входное значение равно нулю или ложно, его необходимо инвертировать. Для второй строки таблицы это будет выглядеть так: F = ¬A ∧ B.

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

Для четвёртой строки таблицы истинности получим выражение: F = A ∧ B. Таким образом, для обеих нужных строк таблицы истинности мы получили свои логические выражения. Но каждое из них по отдельности не даст нам в итоге полностью совпадающую таблицу с данной. Для получения итогового результата необходимо все полученные логические выражения объединить с помощью дизъюнкции или логического сложения:

Мы объединили через ИЛИ все выражения, дающие единицу. Какие бы значения мы не подставляли из выделенных строк, хотя бы одна из скобок будет иметь значение «истина», а, как мы знаем, для операции ИЛИ это означает итоговый результат «истина».

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

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

Такая форма записи логического выражения называется совершенной дизъюнктивной нормальной формой (СДНФ). Совершенной она называется потому, что не содержит повторяющихся слагаемых.

Почему совершенная дизъюнктивная нормальная форма так называется?

Почему же совершенная дизъюнктивная нормальная форма, или СДНФ, называется именно так?

С дизъюнктивной понятно — она состоит из набора дизъюнкций. Но почему совершенная и нормальная?

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

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

Нормальная форма:

F₁ = ¬X₁ ∧ ¬ X₂ ∧ ¬X₃

F₂ = X₁ ∧ ¬ X₂ ∧ ¬X₃

F₃ = X₁ ∧ X₂ ∧ ¬X₃

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

Дизъюнктивная нормальная форма (ДНФ):

Fобщ = (¬X₁ ∧ ¬X₂ ∧ ¬X₃) ∨ (X₁ ∧ ¬X₂ ∧ ¬X₃) ∨ (X₁ ∧ X₂ ∧ ¬X₃).

1. Как можно заметить, в ДНФ нет одинаковых слагаемых, которые представляют собой конъюнкцию входных значений. То есть у нас не будет двух полностью одинаковых конъюнкций.

2. При этом в каждой конъюнкции нет повторяющихся значений — в рамках одной конъюнкции каждое входное значение берётся только один раз.

3. Что ещё можно заметить — внутри каждой конъюнкции присутствуют все входные значения: X₁, X₂, X₃.

Именно комбинация этих трёх условий даёт нам право называть логическое выражение совершенной дизъюнктивной нормальной формой.

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

F = (¬X₁ ∧ ¬X₂ ∧ ¬X₃) ∨ (X₁ ∧ ¬X₂ ∧ ¬ X₃) ∨ (X₁ ∧ X₂ ∧ ¬X₃).

При этом важно, что любое, не равное нулю логическое выражение, всегда можно привести к СДНФ, причём СДНФ будет единственной.

Если вспомнить, что дизъюнкция — это логическая сумма, а конъюнкция — произведение, то можно провести параллель между СДНФ и стандартным видом многочлена.

Если же какое-нибудь из описанных трёх условий не соблюдается, например в одной из конъюнкций участвуют не все входные значения, то такое логическое выражение мы будем называть просто дизъюнктивной нормальной формой. Такое возможно, если строить логическое выражение не по описанному выше алгоритму, а путём преобразования другого логического выражения.

Примеры:

(¬A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ B∧ ¬C) — выражение относится к СДНФ.

(¬A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ ¬C) ∨ A — выражение относится только к ДНФ.

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

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

Для первой выделенной строки получаем логическое выражение: F = A + B.

Для следующей выделенной строки: F = ¬A + B.

Для получения итогового логического выражения необходимо произвести конъюнкцию всех полученных выражений: F = (A + B) ∙ (¬A + B) = (A ∨ B) ∧ (¬ A ∨ B).

Здесь мы объединяем те выражения, которые дают в результате ложь. Для получения в результате истины необходимо подставить в выражение такие значения переменных, чтобы каждая из скобок была истинной. Если же хотя бы одна из скобок даст ложь, то и итоговое выражение также будет ложным. Такая форма записи логического выражения называется совершенной конъюнктивной нормальной формой (СКНФ).

Почему совершенная конъюнктивная нормальная форма так называется?

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

F = (X₁ ∧ ¬ X₂) ∨ ¬X₃

СКНФ: (X₁ ∨ X₂ ∨ X₃) ∧ (X₁ ∨ ¬X₂ ∨ X₃) ∧ (¬X₁ ∨ ¬X₂ ∨ X₃)

По аналогии с совершенной дизъюнктивной нормальной формой конъюнктивная должна обладать следующими свойствами:

1. Она не содержит одинаковых дизъюнкций.

2. В каждой дизъюнкции нет повторяющихся значений.

3. Каждая дизъюнкция содержит все входные значения.

Так же, как и с СДНФ, при несоблюдении одного из этих требований СКНФ будет просто КНФ, или конъюнктивной нормальной формой.

(A ∨ B ∨ C) ∧ (A ∨ ¬B ∨ C) ∧ (¬A ∨ ¬B ∨ C) — выражение относится к СКНФ.

(A ∨ B ∨ C) ∧ (A ∨ ¬B ∨ C) ∧ ¬A — выражение относится только к КНФ.

Для любого, не равного единице логического выражения, всегда будет существовать СКНФ, причём единственная. Здесь можно провести параллель с разложением числа на простые множители.