Логика

Задание1. Представьте с помощью кругов Эйлера отношения между объемами имен.
Дверная ручка из матового золота – Ручка на массивных дверях – Ручка на меж комнатных дверях
Решение.
А – Дверная ручка из матового золота
B – Ручка на массивных дверях
C– Ручка на межкомнатных дверях

 
Журнал – Иллюстрированный журнал – Журнал без иллюстраций
Решение.
A – Журнал
B – Иллюстрированный журнал
C – Журнал без иллюстраций

 
Директор магазина – Верный семьянин – Обеспечивающий двух любовниц
Решение.
A – Директор магазина
B – Верный семьянин
C – Обеспечивающий двух любовниц

 
Тетрадь в клетку – Тетрадь с яркой обложкой – Тетрадь из 18 листов
Решение.
A – Тетрадь в клетку
B – Тетрадь с яркой обложкой
C – Тетрадь из 18 листов


 
Правнук – Внук – Сын
Решение.
A – Правнук
B – Внук
C – ...

Задание1. Представьте с помощью кругов Эйлера отношения между объемами имен.
1. Дверная ручка из матового золота – Ручка на массивных дверях – Ручка на меж комнатных дверях
Решение.

Задание1. Представьте с помощью кругов Эйлера отношения между объемами имен.
1. Дверная ручка из матового золота – Ручка на массивных дверях – Ручка на меж комнатных дверях
Решение.

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