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

Раздел Образование
/
Нормальные формы

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

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

Нормальные формы

Нормальные формы - раздел Образование, Методические указания и контрольные работы Пусть ...

Пусть

(*)

– высказывательные переменные.

Элементарной дизъюнкцией (ЭД)называется дизъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные дизъюнкции. Если в элементарной дизъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной дизъюнкцией (ПЭД). Например, в случае , перечислим всех полных элементарных дизъюнкций: , , , , , , , .

Элементарной конъюнкцией (ЭК)называется конъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные конъюнкции. Если в элементарной конъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной конъюнкцией (ПЭК). Например, в случае , перечислим всех полных элементарных конъюнкций: , , , , , , , .

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкции произвольного количества элементарных конъюнкций. Схематично ДНФ имеет вид:

(ЭК)Ú (ЭК)Ú (ЭК)Ú … .

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

(ПЭК)Ú (ПЭК)Ú (ПЭК)Ú … .

Конъюнктивной нормальной формой (КНФ) называется конъюнкции произвольного количества элементарных дизъюнкций. Схематично КНФ имеет вид:

(ЭД)Ú (ЭД)Ú (ЭД)Ú … .

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

(ПЭД)Ú (ПЭД)Ú (ПЭД)Ú … .

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

Развернуть

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

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

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

Методические указания и контрольные работы

Кафедра высшей математики...

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

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

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

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

Решение.
Найдем все элементы множеств и

Решение.
Доказательство равенства двух множеств состоит из доказательства двух включений: а)

Решение.
Найдем все элементы бинарного отношения :

Решение.
Запишем данную формулу: ; применим формулу 10:

Решение.
Запишем данную формулу: ; дважды применим формулу 22:

Решение.
Построим таблицу истинности данной формулы:

Решение.
Каждой формуле алгебры высказываний соответствует один многочлен Жегалкина. Равносильным формулам соответствует один и тот же многочлен Жегалкина. Обратно, каждому многочлену Жегалкина соответствуе

Решение.
Составим функцию проводимости данной релейно-контакт-ной схемы. Для этого рассмотрим две простейшие релейно-кон-тактные схемы:

Бинарное отношение
Прямым произведением двух множеств

Действия над высказываниями
Высказывание является первичным понятием математической логики, которое не имеет строгого определения. Высказывание – это всякое повествовательное предложение, которое либо истинно

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

Основные тавтологии
Приведем перечень равносильных формул и названий некоторых из них: 1. – коммутативность дизъюнкции;

Функции алгебры логики
Функцией алгебры логики переменных (функцией Буляили булевой функцией) называ

Многочлен Жегалкина
Операция арифметического умножения нами введена. Введем новую логическую операцию, называемую сложением по модулю 2. Сложение по модулю 2 обозначается