Решение задач «1. Запишите приведенное высказывание в виде формулы логики»,
Ш. и. галиев математическая логика и теория алгоритмов в Новосибирске

239 страница из прикреплённого файла, 1 вариант. 1. Запишите приведенное высказывание в виде формулы логики высказываний. Для полученной формулы составьте таблицу истинности. 2. Упростите формулу логики высказываний, используя основные равносильности между формулами. 3. Составьте программу нахождения совершенной конъюнктивной нормальной формы (с.к.н.ф.) на любом известном вам алгоритмическом языке и найдите с.к.н.ф. для заданной булевой функции. Проверьте полученный результат, построив с.к.н.ф. равносильными преобразованиям. 4. Методом резолюций выясните, истинно ли приведённое утверждение. Решите эту задачу, используя два метода из следующих: метод исчерпания уровня, стратегия вычёркивания, лок-резолюция и табличный метод (последний для случая, если заданное множество является множеством хорновских дизъюнктов). 5. Запишите предложение в виде формулы логики предикатов. 6. Привести пример интерпретации, для которой данная формула истинна. 7. Получить предваренные нормальные формы и скулемовские стандартные формы для данных формул. 8. Записать предложения в виде соотношений формул логики предикатов. Методом резолюций выяснить будет ли заключение логическим следствием из посылок. Продемонстрировать результат с помощью диаграмм Эйлера-Венна. 9. Построить нормальный алгоритм для преобразования слова Р в слово Q, при условии что в каждой подстановке Рi ?( •)Qi алгоритма число букв удовлетворяет неравенству: ?Рi ?? n, ?Qi ?? n, где n=2+[N](mod 3), здесь N - ваш номер в списке группы, а [N](mod 3) означает число N по модулю три. 10. Построить машину Тьюринга для преобразования слова Р в слово Q. 11. Построить машину Тьюринга, которая будет считать записанные подряд (без пропусков) единицы (их число не превосходит n) и запишет их число в системе счисления с основанием n +1, здесь n=3+[N](mod 13) и N =(ваш номер в списке группы)+(номер вашей группы).