Докажите, что система функций является полной ~,⋁,0. Подробно обоснуйте решение, показав принадлежность функции из набора к тому или иному классу эквивалентности функций, или приведите пример, опровергающий эту принадлежность.
Решение
Докажем, что система ~,⋁,0 функционально полна.
Функция f=A~B) (эквивалентность):
* не сохраняет константу 0, так как f(0,0)=1;
* сохраняет константу 1, т.к. f(1,1)=1;
* не монотонная, так как f(0,0)>f(0,1);
* не самодвойственная;
* линейная.
Функция g(A,B)=A+B (дизъюнкция):
* сохраняет константу 0, т.к
. g(0,0)=0;
* сохраняет константу 1, т.к. g(1,1)=1;
* монотонна (в любой паре возрастающих наборов функция не уменьшается);
* не самодвойственная;
* не линейная, т.к. g(A,B)=A⊕B⊕AB;
Наконец, функция h(A,B)=0 (константа 0):
* сохраняет константу 0;
* не сохраняет константу 1;
* монотонна;
* не самодвойственна;
* линейная.
Составляем таблицу принадлежности функций системы основным классам булевых функций.
T0 T1 M S L
f ─ + ─ ─ ─
g ─ + ─ ─ ─
h + ─ + ─ +
Как следует из построенной таблицы, для каждого из пяти основных классов булевых функций найдется функция, не принадлежащая этому классу
на новый заказ в Автор24.
