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

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



НазваниеСовершенная дизъюнктивная, совершенная конъюнктивная нормальная форма
Дата конвертации15.07.2012
Размер42.58 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Документы
1. /fiziologiya/Нормальная Физиология v1.0.doc
2. /fiziologiya/Нормальная...

Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconПонятие как форма мышления
Суждение – форма мышления, отражающая вещи, процессы предметные связи и отношения – это мысленное отражение м б либо истинным, либо...
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconДокументы
1. /Нормальная жизнь христианина.doc
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconДокументы
1. /Нормальная христианская вера.doc
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconДокументы
1. /Нормальная Христианская Церковная Жизнь.doc
Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconВ экзаменационную пору всегда присутствует психологическое напряжение. Стресс при этом абсолютно нормальная реакция организма

Совершенная дизъюнктивная, совершенная конъюнктивная нормальная форма iconСоветы выпускникам
В экзаменационную пору всегда присутствует психологическое напряжение. Стресс при этом абсолютно нормальная реакция организма
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов