Докажите полноту базиса, состоящего из одной функции x | y, которая по определению равна ¬(x∧y) (штрих Шеффера, она же NAND).

задан 25 Мар '16 11:18

@marka_17 Необходимо либо выразить каждую из оставшихся 15 булевых функций 2ух переменных через штрих Шеффера (конструктивно), либо проверить выполнение всех условий критерия Поста для штриха Шеффера (теоретически).

(25 Мар '16 11:23) aid78

Самый простой способ такой: x|x даёт отрицание, и если в него подставить штрих Шеффера, то это даёт конъюнкцию. Через отрицание и конъюнкцию выразима дизъюнкция. А то, что любая функция выражается через И, ИЛИ, НЕ -- это известная теорема о представлении функции в виде ДНФ или КНФ.

(25 Мар '16 11:30) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×56
×26

задан
25 Мар '16 11:18

показан
1128 раз

обновлен
25 Мар '16 11:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru