Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций

Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.

 

Замкнутые классы функций.

 

Определение.

Пусть дан класс функций B (т.е. конечное или бесконечное множество функций),объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B.

Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

 

B = [B]

 

Теорема 1

Класс всех линейных функций замкнут.

Доказательство.

Пусть L – класс линейных функций (так и будем обозначать в дальнейшем).

L = {a0+a1x1+a2x2+…+anxn}

Подставим вместо переменной x в одну из функций функцию y такого же вида.

Получим

L = [L].

 

Утверждение (теорема 2)

Необходимое условие линейности.

Если функция линейна и не равна некоторой постоянной, то на половине своих наборов она равна 1.

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

 

Функция называется самодвойственной, если двойственная к ней функция является самой этой функцией. F* = F.

 

S – класс всех самодвойственных функций.

Класс S является функционально замкнутым.

Доказательство следует из принципа двойственности.

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

 

Функция называется монотонной, если из условия a £ b следует, что f(a) £ f(b).

Теорема.

Класс M монотонных функций замкнут.

Свойство.

У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то есть все простые импликанты не содержат отрицаний.

 

Другие замкнутые классы

T0 – константа 0 (класс функций, обращающихся на нулевом векторе в 0).

Т1 – константа 1 (класс функций, обращающихся на единичном векторе в 1)

 

Теорема

Классы Т0 и Т1 функционально замкнуты.

 

Лемма о несамодвойственной функции.

Если функция несамодвойственна, то путем подстановки вместо аргументов переменной x или not(x) можно получить константу.

 

011 – нарушена самодвойственность

 

f(not(x),x,x) = const = 1 при любом x.

001 – нарушена самодвойственность

Если 0, то х с отрицанием, если 1, то без отрицания.

 

Доказательство _ _ _ _ _ _ _ _

F Ï S Þ $a : F*(a) ¹ F(a) Þ F*(a) = F(a)Þ F(a) = F(a) Þ F(a) = F(a)

 

f(x) = {x1a, x2a2, … xnan}

f(0) = {0a, 0a2, … 0an}

 

Путем подстановки получаем, что f(x) = const.

 

Лемма о немонотонной функции

Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).

 

000 £ 001

F(000) = 1 F(001) = 0

F(00X) = NOT(X)

F(100) = 1

F(110) = 0

100 < 110

F(1,x,0) = NOT(X)

 








Дата добавления: 2016-03-27; просмотров: 2755;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.008 сек.