Основы математической логики: Булева алгебра, алгебра высказываний, логические операции

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

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

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

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

Содержание

Булева алгебра
Алгебра высказываний
Операции над высказываниями
Формализация логических высказываний

Булева алгебра

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

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

Основные понятия и операции в булевой алгебре.

Булевы переменные — переменные, которые могут принимать только два значения: истину (1) и ложь (0).
Булевы функции – функции, которые принимают булевы переменные в качестве входных данных и возвращают булевы значения в качестве выходных данных. Примеры булевых функций включают логические операции «И» (AND), «ИЛИ» (OR), «НЕ» (NOT), «Исключающее ИЛИ» (XOR) и другие.
Булевы операции – операции, которые могут быть применены к булевым переменным или функциям для получения новых булевых значений. Эти операции включают конъюнкцию (логическое «и»), дизъюнкцию (логическое «или»), отрицание (логическое «не»), импликацию, эквивалентность и другие.
Булевы выражения — выражения, составленные из булевых переменных, операций и функций.
Булевы законы и тождества — набор правил и свойств, которые определяют поведение булевых операций и функций. К ним относятся, например, законы дистрибутивности, де Моргана, идемпотентности, поглощения и другие.

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

Булевы операции.

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

— Примеры булевых операций включают конъюнкцию (логическое «и»), дизъюнкцию (логическое «или»), отрицание (логическое «не»), исключающее ИЛИ (XOR) и другие.

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

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

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

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

Булева функция — это функция $f:\{0,1\}^{n} \rightarrow \{0,1\}$ , которая принимает входные значения из множества булевых переменных $x_{1},x_{2},\ldots,x_{n}$ и возвращает одно из двух возможных значений: 0 или 1. Каждой комбинации значений входных переменных соответствует ровно одно выходное значение.

Алгебра высказываний

Основным понятием математической логики является «простое высказывание».

Простое (элементарное) высказывание — это некоторое повествовательное предложение, которое может быть либо истинно, либо ложно, но не то и не другое одновременно.

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

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

Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно в данном месте и в данное время. Логические значения высказываний: 1 («истина») или 0 («ложь»).

Примеры высказываний.

Все студенты высших учебных заведений России получают стипендию.
3+3=6.
Земля вращается вокруг Солнца.

Приведем пример суждений, не являющихся высказываниями.

Италия — самая красивая страна.

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

В алгебре высказываний для обозначения простых высказываний принято использовать маленькие латинские буквы: $a, b, c, \ldots, x, y, z, \ldots$ . При этом, если высказывание истинно, то ему приписывается значение «1», а если ложно — то «0». Тем самым алфавит алгебры высказываний будет иметь вид $\{0,1\}$ . Также истину можно обозначать «и», ложь — «л». Джордж Буль — английский ученый, впервые осуществивший математический анализ логики высказываний.

Высказывания, которые получаются из простых с помощью грамматических связок «и», «или», «не», «тогда и только тогда», «либо …, либо …», «если …, то …» называются составными, или формулами алгебры высказываний. Формулы алгебры высказываний принято обозначать большими латинскими буквами A, B, C, и т. д.

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

Формула, истинная при всех значениях, входящих в нее переменных, называется тождественно истинной или тавтологией.

Если $A$ — тождественно истинная формула, то можно записать $A = 1$ .

Формула, ложная при всех значениях, входящих в неё переменных, называется тождественно ложной или противоречием.

Если $B$ — тождественно ложная формула, то можно записать $B = 0$ .

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

Рассматривая высказывания, мы абстрагируемся от их смысла, нас интересует их истинность или ложность. Мы пишем $a = 1$ , если $a$ — истинно, и $a = 0$ , если $а$ — ложно.

Логические значения формулы алгебры логики могут быть описаны с помощью таблицы истинности.

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

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

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

Булева функция n-переменных может иметь $2^{n}$ различных комбинаций аргументов.

Согласно вышеприведенной формуле, число всевозможных булевых функций для двух аргументов (n=2) будет $2^{2} = 4$ .

Таблица 2.2.1 — Комбинации для двух аргументов

$x$	$y$	$f$
0	0	значение
0	1	значение
1	0	значение
1	1	значение

Для трех аргументов (n=3) $2^{3} = 8$ .

Таблица 2.2.2 — Комбинации для трех аргументов

$x$	$y$	$z$	$f$
0	0	0	значение
0	0	1	значение
0	1	0	значение
0	1	1	значение
1	0	0	значение
1	0	1	значение
1	1	0	значение
1	1	1	значение

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

Операции над высказываниями

Рассмотрим основные операции над высказываниями:

дизъюнкция $\vee$ ;
конъюнкция $\land$ ;
отрицание $\overline{a}$ или $\neg a$ ;
импликация →;
эквивалентность $\sim$ или ⟺;
штрих Шеффера |;
стрелка Пирса $\downarrow$ ;
строгая дизъюнкция $\oplus$ .

Конъюнкция $a \land b$ . Запись читается « $a$ конъюнкция $b$ ».

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба эти высказывания истинны. Если хотя бы одно из высказываний ложно, то их конъюнкция также будет ложной.

Конъюнкция в математической логике — это логическая операция, которая соответствует союзу «и» в естественном языке, определяется как логическое умножение.

Таблица 2.2.3 — Таблица истинности конъюнкции

$a$	$b$	$a \land b$
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция $a \vee b$ . Читается эта запись « $a$ дизъюнкция $b$ ».

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

Дизъюнкция в математической логике — это логическая операция, которая соответствует союзу «или» в естественном языке, определяется как логическое сложение.

Таблица 2.2.4 — Таблица истинности дизъюнкции

$a$	$b$	$a \vee b$
0	0	0
0	1	1
1	0	1
1	1	1

Отрицание $\overline{a}$ . Запись читается «не $a$ ».

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

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

Таблица 2.2.5 — Таблица истинности у отрицания

$a$	$\overline{a}$
0	1
1	0

Импликация $a \rightarrow b$ . Запись $a \rightarrow b$ читается как « $a$ импликация $b$ », «из $a$ следует $b$ », «если $a$ , то $b$ ».

Импликация в математической логике — это бинарная логическая операция, которая соответствует выражению условия "если …, то … ". Импликация между двумя высказываниями $a$ и $b$ (где $a$ — это условие, а $b$ — следствие) обозначается как $a \rightarrow b$ и читается как «если $a$ , то $b$ ».

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

Таблица 2.2.6 — Таблица истинности импликации

$a$	$b$	$a \rightarrow b$
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентность $a \Leftrightarrow b$ . Запись читается, как « $a$ эквивалентно $b$ ». Эквивалентность — это бинарная логическая операция, которая истинна тогда и только тогда, когда значения высказываний совпадают, т. е. если они истинны или ложны одновременно.

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

$a$	$b$	$a \Leftrightarrow b$
0	0	1
0	1	0
1	0	0
1	1	1

Эквивалентность $a \Leftrightarrow b$ в математической логике — это логическая операция, которая соответствует выражению « $a$ тогда и только тогда, когда $b$ ».

Штрих Шеффера (отрицание конъюнкции, операция «не и»).

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

Штрих Шеффера, также известный как операция NAND (от англ. NOT AND — не и), является бинарной логической операцией, которая является отрицанием конъюнкции.

Таблица 2.2.8 — Таблица истинности для операции штрих Шеффера

$a$	$b$	$a \| b$
0	0	1
0	1	1
1	0	1
1	1	0

Стрелка Пирса (отрицание дизъюнкции, операция «не или»).

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

Стрелка Пирса, также известная как операция NOR (от англ. NOT OR — не или), является бинарной логической операцией, которая является отрицанием дизъюнкции.

Таблица 2.2.9 — Таблица истинности для операции стрелка Пирса

$a$	$b$	$a \downarrow b$
0	0	1
0	1	0
1	0	0
1	1	0

Строгая дизъюнкция (сложение по модулю два, сложение Жегалкина, исключающее ИЛИ). Запись читается как « $a$ строгая дизъюнкция $b$ ».

Строгая дизъюнкция — это бинарная логическая операция, которая истинна тогда и только тогда, когда значения переменных различны.

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

Таблица 2.2.10 — Таблица истинности для операции строгая дизъюнкция

$a$	$b$	$a \oplus b$
0	0	0
0	1	1
1	0	1
1	1	0

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

Таблица 2.2.11 — Сводная таблица логических операций

$a$	$b$	$a \land b$	$a \vee b$	$\overline{a}$	$a \rightarrow b$	$a \Leftrightarrow b$	$a \| b$	$a \downarrow b$	$a \oplus b$
0	0	0	0	1	1	1	1	1	0
0	1	0	1	1	1	0	1	0	1
1	0	0	1	0	0	0	1	0	1
1	1	1	1	0	1	1	0	0	0

Формализация логических высказываний

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

Таблица 2.3.1 — Формализация сложных высказываний

Союзы и частицы естественного языка	Операции алгебры высказываний	Примеры
Конъюнкция (И, $\land$ ) « $a$ » и « $b$ », где « $a$ » — «сегодня ясно», « $b$ » — «сегодня холодно».	$a \land b$	Сегодня ясно и холодно
Дизъюнкция (ИЛИ, $\vee$ ) « $a$ » или « $b$ », где « $a$ » — «завтра будет солнечно», « $b$ » — «завтра будет ветрено».	$a \vee b$	Завтра будет солнечно или ветрено
Отрицание («не») не « $a$ », где « $a$ » — «сегодня дождливо»	$\overline{a}$	Сегодня не дождливо
Импликация (Если…, то…, →) если « $a$ », то « $b$ », где « $a$ » — «сегодня пятница», « $b$ » - «завтра выходной».	$a \rightarrow b$	Если сегодня пятница, то завтра выходной
Эквивалентность (↔, ⟺) « $a$ » тогда и только тогда, когда « $b$ », где « $a$ » — «электричество доступно», « $b$ » — «генератор работает».	$a \Leftrightarrow b$	Электричество доступно тогда и только тогда, когда генератор работает
Штрих Шеффера (И не, \|), где « $a$ » — «сегодня солнечно», « $b$ » — «сегодня тепло».	$a \| b$	Неверно, что сегодня солнечно и тепло
Стрелка Пирса (Или не, ↓), где « $a$ » — «сегодня дождливо», « $b$ » — «сегодня ветрено».	$a \downarrow b$	Сегодня будет ни дождливо, ни ветрено
Строгая дизъюнкция ( $XOR, \oplus$ ), или « $a$ », или « $b$ », но не оба, где « $a$ » — «завтра будет солнечно», « $b$ » — «завтра будет облачно».	$a \oplus b$	Завтра будет либо солнечно, либо облачно, но не оба одновременно

2.3.1. Даны элементарные высказывания:

$a$ — «Москва — столица России»; $b$ — «Париж — столица Германии»;

$c$ — «Лондон — столица Англии»; $d$ — «Берлин — столица Франции».

Какие из следующих составных высказываний истинны, а какие ложны: 1) $a \land c$ , $a \land d$ , $b \land c$ , $b \land d$ ; 2) $\overline{a} \land \overline{c}$ , $\overline{a} \land \overline{d}$ , $\overline{b} \land \overline{c}$ , $\overline{b} \land \overline{d}$ .

Решение.

Известно, что:

Москва действительно является столицей России, так что $a$ — истинно;
Париж не является столицей Германии (это Берлин), так что $b$ — ложно;
Лондон действительно является столицей Англии, так что $c$ — истинно;
Берлин не является столицей Франции (это Париж), так что $d$ — ложно.

1) Рассмотрим каждое составное высказывание:

$a \land c$ : «Москва — столица России и Лондон — столица Англии». Это высказывание истинно, так как оба утверждения верны.
$a \land d$ : «Москва — столица России и Берлин — столица Франции». Это высказывание ложно, так как второе утверждение неверно.
$b \land c$ : «Париж — столица Германии и Лондон — столица Англии». Это высказывание ложно, так как первое утверждение неверно.
$b \land d$ : «Париж — столица Германии и Берлин — столица Франции». Это высказывание ложно, так как оба утверждения неверны.

2) Анализируем следующие высказывания:

$\overline{a} \land \overline{c}$ : «Москва не является столицей России и Лондон не является столицей Англии». Это высказывание ложно, так как оба утверждения неверны.
$\overline{a} \land \overline{d}$ : «Москва не является столицей России и Берлин не является столицей Франции». Это высказывание ложно, так как первое утверждение неверно.
$\overline{b} \land \overline{c}$ : «Париж не является столицей Германии и Лондон не является столицей Англии». Это высказывание ложно, так как второе утверждение неверно.
$\overline{b} \land \overline{d}$ : «Париж не является столицей Германии и Берлин не является столицей Франции». Это высказывание истинно, так как оба утверждения верны.

2.3.2. Даны элементарные высказывания: $a$ — «8 — четное число»; $b$ — «8 — нечетное число»; $c$ — «9 — простое число»; $d$ — «9 — составное число». Какие из следующих составных высказываний истинны, а какие ложны: 1) $a \land c$ , $a \land d$ , $b \land c$ , $b \land d$ ; 2) $\overline{a} \land \overline{c}$ , $\overline{a} \land \overline{d}$ , $\overline{b} \land \overline{c}$ , $\overline{b} \land \overline{d}$ .

2.3.3. Даны элементарные высказывания: $e$ : «2 + 2 = 4»; $f$ : «2 + 2 = 5»; $g$ : «3 × 3 = 9»; $h$ : «3 × 3 = 10». Какие из следующих составных высказываний истинны, а какие ложны: 1) $e \land g$ , $e \land h$ , $f \land g$ , $f \land h$ ; 2) $\overline{e} \land \overline{g}$ , $\overline{e} \land \overline{h}$ , $\overline{f} \land \overline{g}$ , $\overline{f} \land \overline{h}$ .

2.3.4. Даны элементарные высказывания: $i$ : «Земля круглая»; $j$ : «Земля плоская»; $k$ : «Солнце вращается вокруг Земли»; $l$ : «Земля вращается вокруг Солнца». Какие из следующих составных высказываний истинны, а какие ложны: 1) $i \land l$ , $i \land k$ , $j \land l$ , $j \land k$ ; 2) $\overline{i} \land \overline{l}$ , $\overline{i} \land \overline{k}$ , $\overline{j} \land \overline{l}$ , $\overline{j} \land \overline{k}$ .

2.7.1. Даны элементарные высказывания: $a$ : «8 — четное число»; $b$ : «8 — нечетное число»; $c$ : «9 — простое число»; $d$ : «9 — составное число». Какие из следующих составных высказываний истинны, а какие ложны: 1) $a \vee c,\ \ b \rightarrow d,\ \ c \leftrightarrow d,\ \ a\oplus b;$ 2) $\overline{a} \land \overline{c},\ \ \overline{b} \vee \overline{d},\ \ a|c,\ \ b \downarrow d.$

2.7.2. Даны элементарные высказывания: $e$ : «Солнце — звезда»; $f$ : «Луна — планета». Какие из следующих составных высказываний истинны, а какие ложны: 1) $e \land f,\ \ e \vee f,\ \ e \rightarrow f,\ \ e\oplus f;$ 2) $\overline{e} \vee \overline{f},\ \ \overline{e} \land \overline{f},\ \ e\ |\ f,\ \ e\ \downarrow \ f.$

2.7.3. Даны элементарные высказывания: $g$ : «Вода кипит при 100°C»; $h$ : «Лед тает при 0°C». Какие из следующих составных высказываний истинны, а какие ложны: 1) $g \land h,\ \ g \vee h,\ \ g \rightarrow h,\ \ g\oplus h;$ 2) $\overline{g} \vee \overline{h},\ \ \overline{g} \land \overline{h},\ \ g\ |\ h,\ \ g\ \downarrow \ h.$