Контрольная работа / Контрольная.doc
Федеральное агентство по образованию
Пермский государственный технический университет
Кафедра информационных технологий и автоматизированных систем
Контрольная работа
по дисциплине
Математическая логика
Вариант №3
Выполнил:студентгр.АСУз-05-1уск
Мартемьянов С.Н.
Проверил: Файзрахманов Р.А.
Пермь 2007
1. Комбинаторика
2.2 Бросают три игральные кости (с шесть гранями каждая). Сколькими способами они могут упасть так, что либо все оказавшиеся вверху грани одинаковы, либо все попарно различны?
6 вариантов, когда все одинаковы и 6*5*4=120, когда все попарно различны
Итого: 126 вариантов
6.5. Предложить алгоритм бесповторного перечисления всех (n,n) перестановок чисел 1,2,…,n.
Может быть n вариантов первой цифры, n-1 второй и т.д. Следовательно число вариантов равно
1*2*3*…*n=n!
2. Графы
3. Записать следующие графы матрицами инцидентности и смежности.(Рис.3.).
|
а) б) в)
| Х1 | Х2 | Х3 | Х4 | Х5 | |
| Х1 | 0 | 1 | 0 | 0 | 0 |
| Х2 | 1 | 0 | 1 | 0 | 0 |
| Х3 | 0 | 1 | 0 | 1 | 0 |
| Х4 | 0 | 0 | 1 | 0 | 1 |
| Х5 | 0 | 0 | 0 | 1 | 0 |
а)матрица инцидентности матрица смежности
| Е1 | Е2 | Е3 | Е4 | |
| Х1 | 1 | 0 | 0 | 0 |
| Х2 | 1 | 0 | 0 | 1 |
| Х3 | 0 | 0 | 1 | 1 |
| Х4 | 0 | 1 | 1 | 0 |
| Х5 | 0 | 1 | 0 | 0 |
б)матрица инцидентности матрица смежности
| Х1 | Х2 | Х3 | Х4 | Х5 | |
| Х1 | 0 | 1 | 0 | 0 | 0 |
| Х2 | 1 | 0 | 1 | 0 | 0 |
| Х3 | 0 | 1 | 0 | 1 | 0 |
| Х4 | 0 | 0 | 1 | 0 | 1 |
| Х5 | 0 | 0 | 0 | 1 | 0 |
| Е1 | Е2 | Е3 | Е4 | |
| Х1 | 1 | 0 | 0 | 0 |
| Х2 | 1 | 1 | 0 | 0 |
| Х3 | 0 | 1 | 1 | 0 |
| Х4 | 0 | 0 | 1 | 1 |
| Х5 | 0 | 0 | 0 | 1 |
в)матрица инцидентности матрица смежности
| Х1 | Х2 | Х3 | Х4 | Х5 | |
| Х1 | 0 | 1 | 0 | 0 | 0 |
| Х2 | 0 | 0 | 0 | 0 | 0 |
| Х3 | 0 | 1 | 0 | 0 | 0 |
| Х4 | 0 | 0 | 1 | 0 | 0 |
| Х5 | 0 | 0 | 0 | 1 | 0 |
| Е1 | Е2 | Е3 | Е4 | |
| Х1 | -1 | 0 | 0 | 0 |
| Х2 | +1 | +1 | 0 | 0 |
| Х3 | 0 | -1 | +1 | 0 |
| Х4 | 0 | 0 | -1 | +1 |
| Х5 | 0 | 0 | 0 | -1 |
8. Даны графы типа дерева на рис.7. Для каждого графа выполнить следующее задание. Сколько вершин максимального типа имеется в данном графе? Какое цикломатическое число графа? Чему равно цикломатическое число графа G', являющегося лесом и представленного двумя одинаковыми деревьями рассматриваемого типа графа? Построить ориентированное дерево с корнем n0, являющимся вершиной максимального типа.
Рис. 7
Цикломатическое число v(G)= m-n+1
m- кол-во ребер
n- кол-во вершин
G1)v(G)=20-20+1 =1
G2)v(G)=18-19+1 =0 => G2 уже дерево
G3)v(G)=18-19+1 =0 => G3 уже дерево
Кол-во вершин максимального типа:
G1)7
G2)4
G3)2
Цикломатическое число леса:
G1)1*2=2
G2)0*2=0
G3)0*2=0
Ориентированные деревья:
20. Найти ядро графа с помощью алгоритмов Магу (рис. 4.12).
1.Найдем множества внутренней устойчивости:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | ||||
| 4 | 1 | ||||
| 5 | 1 |
(1v3)(1v4)(2v4)(2v5)(3v5)
Перейдем к ДНФ
123v125v145v234v345
Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.
{4,5},{3,4},{2,3},{1,5},{1,2}
2.Найдем множества внешней устойчивости:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | 1 | |||
| 2 | 1 | 1 | |||
| 3 | 1 | 1 | |||
| 4 | 1 | 1 | |||
| 5 | 1 | 1 |
(1v3)(2v4)(3v5)(1v4)(2v5)
Перейдем к ДНФ
123v125v145v234v345
{1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5}
Совпадающих множеств нет.
21. Привести граф к яруcно-параллельной форме (рис. 4.13).
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | ||||||
| 2 | ||||||
| 3 | 1 | |||||
| 4 | 1 | 1 | 1 | |||
| 5 | ||||||
| 6 | 1 | 1 | 1 | 1 |
6
4
1 5 5
2
28. Используя метод Магу, определить максимально внутренне устойчивые, а также минимально внешне устойчивые множества вершин орграфов и найти их ядра.
v1 v2
v3 v4
1.Найдем множества внутренней устойчивости:
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | ||
| 2 | ||||
| 3 | 1 | 1 | ||
| 4 | 1 |
(1v2)(1v3)(2v3)(3v4)
Перейдем к ДНФ
13v23v124
Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.
{2,4},{1,4},{3}
2.Найдем множества внешней устойчивости:
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | 1 | |
| 2 | 1 | |||
| 3 | 1 | 1 | 1 | |
| 4 | 1 | 1 |
(1v2v3)(2)(2v3v4)(3v4)
Перейдем к ДНФ
23v24
{2,3},{2,4}
{2,4} ядро графа
3. Резолюции
1. Необходимо ответить, являются ли следующие конструкции термами
max (x,y,z), å(x,y), (x±y), .
Все конструкции — термы, т.к. являются функциями
2. Необходимо ответить, являются ли следующие конструкции формулами
Ø P(x); "х P(x)
Все конструкции являются формулами, т.к P(x)это атом.
3. Являются ли выполнимыми следующие формулы? P(a)ÚØ P(a);
Формула является выполнимой т.к. результат 1.
31. Получить множество дизъюнктов.
1) "x, y, z (P(x)&Q(x, y)ÚØR(z))
Приведем к конъюктивной нормальной форме
"x, y, z ((P(x) ÚØR(z))&(Q(x, y)ÚØR(z)))
Кванторов существования нет, а кванторы общности можно отбросить
(P(x) ÚØR(z)),(Q(x, y)ÚØR(z))
2) $x, y, z (P(x)ÚØQ(x, y)®R(z)ÚM(y))
Избавимся от импликации:
$x, y, z (Ø(P(x)ÚØQ(x, y))ÚR(z)ÚM(y))
Приведем к конъюктивной нормальной форме
$x, y, z ((ØP(x)&Q(x, y))ÚR(z)ÚM(y))
Т.к. есть квантор существования, и левее нет кванторов общности, то заменяем хi на константу k.
(ØP(k)&Q(k, y))ÚR(z)ÚM(y)
4. Машины Тьюринга
3. Построить машину Т, сдвигающую головку вправо на следующий массив единиц, который будет обнаружен на ленте: l1q1lx1yl ® l1lx1y-1q01l (машина находит следующий справа массив единиц и останавливается, воспринимая самую правую заполненную ячейку).
| q1 | q2 | |
| 1 | Q21П | Q21П |
| l | Q1lП | Q0lЛ |
8. По заданной машине Т и начальной конфигурации М1 найти заключительную конфигурацию .