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

Введение в алгебру логики


expand

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

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

Как и привычная нам алгебра , алгебра логики также изучает действия над переменными. Переменные в алгебре логики называются высказываниями. А действие над высказываниями, результатом которого является новое высказывание называется логической операцией. Мы будем рассматривать классическую логику, которая утверждает, что высказывание может находиться в одном из двух состояний, называемых истина (логическая единица) и ложь (логический нуль). Например, высказывание "За окном идет дождь" может быть истинным в тот момент, когда вы это читаете, а на следующий день станет ложным, но оно не может быть истинным и ложным одновременно. От этой аксиомы мы будем отталкиваться в дальнейших рассуждениях:

В каждый момент времени высказывание может принимать только одно из двух значений: истина ( 1 ) или ложь ( 0 )
Поскольку количество состояний высказывания ограничено, то для любого количества высказываний количество операций составляет конечное множество. Давайте рассмотрим все возможные действия над одним высказыванием a:
при a = 0 , результат действия = 0
при a = 1 , результат действия = 0

Если результат = 0 вне зависимости от состояния высказывания, значит такая операция называется константа логического нуля ("0"). Эта операция не зависит от количества переменных-высказываний, поэтому является "нульарной" (0-арной).

при a = 0 , результат действия = 0
при a = 1 , результат действия = 1

Здесь видно, что при любом состоянии высказывания результат повторяет его состояние. Читатель может спросить: "Если результат не отличается от входных данных, то как понять, что над этими данными было совершено какое-то действие?" Для одной переменной это так. Однако далее мы увидим, что при количестве высказываний >= 2 будет операция, повторяющая состояния одного из высказываний, не принимая во внимание остальные.

при a = 0 , результат действия = 1
при a = 1 , результат действия = 0

Если при любом значении переменной, результат будет противоположным по значению, то такая унарная операция называется инверсия а ( НЕ а, отрицание а ). Условное обозначение инверсии: ¬. Инверсию часто изображают в виде верхней черты над высказыванием.

при a = 0 , результат действия = 1
при a = 1 , результат действия = 1

Если при любом значении переменной результат = 1, то такая нульарная операция называется константа логической единицы ("1")

Для одного высказывания a существует 2 состояния: (a = 1) или (a = 0) . Для двух высказываний a и b существует всего 4 состояния:

(a = 0 , b = 0)
(a = 0 , b = 1)
(a = 1 , b = 0)
(a = 1 , b = 1)
для трех высказываний - 8 состояний (000, 001, 010, 011, 100, 101, 110, 111), и так далее по следующему закону:
кол. состояний = 2 кол. высказываний

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

Все возможные операции над двумя высказываниями
Все возможные операции над двумя высказываниями ( a и b )

Выше мы рассмотрели нульарные и унарные операции, теперь рассмотрим подробнее бинарные (2-арные) операции, результат которых зависит от двух переменных:

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

Другие названия: конъюнкция, AND
Условные обозначения: ∧ , ∩ , * , ∙ (Иногда знак конъюнкции опускают при записи формулы)

Результат операции a И b принимает значение истина (1) только если обе переменные истинны (1).
Логическое ИЛИ
Таблица истинности операции Логическое ИЛИ
Таблица истинности операции Логическое ИЛИ

Другие названия: дизъюнкция, OR
Условные обозначения: ∨ , ∪ , +

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

Другие названия: сложение по модулю 2, XOR, строгая дизъюнкция
Условные обозначения: ⊕

Результат операции ab принимает значение истина (1) если только одна из двух переменных истинна (1).
Импликация
Таблица истинности операции Импликация
Таблица истинности операции Импликация

Условные обозначения: →

Операцию ab можно описать так: " b необходимо для a". То есть результат импликации принимает значение ложь (0), если переменная a - истинна, а переменная b при этом ложна. Для остальных состояний переменных результат принимает значение истина (1).
В случае операции обратная импликация (ab) читаем так: " a необходимо для b"
Эквивалентность
Таблица истинности операции Эквивалентность
Таблица истинности операции Эквивалентность

Условные обозначения: ↔ , ~
Результат операции ab принимает значение истина если a = b.
Стрелка Пирса
Таблица истинности операции Стрелка Пирса
Таблица истинности операции Стрелка Пирса

Другие названия: NOR, ИЛИ-НЕ
Условные обозначения: ↓
Результат операции ab принимает значение истина если ни a ни b не истинны.
Штрих Шеффера
Таблица истинности операции Штрих Шеффера
Таблица истинности операции Штрих Шеффера

Другие названия: NAND, И-НЕ
Условные обозначения: |
Результат операции a | b принимает значение ложь, если и a и b истинны.

В случае наличия одной переменной мы обнаружили 4 возможных операции. Для двух переменных возможно уже 16 действий над ними. Для трех переменных возможно 2 кол. состояний = 2 8 = 256 операций. Количество высказываний может быть любым, и количество операций будет постоянно возрастать. Когда же остановиться?

Выше мы говорили о том, что алгебра не занимается изучением всех возможных операций, а только тех, которых достаточно для решения задач. Есть ли среди этих операций универсальная, из которой можно получить остальные? C помощью операции стрелка Пирса можно получить отрицание ¬a = a ↓ a, конъюнкцию a ∧ b = (a ↓ a) ↓ (b ↓ b), дизъюнкцию a ∨ b = (a ↓ b) ↓ (a ↓ b), импликацию a → b = ((a ↓ a) ↓ b) ↓ (a ↓ a) ↓ b) и все остальные операции. То же можно сказать и про штрих Шеффера.

Как видите, можно обойтись даже одной операцией, но посмотрите, насколько возросла сложность выражений. Как найти золотую середину? У математиков были разные мнения на этот счет, к примеру алгебра Джорджа Буля включает конъюнкцию, дизъюнкцию, отрицание, а также логический нуль и логическую единицу. То есть в булевой алгебре все отношения между переменными выражают с помощью базиса И-ИЛИ-НЕ. Менее распространена алгебра Жегалкина, включающая операции исключающее ИЛИ , конъюнкцию и логическую единицу.