Докажите, что одна из систем связок I и II полная, а другая - не

Докажите, что одна из систем связок I и II полная, а другая - не (Решение → 14198)

Докажите, что одна из систем связок I и II полная, а другая - не полная. Для доказательства, что система связок полная, используйте системы связок ¬, ⋁ и ¬,⋀ полные. I II ↚, ← ↛,↚,⊕ Таблицы истинности функций ⊕,←,↛,↚: x y ⊕ ← ↛ ↚ 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0



Докажите, что одна из систем связок I и II полная, а другая - не (Решение → 14198)

Нетрудно видеть, что система II не является функционально полной, так как каждая из функций системы {↛,↚,⊕} сохраняет константу 0, т.е. на наборе (00) каждая из этих функций равна 0. По теореме Поста, полная система должна содержать хотя бы одну функцию, не принадлежащую любому из пяти замкнутых классов - сохраняющих константу 0, сохраняющих константу 1, монотонных, линейных и самодвойственных функций.
Рассмотрим систему {↚, ←} . Функция ← не сохраняет константу 0, но сохраняет константу 1, т.е. на наборе (11) функция равна 1. Однако, эта функция не монотонная, не линейная, не самодвойственная

. Функция ← не сохраняет константу 0, но сохраняет константу 1, т.е. на наборе (11) функция равна 1. Однако, эта функция не монотонная, не линейная, не самодвойственная