математическая логика и теория алгоритмов


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ

КАФЕДРА
«Высшая математика»







РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
ПО УЧЕБНОЙ ДИСЦИПЛИНЕ
«Математическая логика и теория алгоритмов»

Специальность: 230100.62 «Информатика и вычислительная техника»






Москва
2010
УДК
К-72

Обсуждена и одобрена на заседании кафедры «Высшая математика» Московского государственного университета технологий и управления (протокол № 4 от 23 декабря 2009 г.).
Одобрена и рекомендована к изданию учебно-методическим советом Московского государственного университета технологий и управления (протокол № ___ от «____» 200 г.)
Одобрена и рекомендована к утверждению на заседании ученого совета института «Системной автоматизации и инноватики» Московского государственного университета технологий и управления (протокол № 8 от 24 декабря 2009г.).

Составитель:
Садыкова Альбина Рифовна – к.п.н., доцент, кафедра «Высшая математика» МГУТУ

Рецензенты:
Копанева Анна Александровна – к.ф-м.н., доцент кафедры «Высшая математика»

Садыкова А.Р.
Математическая логика и теория алгоритмов: рабочая учебная программа. М.: МГУТУ, 2010. – 25 с.

Рабочая учебная программа учебной дисциплины «Математическая логика и теория алгоритмов» цикла ОПД составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 230100 «Информатика и вычислительная техника». Предназначена для студентов всех форм обучения.

© Московский Государственный университет
технологий и управления, 2010.
109004, Москва, Земляной вал, 73
© Садыкова А.Р.
СОДЕРЖАНИЕ

1. Организационно-методический раздел 4

1.1. Цели и задачи изучения дисциплины 4
1.2. Содержание дисциплины 4
1.3. Объем часов по видам учебной нагрузки 4
1.4. Тематические планы изучения учебной дисциплины 7

2. Учебно-методическое обеспечение дисциплины 13

2.1. Методические указания по выполнению курсовых,
контрольных работ 13
2.2. Задания для самостоятельной работы студентов 20
(вопросы для самоконтроля знаний студентов, тестовые задания, вопросы для подготовки к экзамену и (или) зачету)
2.3. Основная литература 24
2.4. Дополнительная литература 25





























1. Организационно-методический раздел
1.1. Цели и задачи изучения дисциплины
Целью курса является приобретение навыков работы с дискретными структурами, умения подсчитывать число комбинаторных объектов различной природы, а также получение представления о принципах помехоустойчивого и криптографического кодирования.
1.2. Содержание дисциплины
Канторова теория множеств.
Логика высказываний и логика предикатов, булевы функции.
Машина Тьюринга и понятие алгоритма.
Графы и алгоритмы на графах: паросочетание, кратчайший путь, минимальное основное дерево, задача коммивояжера.
Матроиды, жадный алгоритм.
Алгоритмы полиномиальной и экспоненциальной сложности. Классы P и NP, NP – полные задачи.

1.3. Объем часов по видам учебной нагрузки

Специальность
2202
Объем в часах по плану
Количество


всего
лекции
практика
Экз.
Зач.
Контр. работа

Очная полная
72
36
36
-
1
-

Очная сокращенная
52
24
28
-
1
-

Очно-заочная полная
56
24
32
-
1
-

Очно-заочная сокращенная
40
16
24
-
1
-

Заочная полная
32
20
12
-
1
-

Заочная соращкнная
20
12
8
-
1
1


Самостоятельная работа студентов по курсу «Математическая логика и теория алгоритмов».
Наименование дисциплины

Форма обучения

Виды самостоятельной работы
СФО, час
ПФО, час



СФО

ПФО





Курс
Кол-во часов
Курс
Кол-во часов




ДФО
I
48
II
28
1. Освоение теоретических основ дисциплины.
18
6






2. Решение задач.
5
5






3. Подготовка к выполнению контрольных работ.
5
5






4. Выполнение контрольной работы.
5
5






5. Подготовка к зачету.
15
7

ВФО
I
60
II
44
1. Освоение теоретических основ дисциплины.
20
16






2. Решение задач.
5
5






3. Подготовка к выполнению контрольных работ.
10
5






4. Выполнение контрольной работы.
5
5






5. Подготовка к зачету.
20
13

ЗФО
I
80
I
68
1. Освоение теоретических основ дисциплины.
20
13






2. Решение задач.
15
15






3. Подготовка к выполнению контрольных работ.
15
10






4. Выполнение контрольной работы.
20
20






5. Подготовка к зачету.
10
10







1.4. Тематические планы изучения учебной дисциплины
ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ 2 КУРСА ДНЕВНОГО ФАКУЛЬТЕТА ПОЛНОЙ ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Множества. Мощность. Счетность рациональных чисел. Нечетность действительных чисел, диагональный метод Кантора. Мощность множества подмножеств.
4
4

2
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
4
4

3
Кванторы и Предикаты. Логика высказываний и логика предикатов.
4
4

4
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
4
4

5
Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).
2
2

6
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
4
4

7
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
2
2

8
Замкнутые классы. Полнота. Теорема Поста.
4
4

9
Алгоритмически неразрешимые проблемы.
2
2

10
Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.
6
6


ВСЕГО:
36
36

ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ
вечернего ФАКУЛЬТЕТА сокращенной ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
4
4

2
Кванторы и Предикаты. Логика высказываний и логика предикатов.
3
4

3
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
2
4

4
Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).
1
2

5
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
2
4

6
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
1
2

7
Полнота. Теорема Поста.
2
2

8
Алгоритмически неразрешимые проблемы.
1
2


ВСЕГО:
16
24







ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ
вечернего ФАКУЛЬТЕТА полной ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
4
4

2
Кванторы и Предикаты. Логика высказываний и логика предикатов.
4
4

3
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
2
4

4
Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).
2
2

5
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
4
4

6
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
2
4

7
Полнота. Теорема Поста.
2
2

8
Алгоритмически неразрешимые проблемы.
2
4

9
Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.
2
4


ВСЕГО:
24
32





ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ 2 КУРСА ДНЕВНОГО ФАКУЛЬТЕТА сокращенной ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
4
4

2
Кванторы и Предикаты. Логика высказываний и логика предикатов.
4
4

3
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
2
4

4
Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).
2
2

5
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
4
4

6
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
2
4

7
Полнота. Теорема Поста.
2
2

8
Алгоритмически неразрешимые проблемы.
2
2

9
Алгоритм полиномиальной и экспоненциальной сложности. Классы P и NP. Выполнимость К.Н.Ф. NP – полные задачи.
2
2


ВСЕГО:
24
28






ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ заочного ФАКУЛЬТЕТА полной ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
4
2

2
Кванторы и Предикаты. Логика высказываний и логика предикатов.
4
2

3
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
4
2

4
Эффективность алгоритма. Линейное упорядочивание массива за время О (n long).
1
0,5

5
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
2
2

6
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
2
0,5

7
Полнота. Теорема Поста.
2
2

8
Алгоритмически неразрешимые проблемы.
1
1


ВСЕГО:
20
12







ТЕМАТИЧЕСКИЙ ПЛАН ЗАНЯТИЙ СО СТУДЕНТАМИ заочного ФАКУЛЬТЕТА сокращенной ФОРМЫ ОБУЧЕНИЯ


ТЕМА
ЛЕКЦИИ
ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

1
Булевы функции. Операции 13 EMBED Equation.3 1415. Правило де Моргана. Двойственность, К.Н.Ф. и Д.Н.Ф.
2
2

2
Кванторы и Предикаты. Логика высказываний и логика предикатов.
2
2

3
Машина Тьюринга и понятие алгоритма. Неразрешимость проблемы останова.
2
2

4
Графы: планарные, регулярные, эйлеровы, гамильтоновы, ориентированные, циклы, деревья, клики, независимые множества, вершинное покрытие.
2
0,5

5
Алгоритмы на графах: кратчайший путь, минимальное остовное дерево. Задача коммивояжера – метод ветвей и границ.
2
0,5

6
Замкнутые классы. Полнота. Теорема Поста.
2
1


ВСЕГО:
12
8









2. Учебно-методическое обеспечение дисциплины.
2.1. Методические указания и задания для контрольных работ студентам специальности 230102 заочной формы обучения.

Предисловие

Целью домашней контрольной работы является закрепление студентами знаний, полученных на лекциях и практических занятиях, а также развития навыков самостоятельного решения задач.
Предусматривается выполнение одной контрольной работы содержащей 9 заданий по 10 вариантам. Вариант выбирается в соответствии с последней цифрой номера зачетной книжки.
Контрольная работа должна быть сделана в отдельной тетради, обложка которой оформляется согласно принятому в МГУТУ образу (обращаться в деканат).
Решению задачи должно предшествовать условие.
Контрольная работа сдается в деканат.

2. Примеры решения типовых задач

Пример 1: Доказать: 13 EMBED Equation.3 1415.
Доказательство: Пусть 13 EMBED Equation.3 1415. Тогда 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Если 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415, а значит, 13 EMBED Equa
·tion.3 1415. Если 13 EMBED Equation.3 1415, то имеем , а значит, 13 EMBED Equation.3 1415. Итак, 13 EMBED Equation.3 1415. Пусть 13 EMBED Equation.3 1415. Если 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Отсюда следует, что 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, т.е. 13 EMBED Equation.3 1415. Если 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Отсюда следует, что 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, т.е. 13 EMBED Equation.3 1415. Итак, 13 EMBED Equation.3 1415. Итак, 13 EMBED Equation.3 1415.
Пример 2: С помощью таблицы покажите упорядоченные пары бинарного отношения 13 EMBED Equation.3 1415 на множествах 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.

Решение. :
13 EMBED Equation.3 1415
Пример 3: Покажите прямым способом, что произведение ху двух нечётных целых чисел х и у всегда нечётно.

Решение: Т.к. х и у нечётные, то 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. Получим, 13 EMBED Equation.3 1415 - нечётное, как сумме чётного числа 13 EMBED Equation.3 1415 и единицы.
Контрольная работа

С помощью диаграмм Эйлера-Вена показать результаты следующих операций:

1.1. 13 EMBED Equation.3 1415 1.6. 13 EMBED Equation.3 1415
1.2. 13 EMBED Equation.3 1415 1.7. 13 EMBED Equation.3 1415
1.3. 13 EMBED Equation.3 1415 1.8. 13 EMBED Equation.3 1415
1.4. 13 EMBED Equation.3 1415 1.9. 13 EMBED Equation.3 1415
1.5.13 EMBED Equation.3 1415 1.10. 13 EMBED Equation.3 1415

Множество R определяет отношение на множестве 13 EMBED Equation.3 1415. Найдите все упорядоченные пары ему принадлежащие:

2.1. 13 EMBED Equation.3 1415 2.6. 13 EMBED Equation.3 1415
2.2. 13 EMBED Equation.3 1415 2.7. 13 EMBED Equation.3 1415
2.3. 13 EMBED Equation.3 1415 2.8. 13 EMBED Equation.3 1415
2.4. 13 EMBED Equation.3 1415 2.9. 13 EMBED Equation.3 1415
2.5. 13 EMBED Equation.3 1415 2.10. 13 EMBED Equation.3 1415

Запишите с помощью кванторов и предикатов следующие утверждения:

3.1. «Яблоки либо сладкие, либо кислые».
3.2. «Некоторые яблоки кислые».
3.3. «Все яблоки кислые».
3.4. «Существуют прилежные и способные студенты».
3.5. «Некоторые студенты ленивые».
3.6. «Все студенты или ленивые или глупые».
3.7. «Некоторые студенты ленивые и глупые».
3.8. «Все студенты ленивые и глупые».
3.9. «Найдется умный и добросовестный студент».
3.10. Все студенты либо умные либо хитрые».

Для простых высказываний:

p: «студент сдаст экзамен».
q: «студент выполнит контрольную работу».
составить сложенные высказывания следующих видов:
4.1. 13 EMBED Equation.3 1415 4.6. 13 EMBED Equation.3 1415
4.2. 13 EMBED Equation.3 1415 4.7. 13 EMBED Equation.3 1415
4.3. 13 EMBED Equation.3 1415 4.8. 13 EMBED Equation.3 1415
4.4. 13 EMBED Equation.3 1415 4.9. 13 EMBED Equation.3 1415
4.5. 13 EMBED Equation.3 1415 4.10. 13 EMBED Equation.3 1415

Построить таблицу истинности сложного высказывания:

5.1. 13 EMBED Equation.3 1415
5.6. 13 EMBED Equation.3 1415

5.2. 13 EMBED Equation.3 1415
5.7. 13 EMBED Equation.3 1415

5.3. 13 EMBED Equation.3 1415
5.8. 13 EMBED Equation.3 1415

5.4. 13 EMBED Equation.3 1415
5.9. 13 EMBED Equation.3 1415

5.5. 13 EMBED Equation.3 1415
5.10. 13 EMBED Equation.3 1415



Доказать, что:

6.1. 13 EMBED Equation.3 1415
6.2. 13 EMBED Equation.3 1415
6.3. 13 EMBED Equation.3 1415
6.4. 13 EMBED Equation.3 1415
6.5. 13 EMBED Equation.3 1415
6.6. 13 EMBED Equation.3 1415
6.7. 13 EMBED Equation.3 1415 для 13 EMBED Equation.3 1415
6.8. 13 EMBED Equation.3 1415 для 13 EMBED Equation.3 1415
6.9. 13 EMBED Equation.3 1415 для 13 EMBED Equation.3 1415
6.10. 13 EMBED Equation.3 1415 для 13 EMBED Equation.3 1415

Заданы предикаты

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 а нравится b больше, чем с.
Используя 13 EMBED Equation.3 1415 запишите высказывания
7.1. 13 EMBED Equation.3 1415
7.2. 13 EMBED Equation.3 1415
7.3. 13 EMBED Equation.3 1415
7.4. 13 EMBED Equation.3 1415
7.5. 13 EMBED Equation.3 1415
7.6. 13 EMBED Equation.3 1415
7.7. 13 EMBED Equation.3 1415
7.8. 13 EMBED Equation.3 1415
7.9. 13 EMBED Equation.3 1415
7.10. 13 EMBED Equation.3 1415.

Доказать эквивалентности:

8.1. 13 EMBED Equation.3 1415
8.2. 13 EMBED Equation.3 1415
8.3. 13 EMBED Equation.3 1415
8.4. 13 EMBED Equation.3 1415
8.5.13 EMBED Equation.3 1415
8.6. 13 EMBED Equation.3 1415
8.7. 13 EMBED Equation.3 1415
8.8. 13 EMBED Equation.3 1415
8.9. 13 EMBED Equation.3 1415
8.10. 13 EMBED Equation.3 1415

Выяснить, применима ли машина Тьюринга, задаваемая программой П, к слову Р.


13 EMBED Equation.3 1415






9.4.
9.5.
9.6.







9.7.
9.8.
9.9.







9.10.



Замечание:
Если в программе отсутствует необходимая команда, то машина Т остановится, и говорят, что она применима к слову.

2.2. Задания для самостоятельной работы студентов
Вопросы для самопроверки
Что называется множеством?
Дайте определение пересечения множеств.
Что называют мощностью множества?
Дайте определение прямого произведения множеств.
Приведите примеры множества.
Дайте определение бинарного отношения.
Какое бинарное отношение называют транзитивным?
Приведите пример бинарного отношения.
Какое бинарное отношение называют отношением эквивалентности?
Что называют функцией?
Дайте определение высказывание.
Перечислите наиболее известные тавтологии.
Перечислите основные методы доказательств. В чем суть каждого метода?
Что такое предикат?
Какие кванторы вы знаете?
Какую функцию называют булевой?
Какое множество является областью определения и областью значений булевой функции?
Какие 3 операции над булевыми функциями задают булеву алгебру?
Дайте определение д.н.ф. и к.н.ф.
Опишите механизм упрощения д.н.ф.
21. Дайте определение понятия «алгоритм».
22. Опишите суть алгоритма Евклида для нахождения наибольшего общего делителя двух многочленов.
23.Что будет, если с помощью алгоритма Евклида находить общую меру стороны и диагонали квадрата?
24.Опишите суть модели алгоритма, называемой машиной Тьюринга.
25.Что называется конфигурацией?

26.Что значит, что машина Тьюринга применима к данному слову?
27.Какие алгоритмически неразрешимые проблемы вы знаете?

Тесты проверки знаний студентов
Тест I
Объединением множеств А и В называется множество
а)13 EMBED Equation.3 1415{13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415}; б) {13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415};
в) {13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415}; в) {13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415};
2. Какая операция над множествами А, В, и С изображена на диаграмме13 EMBED Equation.3 1415








а) 13 EMBED Equation.3 1415; б)13 EMBED Equation.3 1415; в)13 EMBED Equation.3 1415; г)13 EMBED Equation.3 1415;
Даны множества 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Результатом операции (А\В)13 EMBED Equation.3 1415С будет множество:
а) 13 EMBED Equation.3 1415; б)13 EMBED Equation.3 1415; в)13 EMBED Equation.3 1415; г){Ш}.
А={1, 2, 3}, В={а, в}. Какая пара чисел не принадлежит декартовому произведению А13 EMBED Equation.3 1415B
а) (1, а); б) (2, в); в) (3, а); г) (а, 2).
Является ли множество целых чисел счётным?
а) да; б) нет.


Тест II

На множестве А={1,3,5,7} задано бинарное отношение R={(x,y):x-y=4}. Какая из пар принадлежит данному отношению?
а) (1,3); б) (3,7); в) (5,1).
2. Какими свойствами обладает отношение “х делит у” на множестве N ?
а) рефлексивность,
б) рефлексивность,
в) только рефлексивность.

симметричность,
антисимметричность,


транзитивность;
транзитивность;


3. Элемент 13 EMBED Equation.3 1415 называется минимальным, если из 13 EMBED Equation.3 1415следует, что
а) b
4. Если из 13 EMBED Equation.3 1415следует а1=а2, то функцию называют
а) инъекцией; б) сюръекцией; в) биекцией.

5. Является ли функция ; 13 EMBED Equation.3 1415, где f (x)=x2
а) инъекцией; б) сюръекцией; в) биекцией.

Тест III
Высказыванием называется утверждение, имеющее значение: а)истина; б)ложь; в)истина или ложь.
Каким значком обозначают импликацию: а)13 EMBED Equation.3 1415; б)13 EMBED Equation.3 1415; в)13 EMBED Equation.3 1415(13 EMBED Equation.3 1415).
Для логического значка “~” принято следующие чтение: а)”или...“; б):”...если..., то...,”; в) “тогда и только тогда, когда...”.
Квантор 13 EMBED Equation.3 1415 читается: а) для всех; б)существует; в)найдется.
5.Высказывание: “существует вещественное число x, удовлетворяющее уравнению х2+1=0” в символической форме записывается:
а) 13 EMBED Equation.3 1415 б) 13 EMBED Equation.3 1415;
в)13 EMBED Equation.3 1415

Тест IV

Булевой функцией от n переменных называется функция, определенная на множестве всех двоичных наборов длины n и принимающая на каждом из них значение.
а) 0; б) 1; в) 0 или 1; г) любые целые;
Булева функция называется монотонной, если из х13 EMBED Equation.3 1415у следует
а)13 EMBED Equation.3 1415 б) 13 EMBED Equation.3 1415>13 EMBED Equation.3 1415; в) 13 EMBED Equation.3 141513 EMBED Equation.3 141513 EMBED Equation.3 1415; г)13 EMBED Equation.3 1415< 13 EMBED Equation.3 1415;
Выражение 13 EMBED Equation.3 1415 называют
а) элементарной дизъюнкцией; б) элементарной конъюнкцией.
Результатом упрощения д.н.ф. 13 EMBED Equation.3 1415 является форма:
а) 13 EMBED Equation.3 1415 б) 13 EMBED Equation.3 1415; в) 13 EMBED Equation.3 1415.
5. Функцией, двойственной к функции 13 EMBED Equation.3 1415, является
а)13 EMBED Equation.3 1415 б) 13 EMBED Equation.3 1415 в) 13 EMBED Equation.3 1415

Тест V

1) Для нахождения (48,27) алгоритма Евклида выполнит
а) 2 шага; б) 3 шага; в) 4 шага.
2) Наибольший общий делитель многочленов x2-3x+2 и x2-4x+3 равен
а) x+1; б) x-1; в) x2-1.
3) Применима ли к слову 1100 машина Тьюринга, задаваемая программой
q11 q10R
q10 q21L
q21 q01C
q20 q10R
а) применима; б) не применима.
4) Среди трех монет одна фальшивая. В результате какого наименьшего числа взвешиваний можно определить фальшивую монету
а) одного; б) двух; в) трех.


РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
2.3. Основная:
Шапорев С.Д. Матемаьтческая логика. Курс лекций и практических занятий. – СПб.: БХВ – Петербург, 2005.- 416 с.: ил.
Шелупанов А.А., Зюзьков В.М. Математическая логика и теория алгоритмов. – М.: Горячая линия – Телеком, 2007.- 176 с.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. – М.: Академия, 2007.-304 с.
Лавров И.А Математическая логика. – М.: Академия, 2006. – 240 с.

2.4. Дополнительная:
Колмагоров А.Н., Драгалин А.Г. Математическая логика. – М.: Едиториал УРСС 2004.- 240 с.
Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – 2-е изд. – М.: Физматлит, 2002. – 128 с.
Лавров И.А. Максимова Л.Л. Задачи по теории множеств математической логики и теории алгоритмов . – 4-е изд. М.: Физматлит, 2001. – 256 с











13 PAGE \* MERGEFORMAT 14115



9.1
9.2.
9.3.

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

A

B

C



Рисунок 7Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 8958369
    Размер файла: 602 kB Загрузок: 0

Добавить комментарий