Математическая логика - ДЗ
.pdfМАТЕРИАЛЫ для СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ СПбГЭТУ (ЛЭТИ)
Курс "Математическая логика и теория алгоритмов"
Кафедра ВМ-2 Курс 3 Семестр 5
Санкт-Петербург
2015
Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Последняя редакция 09.01.2015
1.Программа курса
1.Множества и отношения
a.Бинарные отношения. Способы задания.
b.Отношение эквивалентности. Метод раскраски.
c.Отношение порядка. Алгоритм топологической сортировки.
d.Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла.
2.Алгебра высказываний и булевы функции
a.Формулы логики высказываний. Равносильность.
b.Логическое следствие.
c.Нормальные формы в логике высказываний (СДНФ и СКНФ).
d.Контактные схемы.
e.Минимизация формул логики высказываний.
f.Самодвойственные, монотонные булевы функции
g.Линейные булевы функции. Полиномы Жегалкина
h.Критерий полноты Поста.
i.Метод резолюций.
j.Стратегии метода резолюций.
3.Автоматы, машины Тьюринга и рекурсивные функции
a.Конечный автомат.
b.Машины Тьюринга. Операции над машинами Тьюринга.
c.Рекурсивные функции.
d.Нормальные алгоритмы Маркова.
e.Конечные автоматы-распознаватели.
4.Языки и грамматики
a.Языки и грамматики. Основные определения
b.Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы.
c.Автоматные грамматики и языки.
d.Проектирование синтаксических анализаторов.
e.Грамматики и алгоритмы обработки скобочных записей.
2.Контрольные работы
2.1. Первый вариант
1.Отношение задано на множестве целых чисел 53, 43, 54, 42, 44, 60, 50, 20 . Для каждого из следующих отношений:
Курс «Математическая логика и теория алгоритмов», кафедра ВМ-2, курс 3, семестр 5 |
2 |
Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Последняя редакция 09.01.2015
i.проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;
ii.построить матрицы и графы этих отношений;
iii.определить являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;
iv.для отношений эквивалентности построить классы эквивалентности;
v.для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строго порядка;
vi.построить транзитивные замыкания всех отношений.
xRy xQy
x и y имеют одинаковые остатки при делении на 3; в наборе имеется элемент, больший x , но меньший
y
;
2.Будет ли логичным следующее рассуждение: Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен и волнения не прекратятся до тех пор, пока участникам волнений это не надоест, и власти не начнут примирительные действия. Следовательно, если губернатор не желает взять на себя ответственность и участникам волнений это не надоест, то волнения не прекратятся.
3. Провести исследование булевой функции
f (x, y, z) ((zx) (z x))((x
y)(z
y))
:
a.построить таблицу функции; ответ записать в виде набора значений, упорядоченного в соответствии с лексикографическим порядком набора аргументов;
b.построить СДНФ этой функции; ответ записать, упорядочив элементарные конъюнкции в лексикографическом порядке;
c. |
упростить полученное выражение с помощью метода минимизирующих карт, |
|
ответ записать в виде минимальной ДНФ; |
d. |
построить многочлен Жегалкина исходной функции; |
e.построить таблицу двойственной функции; ответ записать в виде упорядоченного набора значений;
f.построить СКНФ двойственной функции; ответ записать, упорядочив элементарные дизъюнкции в лексикографическом порядке;
g.проверить исходную функцию на принадлежность основным классам замкнутости
T0 ,T1 , L, M, S;
h.Можно ли через эту функцию выразить все остальные булевы функции.
4.Машина Тьюринга имеет алфавит из трех символов {2,1,*} (символ означает отсутствие символа на ленте), два состояния {q0, q2}, из которых q0 – начальное состояние, q2 – конечное. Символ R означает сдвиг читающей головки вправо по ленте, L – влево, E – головка остается на месте. В начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором: q02 –> q01 R; q01 –> q01 L; q0* –> q21 E. Какой результат даст машина на наборе 22122?
Курс «Математическая логика и теория алгоритмов», кафедра ВМ-2, курс 3, семестр 5 |
3 |
Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Последняя редакция 09.01.2015
5. |
Построить конечный автомат, распознающий язык L над алфавитом a, b |
||||
|
не содержат двух букв b подряд. |
|
|
|
|
6. |
n |
n |
c |
n |
,n 0 . |
Построить порождающую грамматику для языка L a |
b |
|
|||
7. |
Дана инфиксная скобочная форма записи арифметического выражения: |
||||
|
a b *c d e f |
|
|
|
|
Перевести ее в постфиксную форму.
, слова которого
2.2. Второй вариант
1.Отношение задано на множестве целых чисел следующих отношений:
53, 43,
54,
42,
44,
60,
50,
20
. Для каждого из
i.проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;
ii.построить матрицы и графы этих отношений;
iii.определить являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;
iv.для отношений эквивалентности построить классы эквивалентности;
v.для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строго порядка;
vi.построить транзитивные замыкания всех отношений.
xGy |
каждая из цифр числа x больше цифры числа |
разряде; |
|
xSy x y 5 . |
|
y
, стоящей в соответствующем
2.Будет ли логичным следующее рассуждение: Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.
3. Провести исследование булевой функции
f
(x, y, z) ((z
y) x)((xy) (z
x))
:
a.построить таблицу функции; ответ записать в виде набора значений, упорядоченного в соответствии с лексикографическим порядком набора аргументов;
b.построить СДНФ этой функции; ответ записать, упорядочив элементарные
|
конъюнкции в лексикографическом порядке; |
c. |
упростить полученное выражение с помощью метода минимизирующих карт, |
|
ответ записать в виде минимальной ДНФ; |
d. |
построить многочлен Жегалкина исходной функции; |
e.построить таблицу двойственной функции; ответ записать в виде упорядоченного набора значений;
f.построить СКНФ двойственной функции; ответ записать, упорядочив элементарные дизъюнкции в лексикографическом порядке;
Курс «Математическая логика и теория алгоритмов», кафедра ВМ-2, курс 3, семестр 5 |
4 |
Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Последняя редакция 09.01.2015
g. проверить исходную функцию на |
принадлежность основным классам |
замкнутости T0 ,T1 , L, M, S; |
|
h.Можно ли через эту функцию выразить все остальные булевы функции.
4.Машина Тьюринга имеет алфавит из трех символов {2,1,*} (символ означает отсутствие символа на ленте), два состояния {q0, q2}, из которых q0 – начальное состояние, q2 –
конечное. Символ |
R |
означает сдвиг читающей головки вправо по ленте, |
L |
– влево, |
E |
– |
|
|
|
головка остается на месте. В начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором: q02 –> q01 R; q01 –> q02 L; q0* –> q22 E. Какой результат даст машина на наборе 22122?
5.Построить конечный автомат, распознающий язык L над алфавитом которого кратна трем.
a, b
, длина слов
6.Построить порождающую грамматику для языка L ac n cb n , n 0
7.Дана инфиксная скобочная форма записи арифметического выражения:
a b *c |
d e f |
Перевести ее в постфиксную форму.
3.Вопросы для зачета
1.Свойства бинарных отношений. Способы задания.
2.Отношение эквивалентности. Метод раскраски.
3.Отношение порядка. Алгоритм топологической сортировки.
4.Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла.
5.Высказывания и операции над ними.
6.Формулы логики высказываний. Интерпретация.
7.Равносильность и законы логики высказываний.
8.Логическое следствие.
9.Нормальные формы в логике высказываний.
10.Контактные схемы.
11.Метод минимизирующих карт.
12.Замкнутость и полнота.
13.Самодвойственные, монотонные функции.
14.Линейные функции. Полиномы Жегалкина.
15.Критерий полноты Поста.
16.Метод резолюций в логике высказываний.
17.Стратегии метода резолюций.
18.Машины Тьюринга. Основные понятия.
19.Проблема останова машины Тьюринга.
20.Рекурсивные функции.
21.Нормальные алгоритмы Маркова.
22.Языки и грамматики. Классификация грамматик по Хомскому.
23.Контекстно-свободные грамматики.
Курс «Математическая логика и теория алгоритмов», кафедра ВМ-2, курс 3, семестр 5 |
5 |
Материалы для студентов заочного отделения СПбГЭТУ (ЛЭТИ). Последняя редакция 09.01.2015
24.Грамматики и алгоритмы обработки скобочных записей.
25.Автоматные грамматики и языки.
26.Синтаксические анализаторы.
27.Конечные детерминированные автоматы-распознаватели.
4.Список литературы
1.Поздняков С.Н., Рыбин С.В. Дискретная математика. М.: Издательский центр
«Академия», 2007.
2.Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003.
3.Клини. С. Математическая логика. М.: Мир, 1978.
4.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.:
Энергоатомиздат, 1988.
5.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984.
6.Лихтарников Л.М., Сукачева Т.Г., Математическая логика. М.: Лань, 1999
7.Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965.
8.Марков А.А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984.
9.Мендельсон Э. Введение в математическую логику. - М.: Наука, 1984.
10.Нефедов В.Н., Осипова В. А. Курс дискретной математики. М.: Изд-во МАИ, 1992.
11.Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2005.
12.Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.
М.: Мир, 1983.
5.Учебные пособия издательства СПбГЭТУ «ЛЭТИ»
1.Поздняков С.Н., Рыбин С.В. Математическая логика и теория алгоритмов. Учебное пособие. СПб.: Издательство СПбГЭТУ «ЛЭТИ», 2004.
2.Поздняков С.Н., Рыбин С.В. Компьютерная математика. Учебное пособие. СПб.:
Издательство СПбГЭТУ «ЛЭТИ», 2005.
Курс «Математическая логика и теория алгоритмов», кафедра ВМ-2, курс 3, семестр 5 |
6 |