Найти число структур соответствующей сигнатуры на универсе из n элементов, в которых истинны следующие предложения: 1) ∃x(неR)(x, x)
2) ∀x[P(x)& S(x)]

задан 15 Дек '16 23:13

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

Второй пункт тривиален: оба предиката всюду истинны, и такая структура одна.

Первое также просто: всего имеется $%2^{n^2}$% способов задать двуместный предикат на $%n$%-элементом множестве, выбирая одно из двух логических значений для каждой из $%n^2$% упорядоченных пар. Нам не подходят рефлексивные, когда для всех $%x$% истинно $%R(x,x)$%. Таких отношений $%2^{n^2-n}$%, так как они свободно задаются всюду кроме диагонали. Их число вычитаем, и получается $%2^{n^2}-2^{n^2-n}$%.

ссылка

отвечен 16 Дек '16 0:03

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

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

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

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

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

отмечен:

×1,255
×777

задан
15 Дек '16 23:13

показан
343 раза

обновлен
16 Дек '16 0:03

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

по почте:

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

по RSS:

Ответы

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

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