20. Задача о минимизации днф, тупиковые днф, их связь с минималь­ными днф, методы поиска тупиковых днф.

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

D – множество всех ДНФ . D(f) – множество ДНФ предств. f. D=

L : D R – мера сложности

Опр. Б.Ф. f

f , Ф – ДНФ f,

Тупиковая форма с минимально возможной мерой сложности L – минимальная ДНФ f относительно меры сложности f.

Алгоритм Квайна — Мак-Клоски. Операция склейки: Пусть и — две элементарные конъюнкции, входящие в исходную СДНФ, причем , , где K — некоторая элементарная конъюнкция. Тогда . Процесс склейки можно выполнить, используя карты Карно. Получаем сокращённую ДНФ. Определение ядра. Простую импликанту называют ядровой, если она покрывает некоторую импликанту исходной СДНФ, не покрываемую никакими другими импликантами, т.е. на карте Карно, если мы её удалим, возникнет непокрытая единица. ТДНФ — ДНФ без избыточных импликант, т.е. таких импликант, удаление которых не приводит к потери эквивалентности исходной СДНФ. Поиск ТДНФ. Составляем вспомогательную функцию, функцию Патрика, в виде КНФ, где каждая элементарная дизъюнкция состоит из поименованных импликант сокращённой ДНФ и соответствует определённой 1 функции. Раскрыв скобки и используя тождества поглощения, упрощаем запись. Получившаяся ДНФ рассматривается так: каждая импликанта соответствует тупиковой ДНФ, где каждое имя заменяется на соответствующую конъюнкцию, а операция конъюнкции между ними заменяется операцией дизъюнкции.

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

Пусть F — некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F.

Множество F булевых функций называется функционально замкнутым классом, если [F]=F.

— класс всех функций, сохраняющих константу 0, т.е.

— класс всех функций, сохраняющих константу 1, т.е.

S — класс всех самодвойственных функций, т.е. . Например, x и .

Лемма о несамодвойственной функции: если , то, подставляя на места её переменных x и , можно получить константу.

⊲Т.к. , то найдётся набор такой, что

Положим , и . Т.е. имеем: . Следовательно, — константа⊳

22. Замкнутые классы: класс монотонных функций, класс линейных функ­ций. Проверка замкнутости, лемма о немонотонной функции, лемма о нелинейной функции.

Пусть F — некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F.

Множество F булевых функций называется функционально замкнутым классом, если [F]=F.

Функция называется монотонной, если для любых двух наборов и , при . Примеры: f = 0; f = 1; f = х; .

К классу линейных функций L относят функции, реализуемые полиномом Жегалкина не выше первой степени: . ⊲очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция.⊳

Лемма о немонотонной функции: из любой немонотонной функции путем подстановки в неё констант и х можно получить отрицание.

⊲ ⊳