рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Алгоритм построения нормальных форм

Реферат Курсовая Конспект

Выберите учебное заведение

Алгоритм построения нормальных форм

Алгоритм построения нормальных форм - раздел Математика, ДИСКРЕТНАЯ МАТЕМАТИКА 1. С Помощью Равносильностей Алгебры Логики Заменить Все Имеющиеся В Формуле ...

1. С помощью равносильностей алгебры логики заменить все имеющиеся в формуле операции основными: конъюнкцией, дизъюнкцией, отрицанием:

;

2. Заменить знак отрицания, относящийся к выражениям типа или , знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

; .

3. Избавиться от знаков двойного отрицания.

4. Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

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

Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

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

Конструктивно СДНФ для каждой формулы алгебры высказываний, приведенной к ДНФ, можно определить следующим образом:

Определение 2. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами:

1) ДНФ не содержит двух одинаковых конъюнкций;

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

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

4) каждая конъюнкция содержит либо переменную , либо ее отрицание для всех переменных, входящих в формулу.

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

Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить следующим образом.

Определение 4. Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам.

1. КНФ не содержит двух одинаковых дизъюнкций.

2. Ни одна конъюнкция не содержит одновременно двух одинаковых переменных.

3. Ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание.

4. Каждая дизъюнкция СКНФ содержит либо переменную , либо ее отрицание для всех переменных, входящих в формулу.

Теорема 1.Каждая булева функция от переменных, не являющаяся тождественно ложной, может быть представлена в СДНФ, и притом единственным образом.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ДИСКРЕТНАЯ МАТЕМАТИКА

Федеральное агентство железнодорожного транспорта... Федеральное государственное бюджетное образовательное учреждение высшего... Дальневосточный государственный университет путей сообщения...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм построения нормальных форм

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Васильева, В.С.
В 191 Дискретная математика : учеб. пособие / В.С. Васильева, С.В. Коровина, Л.В. Марченко. – Хабаровск : Изд-во ДВГУПС, 2013. – 119 с. : ил. Учебное пособ

Решение
Мера множества – это площадь фигуры. Для данного примера – это площадь треугольника: ед2. Вопросы и задачи для самостоятельного решения 1. Какие из приведенных заданий

Решение
а) множество состоит из элементов: . Так как объединению множеств и принадлежат элементы, входящие или во множество или во множество , причем одинаковые элементы включаются только один раз, то ;

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

Решение
Построим множество, соответствующее левой части заданного тождества. Множество представлено закрашенной областью на рис. 6, а. Множеству соответствует закрашенная область на рис. 6, б

Решение
= /закон де Моргана/ = = = /закон дистрибутивности/ = = = /закон коммутативности/ = = = /закон дистрибутивности/ = = = /закон коммутативности/ =

Решение
Введем обозначения: ; ; ; . Из условия задачи: , , , , , , и . Тогда . Откуда , т. е. – количество студентов, занимающихся туризмом.

Решение
В соответствии с определением декартова произведения – множество точек, расположенных в квадрате с вершинами , , и (рис. 10). Рис. 10

Свойства бинарных отношений
1.Бинарное отношение на множестве рефлексивное, если для всякого выполняется . 2.Бинарное отношение на множестве антирефлексивное, если для

Решение
. Подставим , получим ; , получим . Прообразом отображения (в силу непрерывности функции) являются те , которые попадают в отрезок , тогда . Пример 3. О

Решение
Выделим простые высказывания и запишем их через переменные: – «ветра нет»; – «пасмурно»; – «дождь». Запишем логические функции (сложные высказывания) через введенные переменные:

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

Решение
Изображение графа представлено на рис. 28. Рис. 28 Так как у графа пять вершин, то матрица смежности будет : Вопросы и задачи

Решение
Применяя формулу для числа перестановок, запишем соотношение в виде . Подберем значение , исходя из равенств , , , , , . Следовательно, , откуда и . Вновь рассмотрим множ

Решение
Применяя формулы для числа перестановок и числа размещений, запишем соотношение в виде . После сокращения получим , , , . Поскольку число натуральное, то смысл имеет только значение .