Здравствуйте, можете объяснить, как выполняется проверка функции на монотонность? Знаю, что нужно строить таблицу истинности, а вот что дальше? Например, для xy+yz, где *-конъюнкция, + -исключающее ИЛИ

задан 28 Дек '18 2:44

@Lastik: если таблица большая, то задача проверки может быть сравнительно трудной. Для небольших таблиц можно в принципе перебрать все пары наборов, один из которых покоординатно превосходит другой. Для монотонного случая обычно бывает можно доказать это свойство, выражая функцию через монотонные конъюнкцию и дизъюнкцию. Для немонотонной достаточно одного контрпримера.

С функцией xy+yz всё совсем просто, потому что она равна 0 на максимальном наборе из одних единиц. Монотонная функция с таким свойством только одна -- тождественный ноль. Здесь же это не так: f(1,1,0)=1. Монотонности нет.

(28 Дек '18 3:03) falcao

@falcao а не могли бы вы помочь с монотонностью xz, 0, x+y+1, x->y, где -конъюнкция, + -исключающее ИЛИ У меня задание проверить систему ф-ций на полноту. Но застряла я на монотонности

(28 Дек '18 20:46) Lastik

@Lastik: для исследования системы на полноту, достаточно увидеть хотя бы одну немонотонную функцию, если она есть. Конъюнкция и 0 монотонны, их пропускаем. Смотрим на f(x,y)=x+y+1. Видно, что f(0,0)=1, то есть функция равна 1 на наименьшем наборе. Монотонность означает, что если мы значения переменных как-то увеличиваем, то значение функции не уменьшается. Тогда оно должно остаться равным 1 всегда. Но это не так, поскольку f(0,1)=0+1+1=0. Налицо немонотонность. Для того, чтобы это увидеть, достаточно "не побояться" взять и подставить какие-то числа.

То же самое для импликации: там (0->0)=1.

(28 Дек '18 20:52) falcao

@falcao Огромное вам спасибо, теперь я поняла. А проверить нужно все, ибо после нужно будет выписать ее базис

(28 Дек '18 20:55) Lastik

@Lastik: имейте в виду, что у этой полной системы базис можно выделить несколькими способами.

(28 Дек '18 21:02) falcao

@falcao где-то читала, что мы берем столбец, например, Т0 и выписываем дизъюнкцию тех ф-ций, у которых на этом столбце -. А после переходим к следующему столбцу. И между этими наборами ставим конъюнкцию. И, вроде, этот способ у меня засчитывали И появился вопрос, является ли 0 самодвойственным?

(28 Дек '18 21:12) Lastik

@Lastik: честно говоря, я не понимаю, что Вы пытаетесь сказать в начале. T0 -- это класс функций, а не столбец. Что значит на этом столбце чёрточка? Засчитывали способ решения какой задачи?

Функция 0 двойственная функции 1, а не себе. То есть она не самодвойственна. Есть короткое определение функций из S: она должна на противоположных наборах принимать противоположные значения. Здесь это не так: у функции 0 значение всегда только 0.

(28 Дек '18 22:44) falcao

@falcao Можете, пожалуйста, проверить, правильно ли сделала? + это принадлежит классу, - не принадлежит. Все обозначено таким образом: f(T0,T1,S,L,M). xy+yz (+, -, -, -, -); x*z (+, +, -, -, +); 0 (+, -, -, +, +); x+y+1 (-, +, +, +, -); x->y (-, +, -, -, -)

(28 Дек '18 23:26) Lastik

@Lastik: функция x+y+1 не самодвойственна. У неё значения на противоположных наборах одинаковые. Двойственной для неё будет эквиваленция. Остальное, насколько могу судить, верно.

(29 Дек '18 0:03) falcao

@falcao нашла несколько ошибок. Вот исправленный вариант f(T0,T1,S,L,M). xy+yz (+, -, -, +, -); x*z (+, +, -, +, +); 0 (+, -, -, -, +); x+y+1 (-, +, -, +, -); x->y (-, +, -, -, -) А можете помочь с базисами?

(29 Дек '18 0:04) Lastik

@Lastik: Вы исправили одну ошибку, но сделали кучу новых :) С какой это вдруг стати конъюнкция стала линейной, а функция 0 стала нелинейной? Чем Вы руководствовались для такого заключения?

Базисов в той системе два. Прежде всего, 0 убрать нельзя, так как остальные функции из T1. Если импликацию оставляем, то она вместе с нулём даёт полную систему. Остальные две функции лишние. Это один из базисов. Если импликация не входит, то получается второй базис. Там нельзя убрать первую (попадём в T0), и нельзя третью (окажемся в M).

(29 Дек '18 0:11) falcao

@falcao f(T0,T1,S,L,M). xy+yz (+, -, -, , -); x*z (++, +, -, -, +); 0 (+, -, -, +, +); x+y+1 (-, +, -, +, -); x->y (-, +, -, -, -) И базисы {f3,f5},{f1,f3,f4}?

(29 Дек '18 0:36) Lastik

@Lastik: мне не доставляет удовольствия по десять раз проверять одно и то же -- тем более, что оно переписывается невнимательно и с ошибками. У xy+yz четвёртый знак пропущен, у xz в начале стоит два плюса. Что это такое? Я уже дал ответы на все эти вопросы. Могу лишний раз разъяснить принципы, если нужно, но проверять "цифирки" не хочу.

Система {f1,f3,f4} не базисная -- подсистема {f1,f4} полна. Нахождение базисов -- вещь не очень сложная, но и не такая простая, как установление принадлежности функций пяти классам. Там должен быть какой-то ясный и убедительный принцип нахождения.

(29 Дек '18 0:53) falcao
показано 5 из 13 показать еще 8
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×691

задан
28 Дек '18 2:44

показан
51 раз

обновлен
29 Дек '18 0:53

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

по почте:

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

по RSS:

Ответы

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

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