Как доказать, что ДНФ без отрицаний нельзя построить, если ф-ция немонотонна?

задан 3 Окт '17 19:49

Это очевидно: конъюнкция и дизъюнкция монотонны, и всё, что через них выражается, тоже будет монотонно ввиду функциональной замкнутости класса монотонных функций (это значит, что всё, что выражается через монотонные функции, автоматически монотонно). Значит, немонотонную функцию в таком виде не представить.

(3 Окт '17 20:22) falcao

А есть ли способ доказать это более строго?

(3 Окт '17 20:40) cheburazshka

@cheburazshka: это абсолютно строгое рассуждение -- строже просто некуда. Если Вы имеете в виду более формальное доказательство, на языке формул, то смотрите в учебниках.

Вообще, это утверждение совершенно тривиальное, а вот обратное ему -- что любую монотонную можно в таком виде представить, -- оно гораздо более интересно.

(3 Окт '17 21:19) falcao

Обратное несложно найти, а вот где это утверждение прочитать не получается найти.

(3 Окт '17 21:33) cheburazshka

@cheburazshka: а что Вам здесь непонятно?

(3 Окт '17 21:41) falcao

@falcao к примеру что значит монотонность конъюкции/дизъюнкции и почему всё, что выражается через монотонные ф-ции монотонно, это не очевидно для меня.

(3 Окт '17 22:04) cheburazshka

@cheburazshka: повторите определение монотонной функции из учебника. Посмотрите на таблицы истинности для конъюнкции и дизъюнкции. Убедитесь, что они этому условию удовлетворяют. То, что монотонность сохраняется при суперпозиции, доказывается в учебниках, причём очень просто. Можно взять учебник Яблонского, например.

(4 Окт '17 1:18) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×416

задан
3 Окт '17 19:49

показан
351 раз

обновлен
4 Окт '17 1:18

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

по почте:

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

по RSS:

Ответы

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

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