Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

ПРИЛОЖЕНИЯ 1. Варианты типового задания 1. Записать приведенное высказывание в виде формулы логики высказы­ ваний. Для полученной формулы составьте таблицу истинности. 2. Упростить формулу логики высказываний, используя основные равно­ сильности между формулами. 3. Составить программу нахождения с.к.н.ф. на любом известном вам ал­ горитмическом языке и найти с.к.н.ф. для заданной булевой функции. Прове­ рить полученный результат, построив с.к.н.ф. равносильными преобразовани­ ям. 4. Методом резолюций выяснить, истинно ли приведённое утверждение. 5. Записать предложение в виде формулы логики предикатов. 6. Привести пример интерпретации, для которой данная формула истинна. 7. Получить предваренные нормальные формы и сколемовские стандарт­ ные формы для данных формул. 8. Записать предложения в виде соотношений формул логики предикатов. Методом резолюций выяснить, будет ли заключение логическим следствием из посылок. Продемонстрировать результат с помощью диаграмм Эйлера-Венна. 9. Паписать на языке ПРОЛОГ программу, определяющую названия элек­ тронных книг вашей личной библиотеки. В общем списке бумажных и элек­ тронных книг вашей личной библиотеки привести 10-15 книг, с указанием ав­ тора книги, названия, типа книги (бумажное или электронное). 10. Построить нормальный алгоритм для преобразования слова Р в слово Q, при условии, что в каждой подстановке Pi —>(*)Qi алгоритма число букв удовлетворяет неравенству: \ Pi\< п, \ Qi \ < п, где n=2+[N](mod 3), здесь N - ваш номер в списке группы, а [N](mod 3) означает число N по модулю три. 11. Построить машину Тьюринга, которая будет считать записанные под­ ряд (без пропусков) единицы (их число не превосходит п) и запишет их число в системе счисления с основанием п +1, здесь n=3+[N](mod \3) и Л^=(ваш номер в списке группы)+(номер вашей группы). 12. Доказать методами исчисления секвенций, что заданная формула явля­ ется тавтологией. 13. Выяснить, равносильны ли приведенные формулы в трёхзначной логи­ ке Лукасевича. Сделать это с помощью разработанной вами программы на лю­ бом известном вам алгоритмическом языке. 235