Контрольная работа: Математическая логика

Формулы, содержащие знаки называют полиномами.

Полином вида: , где есть либо 1, либо переменная, либо конъюнкция различных переменных, при , называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на

где k_i – коэффициенты, принимающие значения 0 или 1: .

3.2 Класс линейных функций (К _Л )

Булева функция называется линейной , если она представима полиномом первой степени

.

Количество линейных функций равно , где п – число перемен-ных.

Для п = 2 их 8:

3.3 Класс функций, сохраняющих ноль (К ₀ )

Если булева функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль:

3.4 Класс функций, сохраняющих единицу (К ₁ )

Если булева функция на единичном наборе переменных равна единице, то говорят, что функция сохраняет единицу :

3.5 Класс монотонных функций (К _м )

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

3.6 Класс самодвойственных функций (К _с )

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