Список вопросов к экзамену по дисциплине

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

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

^{(шифр и наименование специальности)}

УТВЕРЖДАЮ

И.О. зав. кафедрой

И.А. Фукин______

^{(подпись)}

«____»_____20___г.

1. Краткие сведения об истории развития дисциплины. Связь дисциплины с предшествующими и последующими дисциплинами.
Краткие сведения об истории развития дисциплины. Связь дисциплины с предшествующими и последующими дисциплинами.
Язык логики высказываний. Операции над высказываниями.
Интерпретация формул.
Общезначимость, выполнимость, противоречивость. Методы анализа выполнимости и общезначимости формул
Нечеткая, модальная, темпоральные логики.
Понятие нечеткого множества. Нечеткая логика.
Алгоритм приведения формул в КНФ.
Алгоритм приведения формул в ДНФ.
Теории первого порядка. Свойства теорий первого порядка (полнота, разрешимость, непротиворечивость (первая и вторая теоремы Геделя)).
Неклассические логики.
Правило modus ponens (МР).

Нечеткие высказывания. Понятие о нечеткой лингвистической логике. Модальные логики. Временные (темпоральные) логики.
Проблема алгоритмической неразрешимости. Понятие о массовой проблеме. Примеры.
Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча).
Сложность вычислений с помощью алгоритмов.
Принцип математической индукции
Умозаключение как форма мышления. Умозаключения с дизъюнктивными и импликативными посылками.
Основные законы логики: тождества, противоречия, исключения третьего. Примеры. Софизмы и парадоксы.
Алгоритмическая система Ч.Хоара.
Язык логики высказываний. Операции над высказываниями.
Интерпретация формул.
Общезначимость, выполнимость, противоречивость. Методы анализа выполнимости и общезначимости формул.

Задачи к экзамену

1. Изобразите на координатной плоскости множество истинности предиката:

2. Докажите, что следующая формула является тавтологией алгебры высказываний

3. Запишите следующие высказывания на языке алгебры предикатов:

а) Существует точно один х, такой , что Р(х);

б) существуют по крайней два различных х, такие, что Р(х);

в) существует не более двух х, таких, что Р(х);

г) существует точно два различных х, такие, что Р(х).

3. Введите одноместные предикаты на соответствующих областях и запишите при их

помощи следующие высказывания в виде формул алгебры предикатов:

а) Жители Швейцарии обязательно владеют или французским, или итальянским, или немецким языком;

б) Некоторые змеи ядовиты;

в) Все собаки обладают хорошим обонянием.

4. Определите, является ли один из предикатов, заданных на множестве действительных чисел, следствием другого:

5. Найдите множества истинности предикатов, заданных на указанных множествах:

6. Четыре друга – Антонов (А), Вербов (В), Сережкин (С), Дмитриев (Д) – решили провести каникулы в четырех различных городах – Москве, Петербурге, Стамбуле и Анапе. В какой город должен поехать каждый из них, если имеются следующие ограничения:

a. если А не едет в Москву, то С не едет в Петербург;

b. Если В не едет ни в Москву, ни в Анапу, то А едет в Москву;

c. Если С не едет в Анапу, то В едет в Стамбул;

d. Если Д не едет в Москву, то В едет в Москву;

e. Если Д не едет в Петербург, то В не едет в Москву.

7. Выделив условие и заключение теоремы, сформулируйте ее посредством связки «если…, то …»:

a. Для делимости произведения на некоторое число достаточно, чтобы по меньшей мере один из сомножителей делился на это число.

b. Четность суммы есть необходимое условие четности каждого слагаемого.

8. Предикат А(х,у) задан на множестве М=(1,2,3) таблицей. Определите истинное значение приводимых далее формул при каждом значении свободной переменной:

х,у
	И	И	И
	Л	Л	И
	И	Л	И

9. Какие из следующих выражений являются высказыванием:

1) x+y=z, 2) x+y>0, 3) x<y, 4) 4+5=13, 5) 7+2.

10. Пусть Р(х) означает «х-простое чтсло», Е(х)-«х-четное число», О(х)-«х-нечетное число», М(х,у) – «х делит у» или «у делится на х». переведите на русский язык следующие символические записи на языке алгебры предикатов, учитывая, что переменные х и у пробегают множество натуральных чисел:

11. Имеется машина Тьюринга с программой:

Определите, в какое слово переработает машина каждое из следующих слов, если она находится в начальном состоянии q и обозревает указанную ячейку: (обозревается ячейка 4, считая слева).

12. Решите системы булевых уравнений:

13. Андрей или переутомился (А) или болен (В). Если он переутомился, то он раздражается (С).Он не раздражается. Следует ли отсюда, что он не болен?

14. Найдите все следствия из посылок: «Если сумма цифр целого числа делится на 3, то это число делится на 3 или на 9»; «Если целое число делится на 9, то оно делится на 3». Найденным следствиям придайте содержательный смысл.

15. Установите истинность выражений:

1)

16. Изобразите на координатной плоскости множество истинности предиката:

.

17. Докажите, что следующая формула является тавтологией алгебры высказываний

18. Запишите следующие высказывания на языке алгебры предикатов:

а) Существует точно один х, такой , что Р(х);

б) существуют по крайней два различных х, такие, что Р(х);

в) существует не более двух х, таких, что Р(х);

г) существует точно два различных х, такие, что Р(х).

19. Введите одноместные предикаты на соответствующих областях и запишите при их помощи следующие высказывания в виде формул алгебры предикатов:

а) Жители Швейцарии обязательно владеют или французским, или итальянским, или немецким языком;

б) Некоторые змеи ядовиты;

в) Все собаки обладают хорошим обонянием.

20. Определите, является ли один из предикатов, заданных на множестве действительных чисел, следствием другого:

21. Найдите множества истинности предикатов, заданных на указанных множествах:

22. Четыре друга – Антонов (А), Вербов (В), Сережкин (С), Дмитриев (Д) – решили провести каникулы в четырех различных городах – Москве, Петербурге, Стамбуле и Анапе. В какой город должен поехать каждый из них, если имеются следующие ограничения:

a. если А не едет в Москву, то С не едет в Петербург;

b. Если В не едет ни в Москву, ни в Анапу, то А едет в Москву;

c. Если С не едет в Анапу, то В едет в Стамбул;

d. Если Д не едет в Москву, то В едет в Москву;

e. Если Д не едет в Петербург, то В не едет в Москву.

23. Выделив условие и заключение теоремы, сформулируйте ее посредством связки «если…, то …»:

a. Для делимости произведения на некоторое число достаточно, чтобы по меньшей мере один из сомножителей делился на это число.

b. Четность суммы есть необходимое условие четности каждого слагаемого.

24. . Предикат А(х,у) задан на множестве М=(1,2,3) таблицей. Определите истинное значение приводимых далее формул при каждом значении свободной переменной:

х,у

И И И

Л Л И

И Л И

Какие из следующих выражений являются высказыванием:

2) x+y=z, 2) x+y>0, 3) x<y, 4) 4+5=13, 5) 7+2.

Пусть Р(х) означает «х-простое чтсло», Е(х)-«х-четное число», О(х)-«х-нечетное число», М(х,у) – «х делит у» или «у делится на х». переведите на русский язык следующие символические записи на языке алгебры предикатов, учитывая, что переменные х и у пробегают множество натуральных чисел:

26. Имеется машина Тьюринга с программой:

Определите, в какое слово переработает машина каждое из следующих слов, если она находится в начальном состоянии q и обозревает указанную ячейку: (обозревается ячейка 4, считая слева).

27. Решите системы булевых уравнений:

Найдите все следствия из посылок: «Если сумма цифр целого числа делится на 3, то это число делится на 3 или на 9»; «Если целое число делится на 9, то оно делится на 3». Найденным следствиям придайте содержательный смысл.

Установите истинность выражений:

1)

Составил _ст.преподаватель кафедры ЕНД Пимукова Л.А. ___________

^{(должность преподавателя) (подпись преподавателя)}