Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма



Скачать 42.55 Kb.
Дата11.07.2014
Размер42.55 Kb.
ТипДокументы
СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ, СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

Мы знаем 2 способа задания логических функций: формулой и таблицей истинности. По формуле легко составляется таблица. На практике при конструировании различных электронных устройств часто возникает обратная задача - от таблицы истинности перейти к формуле.

Предварительно введём следующие определения.


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

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






Всякую дизъюнкцию элементарных конъюнкций
Назовём дизъюнктивной нормальной формой, то есть ДНФ.
Всякую конъюнкцию элементарных дизъюнкций
Назовём конъюнктивной нормальной формой, то есть КНФ.




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


НАПРИМЕР, для переменных X, Y, Z

Название

Соответствует определению

Не соответствует определению

Элементарная дизъюнкция

X V X
X V Z
X V Y V Z

X V Y  X

Элементарная конъюнкция

X  X
X  Z
X  Y  X

X V Y  X

ДНФ

XX V XYZ
XY V Y V XZ

XY
Но ДНФ можно построить для всякой формулы путем ее преобразования

КНФ

(X V Y V X)  (X V Z)
X  (X V Y)  (Y V Z)

XY
Но КНФ можно построить для всякой формулы путем ее преобразования

СДНФ

XYZ V XYZ

XY V Y V XZ

СКНФ

(X V Y V Z)  (X V Y V Z)

(X V Y V X)  (X V Z)

Имеются 2 алгоритма получения формулы по таблице истинности. Формулы можно получить, выполнив четыре пункта алгоритма.

Алгоритмы получения формулы по таблице истинности

СДНФ

|

СКНФ

1. Конструирование логических схем начинается с таблицы истинности

(1)


X

Y

f(X,Y)

0

0

0

0

1

1

1

0

1

1

1

0

2. Отметим те строки таблицы, выходы которых равны

1

X

Y

f(X,Y)

0

0

0

0

1

1*

1

0

1*

1

1

0




|
|
|
|
|
|
|
|
|
|

0

X

Y

f(X,Y)

0

0

0*

0

1

1

1

0

1

1

1

0*




3.Выписываем для каждой отмеченной строки комбинацию переменных через знак

конъюнкцию ()

|

дизъюнкцию (V)

знаки операции отрицания расставим следующим образом:

если переменная = 1, то запишем саму эту переменную, если же она = 0, то запишем ее отрицание.

(X  Y) для 2-й строки


(X  Y) для 3-й строки

|
|
|
|
|
|
|

если переменная = 0, то запишем саму эту переменную,если же она = 1, то запишем ее отрицание.

(X V Y) для 1-й строки


(X V Y) для 4-й строки

4. Все полученные выражения связываем операцией

дизъюнкция

(X  Y) V (X  Y)



|
|
|
|

конъюнкция

(X V Y)  (X V Y)



Таблица истинности (1) и полученные СДНФ и СКНФ демонстрируют принцип действия одной и той же логической схемы.

Покажем, что полученные СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики: (X V Y)  (X V Y) = XX V XY V XY V YY = XY V



Похожие:

Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconСовершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма
Совершенной конъюнктивной нормальной формой (скнф) называется кнф, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconРазвитие устной речи у детей
Речь – особая и наиболее совершенная форма общения, присущая только человеку. Речь – важное средство связи между ребёнком и окружающим...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconСднф и скнф нормальная форма
Нормальная форма логической функции – если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconВопросы к зачету по дисциплине «Дискретная математика» 3ТО(з)
Конъюнктивная и дизъюнктивная нормальные формы. Непротиворечивость конъюнктивной нормальной формы
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconЗамеченные несоответствия
Божественного промысла, когда по самой природе вещей этому промыслу должна быть присуща простая и совершенная правдивость] ?
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconКритерии оценивания заданий заключительного этапа всероссийской олимпиады школьников по праву
Сделка, совершенная с целью, заведомо противной основам правопорядка или нравственности
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconАрамейское cлово
Господь даст вам, как Он говорил, соблюдайте сие служение (Исх. 12: 25. Ср. 13: 5)357. Пасха, совершенная Израилем в Галгале – третья...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconПансионат «Водопад»
Расположен в г. Новый Афон у водопада и храма Симона Кананита, на собственной огороженной территории. Совершенная экология и уникальное...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconСовершенная красота
В разведении они требуют больше знаний, больше умений, больше везения. Персидская шиншилла-кошка неземной красоты. Если человек не...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconКраткий обзор тибетских буддийских традиций
Бонпо. Каждая из этих четырех главных традиций заявляет, что ее школа самая совершенная. Если бы они этого не делали, то не было...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org