Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“

Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“

Поздняков С. Н., Рыбин С. В. Математическая логика и теория алго• ритмов: Учеб. пособие. СПб.: Изд-во СПбГЭТУ „ЛЭТИ“, 2004. 64 с.

Рассматриваются основные идеи, понятия и методы математической логики, интерес к которым вырос благодаря новым приложениям, появив• шимся за последнее время в связи с развитием информационных техноло• гий.

Может использоваться как для студентов дневной формы обучения, так и для вечерних и заочных факультетов технических вузов.

Рецензенты: кафедра математического анализа СПбГУ; доц. М. В. Дмитриева (СПбГУ).

Утверждено редакционно-издательским советом университета

Математическая логика, как и теория алгоритмов, появились задолго до возникновения компьютеров. Их возникновение было связано с внут• ренними проблемами математики, с изучением границ применимости ее теорий и методов.

В настоящее время обе эти (взаимосвязанные между собой) теории получили прикладное развитие в так называемой компьютерной матема• тике (computer science). Вот несколько направлений их использования в прикладных областях:

– экспертные системы используют формально-логические выводы для имитации деятельности экспертов в различных областях;

– при проектировании микросхем используется теория булевых функций;

– тестирование программ основано на логическом анализе их структуры;

– доказательство корректности программ базируется на теории логическо• го вывода;

– алгоритмические языки связывают два важных понятия логики: поня• тие языка и понятие алгоритма;

– автоматизация доказательства теорем основана на методе резолюций, изучаемом в курсе логики.

В данном учебном пособии изложены основные идеи, понятия и мето• ды математической логики, лежащие в основе как перечисленных, так и других ее применений.

Бинарные отношения уже встречались в школьном курсе математи• ки. Примерами таких отношений являются отношения неравенства, равен• ства, подобия, параллельности, делимости и пр. Бинарное отношение каж• дым двум объектам сопоставляет логическое значение “да”, если объекты находятся в этом отношении, и “нет” в ином случае. Другими словами, множество пар объектов разбивается на два подмножества, пары первого подмножества находятся в данном отношении, а второго – не находятся. Это свойство можно положить в основу определения бинарного отношения.

Определение 1.1. Пусть задано множество M . Рассмотрим декар• тово произведение этого множества на себя M × M . Подмножество R множества M ×M называется бинарным отношением R на множестве M . Если пара (x; y) принадлежит множеству R , говорят, что элемент x находится в отношении R с элементом y , и записывают xRy .

Пример 1.1. Введем отношение сравнимости R : x сравнимо с y по модулю m тогда и только тогда, когда x и y имеют одинаковые остатки от деления на m . То есть x ≡ y (mod m) .

Рассмотрим введенное отношение R для случая m = 3 на множе• стве M = <1; 2; 3; 4; 5; 6>, тогда