Читать онлайн «Математическая логика и теория алгоритмов. Учебное пособие»

Министерство образования и науки РФ Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“ С. Н. ПОЗДНЯКОВ С. В. РЫБИН МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Учебное пособие Санкт-Петербург Издательство СПбГЭТУ „ЛЭТИ“ 2004  Министерство образования и науки РФ Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“ С. Н. ПОЗДНЯКОВ С. В. РЫБИН МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Санкт-Петербург Издательство СПбГЭТУ „ЛЭТИ“ 2004  УДК 510. 6 ББК В12 П47 Поздняков С. Н. , Рыбин С. В. Математическая логика и теория алго- ритмов: Учеб. пособие. СПб. : Изд-во СПбГЭТУ „ЛЭТИ“, 2004. 64 с. Рассматриваются основные идеи, понятия и методы математической логики, интерес к которым вырос благодаря новым приложениям, появив- шимся за последнее время в связи с развитием информационных техноло- гий. Может использоваться как для студентов дневной формы обучения, так и для вечерних и заочных факультетов технических вузов. Рецензенты: кафедра математического анализа СПбГУ; доц. М. В. Дмитриева (СПбГУ). Утверждено редакционно-издательским советом университета в качестве учебного пособия ISBN 5-7629-0579-9 c СПбГЭТУ „ЛЭТИ“, 2004 °  Математическая логика, как и теория алгоритмов, появились задолго до возникновения компьютеров. Их возникновение было связано с внут- ренними проблемами математики, с изучением границ применимости ее теорий и методов. В настоящее время обе эти (взаимосвязанные между собой) теории получили прикладное развитие в так называемой компьютерной матема- тике (computer science). Вот несколько направлений их использования в прикладных областях: – экспертные системы используют формально-логические выводы для имитации деятельности экспертов в различных областях; – при проектировании микросхем используется теория булевых функций; – тестирование программ основано на логическом анализе их структуры; – доказательство корректности программ базируется на теории логическо- го вывода; – алгоритмические языки связывают два важных понятия логики: поня- тие языка и понятие алгоритма; – автоматизация доказательства теорем основана на методе резолюций, изучаемом в курсе логики. В данном учебном пособии изложены основные идеи, понятия и мето- ды математической логики, лежащие в основе как перечисленных, так и других ее применений. 1. Бинарные отношения и графы 1. 1. Введение. Постановка задачи Бинарные отношения уже встречались в школьном курсе математи- ки. Примерами таких отношений являются отношения неравенства, равен- ства, подобия, параллельности, делимости и пр. Бинарное отношение каж- дым двум объектам сопоставляет логическое значение “да”, если объекты находятся в этом отношении, и “нет” в ином случае.