|
Здравствуйте! Задача такая. Дана булева функция $%f = x \ \& \ y$%, множество $%M = \{\to\}$% (импликация), глубина $%K = 999$%. Можно ли выразить булеву функцию $%f$% над множеством $%M$% формулой глубины $%K$%? Если нельзя, то доказать это. Кстати, как поставить стрелочку для импликации в редакторе формул? задан 3 Сен '15 19:05 
Math_2012 |
|
Команда \to в математическом режиме даёт требуемую "стрелочку". Докажем, что конъюнкция невыразима через импликацию, каковы бы ни была глубина формулы. Рассуждая от противного, предположим, что выразить одно через другое возможно, и рассмотрим формулу, составленную из импликаций, с наименьшим числом логических связок, которая логически эквивалентна $%x\& y$%. Ясно, что она не может быть переменной, поэтому имеет вид $%A\to B$%, где $%A$% и $%B$% выразимы через импликацию. На наборе значений $%x=y=1$% формула $%A$% должна быть истинна, так как импликация сохраняет единицу. Теперь предположим, что хотя бы одно из значений переменных равно нулю. Конъюнкция при этом оказывается ложной, и в силу тождественности равенства это же должно иметь место для импликации. Но если она ложна, то посылка импликации истинна. Это означает, что $%A$% истинна и на таких наборах, для которых $%x$% или $%y$% равно нулю. Следовательно, $%A$% истинна тождественно, и тогда формула $%A\to B$% логически эквивалентна $%B$%, то есть формуле с меньшим числом связок. Это противоречит предположению о минимальности. отвечен 4 Сен '15 0:05 
falcao |