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

Тема 9.3. Замкнутые классы. Монотонные функции

Тема 7.1. Понятие высказывания, простые и составные высказывания | Тема 7.2. Операции на множестве высказываний | Штрих Шеффера | Тема 8.1. Формулы Булевой алгебры | Тема 8.2. Законы и тождества Булевой алгебры | Тема 8.3. Составление формулы по заданной таблице истинности | Тема 8.4. Двойственность | Тема 8.5. Булева алгебра и теория множеств | Тема 8.6. ДНФ, интервалы и покрытия | Тема 9.1. Функционально полные системы |


Читайте также:
  1. AЧX и ФЧХ передаточной функции цепи.
  2. II. Функции школьной формы
  3. Self и его функции.
  4. В то же время, старение тела - это прогрессирую­щий ожог химическими веществами, который приводит к повреждению желез и нарушению их функций, вплоть до их полой дисфункции.
  5. Верховный тайный совет, его функции и деятельность
  6. Виды аптечных учреждений. Задачи и функции аптечных организаций.
  7. Виды и функции переговоров

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

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

Пример 9.4:

а) Множество всех дизъюнкций, то есть функций вида является замкнутым классом.

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

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

Введём отношение частичного порядка на множестве векторов одинаковой длины. Напомним, что для векторов и выполняется , если для любого выполняется . Воспользуемся этим отношением для двоичных векторов.

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

Пример 9.5:

а) Функция монотонна.

б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.

в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.

         
         
         
         
         
         
         
         

Функция , очевидно, не является монотонной, так как, например , а . Монотонность функции легко установить непосредственной проверкой.

Проверка монотонности функции непосредственно по определению требует анализа таблицы функции и может оказаться достаточно трудоёмкой. Поэтому весьма полезной для установления монотонности является следующая теорема.

Теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.

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

Теорема. Множество всех монотонных функций является замкнутым классом.

Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие.

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


Дата добавления: 2015-10-28; просмотров: 63 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Тема 9.2. Алгебра Жегалкина и линейные функции| Тема 9.4. Теоремы о функциональной полноте

mybiblioteka.su - 2015-2024 год. (0.007 сек.)