Экзаменационные вопросы и задачи вопросы Множества и отношения - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Экзаменационные вопросы и задачи вопросы Множества и отношения - страница №1/1



ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ И ЗАДАЧИ

Вопросы

Множества и отношения

  1. Антиномии Рассела и Греллинга.

  2. Пустое множество, неупорядоченная пара, объединение. Натуральные числа.

  3. Декартово произведение, отношения, функции и операции.

  4. Операции над отношениями.

  5. Отношение эквивалентности и разбиения.

  6. Частично упорядоченные множества.

  7. Принцип максимальности и теорема о существовании линейного порядка, содержащего данное отношение порядка.

  8. Аксиома Цермело и принцип трансфинитной индукции.

  9. Теорема Кантора-Шредера-Бернштейна.

  10. Теорема и антиномия Кантора.

  11. Теорема о сравнении мощностей.

  12. Счетные множества и метод диагонализации.

  13. Булевы алгебры. Поле множеств.

Булевы функции

  1. Равенство булевых функций.

  2. Специальные булевы функции.

  3. Дизъюнктивные и конъюнктивные нормальные формы.

  4. Реализация функций с помощью формул и полнота системы функций.

Исчисление высказываний

  1. Исчисление высказываний, формулы, аксиомы, вывод.

  2. Вывод теоремы АА.

  3. Теорема о дедукции.

  4. Теорема о полноте исчисления высказываний.

  5. Формальная теория, вывод, теорема.

  6. Исчисление высказываний с аксиомами Клини и его равносильность теории L.

  7. Лемма о конечно выполнимом множестве.

  8. Теорема о компактности исчисления высказываний.

Теории первого порядка

  1. Термы и их унификация.

  2. Алгоритм нахождения наибольшего общего унификатора с помощью стека.

  3. Недетерминированный алгоритм решения множества уравнений.

  4. Предикаты и отношения. Кванторы, связанные и свободные вхождения.

  5. Язык первого порядка, формулы, замена переменных.

  6. Исчисление предикатов как формальная теория.

  7. Теорема о непротиворечивости исчисления предикатов.

  8. Модели языка первого порядка и их примеры.

  9. Выполнение формулы в модели.

  10. Теория первого порядка, ее модели и примеры моделей.

  11. Теория чисел и теория множеств.

  12. Лемма о вложении конечно выполнимого множества в полное конечно выполнимое множество.

  13. Теорема о компактности исчисления предикатов.

  14. Теорема Левенгейма-Скулема.

  15. Теорема Геделя о полноте теории первого порядка.

  16. Пренексная нормальная форма и удаление кванторов.

  17. Процедура резолюций Робинсона.

Нечеткая логика

  1. Нечеткие множества и их представление.

  2. Операции над нечеткими множествами и принцип обобщения.

  3. Треугольные нормы и конормы.

  4. Операции отрицания и двойственные операции.

  5. Виды нечеткой импликации.

  6. Нечеткие отношения.

  7. Нечеткие интерпретация, общезначимость, противоречивость.

  8. Принцип резолюции для нечеткой логики.

  9. Нечеткие переменные.

  10. Правила нечеткого вывода.

Модальная и темпоральная логики

  1. Модальные и темпоральные формулы.

  2. Смысловые значения модальностей.

  3. Семантика и шкала Крипке.

  4. Модели Крипке.

  5. Семантика темпоральной логики.

  6. Тавтологии и теорема о нормальности.

  7. Условные тавтологии и теорема о рефлексии.

  8. Пропозициональная алгоритмическая логика PDL.

  9. Семантика логики PDL.

  10. Аксиомы PDL.

  11. Логика Хоара.

  12. Аксиомы систем Гильберта.

  13. Строгие системы Гильберта.

  14. Свойства шкал Крипке.

  15. Теорема Салквиста.

  16. Алгоритм Салквиста.

  17. Система Гильберта для темпоральной логики.

  18. Теорема о потоке времени.

  19. Операторы «завтра» и «вчера», «Since» и «Until».

  20. Теорема Кемпа.

Алгоритмы и рекурсивные функции

  1. Простейшие функции. Операторы композиции и примитивной рекурсии.

  2. Примитивно рекурсивные функции, примеры.

  3. Оператор минимизации и частично рекурсивные функции.

  4. Машины Тьюринга и примеры их работы.

  5. Вычислимые и правильно вычислимые функции, и их примеры.

  6. Тезис Черча и алгоритмическая неразрешимость проблемы остановки.

  7. Равномерный и логарифмический весовые критерии для оценки сложности алгоритмов. Временная сложность, сложность в среднем и сложность в лучшем случае.

  8. Труднорешаемые и NP-полные задачи.
Задачи

Множества и отношения

  1. Существуют ли такие множества А, В и С, что АВ, АС=, (АВ)\С=?

  2. Сколько подмножеств имеет конечное множество, состоящее из n элементов?

  3. Пусть А и В – конечные множества, состоящие соответственно из m и n элементов. Сколько существует бинарных отношений между А и В?

  4. Построить пример частично упорядоченного множества, имеющего один минимальный элемент, но не имеющий ни одного наименьшего элемента.

  5. Доказать, что если множества I и Аi для всех iI счетны, то – счетно.

  6. Доказать, что любое множество попарно непересекающихся непустых открытых интервалов на числовой прямой не более чем счетно.

Булевы функции

  1. Доказать полноту системы булевых функций F={|}, состоящих из единственной функции | – штрих Шеффера. Выразить функцию х1х2  х3 через штрих Шеффера.

  2. Доказать полноту системы булевых функций F={, 0}, где 0 – функция, все значения которой равны 0. Выразить f(х1, х2) = х1х2 через F.

  3. Доказать полноту системы функций F={}, состоящих из стрелки Пирса. Выразить х1  х2 через стрелку Пирса.

  4. Найти совершенную конъюнктивную нормальную форму для функции:
    f(х1, х2) = 1 – (х1х2).

  5. Минимизировать методом карт Карно функцию:

.

Исчисление высказываний

  1. Множество пропозициональных формул  называется противоречивым, если существует вывод  |— 0. Доказать, что  противоречиво, если и только если (1…n) – тавтология для любых 1, …, n  .

  2. Непротиворечиво ли множество формул  = {х1, х2  х1}?

  3. Противоречиво ли множество формул  = {х1  х2, х1 & х2}?

  4. Проверить выполнимость множества формул  = {(х2  х1)  х3, (х1  х3)}.

Теории первого порядка

  1. Пусть М=(, Р) – модель языка первого порядка, состоящая из множества натуральных чисел  и трехместного предиката Р(x,y,z), принимающего значение 1, если xy = z, и значение, равное 0 в других случаях. Записать предложение, означающее существование наибольшего делителя для чисел, одновременно не равных 0.

  2. Пусть М=(, S) – модель, состоящая из множества натуральных чисел  и предиката S(x,y,z), равного 1 в случае x+y = z, и 0 – в других случаях. Записать формулу с одной свободной переменной х, истинную тогда и только тогда, когда х – нечетно.

  3. Линейно упорядоченное множество (X, <) называется плотным, если для любых x,yX существует такой zX, что x<z<y. Сформулировать аксиомы теории плотных линейно упорядоченных множеств.

  4. Линейно упорядоченное множество (X, ) называется вполне упорядоченным, если каждое его подмножество обладает наименьшим элементом. Написать формулы теории множеств ZF, определяющие вполне упорядоченные множества (X, ).

  5. Привести к пренексной нормальной форме х(Р(х)  y(Q(х, y)  z R(y, z))).

  6. Привести к пренексной нормальной форме Р(х, y)  y(Q(y)  (x Q(х)  R(y))).

  7. Привести к пренексной нормальной форме х(Р(х)Q(х,y))  (y Р(y)z Q(y,z))).

  8. Освободиться от кванторов х Р(х)  y Q(х, y).

  9. Освободиться от кванторов y (Р(х, y)  z R(y, z)).

Нечеткая логика

  1. Пусть U = {xR : х0} – универсальное множество, М1 и М2 – нечеткие подмножества, обозначающие М1 – новый, а М2 – старый возрасты машин. Известно, что М1(0) = 1 и М1(х) = 0 при х  100. В интервале [0,100] функция М1 линейна. Известно, что М2(0) = 0 и М2(х) = 1 при х  50, а в интервале [0,50] линейна. Найти пересечение, объединение, ограниченное произведение и ограниченную сумму М1 и М2.

  2. С помощью принципа обобщения определить операцию умножения нечетких подмножеств числовой прямой.

  3. Пусть а = 0.1, b = 0.9, с = 0.5. Вычислить значения а&b  аb по формулам Заде и Лукасевича.

  4. Пусть Х={а, b}. Заданы нечеткие бинарные отношения  и  на Х:

(а,а) = 1, (а,b) = 0.3, (а,а) = 0.1, (а,b) = 0.5,

(b,а) = 0.1, (b,b) = 0.7, (b,а) = 0.6, (b,b) = 0.2.

Вычислить композицию --1 --1.


  1. Будет ли формула (х1  х2)(х1  х2)(х1  х2) нечетко общезначимой?

  2. Будет ли нечетко противоречивой формула:

(х1  х2)(х1  х2)(х1  х2)(х1  х2)?

  1. Пусть с1 = х1  (х2  х3), с2 = х1  (х2  (х3  х4)). Вычислить значения интерпретации t(R(с1, с2)), если t(х1) = 0.1, t(х2) = 0.8, t(х3) = 0.3, t(х4) = 0.5.

Модальная и темпоральная логики

  1. Доказать, что в каждой системе Гильберта верна теорема А  (АВ).

  2. Найти форму Салквиста для формулы р  р и перевести ее в формулу языка первого порядка.

  3. Найти форму Салквиста для формулы р  р и перевести ее в формулу языка первого порядка.

  4. Найти форму Салквиста для формулы р  р и перевести ее в формулу языка первого порядка.

Алгоритмы и рекурсивные функции

  1. Доказать, что функция max(х, y) примитивно рекурсивна.

  2. Доказать, что функция f(х) = х – 1 частично рекурсивна.

  3. Какую функцию вычисляет машина Тьюринга, имеющая программу:

q1 0  q2 0 R, q2 0  q0 0, q3 0  q2 1 R,

q2 1  q3 1 R, q3 1  q3 1 R,

если на входе задаются n аргументов х1, х2,…,хn?



  1. Построить машину Тьюринга, правильно вычисляющую функцию f(х) = х + 2.

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

f(х,y) = хy.