Математическая логика

математика логика информатика

Докажите неполноту следующих систем булевых функций:
1) {V, +}
2) {+, ~};

Ну первая не полная, обе принадлежать классу сохраняющих 0. Так это доказывается? а второе я что-то затрудняюсь
Ответы:
Ну, а во второй системе обе функции линейные => система целиком содержится в классе L.
Полином Жегалкина для +: f(x, y) = x + y — линейный.
Полином Жегалкина для ~ : f(x,y) = 1 + x + y — линейный.
Поэтому, по теореме Поста система не является полной.


11 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.