Сколько функций от 4 переменных можно выразить с помощью логического следствия?

задан 10 Янв 15:59

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

Хорошая задача. Только про импликацию лучше говорить, что это логическое следование. Термин "логическое следствие" более естественно смотрится в другом контексте. Например, если есть истинная импликация $%A\to B$%, то про $%B$% говорят, что это логическое следствие $%A$%.

Прежде всего, нужно дать ясный критерий того, когда функция выразима через импликацию. Допустим, что это так. Тогда крайняя справа переменная в формуле обладает таким свойством: если её значение равно 1, то значение всей формулы равно 1. Это легко проверяется по индукции. Если формула состоит из переменной, то всё очевидно. Если нет, то формула имеет вид импликации $%A\to B$%. По предположению индукции, $%B$% истинна при условии истинности последней переменной. Тогда вся импликация с истинным заключением тоже истинна.

Таким образом, если функция выразима через импликацию, то имеется переменная $%x$% такая, что истинность $%x$% гарантирует истинное значение функции. Это значит, что функцию можно представить в виде дизъюнкции $%f\lor x$%, где $%f$% -- некоторая функция. Докажем, что всякая функция такого вида выразима через импликацию, что и даёт критерий.

Дизъюнкция $%f\lor x$% -- это то же самое, что импликация $%\bar{f}\to x$%. Легко видеть, что система связок $%\{0,\to\}$% полна, то есть любая булева функция выразима через функции такой системы. В частности, выразима $%\bar{f}$%. Запишем её в виде формулы от $%\to$% и $%0$%, и далее заменим все вхождения нуля на $%x$%. Проверим, что это даёт требуемую формулу. Действительно, при $%x=1$% обе наши функции (то есть $%\bar{f}\to x$%, и функция, задаваемая формулой) истинны. А при $%x=0$% получается $%\bar{f}\to0$%, что равно $%f$%, и формула даёт то же самое, так как мы заменяли 0 на равное ему значение $%x$%.

В качестве примера: пусть дана дизъюнкция $%x\lor y$%. Выразим её через импликацию, представляя сначала в виде $%\bar{x}\to y$%. Посылка $%\bar{x}$% выражается формулой $%x\to0$%, где 0 заменяем на $%y$%. Это даёт $%(x\to y)\to y$%, что тождественно равно дизъюнкции.

В то же время, конъюнкция $%x\to y$% через импликацию невыразима, так как истинность никакой отдельно взятой переменной не гарантирует истинность всей функции.

Теперь осталось сделать подсчёты. Обозначим через $%s_n$% количество функций от $%n$% переменных, выразимых через импликацию. Ясно, что $%s_0=1$% (тождественная единица), и $%s_1=2$% (тождественная единица и переменная). Выведем рекуррентную формулу для $%s_n$% при $%n\ge2$%. Прежде всего, будем отдельно учитывать тождественную единицу. Далее, выделим все $%k$% переменных, истинность каждой из которых гарантирует истинность всей функции (где $%1\le k\le n$%). Представим функцию в виде дизъюнкции этих переменных, и какой-то функции, в которую вместо значений этих переменных подставим нули. Получится дизъюнкция $%k$% переменных и некой функции $%g$% от оставшихся $%n-k$% переменных, которая может принимать нулевое значение. В ней уже нельзя выделить ни одну из переменных, истинность которой гарантирует истинность всей функции (поскольку мы изначально выделили все переменные с этим свойством). Тогда $%g$% не выразима через импликацию: при $%n > k$% это следует из критерия, а при $%n=k$% функция $%g$% тождественно нулевая. Значит, $%g$% может принимать $%2^{2^{n-k}}-s_{n-k}$% значений. При разных значениях $%g$% будут получаться разные функции, которые мы учитываем. Это даёт $%s_n=1+\sum\limits_{k=1}^nC_n^k(2^{2^{n-k}}-s_{n-k})$%. Слагаемое 1 соответствует отдельно учитываемой тождественной единице, а число сочетаний отвечает за выбор $%k$% переменных из общего числа $%n$%.

Отсюда последовательно имеем $%s_2=1+2(2^2-2)+(2^1-1)=6$% (можно перечислить все такие функции -- это 1, две переменных, две импликации туда-сюда, и дизъюнкция). Далее $%s_3=1+3(2^4-6)+3(2^2-2)+(2^1-1)=38$% (из общего числа 256), и, наконец, $%s_4=1+4(2^8-38)+6(2^4-6)+4(2^2-2)+(2^1-1)=942$%.

ссылка

отвечен 12 Янв 15:03

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

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

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

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

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

отмечен:

×545
×120
×30

задан
10 Янв 15:59

показан
37 раз

обновлен
12 Янв 15:03

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

по почте:

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

по RSS:

Ответы

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

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