Найти число структур соответствующей сигнатуры на унивёрсум из n элементов, в которых истинны следующие предложения

1) ∃x∃y[R(x,y)&R ̅(y,x)]

R ̅ (это R с штрихом сверху)

задан 23 Дек '18 12:05

изменен 23 Дек '18 12:11

О терминологии: по-русски говорят "универсум", а "унивёрс" -- это "смесь французского с нижегородским" (с) :) Также предложения каковы? -- истиННы (краткое прилагаетельное во множественном числе).

(23 Дек '18 12:09) falcao

Извиняюсь )))

(23 Дек '18 12:10) Алексей1703
10|600 символов нужно символов осталось
0

В логических формулах знак отрицания лучше писать явно в виде символа. В логике предикатов именно так принято, потому что R с чертой будет восприниматься как новый предикатный символ.

Общее число двуместных предикатов на n-элементном множестве равно 2^{n^2}: для каждой упорядоченной пары решаем, истинно или ложно значение R на этой паре. Здесь задано условие, что R не симметрично: существует такая пара (x,y), для которой R(x,y) истинно и R(y,x) ложно. Значит, надо из общего количества вычесть число симметричных отношений.

Мы задаём отношение в виде матрицы из нулей и единиц. Симметричному соответствует матрица, симметричная относительно главной диагонали. На ней самой и выше неё мы выбираем числа произвольно, а числа ниже главной уже определяются однозначно по симметричным им числам выше. Число мест на диагонали равно n; выше и ниже неё -- по n(n-1)/2. Значит, симметричное отношение свободно задаётся n+n(n-1)/2=n(n+1)/2 параметрами. Их будет 2^{n(n+1)/2}, а ответом к задаче будет разность двух степеней двойки.

Для примера: при n=3 получается 2^9-2^6=448 структур.

ссылка

отвечен 23 Дек '18 12:17

falcalo Спасибо большое!Разрешите ещё 1 вопрос задать?

(23 Дек '18 19:04) Алексей1703

Построить поисковые деревья для следующего утверждения:

https://photos.app.goo.gl/RRNSmkEKVM24AD388

(23 Дек '18 19:22) Алексей1703

@Алексей1703: вопросов на форуме можно задавать сколько угодно. Но для новых вопросов полагается открывать новые записи.

По поводу "поисковых деревьев": я не знаю определения этого понятия. Оно явно не общематематическое, а прикладное. Нужно приложить или определение, или ссылки на литературу.

(23 Дек '18 19:48) falcao

Литературы к сожалению нет, но вот пример решения (https://photos.app.goo.gl/4wwcF9ky1uoC5AJa9)

(24 Дек '18 10:33) Алексей1703

@Алексей1703: из этого примера не ясно, что следует делать с кванторами. То есть информации не достаточно. И это уже не математическая задача, а из серии "как оформить".

(24 Дек '18 11:41) falcao

Согласен, спасибо и на этом. Я вам очень благодарен!

(24 Дек '18 11:59) Алексей1703
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,103
×691

задан
23 Дек '18 12:05

показан
57 раз

обновлен
24 Дек '18 11:59

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

по почте:

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

по RSS:

Ответы

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

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