Подскажите пожалуйста, где можно найти доказательство(или как доказать), что:

1) $% Ja(x \vee y) = Ja(x) \wedge (J0(y) \vee J1(y) \vee ... \vee Ja(y)) \vee Ja(y) \wedge (J0(x) \vee J1(x) \vee .. \vee Ja(x)) $%

2) $% Ja(x \wedge y) = Ja(x) \wedge (Ja(y) \vee Ja+1(y) \vee ... \vee Jk-1(y)) \wedge Ja(y) \wedge (Ja(x) \vee Ja+1(x) \vee .. \vee Jk-1(x)) $%

задан 23 Май '17 21:39

изменен 23 Май '17 21:53

Что такое Ja?

(23 Май '17 21:58) falcao

@falcao Ji(x) = k-1, если x = i; 0, если x != i;

(23 Май '17 22:00) GregorySmit

@GregorySmit: я так и подумал, но обычно вообще-то там нижний индекс добавляют.

(23 Май '17 22:27) falcao

@falcao да, тут нижний индекс

(23 Май '17 22:29) GregorySmit
10|600 символов нужно символов осталось
1

Здесь можно всё проверить непосредственно, на основании определений.

1) Предположим, что max(x,y)=a. Тогда левая часть равна k-1. Проверим, что правая часть равна тому же самому. Мы имеем или x=a, y<=a, или x<=a, y=a. Правая часть симметрична, и достаточно разобрать первый случай. Понятно, что Ja(x)=k-1 (раз Вы не добавляете нижний индекс, то и я не буду :)), а в выражении J0(y) V ... V Ja(y) встретится Jy(y)=k-1 ввиду y<=a. Максимум равен k-1, и его минимум с самым первым членом тоже равен k-1. Значит, получается дизъюнкция (максимум) k-1 и чего-то, то есть k-1, как и заказывали.

Теперь достаточно проверить, что если правая часть равна k-1, то и левая тоже. В правой части последней операцией идёт дизъюнкция. Если получилось k-1, то хотя бы один дизъюнктивный член равен k-1. Ввиду симметрии, можно без ограничения общности считать, что это первый член. Он представляет собой конъюнкцию (минимум), откуда Ja(x)=k-1, то есть x=a. Помимо этого, выражение J0(y) V ... V Ja(y) равно k-1, то есть некоторый из членов равен k-1. Это возможно тогда и только тогда, когда среди индексов 0, 1, ... , a встретится y. Последнее равносильно условию y<=a, то есть получилось то, с чего мы начали.

Надо заметить, что проверки здесь тавтологичны. То есть ничего неожиданного или "хитрого" тут нет.

2) Эту формулу можно отдельно не проверять, так как она двойственна предыдущей: мимнимум и максимум меняются ролями, а константы заменяются на отрицание Лукасевича (0 на k-1, 1 на k-2, и так далее).

ссылка

отвечен 23 Май '17 22:40

@falcao спасибо, всё оказалось проще, чем я думал

(23 Май '17 22:58) GregorySmit
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×888

задан
23 Май '17 21:39

показан
426 раз

обновлен
23 Май '17 22:58

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

по почте:

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

по RSS:

Ответы

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

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