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

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

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

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

Считается, что если выражение ложно, то оно имеет значение 0, а если выражение истинно, то - 1. Чтобы обращаться к логическим высказываниям, им назначают имена А, В, С или x, y, z.

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

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

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

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Рассмотрим основные логические операции.

Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием. Высказывание истинно, когда A ложно, и ложно, когда A истинно.

Операция, выражаемая связкой "и", называется конъюнкцией [лат. conjunctio - соединение] или логическим умножением и обозначается точкой "" [может также обозначаться знаками или ]. Высказывание АВ истинно тогда и только тогда, когда оба высказывания А и В истинны.

Операция, выражаемая связкой "или" [в неразделительном, не исключающем смысле этого слова], называется дизъюнкцией [лат. disjunctio - разделение] или логическим сложением и обозначается знаком "" [или плюсом]. Высказывание АВ ложно тогда и только тогда, когда оба высказывания А и В ложны.

Операция, выражаемая связками "если ..., то", "из ... следует", "... влечет ...", называется импликацией [лат. implico - тесно связаны] и обозначается знаком "". Высказывание АВ ложно тогда и только тогда, когда А истинно, а В - ложно. Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

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

Логическая функция

Функцией алгебры логики f(x₁, x₂, ... ,x_n) от n - переменных x₁, x₂, ... ,x_n, принимающих значения 0 или 1, называется функция, принимающая значения 0 или 1.

Функция задается с помощью таблицы истинности. В каждой строке таблицы вначале дается набор значений переменных x₁, x₂, ... ,x_n, а затем значение функции на этом наборе. Число различных двоичных наборов ограничено и равно 2ⁿ.

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)

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

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

Суперпозицией функций 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

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

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

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