journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>В статье сравниваются мощности некоторых классов булевых функций, бесповторных в полном бинарном базисе B2 = {&, ∨, ⊕}. Бесповторные функции представляются помеченными корневыми деревьями, среди которых выделяются канонические. Далее приводится алгоритм, позволяющий преходить от канонических деревьев к полным бинарным каноническим деревьям. Данный алгоритм связывает два принципиально различных подхода к построению однозначного представителя для бесповторной в B₂ функции. Представление бесповторных функций в виде полных бинарных канонических деревьев позволяет доказать,что среди всех бесповторных функций от n переменных, доля функций, в каноническом представлении которых содержится хотя бы одна k-местная фунция &, ∨ или ⊕ экспоненциально стремится к нулю с ростом величины k. Данный результат представляет интерес для тестирования бесповторных функций.</p>

Ключевые слова RU

Литература RU
1. Вороненко А. А. О проверяющих тестах для бесповторных функций // Математические вопросы кибернетики. — 2002. — вып. 11. — С. 163-176. 2. Зубков О. В. О числе бесповторных булевых функций в базисе {&, ∨, ⊕,−}//, Дискретный анализ и исследование операций. — 2003. — серия 1, Т. 10, N 1. — С.41 -60.

Название EN

Авторы EN

Аннотация EN
<p>In this paper we are comparing noniterated in the whole binar basis B2 = {&, ∨, ⊕}some classespowersofBooleanfunctions.Noniterated Booleanfunctions are presented with a marked root trees, in which we can pick out the a canonical forms. To continue there is an algorithm, with the help of whitch we can pass from the canonical trees to the whole binar canonical trees. In this algorithm we can combine two definitely different methods of creating the canonical form of the noniterated in the basis B2 function. The representation of the noniterated Boolean functions as a whole binar canonical trees allowed to proof, that the part of functions in canonical form of which there is one or more k-locative function &, ∨ or ⊕ exponently aspires to zero with a growth of k-value. The result is worth testing of the noniterated Boolean function.</p>

Ключевые слова EN

Литература EN