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

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

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

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

Условие

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

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

Решение

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

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

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

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

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