Алгебра логики

Элементы алгебры логики

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

Создателем алгебры логики является Джордж Буль (1815 - 1864), английский математик и логик, положивший в основу своего учения аналогию между алгеброй и логикой.

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

Логические высказывания

В повседневной жизни часто приходится слышать фразы-утверждения вроде "Сейчас идёт снег" или "Маша - девочка". Если в отношении повествовательного предложения(высказывания) можно однозначно утверждать, что его содержание истинно или ложно, то такое утверждение называется логическим высказыванием.

☑️_"Шесть минус три равно три", "Москва - столица России" - истинные высказывания. "Пять больше шести", "Луна это звезда" - ложные высказывания._

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

☑️_Высказывание "Маша - молодец" не является логическим высказыванием, потому что оценка "молодец" субъективна: для кого-то Маша молодец, а для кого-то - нет._

Различают простые(элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D...), и сложные, составленные из нескольких простых высказываний с помощью логических связок, таких как "не", "и", "или", "тогда и только тогда", "если...то...иначе".

Истинность высказывания

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

Обозначение результатов логических утверждений: Правда: 1, Да(истинно), True, Истина Ложь: 0, Нет(ложно), False, Ложь

В информатике для решения задач на истинность конструкций используются обозначения 0 и 1, в программировании - True/False(true/false) и 1/0.

☑️_Пусть высказывание А - "Саша любит конфеты", высказывание В - "Саша любит шоколад". Если говорится об одном и том же человеке, то оба эти высказывания можно объединить в одно: "Саша любит конфеты и шоколад" - и записать как А И В. Если оба высказывания истинны, то истинно и составное высказывание. Если же какое-нибудь из них ложно, то ложно и всё высказывание А И В._

❗️_Высказывание не может быть выражено побудительным или вопросительным предложением, оценка истинности или ложности которого невозможна._

Выражение А И В — логическая конструкция(функция), где А, В — операнды(аргументы), "И" — операция(действие).Операнд — аргумент операции, т.е. то, над чем выполняется операция.

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

Унарная(одноместная) операция — операция, которая применяется к одному операнду.

☑️_Изменение знака числа. К А применим операцию изменения знака, получим -А._

Бинарная(двуместная) операция — операция, которая выполняется над двумя операндами. Бинарную операцию принято обозначать знаком действия, который ставится между операндами. Такая форма записи называется инфиксной.

☑️_Сложение (А + В), вычитание (А - В), умножение (А * В)._

Тернарная(трёхместная) операция — операция, которая выполняется над тремя операндами.

☑️_Среднее арифметическое трёх чисел, смешанное произведение векторов._

Аналогом тернарной условной операции в математической логике является операция, которая записывается как a, b, c и реализует алгоритм "если a, то b, иначе c".

☑️_Если завтра будет хорошая погода, то я пойду гулять, иначе останусь дома._ Обычно тернарная условная операция ассоциируется с операцией вида a ? b : c, используемой в языках программирования.

Логические операции

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

Логическая функция F зависит от логических переменных. Логические переменные могут принимать значения только: 0(ложь) или 1(истина). С логическими переменными можно производить логические операции. При решении второго и пятнадцатого задания из ЕГЭ по информатике необходимо твёрдо знать каждую логическую операцию.

Логическое отрицание(инверсия)

Логическое отрицание(инверсия) — унарная операция, в результате которой из данного высказывания(например, А) получается новое высказывание (не А) как отрицание исходного высказывания. Порядок работы схемы инверсии: на вход подаётся значение А, после прохождения прямоугольника с операцией ¬ на выходе получается значение ¬А.

☑️_"Катя получила двойку", после применения инверсии получим: "Катя не получила двойку"._ Если на вход схемы отправить значение 0, то на выходе будет значение 1, и наоборот. У данной схемы один вход и один выход, операция - унарная.

Таблица истинности инверсии и схема:

Инверсия обозначается: ¬А, А̅, не А, not А. Читается: «Не А».

Логическое умножение(конъюнкция)

Логическое умножение, или конъюнкция — бинарная операция, соединяющая два высказывания и более с помощью связки "и" (например, "А и В"). Порядок работы схемы: на вход подаются два значения - А, В, на выходе будет новое значение состоящее из результата операции этих двух входящих.

☑️_"Этот треугольник равнобедренный и прямоугольный"._ ❗️Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно. Суть легко запомнить - высказывание А и В истинна только тогда, когда оба высказывания А, В истинны.

Таблица истинности конъюнкции и схема:

Конъюнкция обозначается: А ∧ B, А & В, А · В, А × В, А и В, А and В. Читается: «А и В».

Логическое сложение(дизъюнкция)

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

☑️_"Число x делится на 3 или на 5"._ ❗️Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности дизъюнкции и схема:

Дизъюнкция обозначается: А ∨ В, А + В, А | В, А или В, А or В. Читается: «А или В».

Логическое исключающее или(дизъюнкция строго разделительная)

Дизъюнкция строго разделительная, т.е. исключающее ИЛИ(сложение по модулю 2) — бинарная операция, соединяющая два высказывания с помощью связки "или", употреблённой в исключающем смысле.

☑️_"Этот треугольник тупоугольный или остроугольный"._ ❗️Высказывание истинно, если выполняется одно из условий. Легко запомнить смысл операции: Если операнды А,В имеют различные значения то результатом исключающего или будет 1(истина).

Таблица истинности исключающего ИЛИ:

«Исключающее ИЛИ» обозначается: А ⊕ В, А ^ В, А ≠ В, А xor В, А != В. Читается: «Либо А, либо В».

Логическое следование(импликация)

Логическое следование, или импликация — логическая операция, соединяющая два высказывания с помощью связки "если... то...". Импликация — сокращённая запись для выражения ¬А V В (НЕ А или В). При решении задач можно уверенно заменять в выражении импликацию этой записью.

☑️_"Если четырёхугольник - квадрат, то в него можно вписать окружность"._ ❗️Эта операция связывает два простых выражения, из которых первое является условием, а второе — следствием. Результат ложен только тогда, когда предпосылка есть истина, а следствие ложь.

Таблица истинности следования:

Следование обозначается: А → В. Читается: «Если А, то В», «из А следует В», «А влечёт В», «А имплицирует В».

Логическая операция эквивалентность(двойная импликация, равносильность, равнозначность)

Эквивалентность, или двойная импликация (равносильность, равнозначность) — бинарная операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В. Эквивалентность — это сокращённая запись для выражения (¬А ∧ ¬В) V ( А ∧ В). Можно заменять эквивалентность в любом выражении этой записью. ☑️_"Треугольник будет прямоугольным тогда и только тогда, когда один из его углов равен 90 градусам"._ Операция эквивалентности противоположна исключающему или.

Таблица истинности эквивалентности:

Равносильность(эквиваленция) обозначается: А ↔ В, А ≡ В, А == В. Читается: «А эквивалентно В», «А тогда и только тогда, когда В», «А то же самое, что В», «А равносильно В».

Приоритеты логических связок

Зная значения простых высказываний, можно на основании таблиц истинности определить значения сложных высказываний. При этом важно знать, что для представления любой функции алгебры логики достаточно трёх операций: конъюнкции, дизъюнкции и отрицания(инверсии). При решении математических выражений, состоящих из нескольких действий, в первую очередь необходимо задуматься о порядке действий. Например, 2 + 2 * 2 не то же самое, что (2 + 2) * 2. При работе с логическими конструкциями также важно сначала понять, какое действие следует выполнить первым. Для этого существуют определённые правила. Операции одинакового приоритета выполняются слева направо.

Порядок выполнения логических операций

1. () операции в скобках
2. ¬ логическое отрицание
3. ∧ логическое умножение
4. ∨ логическое сложение
5. ⟶ следование
6. ≡ равнозначность

☑️_Расставим порядок действий в следующих логических высказываниях: А V В → С & D ≡ ¬А_

1. ¬А
2. С & D
3. А V В
4. В → С
5. D ≡ ¬А

Основные законы логики

Законы логики выражают необходимые условия для правильного последовательного мышления. Знание этих законов и порядка выполнения логических операций требуется для результативного упрощения логических выражений. При вычислении логического выражения по таблице истинности следует определить, сколько строк будет в таблице. Для этого необходимо посчитать количество разных аргументов и возвести в полученную степень число 2, т.к. имеется два значения - 0 и 1. Например, для двух аргументов А и В получится 4 строки(2^2), а для функции с тремя аргументами x, y, z в таблице будет отведено 8 строк(2^3), для пяти аргументов понадобится 32 строки и т.д.

Логические соотношения:

• A ⟶ B = ¬A ∨ B
• A ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B)
• A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)

Примеры заданий

☑️ Составьте таблицу истинности для следующей функции: F = (A ∨ B) & (¬A ∨ ¬B).

Решение:

1. Определим количество строк в таблице: 22 = 4, поскольку имеется два разных аргумента А и В и у каждого по два значения – 0 и 1.
2. Количество столбцов: 5 действий и 2 аргумента – 7 столбцов.
3. Расставим порядок выполнения операций(действий)
   1. A ∨ B;
   2. ¬A;
   3. ¬B;
   4. ¬A ∨ ¬B;
   5. (A ∨ B) & (¬A ∨ ¬B) = F
4. Составим таблицу:

☑️ Составьте функцию по заданной схеме и расставьте порядок действий(операций)

Решение:Функция будет иметь следующий вид: F = ¬B & ¬(¬A ∨ B).

Порядок действий(операций):

1. ¬A
2. ¬A ∨ B
3. ¬B
4. ¬(¬A ∨ B)
5. ¬B & ¬(¬A ∨ B)

Предикаты и кванторы

В алгебре высказываний для записи различных утверждений применяют логические знаки. Однако этих знаков недостаточно для выражения мысли типа "Всякий элемент x из множества D обладает свойством P(x)". Введём новые логические знаки, обозначаемые ∀, ∃и ∃!.

Предикат (лат. "заявленное, упомянутое") - утверждение, содержащее переменные и принимающие значение 1 или 0 (истинно или ложно) в зависимости от значений переменных.

☑️_Утверждение "x делится на 9 на множестве целых положительных чисел" при x = 9, 18, 27 истинно, а при x = 8, 16, 33 ложно._

Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката Ip.

☑️_В примере "x делится на 9 на множестве целых положительных чисел" множеством истинности предиката является множество чисел r = 9n, где n ∈ N (N — множество натуральных чисел: 1, 2, 3...)._

Предикатом в программировании является функци, которая принимает один аргумент и более и возвращает значения булева типа(Boolean).

Невыполнимый предикат — предикат, принимающий значение "ложь" при всех допустимых значениях переменной. Так, выражение x^2 + 3 = 0 при всех действительных значениях x не принимает значения "истина", иначе говоря, уравнение не имеет действительных корней.

Предикат A является следствием предиката B, если для любых значений переменных, при которых B — истина, A — тоже истина. Например, если число a делится на 9(B), то число а делится также на 3 (A). Обратное утверждение не всегда будет являться истинным.

Предикаты A и B называются равносильными, если из А следует В и из В следует А. Например, если число а делится на 3(А), то число a + 3 делится на 3(В). Обратное утверждение также будет являться истинным для любых значений а.

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

Часто упоминаемые кванторы: Квантор всеобщности ∀. Читается: "для любого..", "для каждого...", "для всех..." или "каждый...", "любой...", "все...". Квантор существования ∃. Читается: "существует..." или "найдётся...". Квантор существования и единственности ∃!. Выражение "существует точно одно такое x, что...".

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

☑️_Пусть предикат "x кратно 7". С помощью квантора всеобщности можно записать следующие ложные высказывания:_

1. любое натуральное число делится на 7;
2. каждое натуральное число делится на 7;
3. все натуральные числа делятся на 7. Квантор будет иметь вид: (∀x ∈ N) P(x).