Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

 

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

 

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

Пусть дан класс функций 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)

 


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал