Дан набор функций F который не является функционально полной системой. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Дан набор функций F который не является функционально полной системой

Дан набор функций F который не является функционально полной системой .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Дан набор функций F, который не является функционально полной системой. Дополните этот набор пятью различными функциями так, чтобы получившийся набор оставался функционально неполным. Подробно обоснуйте решение, показав принадлежность функции из набора к тому или иному классу эквивалентности функций, или приведите пример, опровергающий эту принадлежность. F=f1A,B=A⋀B; f2A,B=(A→B)⋀A; f3A,B=A↔B.

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Исследуем на принадлежность функций заданного набора основным замкнутым классам булевых функций. Это удобно делать, имея таблицу истинности исследуемой функции.
Имеем
f1A,B=A⋀B.
Итак, первая исследуемая функция - это конъюнкция. Легко видеть, что функция f1A,B=A⋀B:
* сохраняет константу 0, так как f10,0=0⋀0=0, т.е. f1∈T0;
* сохраняет константу 1, так как f11,1=1⋀1=1, т.е. f1∈T1;
* монотонна, так как при возрастании наборов функция не уменьшается, т.е. f1∈M;
* не самодвойственная, т.е. f1∉S;
* не линейная (имеется конъюнкция переменных), т.е . f1∉L.
Вторая функция
f2A,B=A→B⋀A=A⋁B⋀A=A⋀B.
Эта функция была рассмотрена выше.
Наконец, функция
f3A,B=A↔B.
Это эквивалентность.
Итак, функция f3A,B:
* сохраняет константу 0, так как f30,0=0, т.е. f3∈T0;
* сохраняет константу 1, так как f31,1=1, т.е. f3∈T1;
* не монотонна, так как f30,0>f30,1, т.е. f3∉M;
* не самодвойственная, т.е. f3∉S;
* не линейная (имеется конъюнкция переменных), т.е. f3∉L.
Составим таблицу принадлежности заданных функций основным классам булевых функций.
T0 T1 M S L
f1 + + + ─ ─
f2 + + + ─ ─
f3 ─ + ─ ─ +
По теореме Поста, система функций является полной, если она содержит хотя бы одну функцию, не принадлежащую основным классам булевых функций.
Ясно, что заданная система не полна, так как все функции сохраняют константу 1.
Добавим 5 требуемых функций, которые ничего не дают в смысле полноты

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу