РГР по математической логике и теории алгоритмов

РГР НАХОДИТСЯ В ФАЙЛЕ С НАЗВАНИЕМ: "задание_2023"

Расчётно-графическое задание

22 Вариант:

• Решение каждой задачи должно быть подробно и логично описано, отдельно выписан ответ задачи. Перед решением приводить условие задачи согласно варианту.

Логические функции

1. Проверить полноту системы логических функций, используя критерий Поста. Заполнение таблицы Поста должно быть обоснованным. (2б)

Если система не полна, то достроить до полной. (Запрещается использовать функции константы, отрицание, конъюнкция, штрих Шеффера или стрелка Пирса)

Используя функции полученной полной системы выразить константы 0, 1 и функции отрицание, конъюнкция. (2б.)

В полученной полной системе функций перечислить все базисы. (2б)

Варианты:

№ 22 | функции | 2,3,7

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

2) x_1 ~ not x_2 & x_3

3)x_1 ->(x_2?x_3)

7)(01011100)

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

2. Записать рассуждение в логической символике, обосновать выбор логических связок (2б.)

3. Проверить правильность рассуждения методом Куайна или методом редукции (2 б.).

4. Проверить правильность рассуждения методом резолюций (3 б.)

Варианты

22. Если Марии понравятся цветы, она купит семена и посадит цветы. Если погода будет плохой, Мария не станет сеять цветы. Цветы не посажены. Значит, либо Марии не понравились цветы, либо на улице была холодная погода.

Исчисление предикатов

5. На предметной области ? заданы предикаты P и Q . Проверить выполнимость формул (см. список ниже) в заданной интерпретации (см. в таблице Варианты), т.е. найти наборы значений свободных переменных, для которых формула в заданной интрепретаци принимает истинное значение

(5б.)

Формулы

?x(P(x, y) V Q( y, x))

?x(P(x, y) -> Q( y, x))

?x(P(x, y) V not Q(x, y))

?xP(x, y) V ? x not Q(x, y)

?xP(x, y) & ?yQ( y, x))

Варианты

22. ? – целые числа P(x,y)= «x2+y=10» Q(x,y)= «3 ? y»

6. Проверить общезначимость формулы методом резолюций. (5б.)

Варианты

22) A(x, x) -> (?x?yA(x, y) & ?x?yB(x, y))

Теория алгоритмов

7. Построить машину Тьюринга с внешним алфавитом A, которая выполняет заданные действия. (4б)

В начальный момент на ленте записано слово P (конечная последовательность символов внешнего алфавита А, слово P может быть пустым), указатель указывает на крайний левый непустой символ слова P или на пустую ячейку, если P – пустое слово.

В заключительной конфигурации указатель должен указывать на крайний левый непустой символ результата. Если результатом окажется пустое слово, указатель указывает на пустую ячейку.

Пояснения по построению программы для МТ обязательны.

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

Нарисовать граф для построенной МТ. (1б)

Варианты

22. A={a,b, *},

* пустой символ | Действие машины Тьюринга - Удвоить слово P (например: abb заменяется на abbabb).

Там где вопросики это символы не встали, в файле всё есть

Если это как то может помочь, то есть ещё доп материалы и презентации лекций.

Срок выполнения написал до 17 января, но хотелось бы пораньше....

Файлы с названием МЛТА - презентации лекций, загружены не поочерёдно, но у них есть на конце число означающее порядок