- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
259
4)(конечную ленту)&(бесконечный внешний алфавит)&(конечный внутренний алфавит);
5)(конечную ленту)&(конечный внешний алфавит)&(бесконечный внутренний алфавит).
9.Арифметическая функция f(x,y) = x+y
1)(не вычислима по Тьюрингу)&(вычислима по Маркову)&(является общерекурсивной);
2)(вычислима по Тьюрингу)&(вычислима по Маркову)&(является общерекурсивной);
3)(не вычислима по Тьюрингу)&(не вычислима по Маркову) &(является общерекурсивной);
4)(не вычислима по Тьюрингу)&(не вычислима по Маркову) &(не является общерекурсивной);
5)(вычислима по Тьюрингу)&(вычислима по Маркову)&(не является общерекурсивной).
10.Укажите, какая из перечисленных ниже проблем является алгоритмически разрешимой
1)проблема диофантовых корней,
2)проблема эквивалентности слов,
3)проблема остановки,
4)проблема разрешимости логики предикатов,
5)проблема нахождения решения задачи коммивояжёра.
Тест по неклассическим логикам и сложности вычислений (тест № 6)
1. Конъюнкция и дизъюнкция в трехзначной логике Лукасевича, вводятся следующим образом:
1) |
х&у=max(х,у), |
х у=min(х,у); |
2) |
х&у= min(х,у), |
х у= max(х,у); |
3) |
х&у= х×у(mod 3), |
х у= х+у(mod 3); |
4) |
х&у=(х у)+1(mod 3), |
х у= max(х,у); |
5)х&у= min(1, max(х,у)), х у= max(1, min(х,у)).
2.Число различных функций k – значной логики, зависящих от n переменных
равно |
2) nk |
3) kn |
|
|
1) n×k |
4) k k n |
5) nnk |
3. Рассмотрим k значную (k>2) логику Поста, где циклическое отрицание введено как х=х+1 (mod k), а отрицание Лукасевича как Nx=k-1-x. Укажите, какое утверждение истинно
1)N(Nx) = х и ( х) = х;
2)N(Nx) ≠ х и ( х) = х;
3)N(Nx) = х и ( х) ≠ х;
260
4)N(Nx) ≠ х и ( х) ≠ х;
5)N(Nx) ≠ ( х) ≠ х.
4.Рассмотрим k значную логику Поста, где переменные принимают значения 0, 1, …k-1. Импликация в этой логике вводится следующим образом:
k −1, |
если 0 ≤ x < y ≤ k −1, |
|
x y= |
( k −1) − x + y, |
если 0 ≤ y ≤ x ≤ m −1. |
|
Пусть k=3. Обозначим значения 0, 1, и 2 через 0, ½ и 1 соответственно. Укажите, какое из следующих утверждений истинно.
1)эта импликация совпадает с дизъюнкцией логики Рейхенбаха;
2)эта импликация совпадает с импликацией логики Бочвара;
3)эта импликация совпадает с импликацией логики Клини;
4)эта импликация совпадает с импликацией логики Гейтинга;
5)эта импликация совпадает с импликацией логики Лукасевича.
5.Пусть задана лингвистическая переменная, описываемая набором:
(Х, Т(Х), U, G , М)
вкотором:
Х- название лингвистической переменной,
Т(Х) - множество лингвистических значений переменной Х, U - универсальное множество,
G - синтаксические правила, порождающие названия переменной, т.е. правила определения синтаксических значений,
М - семантические правила, которые ставят в соответствие каждой нечеткой переменной ее смысл М(Х), т.е. характеристическую функцию для
Х.
Укажите, какое из следующих утверждений истинно
1)U – нечеткое множество, а Т(Х) – обычное множество;
2)U – обычное множество, а Т(Х) – нечеткое множество;
3)U – нечеткое множество и Т(Х) – нечеткое множество;
4)U и Т(Х) – обычные множества;
5)U – обычное конечное множество, а Т(Х) – обычное бесконечное множество.
6.Пусть]х[ обозначает наименьшее целое q, такое, что q ≥x. Укажите, каково минимальное число символов нужно для представления числа n, заданного в десятичной системе счисления
1) n |
2) ln(n) |
3) ]log(n)[ |
4) ln(log(n)) |
5) ]ln(n)[ |
7. Укажите, какой наименьший порядок (из записанных) имеет размер представления в ЭВМ графа с n вершинами и m ребрами
|
|
|
|
|
|
|
|
|
1) 0(n |
× |
m) |
2) |
0(ln(n)) |
3) 0(mn) |
× |
log(n)) |
5) 0(nm) |
|
|
|
|
4) 0(m |
|
261
8.Рассмотрим задачу о минимальном соединении. Дано n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. На языке теории графов эта задача формулируется следующим образом. Дан полный граф с n вершинами и известны длина каждого ребра. Требуется найти остовный подграф (связный подграф без циклов, содержащий все вершины исходного графа) имеющий минимальную длину, т.е. имеющий минимальную сумму длин ребер.
Эту задачу можно решить, перебирая все остовные подграфы данного полного графа, и выбирая тот остовный подграф который имеет
минимальную длину. Известно, что число всех остовных подграфов полного графа равно n(n-2). Кроме алгоритма перебора всех остовных подграфов данного графа, указанную задачу можно решить, так называемым жадным алгоритмом, число шагов которого есть 0(n log(n)).
Укажите, какое из следующих утверждений истинно
1)задача о минимальном соединении имеет экспоненциальную временную сложность;
2)задача о минимальном соединении имеет полиномиальную временную сложность;
3)алгоритм перебора всех остовных подграфов данного графа имеет полиномиальную временную сложность;
4)жадный алгоритм имеет линейную временную сложность;
5)жадный алгоритм имеет экспоненциальную временную сложность.
9.Проблема выяснения выполнимости произвольной формулы А логики высказываний (пропозициональной формы), представленной в конъюнктивной нормальной форме,
1)является алгоритмически неразрешимой;
2)не является NP – полной задачей;
3)является NP - полной задачей;
4)является задачей, не принадлежащей классу NР;
5)является задачей, не имеющей решения.
10.Укажите, какое из следующих утверждений ложно
1)задача является NP полной, если она входит в NP и каждая задача из NP полиномиально сводится к ней;
2)NP класс задач содержит задачи которые можно решить недетерминированными алгоритмами, работающими в течении полиномиального времени;
3)задача является NP трудной, если каждая задача из NP полиномиально сводится к ней;
4)если одновременно задача Z1 полиномиально сводится к задаче Z2 и Z2 полиномиально сводится к задаче Z1, то задачи Z1 и Z2 полиномиально эквивалентны;