Алгебра высказываний позволяет научиться моделировать простейшие мыслительные процессы. Одним из самых интересных ее приложений является применение к решению логических задач. Логические задачи весьма разнообразны, способов их решения также немало. Но наибольшее распространение получили следующие три способа решения логических задач:
а) средствами алгебры логики;
б) табличный;
в) с помощью рассуждений.
Решение логических задач средствами алгебры логики происходит следующим образом:
а) изучается условие задачи;
б) вводится система обозначений для логических высказываний;
в) конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
г) определяются значения истинности этой логической формулы;
д) из полученных значений истинности формулы определяются значения истинности введенных логических высказываний, на основании которых делается заключение о решении.
При использовании табличного способа решения логических задач условия, которые они содержат, и результаты рассуждений фиксируются с помощью специально составленных таблиц.
Всегда, когда в процессе решения задачи требуется проводить равносильные преобразования логической формулы, студенты, как правило, сталкиваются с другой трудностью. Суть ее такова. Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Мор-гана и др.). Т.е. полного сходства логических операций (конъюнкция и дизъюнкция) с числовыми (умножение и сложение) нет. Кроме того, законы двойственности говорят от том, что логические сложение и умножение являются «перевертышами»: отрицание результата логического умножения А и В совпадает с результатом логического сложения отрицаний А и В, и наоборот. Таким образом, при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.
Чтобы справиться с этими трудностями, нужно решить достаточно много задач [5, 6, 10], что даст возможность глубже понять основные положения разделов изучаемой дисциплины, научиться применять их при анализе конкретной ситуации. В этой связи типовые задачи, рассмотренные в рекомендуемых учебных пособиях, следует разобрать внимательно, обращаясь при необходимости к соответствующим указаниям, подробным решениям или ответам. Задачи должны быть использованы в процессе работы над курсом и затем при подготовке к экзамену. При этом непременным условием является глубокое усвоение соответствующего материала по конспекту лекций или учебнику.
2.4 Самопроверка
После изучения определенной темы и решения достаточного количества соответствующих задач студенту рекомендуется воспроизвести по памяти определения, выводы формул, формулировки и доказательства теорем, проверяя себя каждый раз по учебнику или конспекту лекций. Контрольные вопросы, приводимые в конспекте лекций по дисциплине, имеют цель помочь студенту в таком повторении, закреплении и проверке прочности усвоения изученного материала.
Часто недостаточность усвоения того или иного вопроса выясняется только при изучении дальнейшего материала. В этом случае надо повторить плохо изученный раздел, внимательно разобрав материал учебника, а также прорешать задачи.
2.5 Выполнение индивидуальных заданий
В процессе изучения дисциплины «Математическая логика и теория алгоритмов» студенту предлагается выполнить индивидуальные домашние задания [9] по пяти темам дисциплины: составление таблиц истинности логических формул, нахождение СДН и СКН логической функции, минимизация в классе ДНФ и КНФ, полные системы булевых функций, предикаты. Не следует приступать к решению задания до решения достаточного количества задач по материалу, соответствующему этому заданию. Опыт показывает, что чаще всего неумение решить ту или иную задачу вызывается тем, что у студента отсутствует необходимая практика в решении задач.
Указанные задания должны выполняться самостоятельно. В противном случае студент не приобретает необходимых знаний и может оказаться неподготовленным к их защите, а в конечном итоге к тестированию и к зачету.
Кроме того, по желанию студенты могут повысить свой итоговый рейтинг с помощью успешного выполнения индивидуальных заданий повышенной степени сложности. Список заданий предоставляется преподавателем, ведущим дисциплину.
2.6 Зачет
На зачете, прежде всего, выясняется отчетливое усвоение теоретических и прикладных вопросов программы и умение применять полученные знания к решению практических задач. Зачет проводится по билетам. Каждый билет имеет теоретическую (один вопрос) и практическую (три задачи) составляющие. Определения и алгоритмы решения задач должны формулироваться точно и подкрепляться примерами. Студент должен уметь объяснить как выбор схемы решения задачи, так и все его этапы.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
Основная литература
1. Хаггарти, Р. Дискретная математика для программистов / Р. Хаг-гарти. – М.: Техносфера, 2005.
2. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001.
3. Нефедов, В.Н. Курс дискретной математики: учеб. пособие / В.Н. Нефедов, В.А. Осипова. – М.: Изд-во МАИ, 1992.
4. Яблонский, С.В. Введение в дискретную математику: учебное пособие для вузов / под ред. В.А. Садовничего. – 3-е изд., стер. / С.В. Яблонский. – М.: Высшая школа, 2002.
5. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – Изд. 4-е. – М.: ФИЗМАТЛИТ, 2001.
6. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие / Г.И. Москинова. – М.: Логос, 2000.
Дополнительная литература
7. Судоплатов, С.В. Дискретная математика: учебное пособие / С.В. Судоплатов, Е.В. Овчинникова. – М.: Инфра-М, 2007.
8. Романовский, И.В. Дискретный анализ / И.В. Романовский. – 2-е. изд. – СПб.: Невский диалект, 2000.
Перечень пособий, методических указаний и материалов, используемых в учебном процессе
9. Ростова, О.Д. Дискретная математика: методические рекомендации к типовому расчету по математике с вариантами заданий для студентов специальностей 071900, 351400, 170600, 171200 / О.Д. Ростова, Т.М. Тушкина, В.С. Фролов; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2005.
10. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010.
11. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по самостоятельной работе студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010.
Учебное издание
ТУШКИНА Татьяна Михайловна
ФРОЛОВ Виктор Савельевич
РОСТОВА Ольга Дмитриевна
КУВШИНОВА Лидия Павловна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике»,
230201 «Информационные системы и технологии»
Редактор Идт Л.И.
Технический редактор Сазонова В.П.
Подписано в печать 26.02.2010. Формат 60´84 1/16
Усл. п. л. - 0,93. Уч.-изд. л. - 1,00
Печать - ризография, множительно-копировальный
аппарат «RISO EZ300»
Тираж 50 экз. Заказ 2010-34
Издательство Алтайского государственного
технического университета
656038, г. Барнаул, пр-т Ленина, 46
Оригинал-макет подготовлен ИИО БТИ АлтГТУ
Отпечатано в ИИО БТИ АлтГТУ
659305, г. Бийск, ул. Трофимова, 27