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

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

Само множество Е^п можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k (0≤ k ≤ 2 ⁿ –1), записанного с помощью n знаков. Упорядочение наборов проводится по числу k., например, при n = 3 множество Е ³ может быть упорядочено следующим образом (табл. 1).

1. Таблица 1 – Упорядочение «скользящая единица»

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

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

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

2. Таблица 2 – Таблица истинности функции f(x,y,z)

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

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

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

Заметим, что все функции n переменных также можно перенумеровать по принципу «скользящей единицы». Число таких функций – 2^{2 n} .

Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.

Теперь можно описать основные функции дискретной математики. Перенумеруем четыре функции одной переменной y=f(x) естественным образом и расположим в виде таблицы 3:

3. Таблица 3 – Функции одной переменной

Видно, что f₀ (х) = 0, a f₃ (х) =1, т. е. эти две функции не зависят от х, f₁ (х)= х, т. е. она не меняет аргумента. Функция f ₂(х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f ₂ (х)= x и называется отрицанием.

Число функций двух переменных f(x,y) функций равно 2⁴=16. Перенумеруем и расположим их тоже в естественном порядке (табл. 0).

4. Таблица 4 – Функции двух переменных

переменные                 x             y функции	0 0	0 1	1 0	1 1	Алгебраическое выражение	Наименование функции
f 0	0	0	0	0		Постоянный 0
f 1	0	0	0	1		Конъюнкция (функция И)
f 2	0	0	1	0		Запрет
f 3	0	0	1	1		Тождественность x
f 4	0	1	0	0		Запрет
f 5	0	1	0	1		Тождественность y
f 6	0	1	1	0		Сложение по модулю 2 (исключающее ИЛИ)
f 7	0	1	1	1		Дизъюнкция (функция ИЛИ)
f 8	1	0	0	0		Стрелка Пирса Операция Вебба  (НЕ-ИЛИ)
f 9	1	0	0	1		Эквивалентность (подобие) Равнозначность
f 10	1	0	1	0		Отрицание y
f 11	1	0	1	1		Импликация от y к x
f 12	1	1	0	0		Отрицание x
f 13	1	1	0	1		Импликация от x к y
f 14	1	1	1	0		Штрих Шеффера (НЕ-И)
f1 15	1	1	1	1		Постоянная 1

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

В алгебраических выражениях конъюнкция обозначается знаком ∧, & или , дизъюнкция – знаком ∨ или +, а отрицание – чертой над обозначением переменной или знаком -.