Математическая логика (Основные математические операции)

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т. д. Действия над переменными величинами записываются в виде математических выражений.

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

Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения.

Логические выражения могут быть простыми и сложными.

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

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

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

• НЕ (логическое отрицание, инверсия);
• ИЛИ (логическое сложение, дизъюнкция);
• И (логическое умножение, конъюнкция)

Операция НЕ — логическое отрицание (инверсия)

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

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения:

не А, not A, ¬А.

Приведем примеры отрицания.

1. Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.
2. Высказывание «Уравнение $у = 4х + 3$ в промежутке $ -2 \lt х \lt 2 $ не имеет корня» ложно. Высказывание «Уравнение $у = 4х + 3$ в промежутке $ -2 \lt х \lt 2 $ имеет корень» истинно.
3. Высказывание «$4$ — простое число» ложно. Высказывание «$4$ — не простое число» истинно.

Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает ее, если лампа не горела — включает ее. Такой переключатель можно считать электрическим аналогом операции отрицания.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

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

Применяемые обозначения: А или В, А V В, A or B.

Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.

Приведем примеры логического сложения.

1. Рассмотрим высказывание «В библиотеке можно взять книгу или встретить знакомого». Это высказывание формально можно представить так: С = А V В, где высказывание А — «В библиотеке можно взять книгу», а В — «В библиотеке можно встретить знакомого». Объединение этих высказываний при помощи операции логического сложения означает, что события могут произойти как отдельно, так и одновременно.
2. Рассмотрим высказывание «Знания или везение — залог сдачи экзаменов». "Успешно сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянут единственный выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет.

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

Операция И — логическое умножение (конъюнкция)

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

Применяемые обозначения: А и В, A & B, A and B.

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

Приведем примеры логического умножения.

1. Рассмотрим высказывание «Умение и настойчивость приводит к достижению цели». Достижение цели возможно только при одновременной истинности двух предпосылок — умения И настойчивости.

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

Теперь расмотрим эти операции на примере манипуляции с битами.
Бит — это минимальная единица измерения объёма информации, так как она хранит одно из двух значений — $0$ (False) или $1$ (True). False и True в переводе на русский ложь и истина соответственно. То есть одна битовая ячейка может находиться одновременно лишь в одном состоянии из возможных двух.

Все приведенные выше операции могут быть использованы при манипуляции с битами.

Рассмотрим примеры.

Логическая операция И (AND)

Логическая операция И выполняется с двумя битами, назовем их a и b. Результат выполнения логической операции И будет равен $1$, если a и b равны $1$, а во всех остальных (других) случаях, результат будет равен $0$. Смотрим таблицу истинности логической операции and.

$$
a \ (бит \ 1) | \ b \ (бит \ 2) \ | a \ (бит \ 1) \ and \ b \ (бит \ 2) \\
\ \qquad 0 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
\ \qquad 0 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
$$

Логическая операция ИЛИ (OR)

Логическая операция ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции ИЛИ будет равен $0$, если a и b равны 0 (нулю), а во всех остальных (других) случаях, результат равен $1$ (единице). Смотрим таблицу истинности логической операции OR.

$$
a \ (бит \ 1) | \ b \ (бит \ 2) \ | a \ (бит \ 1) \ or \ b \ (бит \ 2) \\
\ \qquad 0 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
\ \qquad 0 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
$$

Логическая операция исключающее ИЛИ (XOR).

Логическая операция исключающее ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции XOR будет равен $1$ (единице), если один из битов a или b равен $1$ (единице), во всех остальных случаях, результат равен $0$ (нулю). Смотрим таблицу истинности логической операции исключающее ИЛИ.

$$
a \ (бит \ 1) | \ b \ (бит \ 2) \ | a \ (бит \ 1) \ xor \ b \ (бит \ 2) \\
\ \qquad 0 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
\ \qquad 0 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 0 \ \qquad \ \ \qquad \ \ \ \ 1 \qquad \qquad \quad \\
\ \qquad 1 \ \qquad \quad \ 1 \ \qquad \ \ \qquad \ \ \ \ 0 \qquad \qquad \quad \\
$$

Логическая операция НЕ (not)

Логическая операция НЕ выполняется с одним битом. Результат выполнения этой логической операции напрямую зависит от состояния бита. Если бит находился в нулевом состоянии, то результат выполнения NOT будет равен единице и наоборот. Смотрим таблицу истинности логической операции НЕ.

$$
a \ (бит \ 1) | \ ¬a (отрицание бита) \\
\ 0 \ \qquad \quad \ 1 \qquad \quad \quad \\
\ 1 \ \qquad \quad \ 0 \qquad \quad \quad \\
$$