Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Курс "`Математическая логика и теория алгоритмов"

МАТЕРИАЛЫ

для СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ СПбГЭТУ (ЛЭТИ)

Курс "`Математическая логика и теория алгоритмов"'

Кафедра ВМ-2

Курс 3

Семестр 5

Санкт-Петербург

2006

Курс "`Математическая логика и теория алгоритмов"'

кафедра ВМ-2, курс 3, семестр 5

1. Программа курса

Множества и отношения Бинарные отношения. Способы задания. Отношение эквивалентности. Метод раскраски. Отношение порядка. Алгоритм топологической сортировки. Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла. Алгебра высказываний и булевы функции Формулы логики высказываний. Равносильность. Логическое следствие. Нормальные формы в логике высказываний (СДНФ и СКНФ). Контактные схемы. Минимизация формул логики высказываний. Самодвойственные, монотонные булевы функции Линейные булевы функции. Полиномы Жегалкина Критерий полноты Поста. Метод резолюций. Стратегии метода резолюций. Автоматы, машины Тьюринга и рекурсивные функции Конечный автомат. Машины Тьюринга. Операции над машинами Тьюринга. Рекурсивные функции. Нормальные алгорифмы Маркова. Языки и грамматики Языки и грамматики. Основные определения Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы. Автоматные грамматики и языки. Проектирование синтаксических анализаторов.

2. Контрольные работы

2.1. Первый вариант

1.  Отношение задано на множестве целых чисел . Для каждого из следующих отношений

  i.  проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;

  ii.  построить матрицы и графы этих отношений;

  iii.  определить являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;

  iv.  для отношений эквивалентности построить классы эквивалентности;

  v.  для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строго порядка;

  vi.  построить транзитивные замыкания всех отношений.

и имеют одинаковые остатки при делении на 3;

в наборе имеется элемент, больший , но меньший ;

в наборе имеется элемент , такой что ;

каждая из цифр числа больше цифры числа , стоящей в соответствующем разряде;

.

2.  Будет ли логичным следующее рассуждение: Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен и волнения не прекратятся до тех пор, пока участникам волнений это не надоест, и власти не начнут примирительные действия. Следовательно, если губернатор не желает взять на себя ответственность и участникам волнений это не надоест, то волнения не прекратятся.

3.  Провести исследование булевой функции :

  i. Составить таблицу истинности

  ii. Построить по таблице истинности СКНФ.

  iii. Построить по таблице истинности СДНФ.

  iv. Построить минимальную ДНФ методом минимизирующих карт.

  v. По минимальной ДНФ нарисовать схему логического устройства, описываемого исходной булевой функцией и состоящего из элементов "и", "или", "не".

  vi. Определить, какая функция двух переменных задается выражением двумя способами: построив таблицу значений и упростив данное выражение с помощью алгебраических преобразований;

  vii. Построить для заданной булевой функции многочлен Жегалкина двумя способами.

  viii. Построить по исходной формуле двойственную. Упростить выражение. Построить таблицу двойственной функции по таблице исходной.

  ix. Проверить принадлежность построенной булевой функции к замкнутым классам Поста: .

  x. Можно ли через эту функцию выразить все остальные булевы функции.

4.  Построить машину Тьюринга, которая вычисляет функциюв алфавите восьмеричной системы счисления.

5.  Построить порождающую грамматику для языка

2.2. Второй вариант

1.  Отношение задано на множестве целых чисел . Для каждого из следующих отношений

  i.  проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;

  ii.  построить матрицы и графы этих отношений;

  iii.  определить являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;

  iv.  для отношений эквивалентности построить классы эквивалентности;

  v.  для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строго порядка;

  vi.  построить транзитивные замыкания всех отношений.

и имеют одинаковые остатки при делении на 3;

в наборе имеется элемент, больший , но меньший ;

в наборе имеется элемент , такой что ;

каждая из цифр числа больше цифры числа , стоящей в соответствующем разряде;

.

2.  Будет ли логичным следующее рассуждение: Таможенные чиновники обыскивают всякого, кто въезжает в страну, кроме высокопоставленных лиц. Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, также способствовавшими провозу наркотиков. Никто из высокопоставленных лиц не способствовал провозу наркотиков. Следовательно, некоторые из таможенников способствовали провозу наркотиков.

3.  Провести исследование булевой функции:

  i. Составить таблицу истинности

  ii. Построить по таблице истинности СКНФ.

  iii. Построить по таблице истинности СДНФ.

  iv. Построить минимальную ДНФ методом минимизирующих карт.

  v. По минимальной ДНФ нарисовать схему логического устройства, описываемого исходной булевой функцией и состоящего из элементов "и", "или", "не".

  vi. Определить, какая функция двух переменных задается выражением двумя способами: построив таблицу значений и упростив данное выражение с помощью алгебраических преобразований;

  vii. Построить для заданной булевой функции многочлен Жегалкина двумя способами.

  viii. Построить по исходной формуле двойственную. Упростить выражение. Построить таблицу двойственной функции по таблице исходной.

  ix. Проверить принадлежность построенной булевой функции к замкнутым классам Поста: .

  x. Можно ли через эту функцию выразить все остальные булевы функции.

4.  Построить машину Тьюринга, вычисляющую функциюв алфавите семеричной системы счисления.

5.  Построить порождающую грамматику для языка

3. Вопросы для зачета

Свойства бинарных отношений. Способы задания. Отношение эквивалентности. Метод раскраски. Отношение порядка. Алгоритм топологической сортировки. Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла. Высказывания и операции над ними. Формулы логики высказываний. Интерпретация. Равносильность и законы логики высказываний. Логическое следствие. Нормальные формы в логике высказываний. Контактные схемы. Метод минимизирующих карт. Замкнутость и полнота. Самодвойственные, монотонные функции. Линейные функции. Полиномы Жегалкина. Критерий полноты Поста. Метод резолюций в логике высказываний. Стратегии метода резолюций. Конечный автомат. Машины Тьюринга. Основные понятия. Проблема останова машины Тьюринга. Рекурсивные функции. Нормальные алгоритмы Маркова. Языки и грамматики. Классификация грамматик по Хомскому. Контекстно-свободные грамматики. Автоматные грамматики и языки. Синтаксические анализаторы.

4. Список литературы

Теория автоматов. СПб.: Питер, 2003. Клини. С. Математическая логика. М.: Мир, 1978. , Адельсон- Дискретная математика для инженера. М.: Энергоатомиздат, 1988. , Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984. , , Математическая логика. М.: Лань, 1999 Алгоритмы и рекурсивные функции. М.: Наука, 1965. , Теория алгорифмов. М.: Наука, 1984. Введение в математическую логику. - М.: Наука, 1984. , Курс дискретной математики. М.: Изд-во МАИ, 1992. Дискретная математика для программистов. СПб.: Питер, 2005. Ли. Р. Математическая логика и автоматическое доказательство теорем. М.: Мир, 1983.

5. Учебные пособия издательства СПбГЭТУ «ЛЭТИ»

Н., Математическая логика и теория алгоритмов. Учебное пособие. СПб.: Издательство СПбГЭТУ «ЛЭТИ», 2004, Н., Компьютерная математика. Учебное пособие. СПб.: Издательство СПбГЭТУ «ЛЭТИ», 2005.

6. Интернет – ссылки

http://www. ipo. *****/zao/