12.3. Булевы функции одной и двух переменных

Для представления функций используются таблицы истинности.

Областью определения БФ от n переменных служит множество слов длины n. Они представляют собой все возможные наборы из n двоичных цифр и их общее количество  = . При n = 3 число возможных наборов = 256, а при n = 5 число наборов > 4 миллиардов. В табл.12.4 представлена БФ одной переменной:

Таблица 12.4

Y	x 0 1	Обозначение	Название
y0	0 0	0	const 0
y1	0 1	x	переменная x
y2	1 0		инверсия x
y3	1 1	1	const 1

Функции y₀ = 0 и y₃ = 1 — функции константы (тождественный нуль и тождественная единица).

Приведем таблицу булевых функций для двух переменных (табл. 12.5).

Таблица 12.5

Y	x1 0011 x2 0101	СДНФ СКНФ	Обозна-чение	Название
y0	0000	(x1  x2)(x1  )(  x2)(  )	0	const 0
y1	0001	x1 x2 (x1  x2)(x1  )(  x2)	x1 x2	конъюнкция
y2	0010	x1  (x1  x2)(x1  )(  )	x1  x2	Отрицание импликации
y3	0011	x1   x1 x2 (x1  x2)(x1  )	x1	переменная x1
y4	0100	x2 (x1  x2)(  x2)(  )	x2  x1	Отрицание обратной импликации
y5	0101	x2  x1 x2 (x1  x2)(  x2)	x2	переменная x2
y6	0110	x2  x1  (x1  x2)(  )	x1  x2	неравнознач-ность
y7	0111	x2  x1   x1 x2 (x1  x2)	x1  x2	дизъюнкция
y8	1000	(x1  )(  x2)(  )	x1  x2	Стрелка Пирса
y9	1001	 x1 x2 (x1  )(  x2)	x1 ~ x2	Эквивалент-ность
y10	1010	 x1  (x1  )(  )		Инверсия x2
y11	1011	 x1   x1 x2 (x1  )	x2  x1	Обратная импликация
y12	1100	  x2 (  x2)(  )		Инверсия x1
y13	1101	  x2  x1 x2 (  x2)	x1  x2	Импликация
y14	1110	  x2  x1  (  )	x1  x2	Штрих Шеффера
y15	1111	  x2  x1   x1 x2	1	const 1

Как видно, в табл. 12.5 встречаются некоторые неизвестные ранее понятия. Опишем их.

Стрелка Пирса - приводится к виду и называется операцией ИЛИ - НЕ.

Штрих Шеффера - можно привести к виду и называется операцией И - НЕ.

Функции отрицания импликации (прямой и обратной) называются иначе функциями запрета по х₁ и х₂ соответственно и читаются (не х₂, а х₁) и наоборот.

Всякая функция от меньшего числа переменных содержится среди функций большего числа переменных. Между функциями имеются зависимости, на основании которых можно записать соотношения для констант 0 = и 1 = , для функции одной переменной х = и для функций двух переменных: x₁x₂ = , = , x₁  x₂ = .

Любая функция двух переменных (включая константы) выражается в аналитической форме через совокупность шести функций, содержащей отрицание и любую из каждой пары функций:

{y₀, y₁₅}, {y₁, y₁₄}, {y₂, y₁₃}, {y₆, y₉}, {y₇, y₈}.

Например, такой совокупностью могут быть функции: константа 0, отрицание , конъюнкция х₁  х₂, дизъюнкция x₁  x₂, эквивалентность x₁ ~ x₂, импликация x₁  x₂.

Выбранная совокупность шести функций является избыточной. Покажем, что эквивалентность и импликация выражаются через остальные функции этой совокупности:

x₁  x₂ =  x₂, x₁ ~ x₂ = (  x₂)(x₁  ).

Для этого построим таблицу 12.6 и сравним ее с основной таблицей.

Таблица 12.6

x1	0	0	1	1
x2	0	1	0	1
	1	1	0	0
	1	0	1	0
 x2	1	1	0	1	x1  x2
x1 	1	0	1	1
(  x2)(x1  )	1	0	0	1	x1 ~ x2

Итак, комплект элементарных функций сокращается до четырех:

• константа 0,

• конъюнкция х₁  х₂,

• отрицание ,

• дизъюнкция x₁  x₂.

Его можно сократить за счет законов де Моргана: x₁  x₂ = , x₁  x₂ = .

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

= х  х = х | х, x₁  x₂ = (x₁  x₂) | (x₁  x₂), x₁  x₂ = (x₁  x₂)( x₁  x₂).

С помощью суперпозиции функций, т.е. подстановок в логические формулы вместо переменных, некоторых БФ получают более сложные функции от любого числа переменных.

Например, подставляя в формулу a*b выражение: a = x₁  x₂, b = x₂  c, c = получим (x₁  x₂) (x₂  ).

Таблица 12.7 для сложения формул записывается на основании общей таблицы для элементарных функций.

Например:

Таблица 12.7

x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
x1  x2	0	0	1	1	1	1	1	1
	1	0	1	0	1	0	1	0
x2 	1	1	1	0	1	1	1	0
(x1  x2)(x2  )	0	0	1	0	1	1	1	0

Область определения БФ от n переменных y = f(x₁, ..., x_n) рассматривают как совокупность n-мерных векторов, компонентами которого являются буквы 0 и 1.

При n = 3 каждый вектор представляется вершиной единичного куба в трехмерном пространстве.

В общем случае совокупность векторов (x₁, ..., x_n) отображается на множество вершин n-мерного куба.

БФ отображается на n-мерном кубе путем выделения вершин, соответствующих векторам (x₁, ..., x_n), на которых БФ принимает значение 1.