Методические указания к выполнению лабораторных работ 1-3 по дисциплине «Математическая логика и теория алгоритмов»

18. По поводу приглашения друзей на день рождения были высказаны следующие предположения: 18.1. Если пригласим Володю, то надо пригласить и Андрея. А Сережу приглашать не надо. 18.2. Неверно, что Андрея или Володю, а также Сергея можно пригласить тогда и только тогда, когда будет приглашен или Сережа или Володя. 18.3. Нельзя пригласить ни Андрея, ни Володю. Было решено в качестве инструкции взять не эти высказывания, а их отрицания. Кроме того, необходимо свести эти новые инструкции к простейшим условиям. Какие условия получились? 19. Были высказаны следующие предположения по поводу рыбалки: 19.1. Тихая погода и наличие лодки являются достаточным условием хорошего улова. 19.2. Хороший улов бывает только при тихой погоде. Значит, лодку брать не надо. 19.3. Если будет тихая погода, то невозможно, чтобы наличие лодки было необходимым условием плохого улова. Эти высказывания сводятся к двум простейшим условиям. Кроме того, лодку достать не удалось, а из двух простейших условий выполненным оказалось только одно. Как прошла рыбалка? 20. О яблоках, лежащих в корзине, известно, что каждое из них либо большое, либо маленькое; либо сладкое, либо кислое; либо желтое, либо зеленое. Из корзины надо взять яблоки, удовлетворяющие следующим условиям: 20.1. Сладкое яблоко надо взять только при условии, что оно большое и желтое. 21 20.2. Если яблоко большое, то сладкий вкус должен быть достаточным признаком желтого цвета. 20.3. Если яблоко зеленое, то для того, чтобы оно было кислым, необходимо, чтобы оно было маленьким. Свести эти условия к двум простейшим и узнать, какие яблоки разрешено взять из корзины? 21. Относительно покупаемых цветов известно, что они могут быть либо астрами, либо гладиолусами; либо красными, либо фиолетовыми; либо светлыми, либо темными. Кроме того, заказанные цветы должны удовлетворять следующим условиям: 21.1. Если цветы будут темными, то они могут быть фиолетовыми только тогда, когда это гладиолусы. 21.2. Чтобы цветы были астрами, необходимо, чтобы они были светлыми и красными. 21.3. Если цветы будут красными, то для того, чтобы это были астры достаточно, чтобы они были темными. 21.4. Если цветы будут светлыми, то они могут быть фиолетовыми, если это астры. 21.5. Все фиолетовые светлые цветы являются гладиолусами. Оказалось, что первые три условия сводятся к двум простейшим, из которых выполнить удалось только одно. Из четвертого и пятого условий тоже удалось выполнить только одно. Какие цветы были заказаны и какие цветы были куплены? 22 ЛАБОРАТОРНАЯ РАБОТА № 3 ЛОГИЧЕСКИЙ ВЫВОД В ИСЧИСЛЕНИИ ВЫСКАЗЫВАНИЙ 1. ЦЕЛЬ РАБОТЫ Целью работы является приобретение навыков проверки правильности умозаключений с использованием различных формальных методов математической логики. 2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 2.1. Метод прямого преобразования Высказывание есть логическое следствие высказываний , то есть, ╞, если для всякого распределения истинностных значений, приписываемых каждой из простых формул , входящих в одну или несколько из формул и в формулу , формула получает значение истина всякий раз, когда каждое значение получает значение истина. Проиллюстрируем сказанное на примере. Если будет потепление, то пойдет снег. Потепления не будет. Вывод: снега не будет. На языке исчисления высказываний эти условия будут выглядеть так: ╞ , где - потепление; - снег. Для проверки правильности умозаключения составим таблицу истинности 23 Из таблицы истинности следует, что умозаключение является неверным, так как не всякий раз истинность посылок приводит к истинности вывода. Теорема 1. 1. ╞ тогда и только тогда, когда импликация является тавтологией. 2. ╞ тогда и только тогда, когда является тавтологией. Теорема 2. Если импликация является тавтологией, то умозаключение будет правильным, то есть, ╞ . Воспользуемся рассмотренными теоремами для доказательства правильности умозаключения. Рассмотрим пример. Будет пасмурная погода со снегом. Если будет снег, то будет и дождь. Если будет пасмурная погода с ветром, то дождя не будет. Вывод: ветра не будет. На языке исчисления высказываний эти условия запишутся так ╞ , где - пасмурная погода; - снег; - ветер, - дождь. Докажем, что является тавтологией. 24 2.2. Метод семантических таблиц Методы доказательства – это алгоритмические процедуры, посредством которых можно установить, является ли данное высказывание тавтологией. Основой для построения семантических таблиц является атомарная семантическая таблица, которая строится на основе законов исчисления высказываний.                     25 Пусть – высказывание. Обозначим через - утверждение “истинно”, а через - утверждение “ложно”. При этом – и называются помеченными формулами. Вершинами семантической таблицы называются все помеченные формулы, встречающиеся в таблице. Вершина семантической таблицы называется особой, если она встречается как корень некоторой атомарной семантической таблицы. В противном случае вершина называется обычной. Ветвь семантической таблицы называется противоречивой, если для некоторого высказывания помеченные формулы и являются вершинами этой ветви. Семантическая таблица называется замкнутой, если каждая непротиворечивая ее ветвь не содержит обычных вершин. В противном случае семантическая таблица называется незамкнутой. Семантическая таблица противоречива, если каждая ее ветвь противоречива. Алгоритм построения семантической таблицы для выражения : Помещаем помеченную формулу или в корень. Шаг . Пусть мы уже построили семантическую таблицу , . Шаг . Расширим семантическую таблицу до семантической таблицы . При этом мы пользуемся некоторой вершиной семантической таблицы , которую в дальнейшем не будем использовать. Из всех обычных вершин , ближайших к корню, выбираем самую левую. Обозначим выбранную вершину . К концу каждой непротиворечивой ветви семантической таблицы мы присоединяем атомарную семантическую 26 таблицу, имеющую корнем . (При этом вершина становится особой вершиной.) В результате получаем семантическую таблицу (как правило, мы не записываем саму вершину , так как она уже присутствует в каждой из рассматриваемых непротиворечивых ветвей). Построение заканчивается, если каждая непротиворечивая ветвь не содержит обычных вершин. Доказательством или выводом по Бету высказывания называется замкнутая противоречивая семантическая таблица, в корне которой помещена помеченная формула . Замкнутая противоречивая таблица, имеющая в качестве корня , называется опровержением по Бету высказывания . Итак, если замкнутая семантическая таблица с в корне противоречива (что означает, что мы всеми возможными способами пытались сделать высказывание ложным и не сумели), то - тавтология. Если не все ветви семантической таблицы противоречивы, то это свидетельствует о том, при некоторой комбинации значений атомов, входящих в исходное выражение, это выражение будет истинным, а при другой комбинации - ложным, то есть, выражение не является тавтологией. На рис. 1 изображена семантическая таблица для выражения . В построенной семантической таблице нет противоречивых ветвей, что свидетельствует о том, что не при какой комбинации значений атомов данное выражение не будет истинным. 27         Рис. 1. Непротиворечивая семантическая таблица В построенной семантической таблице (рис.1.) нет противоречивых ветвей, что свидетельствует о том, что не при какой комбинации значений атомов данное выражение не будет истинным. Докажем методом семантических таблиц, что выражение является тавтологией. Помещаем в корень семантической таблицы , а затем, пользуясь атомарной семантической таблицей, раскроем последовательно функцию импликации, функцию отрицания, функцию конъюнкции и, наконец, оставшиеся функции импликации (рис. 2.). Все ветви построенной семантической таблицы являются противоречивыми, следовательно, предположение 28 о ложности рассматриваемого выражения является неверным, следовательно, данное выражение есть – тавтология.  | |         | | | | |    Рис. 2. Пример противоречивой семантической таблицы 29 2.3. Метод резолюций Пропозициональные символы с отрицанием либо без отрицания, входящую в элементарную сумму (дизъюнкт), называют литералами (литерами) логики высказываний. Литеры и называют контрарными. Резольвентой двух дизъюнктов и называется дизъюнкт .

Похожие:

	Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» Методические указания предназначены для студентов, обучающихся по направлению 020400. 68 «Биология», магистерская программа 020400....
	Программа дисциплины «Информатика, математическая логика и теория... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....		«Разработка алгоритмов и программирование на языке Pascal» Лабораторный практикум содержит методические указания к выполнению лабораторных работ по алгоритмизации и программированию на языке...
	Методические указания по выполнению контрольных работ для экономических специальностей Методические указания по выполнению контрольных работ по дисциплине "Экономическая теория" для студентов экономических специальностей–...		Методические указания к выполнению контрольных работ по дисциплине “ Методические указания к выполнению контрольных работ по дисциплине “Основы внешнеэкономической деятельности” для студентов экономических...
	Программа вступительных испытаний по дисциплине «Математика» Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Методические указания по выполнению контрольных работ по дисциплине Методические указания по выполнению контрольных работ по дисциплине «Правовые основы российского государства» для студентов по специальности...
	Методические указания к выполнению контрольных работ по дисциплине «Информатика» Задания и методические указания к выполнению контрольных работ по дисциплине «Информатика». Екатеринбург, фгаоу впо «Российский государственный...		Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность
	Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность		Факультет экспертизы и товароведения методические указания к выполнению... «Нам дан во владение самый богатый, меткий, могучий и поистине волшебный русский язык». (К. Г. Паустовский)
	Сборник методических указаний для студентов по выполнению лабораторных работ дисциплина «химия» Методические указания для выполнения лабораторных работ являются частью основной профессиональной образовательной программы Государственного...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	Методические указания по выполнению курсов ых работ по дисциплине «теория управления» Методические указания предназначены для выполнения курсовой работы студентами направления подготовки бакалавриат 081100. 62 «г осударственное...		Методические указания по выполнению реферативных работ по дисциплине «История и философия науки» Методические указания к выполнению реферативных работ аспирантов и соискателей по дисциплине «История и философия науки» /Уфимск...