alt text

задан 17 Сен '17 13:45

10|600 символов нужно символов осталось
0

Как-то пропустил условие этой задачи в своё время.

Предположим, что равенство вида $%\Phi_1=\Phi_2$% не является тождеством, где $%\Phi_i$% ($%i=1,2$%) -- формулы, составленные из $%A_1,\ldots,A_n$% по указанным правилам. Тогда новая формула $%(\Phi_1\setminus\Phi_2)\cup(\Phi_2\setminus\Phi_1)$% задаёт множество, которое не всегда является пустым.

Известно, что всякую формулу можно представить в виде СДНФ (совершенной дизъюнктивной нормальной формы). В данном случае это будет объединение множеств вида $%B_1\cap\cdots\cap B_n$%, где каждое $%B_j$% ($%1\le j\le n$%) есть либо $%A_j$%, либо его дополнение. В нашем случае хотя бы один такой дизъюнктивный член должен быть (в противном случае мы получили бы тождество). Теперь достаточно рассмотреть область (универсальное множество) из одного элемента $%x$%, и потребовать условия $%B_j=\{x\}$% для каждого $%j$%. При этом каждое $%A_j$% будет состоять из $%x$% или окажется пустым.

Более интересный вариант задачи получился бы при рассмотрении формул с участием кванторов. Тогда одноэлементной области уже могло бы не хватить, но сами множества можно было бы оставить не более чем одноэлементными.

ссылка

отвечен 24 Дек '17 0:51

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×889

задан
17 Сен '17 13:45

показан
234 раза

обновлен
24 Дек '17 0:51

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

по почте:

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

по RSS:

Ответы

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

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