Транзитивное и антирефлексивное бинарное отношение не содержит циклов длины 3

задан 13 Мар 18:59

как это доказать с помощью метода резолюций, составив формулу логики предикатов?

(13 Мар 19:00) olga5

@olga5: я могу дать обычное доказательство. Если есть цикл длиной 3, то существуют a, b, c такие, для которых P(a,b), P(b,c), P(c,a). Из первых двух условий следует P(a,c) ввиду транзитивности, что противоречит P(c,a) по причине антирефлексивности.

Это всё можно оформить в рамках доказательств в логике предикатов, так как суть довольно простая. Правда, делать это по схеме метода резолюций я бы не стал, так как саму эту технику считаю безнадёжно устаревшей. Она появилась где-то лет 90 назад, на заре развития математической логики. Кто-то по инерции до сих пор изучает эту "лошадиную упряжь" :)

(13 Мар 22:00) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×64

задан
13 Мар 18:59

показан
105 раз

обновлен
13 Мар 22:00

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

по почте:

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

по RSS:

Ответы

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

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