Определим понятие суперпозиции булевых функций из данного множества функций. Термином «суперпозиция» обозначают способ получения новых функций из заданного множества функций путем
a) отождествления переменных,
b) подстановкой имеющихся и вновь полученных функций в качестве аргументов имеющихся и вновь полученных функций до тех пор, пока это приводит к получению новых функций.
Множество всех функций, полученных применением операции суперпозиции к функциям данного множества F, называется замыканием 
и обозначается 
.
Система булевых функций называется функционально полной, если суперпозициями функций этой системы можно задать любую булеву функцию из Р2.
Естественной заведомо функционально полной системой является система {&, Ú, Ø}, которая позволяет представить любую функцию, заданную таблицей в виде СДНФ или СКНФ. Константы 0 и 1 также имеют представление в этой системе. Спрашивается, является ли эта система функций единственной функционально полной системой. Интуитивно можно ожидать, что нет. Действительно, как будет видно из дальнейшего рассмотрения, существует счетное множество таких систем. Используются два критерия, позволяющие судить о функциональной полноте системы булевых функций.
Первый основан на сравнении системы с заведомо функционально полной системой и использует следующую теорему.
Теорема о доказательстве функциональной полноты системы функций сравнением с заведомо функционально полной системой:
Пусть G и F подмножества Р2, известно, что система F функционально полна в Р2, и любая функция из F может быть задана суперпозицией функций из G. Тогда система G также функционально полна в Р2.
ª Пусть 
, 
, h(x1,x2,…,xn)ÎP2(n). Представим функцию h(x1,x2,…,xn) суперпозицией функций из F:
h(x1,x2,…,xn)=f(f1(x1,x2,…,xn), f2(x1,x2,…,xn),…,fm(x1,x2,…,xn)).Согласно условию, каждую из функций полученной суперпозиции можно выразить суперпозицией функций из G:
f=g(g1(x1,x2,…,xn), g2(x1,x2,…,xn),…,gk(x1,x2,…,xn)),
f1 =g1i(g1(x1,x2,…,xn), g2(x1,x2,…,xn),…,gk(x1,x2,…,xn)),
…………………………………………………………
fm=gmi (g1(x1,x2,…,xn), g2(x1,x2,…,xn),…,gk(x1,x2,…,xn)).
Объединяя полученные записи, получим для h суперпозицию
h(x1,x2,…,xn)=gh(g1(x1,x2,…,xn), g2(x1,x2,…,xn),…,gk(x1,x2,…,xn)). ¨
Используя эту теорему легко доказать функциональную полноту систем {&,Ø}, {Ú,Ø}, {®,0}, {0,Å,&}, {|}, {¯}.
Примеры:
1. Пусть D={&, Ú, Ø} – заведомо функционально полная система, и G={&, Ø}. Докажем, что система G функционально полна в Р2. Так как функции &, Ø уже имеются в G, остается показать, что функция Ú может быть определена суперпозицией над G. Воспользовавшись правилом де Моргана, получаем сразу 
, т.е. представляем дизъюнкцию суперпозицией над G.
2. Доказать, что система G={0, ®} функционально полна в Р2.
Выберем в качестве заведомо функционально полной системы множество D={&, Ø}. Для доказательства необходимо определить конъюнкцию и отрицание формулами над G. Целесообразная последовательность действий состоит в определении вначале Ø, а затем &. Поскольку константа 0 – нульместная функция, ее можно использовать только для подстановки в качестве аргумента в другие функции. Импликация – двуместная функция, в которой можно выполнить вначале отождествление переменных, а затем подстановку константы вместо одного из аргументов. Учитывая, что 
, и выполняя подстановку x ® y| y 0 = 
. Далее используем правило де Моргана для получения конъюнкции. 
Доказанная теорема дает универсальный способ доказательства функциональной полноты системы булевых функций. Однако если в проверяемое множество входят функции, более сложные, чем элементарные, процедура может оказаться достаточно трудоемкой. А учитывая отсутствие критерия, определяющего возможность получения требуемых функций из имеющихся, и невыполнимой.
Другой критерий функциональной полноты основан на критерии Поста. Прежде чем сформулировать этот критерий рассмотрим операцию замыкания и замкнутые классы булевых функций.
Дата: 2019-03-05, просмотров: 235.
