Полнота и замкнутость
Ранее рассматривались два способа задания логической функции – табличный вид и формулой. Табличный способ универсален (т.е. пригоден для любой функции), но громоздок. Формула – более компактный способ, но она задает функцию через другие функции. Поэтому возникает вопрос: любая ли логическая функция может быть представлена формулой через функции некоторой системы функций?
Определение. Система функций из Р2 { f1, … , fn } называется (функциональ-но) полной, если любая логическая функция может быть представлена в виде формулы через функции этой системы.
Пример. Система функций {
, x1 & x2,
x1
x2 } является полной.
Это следует из того, что любая логическая функция может быть представлена в СДНФ, т.е. формулой в которую входят только функции данной системы. Это и означает, что данная система будет полной.
Теорема. Пусть система функций F1 = { f1, … ,fn } полная, а каждая ее функция выражается в виде формулы через функции системы F2 = { h1, … , hm }. Тогда система F2 так же полная.
Доказательство данной теоремы приведено в [1]. Опираясь на эту теорему, можно установить полноту других систем.
Пример. Доказать, что система функций {, x1 & x2}
будет полной.
Согласно закону де Моргана имеем: x1 x2 =
, т.е.
функция x1 x2 выражается через функции данной
системы. Следовательно, каждая функция системы предыдущего примера выражается через функции
данной системы. Поэтому по представленной теореме эта система тоже будет полной.