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

Обозначим через 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) может определяться следующей таблицей истинности.

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