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

Обозначим через E = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как “ложь” (л ={0}) и как “истина” (и ={1}). Декартово произведение E* Е* Е* …* E = Eⁿ является множеством упорядоченных наборов, состоящих из п чисел (нулей и единиц). Как известно, Е^п cодержит 2 ^п элементов (упорядоченных наборов). Само множество Е^п можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k (0£ k £2 ⁿ– 1), записанного с помощью п знаков. Упорядочение наборов проводится по числу k.

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

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

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

Логической (булевой) функцией (или просто функцией) n переменных y = f(x ₁, x ₂, …, x_n) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

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

Из определения логической функции следует, что функция п переменных – это отображение Е^п в Е,которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.