RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1999, том 11, выпуск 4, страницы 127–138 (Mi dm398)

Эта публикация цитируется в 2 статьях

О числе функций алгебры логики в классах Поста $F_8^\mu$

В. Йовович, Г. Килибарда


Аннотация: Рассматривается проблема перечисления функций алгебры логики от $n$ переменных ранга $k$ из классов Поста $F^\mu_8$. Эта проблема, выраженная на языке теории множеств, эквивалентна проблеме перечисления всех $k$-семейств попарно различных подмножеств $n$-множества, у которых любые $\mu$ членов имеют непустое пересечение. Получены формулы в терминах теории графов для числа элементов этих классов. Явные формулы для случаев $\mu=2$, $k\le8$ (для $k\le6$ они приведены в конце настоящей статьи), $\mu=3,4$, $k\le6$, и при любом $n$ получены с помощью компьютера. В качестве следствия получены соответствующие результаты для классов $F^\mu_5$.

УДК: 519.7

Статья поступила: 12.11.1998

DOI: 10.4213/dm398


 Англоязычная версия: Discrete Mathematics and Applications, 1999, 9:6, 593–605

Реферативные базы данных:


© МИАН, 2024