Дан набор функций F, который не является функционально полной системой. Дополните этот набор пятью различными функциями так, чтобы получившийся набор оставался функционально неполным. Подробно обоснуйте решение, показав принадлежность функции из набора к тому или иному классу эквивалентности функций, или приведите пример, опровергающий эту принадлежность.
F=f1A,B=A↓A→B; f2A,B=A⋀B; f3A,B=¬AB.
Решение
Исследуем на принадлежность функций заданного набора основным замкнутым классам булевых функций. Это удобно делать, имея таблицу истинности исследуемой функции.
Имеем
f1A,B=A↓A→B=A↓A+B=AA+B=
=AAB=0.
Итак, первая исследуемая функция - это константа 0. Легко видеть, что она:
* принадлежит к классу функций, сохраняющих константу 0, т.е. 0∈T0;
* не принадлежит к классу функций, сохраняющих константу 1, т.е. 0∉T1;
* является монотонной, так как при возрастании наборов, функция не уменьшается, т.е. 0∈M;
* не является самодвойственной, так как при повороте значений истинности и их инвертировании, не получаем исходную функцию, т.е
. 0∉S;
* является линейной (нет конъюнкции переменных), т.е. 0∈L.
Функция f2A,B=A⋀B:
* сохраняет константу 0, так как f20,0=0⋀0=0, т.е. f2∈T0;
* сохраняет константу 1, так как f21,1=1⋀1=1, т.е. f2∈T1;
* монотонна, так как при возрастании наборов функция не уменьшается, т.е. f2∈M;
* не самодвойственная, т.е. f2∉S;
* не линейная (имеется конъюнкция переменных), т.е. f2∉L.
Наконец, функция
f3A,B=¬AB=(A+B)=AB.
Эта функция дублирует вторую функцию набора.
Составим таблицу принадлежности заданных функций основным классам булевых функций.
T0 T1 M S L
f1 + ─ + ─ +
f2 + + + ─ ─
f3 + + + ─ ─
По теореме Поста, система функций является полной, если она содержит хотя бы одну функцию, не принадлежащую основным классам булевых функций.
Ясно, что заданная система не полна, так как все функции сохраняют константу 0 и монотонны.
Добавим 5 требуемых функций, которые ничего не дают в смысле полноты