Докажите, что всякую булеву схему размера s с n переменными можно переделать в булеву схему, в которой все отрицания применяются только к переменным, и при этом размер новой схемы не превышает p(s;n), где p – некоторый фиксированный полином

задан 24 Янв '16 18:36

Здесь надо дать точное определение размера схемы, чтобы можно было аккуратно проводить доказательство. Вообще-то здесь достаточно законов де Моргана и индукции.

(24 Янв '16 21:46) falcao

Будем считать, что размер схемы - это количество в ней элементов, а сама схема вычисляется в базисе из отрицания, конъюнкции и дизъюнкции

(24 Янв '16 22:06) kernel2111

@kernel2111: допустим, есть схема $%\bar{x}\lor(y\land z)$%. Каков у неё размер? Верно ли, что это число использованных при построении формулы логических связок?

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

Ваш ответ

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

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

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

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

отмечен:

×1,343
×26

задан
24 Янв '16 18:36

показан
564 раза

обновлен
24 Янв '16 23:12

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

по почте:

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

по RSS:

Ответы

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

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