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

ГОУВПО «Воронежский государственный технический университет» Кафедра автоматизированных и вычислительных систем 62-2009 МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению лабораторных работ 1-3 по дисциплине «Математическая логика и теория алгоритмов» для студентов специальности 230101 «Вычислительные машины, комплексы, системы и сети» очной, сокращенной очной, заочной и сокращенной заочной форм обучения   Воронеж 2009 Составители: канд. техн. наук Л.В. Холопкина, ст. преп. М.П. Носачева УДК 681.3.06:800.92(075) Методические указания к выполнению лабораторных работ 13 по дисциплине “Математическая логика и теория алгоритмов” для студентов специальности 230101 очной и сокращенной очной, сокращенной очной, заочной и сокращенной заочной форм обучения / ГОУВПО «Воронежский государственный технический университет»; сост. Л.В. Холопкина, М.П. Носачева. Воронеж, 2009. 47 с. Методические указания содержат краткие теоретические сведения по основным темам курса, примеры решения типовых задач, перечень задач, предназначенных для самостоятельного решения. Предназначены для студентов второго курса. Табл.2. Ил. 3 Библиогр.: 5 назв. Рецензент канд. техн. наук, доц. А.А. Кисурин Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. С.Л. Подвальный Печатается по решению редакционно-издательского совета Воронежского государственного технического университета © ГОУВПО «Воронежский государственный технический университет», 2009 ЛАБОРАТОРНАЯ РАБОТА № 1 АЛГЕБРА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ 1. ЦЕЛЬ РАБОТЫ Целью работы является теоретическое изучение основных логических функций и эквивалентностей исчисления высказываний и приобретение навыков при решении практических задач. 2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Высказывание – это повествовательное предложение, которое может быть классифицировано либо как истинное, либо как ложное, но не как, то и другое одновременно. 2.1. Основные логические функции исчисления высказываний Пусть и - высказывания. Основные логические функции исчисления высказываний задаются с помощью следующих таблиц истинности. Отрицание высказывания ( ) Дизъюнкция высказываний и () Пусть “60 делится на 5 ”; : “60 делится на 6”; “60 делится на 5 или на 6” Конъюнкция высказываний и () Пусть “”; : “”; “3 Импликация высказываний и - посылка импликации; - заключение импликации. Пусть “число кратно 10 ”; : “число кратно 5”; “Если число кратно 10, то оно кратно 5”. Эквиваленция высказываний и Используя таблицы истинности, можно выразить импликацию и эквиваленцию через элементарные логические операции. 2 В исчислении высказываний справедливы следующие эквивалентности (равносильности). Таблица 1 Основные эквивалентности Для дизъюнкцииДля конъюнкцииНазвание законаКоммутативный = Сочетательный Дистрибутивный Законы де МорганаФормула поглощенияФормула поглощения 3 2.2. Дизъюнктивно-нормальная и конъюнктивно- нормальная формы Элементарной конъюнкцией называется конъюнкция, состоящая из переменных или их отрицаний. Дизъюнктивно-нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций. Минимальной ДНФ называется та ДНФ, которая имеет самую короткую запись. В общем случае для получения минимальной ДНФ существуют эффективные алгоритмы, например, метод Квайна, карта Карно. Однако для получения минимальной ДНФ в некоторых частных случаях можно использовать следующие правила: Правило 1. Если ДНФ является трехчленом, зависящим от трех переменных, и если симметрия нарушена только по одной из переменных, то устраняется тот член дизъюнкции, который эту переменную не содержит. Пусть необходимо привести к минимальной ДНФ следующее выражение . Приводим сначала это выражение к ДНФ, пользуясь формулами перевода импликации и эквиваленции в элементарные логические операции и таблицей эквивалентностей (табл.1). == = . Поскольку в полученной ДНФ симметрия нарушена по переменной , так как переменная входит в ДНФ и с отрицанием и без отрицания, то для минимизации используется первое правило, то есть из выражения удаляется член, не содержащий эту переменную. 4 Правило 2. Если ДНФ является трехчленом, зависящим от трех переменных и если симметрия нарушена по двум из этих переменных, то данная ДНФ равносильна дизъюнкции, одним из членов которой является переменная, по которой симметрия не нарушена, а вторым членом служит тот член первоначальной ДНФ, который эту переменную не содержит. Совершенная ДНФ (СДНФ) должна удовлетворять следующим условиям: 1. Все элементарные конъюнкции различны. 2. Нет нулевых конъюнкций. 3. Ни одна из элементарных конъюнкций не содержит одинаковых членов. 4. Каждая элементарная конъюнкция содержит все переменные. Для получения СДНФ необходимо сначала найти минимальную ДНФ, а затем путем ввода дополнительных множителей добиться выполнения условия 4, например, Элементарной дизъюнкцией называется дизъюнкция, состоящая только из переменных или их отрицаний. Конъюнктивно-нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Минимальной КНФ называется такая КНФ, которая имеет самую короткую запись. Для получения минимальной КНФ, также как и для получения ДНФ, в некоторых частных случаях можно использовать следующие правила: Правило 1. Если КНФ зависит от трех переменных и представляет конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена по одной из переменных, то поглощается та элементарная дизъюнкция, которая эту переменную не содержит. 5 Правило 2. Если КНФ зависит от трех переменных и представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена по двум из этих переменных то данная КНФ равносильна конъюнкции, одним из членов которой является переменная, по которой симметрия не нарушена, а вторым членом является тот член первоначальной КНФ, который эту переменную не содержит. Для получения минимальной КНФ сначала получают КНФ. Пусть необходимо привести к минимальной КНФ следующее выражение . Сначала получаем ДНФ: = . Полученную ДНФ минимизируем, используя правило 2 для ДНФ, и получаем . Для получения КНФ преобразуем ДНФ в КНФ, используя последнюю формулу из таблицы эквивалентностей: 3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ Упростить следующие выражения: 1. ; 2. ; 6 3. . Используя основные эквивалентности исчисления высказываний, проверить следующие равносильности: 1. ; 2. ; 3. 4. ; 5. ; 6. 7 ; 8 9. ; 10. ; 11.; 12. ; 13. ; 14.; 15. ; 16. ; 17. ; 18. ; 7 19. 20. 21. ; 22. ; 23. ; 24. 25. ; 26. 27. 28. ; 29. ; 30. ; 31. ; 32. . Привести следующие формулы к минимальной ДНФ. 1. ; 2. ; 3. ; 8 4. ; 5. ; 6. ; 7. ; 8. ; 9. . Привести следующие формулы к минимальной КНФ. 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ; 8. ; 9. . Привести следующие формулы к виду СДНФ. 1.; 2.; 3.; 4. ; 5. ; 6. ; 9 7. ; 8. ; 9. . ЛАБОРАТОРНАЯ РАБОТА № 2 ПЕРЕВОД ВЫСКАЗЫВАНИЙ ЕСТЕСТВЕННОГО ЯЗЫКА НА ЯЗЫК ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ ЦЕЛЬ РАБОТЫ Целью работы является приобретение навыков перевода высказываний естественного языка на язык исчисления предикатов 2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Язык алгебры логики может быть использован при решении большого числа содержательных логических задач. Решение таких задач с помощью логических рассуждений достаточно трудно. Если же применить аппарат алгебры логики к решению таких задач, то все рассуждения могут быть заменены на простые формализованные вычисления, гарантирующие правильность ответа. Но прежде чем применить формализованный подход, исходные рассуждения надо нужно правильно перевести на яэык алгебры логики. Для решения данной задачи может быть использована таблица соотношений между наиболее часто встречающимися выражениями естественного языка и формулами алгебры логики. 10 Таблица 2 Таблица соотношений Форма выражения естественного языкаФормула языка алгебры логикиНе A; неверно, что A; A не имеет места A и B; как A, так и B; не только A, но и B ; A вместе с B; A, несмотря на B; A в то время, как B А, но не В ; не В, а А А или В; А или В, или обаА, либо В; А, разве, что В; либо А, либо В; не А, разве, что не В; либо не А, либо не В;

Похожие:

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