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

Упражнение 1.2.1 а) Найти число всех функций алгебры логики от n переменных.

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

Так как при стандартном расположении наборов таблица 1 для функции полностью определяется последним столбцом (столбцом значений для f), то эту функцию можно задать набором длины :

(2)

где - значение функции f на наборе , - номер, которой равен i. задание булевой функции в виде (2) будем называть векторным.

Пример 1.2.2 Векторное задание функции из примера 1.2.1 будет таким:

.

1.3 Существенные и несущественные переменные. Отношение равенства.

Функция называется существенно зависящей от переменной , если существует хотя бы один набор значений для переменных соответственно, что

.

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

Дадим описание процедур, посредством которых:

а) в функцию f, не зависящую от , можно переменную ввести фиктивно (процедура введения фиктивной переменной);

б) из функции f, зависящей от фиктивно можно удалить переменную (процедура удаления фиктивной переменной).

а) Пусть функция f зависит от переменных , и (или ; или ). Чтобы ввести в функцию f переменную фиктивно в табличное задание для функции f вставляем столбец для переменной между столбцами значений для переменных и (или перед столбцом для переменной ; или после столбца для переменной ). Далее удваиваем эту расширенную ( за счет добавления столбца для ) таблицу и в столбце для переменной записываем (сверху вниз) сначала нулей, а затем единиц. После этого переставляем строки получившейся таблицы в соответствии со стандартным расположением наборов .

Пример 1.3.1 Пусть функция f, зависящая от двух переменных и задана таблицей (таблица 3). Введем в эту функцию переменную фиктивно. От таблицы 3 переходим к расширенной таблице (таблица 4), вставляя между столбцами значений для переменных и столбец для переменной .

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

Таблица 3

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

Таблица 4

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

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

Таблица 5

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

Таблица 6

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

Пример1.3.2 Пусть функция f, зависящая от четырех переменных , задана таблицей (таблица 7). Из таблицы 7 непосредственно видно, что на парах наборов вида и функция f принимает одинаковые значения, т. е. функция f от переменной фиктивно.

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

Таблица 7