Элементарные булевы функции от двух переменных

Глава III. Алгебра логики.

(Лекция 7)

Функции алгебры логики

E2 = {0, 1} Элементарные булевы функции от двух переменных - student2.ru

Определение. Функцией алгебры логики называется отображение f: Элементарные булевы функции от двух переменных - student2.ru ® E2, где xi Î E2, i = 1, 2, …, n. Функции алгебры множеств называются булевыми функциями. Обозначим все множество булевых функций через P2(n).

Теорема (О количестве булевых функций от n переменных):

Мощность множества булевых функций |P2(n)| = Элементарные булевы функции от двух переменных - student2.ru .

Доказательство: (Следует из Теоремы о мощности всех подмножеств данного множества)

Пример: |P2(4)| = Элементарные булевы функции от двух переменных - student2.ru = 216 = 65536

Существенные и фиктивные переменные

Определение. Функция f(x1, x2, … xi-1, xi, xi+1, … xn) существенно зависит от переменной xi, если существует набор a1, …, an переменных x1, …, xn, что выполняется неравенство:

f(x1, x2, … xi-1, 0, xi+1, … xn) ¹ f(x1, x2, … xi-1, 1, xi+1, … xn).

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

Определение. Переменную xi называют фиктивной, если для любого набора значений a1, …, an переменных x1, …, xn выполняется равенство: f(x1, x2, … xi-1, 0, xi+1, … xn) = f(x1, x2, … xi-1, 1, xi+1, … xn).

Примеры:

1) f(x1, … xn) º 0 Þ "xi – фиктивная, i = 1, 2, …, n.

2)

x y f(x, y)

f(0, 0) ¹ f(0,1) Þ Переменная x – существенная

f(0, 0) = f(1,0) ü

f(0, 1) = f(1,1) þÞ Переменная y – фиктивная

Исключение и введение фиктивных переменных

Пусть для функции f(x1, … xn) переменная xi – фиктивная. Ее можно исключить и перейти к булевой функции g(x1, x2, … xi-1, xi+1, … xn) с n – 1 переменной. Для этого в таблице для функций вычеркнем все строки, соответствующие значениям xi = 1 и столбец для аргумента xi. Полученная таблица будет определять функцию g(x1, x2, … xi-1, xi+1, … xn). При этом говорят, что функция g получена из функции f исключением фиктивной переменной xi. Кроме того, можно сказать, что f получена из g введением фиктивной переменной xi.

Равенство функций

Определение. Две функции называются равными, если на каждом наборе переменных значения функций совпадают.

Пример:

x y f(x, y)       x g(x)
   
   

g(y) = f(x, y)

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

Замечание:

1) Существует два типа функций, которые не имеют существенных переменных. Это функции-константы: 0 и 1. Поэтому целесообразно считать эти функции зависящими от пустого множества существенных переменных.

2) Если дана конечная система булевых функций {f1, …, fs}Ì P2, то можно считать, что все s функций зависят от одних и тех же переменных.

В Алгебре логики некоторые функции принято считать элементарными.

Элементарные булевы функции от одной переменной

x x Элементарные булевы функции от двух переменных - student2.ru

Элементарные булевы функции от двух переменных - student2.ru - инверсия (отрицание) x

Элементарные булевы функции от двух переменных

x y x & y x Ú y x ~ y x Å y x ® y x / y x ¯ y

x & y – конъюнкция (логическое умножение)

(x & y = 1 Û x = 1 Ù y = 1)

x Ú y – дизъюнкция (логическое сложение)

(x Ú y = 0 Û x = 0 Ù y = 0)

x ~ y – эквивалентность

(x ~ y = 1 Û x = y)

x Å y – сумма по модулю 2 (разделительная дизъюнкция) ( Элементарные булевы функции от двух переменных - student2.ru )

(x Å y = 0 Û x = y)

x ® y – импликация (логическое следование)

x / y – штрих Шеффера (антиконъюнкция) ( Элементарные булевы функции от двух переменных - student2.ru )

x ¯ y – стрелка Пирса (антидизъюнкция, функция Вебба, функция Даггера) ( Элементарные булевы функции от двух переменных - student2.ru )

Наши рекомендации