RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., 2019, том 26, номер 1, страницы 89–113 (Mi da919)  

Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов

К. А. Попков

Институт прикладной математики им. М.В. Келдыша РАН, Миусская пл., 4, 125047 Москва, Россия

Аннотация: Установлено, что почти любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе $\{x & y,x\vee y,x\oplus y,1\}$, допускающей полный проверяющий тест длины не более $4$ относительно произвольных константных неисправностей на выходах элементов. Доказаны также следующие утверждения: любую булеву функцию от $n$ переменных можно реализовать схемой из функциональных элементов в базисе $\{x & y,x\vee y,x\oplus y,1\}$ (в базисе $\{x & y,x\vee y,x\vee\overline y,x\oplus y\}$), содержащей не более одной фиктивной входной переменной и допускающей полный проверяющий тест длины не более $5$ (соответственно не более $4$) относительно неисправностей такого же типа. Ил. 2, библиогр. 24.

Ключевые слова: схема из функциональных элементов, произвольная константная неисправность, полный проверяющий тест.

Финансовая поддержка Номер гранта
Российский научный фонд 14-21-00025 П
Работа выполнена при поддержке гранта Российского научного фонда (проект № 14–21–00025 П).


DOI: https://doi.org/10.33048/daio.2019.26.623

Полный текст: PDF файл (387 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.718.7
Статья поступила: 16.07.2018
Переработанный вариант: 02.08.2018

Образец цитирования: К. А. Попков, “Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов”, Дискретн. анализ и исслед. опер., 26:1 (2019), 89–113

Цитирование в формате AMSBIB
\RBibitem{Pop19}
\by К.~А.~Попков
\paper Короткие полные проверяющие тесты для схем из двухвходовых функциональных элементов
\jour Дискретн. анализ и исслед. опер.
\yr 2019
\vol 26
\issue 1
\pages 89--113
\mathnet{http://mi.mathnet.ru/da919}
\crossref{https://doi.org/10.33048/daio.2019.26.623}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da919
  • http://mi.mathnet.ru/rus/da/v26/i1/p89

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:15
    Литература:2
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019