Аналитическое построение сднф и скнф

Под аналитическим построением будем понимать получение формулы вида СДНФ или СКНФ с помощью эквивалентных преобразований заданной формулы.

Пусть функция представлена формулой со связками {, &, }. Тогда для преобразования формулы в совершенную дизъюнктивную нормальную форму необходимо вначале представить формулу в виде – логической суммы логических произведений. Этого можно добиться с помощью законов дистрибутивности или других тождеств. Затем добавить к каждой элементарной конъюнкции (каждому логическому произведению переменных) единичные множители, составленные по закону исключенного третьего из символов тех переменных, которых недостает в данной конъюнкции до полного набора переменных, и далее выполнить преобразования, раскрывая скобки и приводя «подобные члены» по закону идемпотентности.

Например, f(x,y,z)=. Первое слагаемое в формуле преобразуем по закону Де Моргана, во втором слагаемом раскроем скобки с помощью закона дистрибутивности и поменяем местами сомножители, используя закон коммутативности. Тогда f(x,y,z)= – это выражение имеет требуемую форму: логическая сумма логических произведений переменных или их отрицаний, такая форма называется также дизъюнктивной нормальной формой (ДНФ). Теперь к каждой элементарной конъюнкции в ДНФ добавим единичный множитель: к первой –, ко второй – и к третьей . Получим:

f(x,y,z)==

=. Теперь приведем «подобные члены»: . Полученное выражение и есть СДНФ данной функции.

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

Например, . Приведем к виду КНФ:

f(x,y,z)=. В этом выражении 4 элементарных дизъюнкции, причем в первой из них не хватает до полного набора переменных y и z, во второй – переменной z, в третьей – х и в четвертой – у. Добавим их в виде нулевых слагаемых, пользуясь законом противоречия. Тогда f(x,y,z)==

=

. Теперь воспользуемся законами идемпотентности и коммутативности и получим СКНФ(f(x,y,z))=

=

12. Yandex.RTB R-A-252273-3
    Содержание

    • Часть II
    • Алгебра двузначной логики
    • Функции алгебры логики
    • Способы задания функций алгебры логики
    • Эквивалентность функций
    • Реализация функций формулами
    • Эквивалентность формул и тождества
    • Упрощение формул
    • Двойственные функции и принцип двойственности
    • Применение принципа двойственности
    • Аналитическая запись функций алгебры логики
    • Аналитическое построение сднф и скнф
    • Теорема о тройке связок
    • Полные системы функций и полиномы Жегалкина
    • Замыкание систем функций алгебры логики
    • Важнейшие замкнутые классы
    • Теорема Поста о полноте
    • Минимизация булевых функций
    • Основные понятия
    • Метод неопределенных коэффициентов
    • Тупиковые днф и алгоритм наискорейшего спуска
    • Геометрическое представление функций алгебры логики
    • Аналитическое построение сокращенной днф
    • Локальные алгоритмы
    • Алгоритм Куайна
    • Диаграммы Вейча–Карно
    • Построение днф по карте Карно
    • Задачи и упражнения
    • Список литературы
    • Часть II
    • 400131, Волгоград, просп. Им. В.И.Ленина, 28
    • 400131, Волгоград, ул. Советская, 35

    Yandex.RTB R-A-252273-4