Задание № 3

Доказать общезначимость формулы без построения истинностных таблиц.

(P  Q) /\ (Q  R) (P  R)

1. Метод от противного.

Пусть данная формула не общезначима, тогда

(P  Q) /\ (Q  R) (P  R) =Л

Это уравнение равносильно системе:

P  Q = И P= И

Q  R = И R = Л

P  R = Л, откуда И  Q = И

Q  Л = И

Два последних уравнения противоречат друг другу. Значит, предположение неверно, а формула – общезначима.

2. Метод равносильных преобразований.

При равносильных преобразованиях формул поступают обычно следующим образом: вначале, используя равносильности, соответствующие общезначимым формулам ( 14 ), (15) Предложения 9 избавляются от эквиваленций и импликаций, затем, наиболее часто используют дистрибутивные законы, законы идемпотентности, поглощения, де Моргана, двойного отрицания, импликации и др., учитывая, что А\/И  И, А/\Л  Л,

А\/Л  А, А/\И  А.

В нашем случае имеем:

(P  Q) /\ (Q  R) (P  R)  ⁽¹⁵⁾ ┐((P  Q) /\ (Q  R)) \/(P  R)  ⁽³⁸⁾ ┐(P  Q) \/ ┐(Q  R) \/(P  R)  ^{(18, 15)} P /\ ┐ Q \/ Q /\ ┐R \/ ┐P\/ R ^(22,25) (┐P\/ P/\┐ Q) \/ (R\/ Q/\ ┐R) ⁽²⁸⁾ (┐P\/ P) /\ (┐P\/┐Q) \/ (R\/ Q) /\ (R\/┐R) ^(44,25) ┐P\/┐Q\/ R\/ Q ^(22,25) ┐P\/ R\/ (Q\/┐Q) ⁽⁴⁴⁾ ┐P\/ R\/И  И.

Задание № 4

Записать предикат, связанный с логической функцией, Область истинности которой заштрихована на рисунке.

Искомый предикат А (х) обращается в истинное высказывание при всех тех и только тех значениях х , которые определены на некотором множестве D, при которых Р (х) имеет своими значениями истинное высказывание, а Q (x)- ложное. Значит,

Задание № 5

Проанализировать рассуждение: «Ни одно животное не бессмертно. Кошки – животные. Значит некоторые кошки не бессмертны».

Переведем каждое высказывание на язык алгебры предикатов. Выберем в качестве области D множество живых существ.

Обозначения: Ж(х): х – животное; Б(х): х – бессмертно; К (х) : х- кошка

Структура рассуждения : х(Ж(х) Б (х)), х(К(х)Ж (х)) = х (К(х)  /\  Б (х)).

Анализ рассуждения сводится к проверке правильности следования :

х(Ж(х) Б (х)), х(К(х)Ж (х)) = х (К(х)  /\  Б (х)).

Проверяем « Методом от противного»

Предположим, что следование неверно. Тогда хотя бы в одной интерпретации будет иметь место система :

 х ( l_i(x)  l_i(x) ) = И

 х ( l_k(x)  l_i(x) ) = И (1), откуда

х( l_k(x) /\  l_i(x) ) = Л

l_i(x)  l_i(x) = И

l_k(x)  l_i(x) = И (2)

l_k(x) /\  l_i(x) = Л при всех х  D.

Но на D = 1,2,3 возможно (l₂(2), l₃(2), l₆(2)) = ( И, И, И), и при этом система (2) непротиворечива. Значит рассуждение правильное.

Задание № 6

Составить программу МТ, вычисляющей значения функции

1, если 2а

f(a) =

0, если  2а

Будем считать, что алфавит машины Т к вычислениям для данного аргумента а, в момент 0 установим машину Т в начальное положение, в котором самая левая клетка на лента пустая, аргумент представлен знаками в следующих а+1 клетках, все клетки справа от них - пустые, машина обозревает самую правую из заполненных клеток и находится в начальном состоянии q₁. В таком случае говорят, что машина применяется к числу а как к аргументу.

Машина вычисляет значение с для а в качестве аргумента, если, исходя из начального положения в момент 0 , машина в некоторый последующий момент приходит в пассивное состояние q₀ (останавливается), причем на ленте после а+1 знаков, представляющих аргумент, и одного пробела напечатано с +1 знаков, на остальной части ленты ничего не напечатано и машина опять обозревает самую правую из заполненных клеток.

Если машина для каждого а вычисляет значение с, где с= f(a), то говорят, что машина вычисляет функцию f(a).

Функция f(a) называется вычислимой по Тьюрингу, если существует МТ, вычисляющая f(a) для любого а.

Условимся не рисовать ленту и изображать ситуацию последовательностью нулей и единиц, указывая состояние машины над той буквой, которую машина обозревает, например 011011⁰00…

Условимся нули, обозначающие все пустые клетки после последней заполненной, не писать и опускать также знак многоточия.

В нашей машине всякой четное число изображается нечетным числом знаков, всякое нечетное число – четным числом. Работа машины Т может быть описана следующей блок-схемой: