Здравствуйте! Задача такая. Дана булева функция $%f = x \ \& \ y$%, множество $%M = \{\to\}$% (импликация), глубина $%K = 999$%. Можно ли выразить булеву функцию $%f$% над множеством $%M$% формулой глубины $%K$%? Если нельзя, то доказать это.

Кстати, как поставить стрелочку для импликации в редакторе формул?

задан 3 Сен '15 19:05

изменен 5 Сен '15 0:57

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

Команда \to в математическом режиме даёт требуемую "стрелочку".

Докажем, что конъюнкция невыразима через импликацию, каковы бы ни была глубина формулы.

Рассуждая от противного, предположим, что выразить одно через другое возможно, и рассмотрим формулу, составленную из импликаций, с наименьшим числом логических связок, которая логически эквивалентна $%x\& y$%. Ясно, что она не может быть переменной, поэтому имеет вид $%A\to B$%, где $%A$% и $%B$% выразимы через импликацию.

На наборе значений $%x=y=1$% формула $%A$% должна быть истинна, так как импликация сохраняет единицу. Теперь предположим, что хотя бы одно из значений переменных равно нулю. Конъюнкция при этом оказывается ложной, и в силу тождественности равенства это же должно иметь место для импликации. Но если она ложна, то посылка импликации истинна. Это означает, что $%A$% истинна и на таких наборах, для которых $%x$% или $%y$% равно нулю. Следовательно, $%A$% истинна тождественно, и тогда формула $%A\to B$% логически эквивалентна $%B$%, то есть формуле с меньшим числом связок. Это противоречит предположению о минимальности.

ссылка

отвечен 4 Сен '15 0:05

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

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

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

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

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

отмечен:

×1,326
×150

задан
3 Сен '15 19:05

показан
555 раз

обновлен
7 Сен '15 18:29

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

по почте:

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

по RSS:

Ответы

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

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