Основные логические функции

Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как “ложь” (л = {0}) и как “истина” (и = {1}).

Декартово произведение E Е Е … E = En является множеством упорядоченных наборов, состоящих из п чисел (нулей и единиц). Как известно, Еп cодержит 2п элементов (упорядоченных наборов). Само множество Епможно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k, записанного с помощью п знаков. Упорядочение наборов проводится по числу k .

Например, при п = 3 множество Е3 может быть упорядочено следующим образом.

Такое упорядочение еще называют “скользящей единицей”.

Этот естественный порядок элементов Еп является самым распространенным, но иногда удобен другой способ упорядочения.

Логической (булевой) функцией(или просто функцией)nпеременных

y = f(x1, x2, …, xn)

называется такая функция, у которой все переменные и сама функция могут принимать только два значения:0и1.

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.

Пример.

Высказывание “Москва находится в Европе” является истинным и, значит, с точки зрения дискретной математики принимает значение 1.

Высказывание “в сутках 27 часов” является ложным, и переменная, которая заменяет это высказывание, принимает значение 0.

Имеется много высказываний, которые либо истинны, либо ложны, но о которых мы не знаем, что имеет место на самом деле. Например, высказывание “студент Петров (имеется в виду конкретный человек) имеет дома компьютер”. Такого рода высказывания требуют проверки (конечно, если нам важен этот факт). Поэтому считаем, что переменная, заменяющая это высказывание может принимать значение 0 или 1.

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

Пример.

Функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.

x
y
z
f(x,y,z)

Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.

Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

При таком задании наборы Еп всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию f(x,y,z) можно задать так: f = (10110100), это означает, что последний столбец таблицы истинности

Заметим, что все функции п переменных также можно перенумеровать по принципу “скользящей единицы”. Теоретически число таких функций –, но некоторые из них являются по существу функциями меньшего числа переменных, а две – вообще константами. Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.

Теперь можно описать основные функции дискретной математики.