Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Конкурс'
Областной этап Всероссийского конкурса исследовательских краеведческих работ учащихся образовательных учреждений Нижегородской области "Отечество" (да...полностью>>
'Документ'
1. Оптимальной для первоклассников считается продолжительность сна -12 часов в сутки, для детей средних классов - до 9,5-10 часов, необходимо помнить,...полностью>>
'Документ'
Во время паломничества (и, я надеюсь, после его окончания) я попрошу вас заниматься утренними страницами – каждое утро писать по три страницы текста о...полностью>>
'Документ'
11с Телефон: 8(9 5)1777 50 E-mail: Luizza9 @inbox.ru II. Образование Годы учебы Наименование школы, вуза, где учились в интернатуре, ординатуре, аспир...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

СДНФ и СКНФ

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

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

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

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

Примеры

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

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

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

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

Примеры

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

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. Соединить элементарные дизъюнкции знаком конъюнкции.

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



Похожие документы:

  1. Данное учебное пособие содержит в себе весь курс информатики, необходимой для подготовки специалистов в системе высшего образования. Тематическая структура пос

    Реферат
    ... содержит ... операция. Конъюнкцией ... дизъюнктивная нормальная форма ... нормальная форма (КНФ), имеет вид А1  А2  ...  An, где каждое из составляющих есть дизъюнкция ... собой связанный ... между собой элемен­тарными объектами, а также тем, как свойства элементарных ...
  2. 1 Логические функции, Способы описания функций алгебры логики

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

Другие похожие документы..