Математическая логика и теория алгоритмов (стр. 3 )

Контрольная работа в 4 семестре

1.  Применяя равносильные преобразования доказать, что формула алгебры высказываний является тавтологией:

а)

б)

2.  Составить таблицу истинности и выяснить равносильны ли следующие формулы алгебры высказываний:

а)

б)

3.  Найти формулу алгебры высказываний от трех переменных, которая

а) принимает значение 1 тогда и только тогда, когда либо первый ее аргумент равен 1, либо все аргументы равны 0.

б) принимает значение 0 тогда и только тогда, когда два ее последних аргумента принимают различные значения.

4.  Найти все формулы алгебры высказываний, являющиеся логическими следствиями следующих формул (посылок):

а)

б)

5.  Решить логически задачи.

а) Вова, Рома, Юра и Саша заняли на олимпиаде четыре первые места. Когда их спросили о распределении мест, они дали три таких ответа:

- Саша занял первое место, а Рома – второе;

- Саша – второе, а Вова – третье;

- Юра занял второе место, а Вова – четвертое место.

Как распределились места, если в каждом ответе только одно утверждение истинно.

б) По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:

1) Если Иванов не виновен или Петров виновен, то Сидоров виновен.

2) Если Иванов не виновен, то Сидоров не виновен.

Виноват ли Иванов?

Контрольная работа в 5 семестре

1.  Пусть f(0,n)=1, f(m,0)=m+1, f(m+1,n+1)=f(m, mn)∙f(m+1,n). Найдите f(2,5); f(4,4).

2.  Докажите, что если функция φ(x) – примитивно рекурсивна, то функция f(x), определяется условием (1) f(0)=0, (2) f(x+1)=φ(x+1) примитивно рекурсивна.

3.  Докажите, что функция, определенная схемой примитивно рекурсивна.

4.  Пусть f(x)=2x+1, Imf – множество ее значений. Докажите, что Imf – примитивно рекурсивная.

5.  Решите уравнений: а) q(x)=5; б) x¸[]=2.

6.  Найдите пару (x, y) натуральных чисел, канторовский номер которой равен 121.

7.  Найдите упорядоченную тройку (x, y,z) натуральных чисел, с канторовским номером 20.

Тестовые задания в 4 семестре

1. Под высказыванием понимают…

а) любое повествовательное предложение;

б) предложение с переменной, превращающееся в правильное утверждение при подстановке вместо переменных конкретных

значений;

в) предложение, представляющее собой утверждение, о котором можно судить, истинно оно или ложно;

г) безличные, вопросительные и восклицательные предложения.

2. Отрицанием высказывания Р называется такое высказывание ù Р, которое

а) истинно, если Р истинно, и ложно, если Р ложно;

б) всегда ложно;

в) всегда истинно;

г) истинно, если Р ложно, и ложно, если Р истинно.

3. Конъюнкцией высказываний Р и Q называется

высказывание Р Ù Q, которое

а) истинно тогда и только тогда, когда Р и Q одновременно

истинны;

б) ложно тогда и только тогда, когда Р и Q одновременно

ложны;

в) ложно тогда и только тогда, когда Р – истинно, а Q ложно;

г) истинно тогда и только тогда, когда Р и Q имеют одинаковое значение истинности.

4. Дизъюнкцией высказываний Р и Q называется высказывание РÚQ, которое

а) истинно тогда и только тогда, когда Р и Q одновременно истинны;

б) ложно тогда и только тогда, когда Р и Q ложны одновременно;

в) ложно тогда и только тогда, когда Р - истинно, а Q ложно;

г) истинно тогда и только тогда, когда Р и Q имеют одинаковое значение истинности.

5. Импликацией высказываний Р и Q называется высказывание Р®Q, которое

а) истинно, тогда и только тогда, когда Р - истинно, а

Q-ложно;

б) ложно, тогда и только тогда, когда Р - истинно, а

Q-ложно;

в) истинно, тогда и только тогда , когда Р - ложно, а

Q-истинно;

г) ложно, тогда и только тогда, когда Р - ложно и

Q-истинно;

6. Эквиваленцией высказываний Р и Q называется

высказывание Р«Q, которое

а) истинно, тогда и только тогда , когда Р и Q принимают разное значение истинности;

б) ложно, тогда и только тогда, когда Р и Q принимают одинаковое значение истинности;

в) истинно, тогда и только тогда, когда Р и Q принимают одинаковое значение истинности;

г) ложно, тогда и только тогда, когда, Р и Q принимают разное

значение истинности.

7. Пропозиционными переменными называются такие переменные

а) вместо которых можно подставлять конкретные высказывания;

б) значение которых зависит от позиции переменной в формуле;

в) которые принимают значение истины в любом высказывании;

8. Определите, какая последовательность символов не является

формулой (внешние скобки опущены)

а) ù((РÙùQ)®(PÚ(RÙùS)));

б) (PÚùQ)®(PùS);

в) (QÙ(PÚùP ))Ù((ùQ®P)ÚQ);

г) ù((P«ùQ)ÚR)ÙQ.

9. Формула алгебры высказываний называется тавтологией,

если

а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение истинно.

10. Формула алгебры высказываний называется противоречием, если

а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе входящих в нее переменных

данная формула принимает значение истинно.

11. Формула алгебры высказываний называется выполнимой, если

а) при любом выборе значений входящих в нее переменных

данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных

данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе входящих в нее переменных

данная формула принимает значение истинно.

12 Формула алгебры высказываний называется опровержимой, если

а) при любом выборе значений входящих в нее переменных

данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение истинно.

13. Определить вид формулы (PÙ(QÚùP))Ù((ùQ®P)ÚQ)

а) тавтология;

б) противоречие;

в) выполнимая и опровержимая.

14. Формула алгебры высказываний называются равносильными, если

а) при любых значениях, входящих в них пропозиционных

переменных данные формулы принимают значение истинно;

б) при любых значениях, входящих в них пропозиционных переменных логические значения получающихся из формул высказываний не совпадают;

в) при любых значениях, входящих в них пропозиционных переменных логические значения получающихся из формул высказываний совпадают;

г) при любых значениях, входящих в них пропозиционных переменных данные формулы принимают значение ложно.

15. Формула (P®Q)Ù(Q®ùP)Ù(R®P) равносильна следующей формуле:

а) ùP Ù Q Ù R;

б) P Ú R;

в) ùP Ù ùR;

г) (R®P) Ù Q.

16. Конъюнктивной нормальной формой для формулы алгебры высказываний называется

а) произвольная конъюнкция конъюнктивных одночленов;

б) произвольная конъюнкция дизъюнктивных одночленов;

в) произвольная конъюнкция дизъюнктивных совершенных одночленов;

г) произвольная дизъюнкция конъюнктивных одночленов.

17. Одночлен от нескольких переменных называется совершенным, если

а) каждая его переменная совершенна;

б) каждая его переменная входит в него только один раз;

в) каждая из этих переменных входит в него хотя бы один раз со знаком отрицания или без него;

г) каждая из этих переменных входит в него хотя бы один раз со знаком отрицания или без него.

18. СКН – форма некоторой формулы от трех переменных содержит пять сомножителей (совершенных дизъюнктивных одночленов). Что проще: СКН – форма или СДН – форма этой формулы?

а) СКН – форма;

б) СДН – форма;

в) СКН – форма и СДН – формы одинаковы по простоте.

19. Формула B называется логическим следствием формулы А тогда и только тогда, когда

а) формула (АВ) – тавтология;

б) формула А равносильна формуле В; (x1,x2,...,xn)

в) формула (АВ) – тавтология;

г) формула (АВ) – выполнима.

20. Формула В(x1,x2,...,xn) называется логическим следствием формулы А1(x1,x2,...,xn), А2(x1,x2,...,xn),…,Аs(x1,x2,...,xn) тогда и только тогда, когда

а) ((А1 А2… Аs)В) – тавтология;

б) ((А1А2…Аs)В) – тавтология;

в) из того, что |B| = 1 следует, что |А1| = |А2| =…=|Аs| = 1.

21. Если логическая структура данной теоремы выражается следующей формулой: (А®В), то противоположное утверждение имеет следующую структуру:

а) (ВА);

б) (ùАùВ);

в) (ùВùА).

22. Булевой функцией от n аргументов называется

а) любая функция, принимающая значение в множестве [ 0; 1];

б) любая функция, заданная на множестве { 0; 1};

в) любая функция от n аргументов, заданная на двухэлементном множестве { 0; 1} и принимающая значение в том же множестве.

23. Булевых функций от трех переменных существует ровно:

а) 8;

б) 28;

в) 26;

г) 27.

24. Суперпозиция функций h1(x1,x2) = x1x2, h2(x1) = x1,

h3(x1,x3) = x1x3 в функцию g(u, v,t) = u Ú v Ú t есть функция:

а) G(x1, x2, x3) = x1(x2 Ú x3);

б) G(x1, x2, x3) = x1 Ú x2 Ú x3;

в) G(x1, x2, x3) = (x1x2) Ú x3.

25. Данная релейно-контактная схема

X Z¢

Y

X¢

Y Z

X Y

равносильна следующей схеме:

а) X Y¢

Z

б) X ¢

Y

Z¢

в)

X

Y¢

Z

Вопросы к коллоквиуму в 4 семестре

1. Высказывания. Операции над ними.

2. Тавтологии. Основные свойства.

3. Отношения логического следования. Свойства

4. Равносильность формул. Основные равносильности

5. Полные и неполные системы логических связок.

6. Двойственные формулы. Приведенные формулы. Свойства.

7. Теорема двойственности

8. Логическое следование формул алгебры высказываний: основные логические следствия. Свойства логического следования.

9. Приложение алгебры высказываний к логико-математической практике.

10. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции.

11. Элементарная конъюнкция и элементарная дизъюнкция. Свойства

12. Конъюнктивная и дизъюнктивная нормальные формы

13. Полные элементарные конъюнкции и дизъюнкции.

14. Совершенные дизъюнктивные нормальные формы. Алгоритмы построения СДНФ

15. Совершенные конъюнктивные нормальные формы.

16. Алгоритмы построения СКНФ

17. Приложения совершенных форм.

18. Методы математических доказательств: метод от противного.

19. Применение алгебры высказываний к описанию релейно-контактных схем: анализ и синтез схем.

Вопросы к коллоквиуму в 5 семестре

1.  Понятие предиката. Область истинности предиката.

2.  Логические операции над предикатами.

3.  Кванторные операции над предикатами.

4.  Понятие формулы логики предикатов, их классификация.

5.  Тавтологии логики предикатов.

6.  Равносильность формул логики предикатов. Основные равносильности.

7.  Логическое следование формул логики предикатов.

8.  Приведенные формы формул логики предикатов.

9.  Предваренная нормальная форма.

10.  Проблема общезначимости для формул логики предикатов.

11.  Выполнимость формул на бесконечном множестве.

12.  Частные случаи выполнимости формул.

Вопросы для собеседования в 4 семестре

1.  Перечислить объекты, которые необходимо задать для построения формализованного исчисления высказываний.

2.  Перечислить аксиомы формализованного исчисления.

3.  Сформулировать теорему дедукции и основные идеи ее доказательства.

4.  Сформулировать и доказать следствия теоремы дедукции.

5.  Применения теорему дедукции, доказать правило силлогизма, правила снятия и введения двойного отрицания, правила контрапозиции.

6.  В чем состоит свойство полноты исчисления высказываний?

7.  Сформулировать и доказать лемму о выводимости формулы из специального множества гипотез.

8.  Какое исчисление называется непротиворечивым? Доказать его непротиворечивость.

9.  Свойство независимости системы аксиом.

10.  Доказать независимость аксиомы А1.

11.  Доказать независимость аксиомы А2.

12.  Доказать независимость аксиомы А3.

Вопросы для собеседования № 1 в 5 семестре

1.  Понятие предиката. Приведите примеры.

2.  Область истинности предиката. Примеры выполнимых предикатов, опровержимых.

3.  Логические операции над предикатами.

4.  Кванторные операции над предикатами.

5.  Понятие формулы логики предикатов, их классификация.

6.  Тавтологии логики предикатов.

7.  Равносильность формул логики предикатов.

8.  Основные равносильности.

9.  Логическое следование формул логики предикатов.

Вопросы для собеседования № 2 в 5 семестре

1.  Приведите примеры алгоритмов. Опишите характерные черты алгоритмов.

2.  Объясните необходимость уточнения понятия алгоритма.

3.  Назовите простейшие функции. Определите операцию подстановки.

4.  Оператор примитивной рекурсии. Понятие примитивно-рекурсивной функции.

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

6.  Сформулируйте и докажите теорему о суммируемости рекурсивных функций.

7.  Сформулируйте и докажите теорему о мажорируемых неявных функциях.

8.  Приведите примеры примитивно рекурсивных функций.

9.  Определите функции Кантора. Опишите их свойства.

10.  Рекурсивно-перечислимое множество.

Вопросы к зачету в 4 семестре

1.  Высказывания. Операции над высказываниями.

2.  Формулы алгебры высказываний. Таблица истинности.

3.  Виды формулы. Основные тавтологии.

4.  Тавтологии и их свойства.

5.  Равносильность формул алгебры высказываний и их свойства.

6.  Основные равносильности.

7.  Логическое следствие, его свойства.

8.  Совершенные нормальные формы.

9.  Приведение формул к совершенной нормальной форме.

10.  Алгоритм построения СДНФ.

11.  Алгоритм построения СКНФ.

12.  Нахождение следствий из данных посылок.

13.  Нахождение посылок для данного следствия.

14.  Обоснование метода доказательства от противного.

15.  Применение алгебры высказываний к анализу и синтезу релейно-контактных схем.

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

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

18.  Следствия теоремы дедукции.

19.  Применение теоремы дедукции.

20.  Полнота исчисления высказываний.

21.  Лемма о выводимости формулы из специального множества гипотез.

22.  Непротиворечивость исчисления высказываний.

23.  Независимость системы аксиом.

Вопросы к экзамену в 5 семестре

1.  Понятие предиката. Область истинности предиката.

2.  Логические операции над предикатами.

3.  Кванторные операции над предикатами.

4.  Понятие формулы логики предикатов, их классификация.

5.  Тавтологии логики предикатов.

6.  Равносильность формул логики предикатов. Основные равносильности.

7.  Логическое следование формул логики предикатов.

8.  Приведенные формы формул логики предикатов.

9.  Предваренная нормальная форма.

10.  Проблема общезначимости для формул логики предикатов.

11.  Выполнимость формул на бесконечном множестве.

12.  Частные случаи выполнимости формул.

13.  Понятие алгоритма. Примеры.

14.  Характерные черты алгоритмов.

15.  Необходимость уточнения понятия алгоритма. Примеры алгоритмически неразрешимых проблем.

16.  Понятие вычислимой функции.

17.  Простейшие функции. Суперпозиция функций. Операция подстановки.

18.  Оператор примитивной рекурсии. Понятие примитивно-рекурсивной функции.

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

20.  Примитивно-рекурсивные и частично-рекурсивные подмножества множества N.

21.  Теорема о суммируемости рекурсивных функций.

22.  Кусочно-определённые функции. Теорема о мажорируемых неявных функциях.

23.  Примитивная рекурсивность функции [X/Y].

24.  Примитивная рекурсивность функции REST.

25.  Примитивная рекурсивность функции DIV.

26.  Примитивная рекурсивность функции P(X).

27.  Примитивная рекурсивность функции .

28.  Примитивная рекурсивность функции .

29.  Понятие о возвратной рекурсии теоремы).

30.  Примитивная рекурсивность функции .

31.  Функции Кантора(понятие, формулы).

32.  Примитивная рекурсивность функции Кантора.

33.  Обобщённые функции Кантора.

34.  Рекурсивно-перечислимое множество.

35.  Теорема о задании перечислимого множества.

36.  Теорема о перечислимости пересечения и объединения перечислимых множеств.

37.  Теорема Поста.

38.  Рекурсивно-перечислимое множество . Универсальная функция.

39.  Машины Тьюринга. Команды. Конфигурация.

40.  Описание машины Тьюринга.

41.  Вычислимые по Тьюрингу функции.

42.  Нормальные алгоритмы Маркова.

7. Учебно-методическое и информационное обеспечение дисциплины

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

Основная литература

1.  Игошин логика и теория алгоритмов.- М.: Издательский центр «Академия»; 2004.

2.  Игошин и упражнения по математической логике и теории алгоритмов.- М.: Издательский центр «Академия»; 2005.

3.  Лавров логика – М.: Академия, 2006.

4.  , Максимова по теории множеств, математической логике и теории алгоритмов.- М., 2005.

5.  Введение в математическую логику. – М.: Либроком, 2010.

Дополнительная литература

Блох -схемы и алгоритмы: учеб. Пособие для физ-мат. пед. ин-тов – Минск: Высш. школа, 1987. Заитдинов логических задач: учеб. пособие – Тверь: 2004 Математическая логика.- М.: Мир, 1973. , Парфенов математической логики: учеб.-метод. пособие – Пенза, 2001. Мальцев и рекурсивные функции.- М., 1965. Новиков математической логики.- М.: Наука, 1973. Осьминина теории алгоритмов: метод. рекоменд. – Пенза, 2004. Введение в математическую логику.- М.: Наука, 1960.

Программное обеспечение и Интернет-ресурсы

№	Название	Электронный адрес	Содержание
1.	Exponenta.ru	www. *****	На сайте размещены электронные учебники, справочники, статьи, примерами применения математических пакетов в образовательном процессе, демо-версии популярных математических пакетов, электронные книги и свободно распространяемые программы.
2.	*****	www. *****	Математический сайт для школьников, студентов, учителей и всех, кто интересуется математикой.
3.	Математика	www. *****	Учебный материал по различным разделам математики.
4.	Математика для студентов и прочее.	www. xplusy. *****	Содержит большое количество видеолекций для школьников, абитуриентов и студентов по математике и физике.
5.	Российское образование.	www. *****	Федеральный образовательный портал: учреждения, программы, стандарты, ВУЗы, тесты ЕГЭ.

8. Материально-техническое обеспечение дисциплины

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

Для освоения данной дисциплины необходимы:

– мультимедийные средства обучения (компьютер и проектор, ресурсы Интернета).

Рабочая программа дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций примерной ООП ВПО по направлению подготовки 050100 «Педагогическое образование» и профилю подготовки «Информатика».

Программу составили:

1. , доцент, к. ф.-м. н.

(Ф. И.О., должность, подпись)

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры алгебры

Протокол № ___ от «____» ______________ 2011 года

Зав. кафедрой ___________________

(подпись, Ф. И.О.)

Программа одобрена учебно-методическим советом физико-математического факультета

Протокол № ___ от «____» ______________ 2011 года

Председатель учебно-методического совета

физико-математического факультета _______________________

(подпись) (Ф. И.О.)

Программа одобрена учебно-методическим управлением университета

«_____» _____________ 2011 года

Начальник учебно-методического

управления университета ___________________________

(подпись)