03.1. Полнота и замкнутость. Функционально полные системы
Определение 3.1. Для произвольного класса системы двоичных функций 
множество всех двоичных функций, представимых формулами, над , называется замыканием класса (системы) функций и обозначается через 
.
Имеют место следующие свойства замыкания.
Свойство 3.2. 
.
Свойство 3.3. 
.
Свойство 3.4. 
.
Обозначим через 
множество всех двоичных функций от N переменных, а через 
множество всех двоичных функций (от произвольного числа переменных).
Определение 3.5. Система функций называется полной, если 
.
Утверждение 3.6. Система функций 
является полной системой функций.
Доказательство. Очевидно, что элементарная конъюнкция 
является формулой над 
. Отсюда следует, что дизъюнкция любого числа элементарных конъюнкций является формулой над . Отсюда и из равенства (2.5) следует, что любая функция 
, представима над формулой . Следовательно, 
.
Утверждение 3.7. Система функций 
является полной системой функций.
Доказательство. Очевидно, что 
, из равенства 
следует, что 
. Отсюда и из свойств 3.3 и 3.4 имеем: 
, т. е. 
. Таким образом, показано, что 
и . Полученные включения означают, что 
Утверждение 3.8. Система функций 
является полной системой функций.
Доказательство. Очевидно, что 
, из равенства 
следует, что 
. Отсюда и из свойств 3.3 и 3.4 имеем: 
, т. е. 
. Таким образом, показано, что 
и 
. Полученные включения означают, что 
Утверждение 3.9. Система функций 
является полной системой функций, где 
— двоичная функция, называемая штрихом Шеффера, задается табл.3.1.
|
Доказательство. Очевидно, что
Следует, что |
Таблица 3.1 |
|
|
|
|
0 1 0 1 1 |
1 1 1 0 |
. Из равенств
и 
. Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановке 
вместо 
Утверждение 3.10. Система функций 
, является полной системой функций.
Доказательство. Очевидно, что 
. Из равенства 
следует, что 
. Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановке 
вместо 
Утверждение 3.11. Система функций 
является полной системой функций, где 
— двоичная функция, называемая стрелкой Пирса, задается табл.3.2.
|
Доказательство. Очевидно, что |
Таблица 3.2 |
|
|
|
|
0 1 0 1 1 |
1 0 0 0 |
. Из равенств 
и 
следует, что 
. Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановке 
вместо 
и 
вместо 
Определение 3.12. Каждая двоичная функция 
, образующая полную систему, называется Шефферовой функцией.
Пример 3.13. Функция 
является шефферовой функцией. Это следует из утверждения 3.9.
Пример 3.14. Функция 
является шефферовой функцией. Это следует из утверждения 3.11.
Примеры шефферовых функций от большего числа переменных будут приведены ниже, после изложения критерия полноты системы двоичных функций.
| < Предыдущая | Следующая > |
|---|
