Тема: «Переключательные (булевы) функции»

Цель занятия:

усвоение таких понятий, как булевы функции, формулы логики булевых функций, булева алгебра, замкнутые классы.

Пояснение к работе

Время выполнения практического задания – 4 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Как реализуется табличное представление булевой функции?

Что является важнейшей интерпретацией теории булевых функций?

Какие существуют элементарные булевы функции двух переменных?

Как задается функция вектором ее значений?

Какие булевы функции называются равными?

Какая система булевых функций называется полной?

2. Дать определение следующих понятий:

– булева функция;

– фиктивная и существенная переменная;

– булева алгебра (алгебра логики).

3. Записать булеву функцию в виде произвольного отображения.

4. Выполнить задания для аудиторных занятий.

5. Выполнить задания для самостоятельной работы.

10.1. Основные определения

Булевой функцией f (x ₁, x ₂,..., x_n) называется произвольная функция n переменных, аргументы которой x ₁, x ₂,..., x_n  и сама функция f принимают значения 0 или 1, т. е. x_i {0, 1}, i = 1, 2,..., n; f (x ₁, x ₂,  ..., x_n) {0, 1}. Булева функция от n переменных – это произвольное отображение вида f: {0, 1}ⁿ  → {0, 1}.

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

Любая булева функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных (2 ⁿ), а в правой части – значения функции. Для формирования столбца значений переменных удобен лексикографический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления.

Функций одной переменной четыре. Из них выделим функцию “отрицание x ” (обозначается Ø x). Булевых функций двух переменных – 16. Те из них, которые имеют специальные названия (элементарные функции), представлены в табл. 2.

                                                                                        Таблица 2

x 1  x 2	x 1 V x 2	x 1 & x 2 ; x 1 Ù x 2	x 1 x 2 ; x 1→ x 2	x 1 ~ x 2	x 1 Å x 2	x 1 ¯ x 2	x 1 ï x 2
0 0 0 1 1 0 1 1	0 1 1 1	0 0 0 1	1 1 0 1	1 0 0 1	0 1 1 0	1 0 0 0	1 1 1 0
Названия	дизъ- юнкция	конъюнк-ция	имплика-ция	эквива-лентность	сложение по модулю 2	стрелка Пирса	штрих Шеффера

Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции.