Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Совершенные нормальные формы.
Формулы х и будем называть литералами, т.е. литерал – это или х, или . Если в ДНФ каждое элементарное произведение содержит все элементарные высказывания, но только в виде единственного литерала, то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ). Например: =pqr r является ДНФ, но не является СДНФ, т.к. во второе элементарно произведение не входит ни р, ни . Формула = pqr r – СДНФ. Формула = pqr rq – не СДНФ, т.к. во втором элементарном произведении содержится два литерала. Теорема. Любаяформула, отличная от 0, представима в виде СДНФ. Доказательство: Пусть Ф – формула, содержащая n литералов. Пусть ДНФ содержит элементарное произведение без литерала . = , - литералы. Введем дизъюнкцию , которая равна 1. Получим = ( )=(по первому закону дистрибутивности)= . Теперь каждое из элементарных произведений содержит все литералы. Поступая аналогично с другими элементарными произведениями, и, заменяя р нулем, получим СДНФ. Что и требовалось доказать. Пример 1. Пусть = pqr q – ДНФ. Приведем к СДНФ. Добавим 1 в виде дизъюнкции r . Получим =pqr q (r ) pqr qr q - СДНФ. Если каждая элементарная сумма КНФ формулы содержит все литералы по одному разу, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ). Теорема. Любая формула может быть приведена к СКНФ. Доказательство: Если элементарная сумма не содержит литерал , то можно в нее ввести конъюнкцию и воспользоваться вторым законом дистрибутивности. Пример 2. Пусть =(p q r) ( q) – КНФ. Приведем к СКНФ. Добавим 0 в виде r . Получим =(p q r) ( q r ) (p q r) ( q r) ( q ) это – СКНФ. Восстановление формул. Каждой формуле соответствует таблица истинности, следовательно, каждой таблице истинности соответствует некоторая формула. Возникает задача - для заданной таблицы истинности восстановить формулу, которой она соответствует. Этого можно достичь двумя способами: С помощью СКНФ или с помощью ДНФ. 1. СКНФ. В таблице истинности выделяются строки, в которых формула ложна. Каждой такой строке будет соответствовать единственная элементарная сумма КНФ. В эту сумму высказывание истинное будет входить с отрицанием, а высказывание, которое ложно - без отрицания. Это объясняется тем, что элементарная сумма должна быть ложной, а если в нее будут входить истинное высказывание, то она ложной не будет. Составляя СКНФ из этих строк, мы получим исходную формулу.
Пример: дана таблица
Так как во 2-ой строке функция ложна, то должна быть ложна элементарная сумма. А элементарная сумма ложна тогда, когда каждый ее член равен 0. Т. к. р=1, =0; и в дизъюнкцию должно входить . Т. к. q=1, =0; и в дизъюнкцию должно входить . r=0- без отрицания. Получим: r. Аналогично Для 4-ой строки: р Для 7-ой строки: . Тогда Ф=( r)(р )( ). 2. СДНФ. В таблице истинности выделяются строки, в которых формула истинна. Каждой такой строке поставим в соответствие элементарное произведение, которое должно быть истинно. В это произведение истинные высказывания входят без отрицания, а ложные - с отрицанием. Затем составляется дизъюнкция элементарных произведений. Для нашего примера: Ф = рqr р r р q Построение минимальной ДНФ. Формула (булева функция) имеет минимальную ДНФ, если она содержит наименьшее количество литералов среди всех ДНФ, эквивалентных ей. Пример: ДНФ - содержит 4 литерала, но она не является минимальной. Преобразуем ее ( ) =1* = . Получили один литерал. Рассмотрим алгоритм Квайна Мак-Клоски: Пусть функция задана СДНФ и , - два элементарных произведения, входящих в СДНФ. Пусть х - литерал, такой, что =xk и = k. Тогда = хk k = (x )k = k. Мы получили элементарное произведение, содержащее на один литерал меньше. Такая операция называется склейкой. Пример: Ф=pqr р r q r. Произведем склейку 1й и 2й, а так же 3й и 4й элементарных произведений. Ф= pr(q ) (q ) r pr r. Решение логических задач. В ряде задач приводится несколько высказываний относительно некоторого события, и имеются некоторые сведения об их ложности или истинности. Требуется определить какое из событий имело место. Такие задачи называются логическими. Задача: В конкурсе участвовало 4 девушки: Оля, Нина, Марина и Тамара. На вопрос о том, как распределились между ними места, были получены ответы:
Оля 1 - Нина-2, Оля-2 - Тамара-3, Марина-2 - Тамара-4. Известно, что хотя бы одна высказывание в каждом ответе истинно. Как распределились места? Решение: Введем обозначения: О Н ; О Т ; М Т . Тогда КНФ: (О Н ) (О Т ) (М Т ) 1, т.к. Каждое из элементарных сумм истинно. Преобразуем в ДНФ, раскрывая скобки: (О Н ) (О М О Т Т М Т Т ) (т.к. О2 М 2 =0 и Т3Т4=0) (О Н ) (О Т Т М ) (раскрываем скобки) О О Т О Т М Н О Т Н Т М О Т М . Получили О Т М 1. Следовательно: Оля-1,Марина-2, Тамара-3, Нина-4. Анализ рассуждений. Рассуждение - это вывод, позволяющий из данных высказываний (называемых посылками) получить новое высказывание (заключение). Рассуждение состоит из последовательности посылок и заключения, то есть на основании известных свойств некоторых посылок мы получаем новое свойство этого объекта - заключение.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2022-09-03; просмотров: 54; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.133.108.241 (0.037 с.) |