Назад (Информатика).

Основные понятия алгебры логики

Алгебра логики - это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Логическое высказывание - это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Считается, что если выражение ложно, то оно имеет значение 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.

x1x2...xnf(x1, x2, ... ,xn)
00...0f(0, 0, ... ,0)
00...1f(0, 0, ... ,1)
...............
11...0f(1, 1, ... ,0)
11...1f(1, 1, ... ,1)

В таблице наборы располагают в определенном порядке - лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. При любом фиксированном упорядочении наборов логическая функция полностью определяется столбцом своих значений, длина которого равна 2n. Поэтому число различных функций от n переменных равно числу различных двоичных наборов длины 2n, т.е. 22n.

Логическая формула

Суперпозицией функций f1,...,fm называется функция f, полученная с помощью подстановок этих функций друг в друга, а формулой называется выражение, описывающее эту суперпозицию.

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

Например, пусть функция f задана таблицей истинности:

x1x2x3f
0000
0010
0101
0111
1000
1010
1101
1111

Перечислим все наборы, на которых функция истинна. В результате получим Совершенную дизъюнктивную нормальную форму (СДНФ):

cовершенная дизъюнктивная нормальная форма (СДНФ)

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

cовершенная конъюнктивная нормальная форма (СДНФ)

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