Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Различные формы представления высказыванийСодержание книги
Поиск на нашем сайте
Литерой - называется элемент высказывания x или её отрицание. Элементарной дизъюнкцией называется выражение следующего вида: , (2.2) где - литера. Элементарной конъюнкцией называется выражение следующего вида: , (2.3) Дизъюнктивной нормальной формой (ДНФ) формулы называется выражение вида: , (2.4) где - элементарная конъюнкция.
Конъюнктивной нормальной формой (КНФ) формулы называется выражение вида: , (2.5) где - элементарная дизъюнкция. Любую формулу можно представить в виде ДНФ или КНФ.
ПРИМЕР Пусть дана формула Требуется получить ДНФ и КНФ данной формулы. Применяя формулы равносильности, получаем КНФ : Применяя формулы равносильности, получаем ДНФ : Совершеннойдизъюнктивной нормальной формой(СДНФ) формулы называется такая ДНФ, для которой выполняются следующие условия: 1. Все элементарные конъюнкции, входящие в ДНФ , различны. 2. Все элементарные конъюнкции, входящие в ДНФ , содержат литеры, соответствующие всем переменным. 3. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит двух одинаковых литер. 4. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит переменную и ее отрицание. СДНФ можно получить двумя способами: 1. по таблице истинности; 2. с помощью равносильных преобразований. Первый способ получения СДНФ рассмотрен выше. Рассмотрим второй способ, который состоит в следующем: С помощью равносильных преобразований формулы получают ДНФ . При этом в полученной ДНФ возможны следующие ситуации: 1. Элементарная конъюнкция ДНФ не содержит переменную , тогда используются следующие равносильные преобразования: 2. Если в ДНФ входят две одинаковые элементарные конъюнкции, то используя следующее равносильное преобразование: , одну элементарную конъюнкцию можно отбросить. 3. Если элементарная конъюнкция ДНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования: , эту элементарную конъюнкцию можно отбросить 4. Если элементарная конъюнкция ДНФ содержит дважды переменную , то используя следующее равносильное преобразование: , одну переменную можно отбросить СДНФ формулы существует в единственном виде.
ПРИМЕР Получить СДНФ формулы С помощью равносильных преобразований получаем СДНФ : С помощью таблицы истинности получаем СДНФ :
СДНФ Очевидно, что в результат двух способов совпадает.
Совершеннойконъюнктивной нормальной формой(СКНФ) формулы называется такая КНФ, для которой выполняются следующие условия: 1. Все элементарные дизъюнкции, входящие в КНФ , различны. 2. Все элементарные дизъюнкции, входящие в КНФ , содержат литеры, соответствующие всем переменным. 3. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит двух одинаковых литер. 4. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит переменную и ее отрицание. СКНФ можно получить двумя способами: 1. по таблице истинности; 2. с помощью равносильных преобразований. По первому способу по таблице истинности получаем СДНФ , а СКНФ можно получить, следуя следующему правилу С помощью равносильных преобразований формулы получают КНФ . При этом в полученной КНФ возможны следующие ситуации: 1. Элементарная дизъюнкция КНФ не содержит переменную , тогда используются следующие равносильные преобразования: 2. Если в КНФ входят две одинаковые элементарные дизъюнкции, то используя следующее равносильное преобразование: , одну элементарную дизъюнкцию можно отбросить. 3. Если элементарная дизъюнкция КНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования: , эту элементарную дизъюнкцию можно отбросить. 4. Если элементарная дизъюнкция КНФ содержит дважды переменную , то используя следующее равносильное преобразование: , одну переменную можно отбросить. СКНФ формулы существует в единственном виде.
ПРИМЕР Получить СКНФ формулы С помощью равносильных преобразований получаем СКНФ : С помощью таблицы истинности получаем СДНФ :
Очевидно, что в результат двух способов совпадает.
СДНФ формулы можно получить из СКНФ , используя следующее правило:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-08-01; просмотров: 236; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.119.106.176 (0.007 с.) |