решение задач по математической логике и теории алгоритма. вариант 4

1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.

В состав нелогических символов языка исчисления предикатов входят: (а) кванторы; (б) пропозициональные переменные; (в) функциональные символы; (г) предметные переменные.

2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.

3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.

4. Задана формула исчисления предикатов и множество М={a,b}. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P(a)=«и», P(b)=«л», R(a)=«л», R(b)=«и», Q(a,a)=«и», Q(a,b)=«л», Q(b,a)=«л», Q(b,b)=«л».

5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).

6. Задана программа машины Тьюринга (q1¬– начальное состояние, q0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р=111.

q1

0 q01C

1 q11R

Задачи решены правильно, в печатном виде, все подробно расписано.Все задачи решены согласно методички. Вы можете купить как всю работу целиком, так и каждую задачу по отдельности.