Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Полные системы функций. Система функций {}

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость

Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .

Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2n строк. Каждую строку можно представить в виде конъюнкции переменных х1,…хn, куда входит либо , либо . Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.

Пример.

x

y

f(x,y)

0

0

1

0

1

1

1

0

0

1

1

1

Получим СДНФ, используя таблицу истинности.

Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.

Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?