Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций
Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.
Замкнутые классы функций.
Определение.
Пусть дан класс функций 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; просмотров: 2769;