Логика

Министерство образования Российской Федерации
Пермский государственный технический университет
Кафедра автоматизированных систем управления












КОНТРОЛЬНАЯ РАБОТА
по «Математической логике и теории алгоритмов»

Вариант № 3













Выполнил:
Рахимзянов В.Р.
Группа: АСУ-13бзу
Проверила:
Викентьева О.Л.







Пермь 2014
...

I. Логика и исчисление высказываний
1. Записать высказывания в виде формул логики высказываний.
Если х=5 и у=3, то х>y.
Решение:
1.3

2. Построить таблицы истинности для формул
2.1.

2.2




3. Доказать, что формулы являются тавтологиями
3.3.
Решение:
A B C





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

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.

5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.3

6. Получить СКНФ, а затем перейти к СДНФ
6.3

7. Получить МДНФ для формул
7.3


2.Получить множество дизъюнктов.
2.3 x,y,z (P(x)  Q(x,y) →R(z)  M(y))
Формула, в которой из логических символов встречаются только ⌐, &, , причем отрицание должно стоять перед символами предикатов, называется приведенной формой.
Приведенная форма называется нормальной (ПНФ), если она не содержит символов кванторов или все символы кванторов стоят в начале формулы за скобками (кванторная приставка).

3.3 Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
А1: Кто ходит в гости по утрам, тот поступает мудро.
А2: Если у кого угодно есть воздушный шарик, тот поступает мудро.
А3: У Пяточка есть воздушный шарик.
Вопрос: Кто поступает мудро?

Решение:

4.3 Для заданной системы аксиом доказать теорему.
А1:
T:
Решение.

III Теория алгоритмов
1. Построить машину Тьюринга (результат представить в форме таблицы):
В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево.

Решение. Дан входной алфавит A = {0, 1, l}.
2.1 Доказать, что функции примитивно-рекурсивны:
f(x)=x+n;
Доказательство:

3.3 Построить нормальный алгоритм Маркова, который:
Преобразует любое слово в алфавите {x,y,z} в слово zzx.
Нормальная схема подстановок:

Контрольная работа по «Математической логике и теории алгоритмов»

527 mod 15 = 2+1 = 3 вариант

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Формулы являются тавтологиями, так все значения – истина.
4. Доказать полноту (неполноту) систем булевых функций
Класс функций F называется полным, если его замыкание совпадает с Pn:
.
Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F.
Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.
1) P0 - класс функий, сохраняющих нуль (т.е если f(0,0,...,0)=0, то f принадлежит этому классу). Проверяем
F(0,0)=0↓0=1 – не принадлежит классу P0
2) P1 - класс функций, сохраняющих единицу (т.е если f(1,1,...,1)=1, то f принадлежит этому классу).
F(1,1)=1↓1=0 – не принадлежит P1
3)L-класс функций, представимы линейным многочленом Жегалкина.
F(x,y)=x↓y=¬xÙ¬y=(x⊕1)Ù(y⊕1)= xy⊕x⊕y⊕1
Получился нелинейный многочлен, значит, функция не принадлежит классу L.
4) S - класс самодвойственных функций. То есть функций, для которых выполняется:
f(x1,x2,...,xn)=¬f(¬x1,¬x2,...,¬xn)
Самодвойственность проще всего определять по таблице значений функции. 
x
y
F
1
1
1
1
1
Таблица самодвойственной функции интересна тем, что столбец ее значений переходит сам в себя при инвертировании. То есть, например, первое значение функции должно равняться отрицанию последнего, второе - отрицании предпоследнего, и так далее. 
В нашем случае функция F является несамодвойственной функцией.
5) M -класс монотонных функций. 
Функция f называется монотонной, если для любых наборов значений переменных(α1,α2,...,αn) и (β1,β2,...,βn), таких что (α1,α2,...,αn)≤(β1,β2,...,βn), выполняется f(α1,α2,...,αn)≤f(β1,β2,...,βn).
Бинарное отношение ≤ понимается так: (α1,α2,...,αn)≤(β1,β2,...,βn) ⇔ ∀i (αi≤βi).
Тогда функция F не монотонна.
Теперь, когда мы проверили все функции на принадлежность к этим пяти классам, можно построить таблицу Поста.
P0
P1
L
S
M
F
-
-
-
-
-
Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.
Значит, наша система функций полна.
5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.3
x
y
z
1
2
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
СДНФ:
Переход к СКНФ:
6. Получить СКНФ, а затем перейти к СДНФ
6.3
x
y
z
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
СКНФ:
Переход к СДНФ:
7. Получить МДНФ для формул
7.3
x
y