Сднф и скнф нормальная форма icon

Сднф и скнф нормальная форма



НазваниеСднф и скнф нормальная форма
Дата конвертации14.07.2012
Размер53.33 Kb.
ТипДокументы

СДНФ и СКНФ


Нормальная форма логической функции – если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией.

Элементарная конъюнкция – конъюнкция конечного множества логических переменных и их инверсий.

Элементарная дизъюнкция – дизъюнкция конечного множества логических переменных и их инверсий.

Ранг элементарной конъюнкции или дизъюнкции – число аргументов ее образующих.

Примеры



Элементарная конъюнкция третьего порядка



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




^ Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операциями конъюнкции.

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

Примеры








^ Совершенная конъюнктивная нормальная форма (СКНФ):

1) нет двух элементарных дизъюнкций;

2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных;

3) ни одна элементарная дизъюнкция не содержит переменную вместе с ее инверсией;

4) все дизъюнкции имеют один и тот же ранг.


^ Совершенная дизъюнктивная нормальная форма (СДНФ)


Алгоритм образования СКНФ и СДНФ по таблице истинности

1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.

1. Выделить в таблице истинности все строки, в которых функция принимает значения 1.

2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:

а) если значение переменной равно 0, то записывается сама переменная,

б) если значение переменной равно 1, то записывается инверсия этой переменной.

2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:

а) если значение переменной равно 0, то записывается инверсия этой переменной,

б) если значение переменной равно 1, то записывается сама переменная.

3. Соединить элементарные дизъюнкции знаком конъюнкции.

3. Соединить элементарные конъюнкции знаком дизъюнкции.

^ Пример создания СКНФ

Исходная таблица

X

Y

Z

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1


1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.


X

Y

Z

F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1


2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные

    1. если значение переменной равно 0, то записывается сама переменная,

    2. если значение переменной равно 1, то записывается инверсия этой переменной.




X

Y

Z

F







0

0

0

0






0

0

1

0






0

1

0

0






0

1

1

1







1

0

0

0






1

0

1

1







1

1

0

1







1

1

1

1








3. Соединить элементарные дизъюнкции знаком конъюнкции.





Давыдова Елена Владимировна,




Похожие:

Сднф и скнф нормальная форма icon9 класс Домашнее задание по теме сднф и скнф

Сднф и скнф нормальная форма iconСоставьте сднф и скнф выражения по следующим таблицам истинности

Сднф и скнф нормальная форма iconСовершенная дизъюнктивная, совершенная конъюнктивная нормальная форма
Мы знаем 2 способа задания логических функций: формулой и таблицей истинности. По формуле легко составляется таблица. На практике...
Сднф и скнф нормальная форма iconДокументы
1. /fiziologiya/Нормальная Физиология v1.0.doc
2. /fiziologiya/Нормальная...

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

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


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

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