Методические рекомендации по изучению дисциплины (стр. 4 )

0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Таблица 8

Удаление из таблицы 7 столбца значений для переменной и всех строк, соответствующих наборам , даёт функцию , полученную из функции удалением фиктивной переменной (таблица 8).

Упражнение 1.3.1 Ввести в функцию переменные и фиктивно.

Упражнение 1.3.2 Проверить, что переменная входит в функцию фиктивно. Получить из функцию , удалив переменную .

Пример1.3.3 Найдём существенные и фиктивные переменные функции .

Перейдём от векторного задания функции к табличному (таблица 9).

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Таблица 9

Для переменной в таблице имеется пара наборов и таких, что . Следовательно, существенная переменная. Аналогично, для имеются наборы и , на которых функция f принимает различные значения, т. е. также существенная переменная. Но для каждой пары наборов вида ; имеем: , т. е. фиктивная переменная.

Упражнение 1.3.3 Найти существенные и фиктивные переменные функций:

а) ;

б) .

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

Пример1.3.4 Покажем, что функции:

и равны.

Действительно, легко проверяется, что функция получается из функции удалением фиктивной переменной , а функция получается из введением фиктивной переменной .

Упражнение 1.3.4 Доказать, что функции f и g равны:

а) ;

.

б) ;

.

1.4 Представление функций алгебры логики термами.

Пусть В – некоторое множество (конечное или бесконечное) функций алгебры логики и - множество переменных (множество Х может быть и конечным). Понятие терма над множеством В с переменными из Х определяется индуктивно:

1)  любая переменная из множества Х есть терм;

2)  если f – n местная функция, принадлежащая В, и - термы, то есть терм.

Параллельно определению терма даётся понятие подтерма и сложности терма t:

1)  если , то является единственным подтермом терма t, ;

2)  если , то подтермами терма t являются термы и сам терм t, .

Очевидно, что все подтермы терма t являются термами на В.

Пример1.4.1 Пусть и (здесь верхний индекс указывает местность функции, т. е., к примеру, - двух местная булева функция).

Проверим, что выражение

-

терм над В от множества переменных Х. с этой целью будем последовательно (по шагам) выписывать подтермы этого выражения.

шаг 0 -

подтермы сложности 0;

шаг 1 -

подтермы сложности 1;

шаг 2 -

подтермы сложности 2;

шаг 3 -

подтермы сложности 3;

шаг 4 -

подтермы сложности 4.

Так как данное выражение удалось получить в качестве подтерма (на последнем шаге 4) в соответствии с правилами индуктивного определения, то оно является термом сложности 4.

Упражнение 1.4.1 Проверить, что данные выражения являются термами над множеством

от переменных множества и найти их сложность.

а) ;

б) .

Пусть t терм над В от переменных Х и - переменные этого терма. Определим значение терма t на наборе (т. е. при , ) индукцией по сложности :

1) если , то (для некоторого ), то значение

терма t равно ;

2) если , то , где f – m- местная функция, принадлежащая множеству В, а - термы над В, переменные которых принадлежат множеству и .

Так как сложности термов не превосходят k, то их значения на наборе уже определены. Пусть эти значения равны соответственно. Тогда значением терма t будет .

Если переменные терма t, то будем писать и значение этого терма на наборе будем обозначать через .

Будем говорить, что n – местная функция f представима термом , если для любого набора .

Если функция f представима термом t, то говорят также, что терм t реализует функцию f.

1.5 Элементарные функции. Формулы алгебры логики.

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

а) Одноместные (унарные) функции:

0	0	1	0	1
1	0	1	1	0

Таблица 10

- «константа 0» (функция тождественно равная 0);

- «константа 1» (функция тождественно равная 1);

- «тождественная функция»;

- «отрицание х» (не х).

б) Двуместные (бинарные) функции:

0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	1
1	0	0	1	0	0	1	1
1	1	1	1	1	1	0	0

Таблица 11