Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 3. Тема: ДНФ. СДНФ. Цель: Определить.

Презентация:



Advertisements
Похожие презентации
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 2. Тема: Таблица истинности. Основные.
Advertisements

Решение логических задач (табличный способ). Курсовая работа Закировой Лены, СШ 23, 2002 г.
Применение алгебры высказываний в логике. Комиссару Мэгрэ поступили следующие сообщения от инспекторов (доказанные ими): 1) если Франсуа был пьян, то.
Решение логических задач табличным методом Автор: к.ф.-м. наук Жанабергенова Г.К.
Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Логика в информатике Решение уравнений. Логические основы ПЭВМ.
содержание 1определение 1.определение 2.логическоеотрицание 2.логическое отрицание 3.логическое сложение 4.логическое умножение 5логическоеследование.
Логические законы и правила преобразования логических выражений.
1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление высказываний Высказывание – утверждение о математических.
1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.
Алгебра высказываний Лекция 2 2. Определение высказывания. Таблица истинности для высказываний Определение 1 Переменная А, принимающая два значения –
ГБПОУ «МСС УОР 2» Москомспорта Преподаватель информатики Володина М.В г.
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании,
Алгебра логики. Логика Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и.
ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Элементарной дизъюнкцией называется выражение вида: Элементарной конъюнкцией называется выражение вида: Где A i - либо.
Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и опровержений, т. е. методы.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 1. Тема: Высказывание. Основные логические.
Математическая логика. Пон я тие высказываний Понятие высказываний Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее.
Таблица истинности составных высказываний – это таблица, которая показывает какие значения принимает составное высказывание при всех сочетаниях значений.
Транксрипт:

Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 3. Тема: ДНФ. СДНФ. Цель: Определить ДНФ, СДНФ, сформировать навык приведения высказывания к ДНФ, СДНФ.

Определение 1 Конъюнкция логических переменных или их отрицаний называется элементарной конъюнкцией. Пример Определение 2 Высказывание называется дизъюнктивной нормальной формой (ДНФ), если оно представляет собою дизъюнкцию элементарных конъюнкций. Общий вид ДНФ: 3. Дизъюнктивные нормальные формы (ДНФ)

Примеры

Теорема Любое высказывание приводимо к ДНФ. Схема приведения высказывания к ДНФ 1)Избавиться от импликации и эквивалентности, используя законы 16), 17) 2) Донести отрицания до переменных, используя законы Моргана. 3) Раскрыть скобки, используя дистрибутивные законы. 4) Упростить полученное высказывание.

Пример Привести высказывание к ДНФ

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

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

Приведение высказывания к СДНФ Теорема Высказывание, не являющееся тождественно ложным, приводимо к СДНФ. Правило приведения высказывания к СДНФ СДНФ содержит столько полных элементарных конъюнкций, сколько единиц в последнем столбце таблице истинности. Вид каждой полной элементарной определяется соответствующим набором значений переменных, а именно, если переменная принимает значение 0, то над ней в полной элементарной конъюнкцией ставится отрицание, иначе – отрицание не ставится.

Пример Построить по таблице истинности СДНФ ABC

Задача «Вернувшись домой, Мегрэ позвонил на набережную Орфевр. - Говорит Мегрэ. Есть новости? - Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать Вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила … - Все. Спасибо. Этого достаточно. – Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.» Что знал Мегрэ?

Решение задачи Пусть P=« Франсуа был пьян» L=«Франсуа лжет» I=«Этьен убийца» U=«Убийство произошло после полуночи» Тогда получим высказывание Так как, то Этьен - убийца

Вопросы: Является ли СДНФ-ДНФ? Можно ли построить СДНФ для высказывания, в таблице истинности которого отсутствуют 1?