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

Совершенные ДНФ и КНФ.

Читайте также:
  1. Perfect Tenses (Совершенные времена)
  2. Несовершенные объяснения
  3. Совершенные и несовершенные котлованы
  4. Экологически совершенные горелочные устройства камер сгорания
  Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ). Пусть (x1,...,хn) — набор логических переменных, = - набор нулей и единиц. Конституентой единицы набора называется конъюнкт . Конституентой нуля набора называется дизъюнкт Отметим, что тогда и только тогда, когда .   Пример4.1 - Формула есть конституента единицы К1 (1,0,1), формула есть конституента нуля К0(0,0,1).   Совершенной ДНФ называется дизъюнкция всех конституент единицы, а совершенной КНФ называется конъюнкция всех конституент нуля, среди которых нет одинаковых. Таким образом; СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная xi из набора { xi,..., хn } входит ровно один раз, причем входит либо сама xi,либо ее отрицание .   Пример4.2 формула - СДНФ, формула - СКНФ, а формула не является СДНФ.   Для решения задачи нахождения СДНФ и СКНФ, эквива­лентных исходной формуле , предварительно рассмотрим разложения булевой функции f{x1,x2,...,хn) по m переменным (для определенности по х1, х2,..., хm) - разложения Шеннона.   ТЕОРЕМА(О разложении булевой функции по переменным)   Где дизъюнкция берется по всем возможным наборам ()   Доказательство. ЗАМЕЧАНИЕ.Здесь доказывается, что некоторая формула реализует заданную функцию. Для этого до­статочно взять произвольный набор значений аргументов функции, вычислить на этом наборе значение формулы, и если оно окажется равным значению функции на этом на­боре аргументов, то из этого следует доказываемое утверждение.   СЛЕДСТВИЕ 1. СЛЕДСТВИЕ 2.   Предельное представление (т.е. когда n=m) булевой функции f(x1,x2,…, xn) в виде     называется совершенной дизъюнктивной нормальной формой (СДНФ). ЗАМЕЧАНИЕ.СДНФ называется совершенной, потому что каждое слагаемое в дизъюнкции включает все переменные; дизъюнктивной, потому что главная операция — дизъюнкция, а почему она называется нормальной, объяснено в следующем отступлении.   ТЕОРЕМА. Всякая булева функция (кроме 0) имеет единственную СДНФ. Доказательство. ТЕОРЕМА. Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание:     доказательство   ТЕОРЕМА. Всякая булева функция (кроме 1) может быть единственным образом выражена в виде совершенной конъюнктивной нормальной формы (СКНФ): Доказательство. По принципу двойственности из предыдущей теоремы. Пример 4.2. Построим совершенные ДНФ и КНФ булевой функции f(x1, х2, х3), заданной таблицей истинности (табл. 4.1).   Таблица 4.1
x1 х2 х3 f(x1, х2, х3)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Совершенные ДНФ и КНФ этой функции имеют соответственно вид

f(x1, х2, х3) =

f(x1, х2, х3) =

 

 

 

Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий ал­горитм.

 


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


Читайте в этой же книге: Представление функций формулами. Равносильные формулы. | Принцип двойственности | Минимизция булевых функций в классе ДНФ | Задача минимизция булевых функций в классе ДНФ заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшую сложность L(f). | Замыкание множества булевых функций. | Многочлены Жегалкина |
<== предыдущая страница | следующая страница ==>
Дизъюнктивные и конъюнктивные нормальные формы.| Алгоритм нахождения СДНФ функции, заданной таблицей истинности.

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