Основные понятия алгебры логики
Алгебра логики - это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
Логическое высказывание - это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Считается, что если выражение ложно, то оно имеет значение 0, а если выражение истинно, то - 1. Чтобы обращаться к логическим высказываниям, им назначают имена А, В, С или x, y, z.
Слова и словосочетания "не", "и", "или", "если... , то", "тогда и только тогда" и другие называются логическими связками и позволяют из уже заданных высказываний строить новые высказывания.
Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называются элементарными.
Логические операции
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Рассмотрим основные логические операции.
Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием. Высказывание истинно, когда A ложно, и ложно, когда A истинно.
Операция, выражаемая связкой "и", называется конъюнкцией [лат. conjunctio - соединение] или логическим умножением и обозначается точкой "" [может также обозначаться знаками или ]. Высказывание АВ истинно тогда и только тогда, когда оба высказывания А и В истинны.
Операция, выражаемая связкой "или" [в неразделительном, не исключающем смысле этого слова], называется дизъюнкцией [лат. disjunctio - разделение] или логическим сложением и обозначается знаком "" [или плюсом]. Высказывание АВ ложно тогда и только тогда, когда оба высказывания А и В ложны.
Операция, выражаемая связками "если ..., то", "из ... следует", "... влечет ...", называется импликацией [лат. implico - тесно связаны] и обозначается знаком "". Высказывание АВ ложно тогда и только тогда, когда А истинно, а В - ложно. Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.
Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком "" или "". Высказывание АВ истинно тогда и только тогда, когда значения А и В совпадают.
Логическая функция
Функцией алгебры логики f(x1, x2, ... ,xn) от n - переменных x1, x2, ... ,xn, принимающих значения 0 или 1, называется функция, принимающая значения 0 или 1.
Функция задается с помощью таблицы истинности. В каждой строке таблицы вначале дается набор значений переменных x1, x2, ... ,xn, а затем значение функции на этом наборе. Число различных двоичных наборов ограничено и равно 2n.
x1 | x2 | ... | xn | f(x1, x2, ... ,xn) |
0 | 0 | ... | 0 | f(0, 0, ... ,0) |
0 | 0 | ... | 1 | f(0, 0, ... ,1) |
... | ... | ... | ... | ... |
1 | 1 | ... | 0 | f(1, 1, ... ,0) |
1 | 1 | ... | 1 | f(1, 1, ... ,1) |
В таблице наборы располагают в определенном порядке - лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. При любом фиксированном упорядочении наборов логическая функция полностью определяется столбцом своих значений, длина которого равна 2n. Поэтому число различных функций от n переменных равно числу различных двоичных наборов длины 2n, т.е. 22n.
Логическая формула
Суперпозицией функций f1,...,fm называется функция f, полученная с помощью подстановок этих функций друг в друга, а формулой называется выражение, описывающее эту суперпозицию.
Для записи формулы функции алгебры логики необходимо либо перечислить все ситуации, в которых она истинна, либо исключить все ситуации, в которых она ложна.
Например, пусть функция f задана таблицей истинности:
x1 | x2 | x3 | f |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Перечислим все наборы, на которых функция истинна. В результате получим Совершенную дизъюнктивную нормальную форму (СДНФ):

Исключение всех наборов, на которых функция ложна, даст Совершенную конъюнктивную нормальную форму (СКНФ):

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