Мегаобучалка Главная | О нас | Обратная связь


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



2015-11-27 719 Обсуждений (0)
Замкнутые классы функций 0.00 из 5.00 0 оценок




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

Всякая система функций алгебры логики порождает замкнутый класс - класс, состоящий из функций, которые можно получить суперпозициями из М.Такой класс называется замыканием Ми обозначается [М].Очевидно, что если М - замкнутый класс, то [М]=М.ЕслиМ - полная система функций, то [М]= , где -множество всех функций алгебры логики.


Монотонные функции. Теорема о монотонных функциях.

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

Теорема о монотонных функциях.

Всякая булева функция в сигнатуре алгебры логики, не содержащая отрицаний, является монотонной функцией.

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

Доказательство первой части теоремы основано на рассмотрении ДНФ, равносильной исходной функции без отрицаний. Для произвольного двоичного набора, на котором значение ДНФ равно 1, найдется элементарная конъюнкция, которая на этом наборе равна 1. Так как в этой конъюнкции нет отрицаний, то это означает, что все компоненты набора равны 1. Тогда на любом другом большем или равном наборе значение элементарной конъюнкции тоже будет равно 1, а тем самым выполняются условия монотонности.

Доказательство второй части теоремы основано на рассмотрении СДНФ, равносильной исходной монотонной функции, и предположении, что в ней существует полная правильная элементарная конъюнкция, содержащая хотя бы одну переменную с отрицанием. Тогда исходя из монотонности функции, а тем самым и СДНФ, найдется другая элементарная полная правильная коньюнкция, которая отличается от найденной лишь тем, что переменная, входящая в первую конъюнкцию с отрицанием, входит во вторую без отрицания. Таким образом от исходной СДНФ можно перейти к ДНФ, в которой мы избавились от одной переменной, входящей в СДНФ с отрицанием. Так для всех переменных с отрицаниями.

Следствие из теоремы.

Класс монотонных функций является замыканием системы функций М={&,V,0,1}.


Двойственность в алгебре логики. Самодвойственные функции.

 

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

Функция называется двойственнойфункцией к функции .

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

Самодвойственными являются функции x, .

Функции сохраняющие константы 0, 1.

 

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

Функция ,для которой выполняется ,называется функцией, сохраняющей константу 0.

Функция ,для которой выполняется ,называется функцией, сохраняющей константу 1.

 



2015-11-27 719 Обсуждений (0)
Замкнутые классы функций 0.00 из 5.00 0 оценок









Обсуждение в статье: Замкнутые классы функций

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (719)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)