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

(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…

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

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

 

 

 

 

 

ЗАДАНИЯ ДЛЯ ДОМАШНЕЙ КОНТРОЛЬНОЙ РАБОТЫ

 

Указания к заданиям: знак É читать как знак ®, а знак» как знак «

 

Вариант №1

Задание № 1

Составить СНФ, преобразовать и построить схему: P/\ ┐ (┐QÉ R)

 

Задание № 2

Три девочки – Роза, Маргарита и Анюта представили на конкурс цветоводов корзины с выращенными ими цветами: розами, маргаритками и анютиными глазками. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием выращенных цветов.

Какие цветы вырастила каждая из девочек?

 

Задание № 3

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

(P\/Q~Q) ~ (P É Q).

Задание № 4

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

 

Задание № 5

Проанализировать рассуждение: «Перья есть только у птицы. Ни одно млекопитающие не является птицей. Значит, все млекопитающие лишены перьев».

 

Задание № 6