LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Узагальнені кон'юнктивні перетворення та їх застосування в теорії функцій двозначної логіки

розгляду та дослідженню властивостей одного з неортогональних перетворень сигналів (функцій) з скінченою областю визначення, яке називається узагальненим кон’юнктивним перетворенням, та розробці на основі цих властивостей методів та ефективних алгоритмів розв’язування ряду задач теорії функцій двозначної логіки.

Запропоновано нові методи побудови поліноміальних представлень функцій двозначної логіки. На основі введеного поняття -монотонної бульової функції розроблено методи розпізнавання і мінімізації однорідних бульових функцій. Розроблено алгоритм побудови скороченої ДНФ на основі алгоритму виділення в заданій множині бульових наборів, на яких фукція приймає значення 1, максимальної -монотонної підмножини. Ефективність запропонованих алгоритмів досягається за рахунок можливості використання швидких узагальнених кон’юнктивних перетворень, оскільки не будується матриця перетворення і набагато зменшується число необхідних арифметичних операцій.

Ключові слова: кон’юнктивне перетворення, швидке перетворення, канонічний поліном, монотонність, однорідність, мінімізація бульових функцій.


МЫЧ И.А. Обобщенные конъюнктивные преобразования и их применение в теории функций двузначной логики. – Рукопись.

Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 2001.

Диссертация посвящена рассмотрению та исследованию свойств одного с неортогональных преобразований конечномерного пространства сигналов (функций), которое называется обобщенным конъюнктивным преобразованием и разработке на основе этих свойств методов и алгоритмов решения ряда задач теории функций двузначной логики.

Рассматриваются матрицы обобщенных конъюнктивных преобразований и исследуются свойства этих преобразований. Приведены формулы, которые лежат в основе алгоритмов быстрых обобщенных конъюнктивных преобразований дискретных сигналов. Использование этих формул представляет возможность вычислять спектр сигнала без построения матрицы самого преобразования, а также значительно сократить число необходимых арифметических операций.

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

Введено понятие -монотонной булевой функции на основе отношения частичного порядка , порожденного заданным булевым набором . Рассматриваются два критерия распознавания -монотонности булевой функции.

Предложено методы нахождения минимальных и максимальных элементов частично упорядоченного множества булевых векторов, относительно заданного отношения частичного порядка.

Введено понятие максимального -монотонного подмножества множества . Описан алгоритм построения такого подмножества.

Рассмотрены задачи распознавания однородности заданной булевой функции и минимизации таких функций. Для булевой функции и заданного вектора введено понятие -полиномиальной ДНФ, которая строится на основе -канонического полинома функции . Показано, что -полиномиальная ДНФ функции тогда и только тогда есть ДНФ этой функции когда функция -монотонна. Также показано, что построена на основе -полиномиальной ДНФ с использованием операции поглощения сокращенная ДНФ -монотонной булевой функции является единственной минимальной ДНФ этой функции.

Разработан алгоритм построения сокращенной ДНФ заданной булевой функции. В основе алгоритма лежит идея представления булевой функции у виде дизъюнкции некоторого числа -монотонных функций, которые являются импликантами функции . Использование при этом быстрых конъюнктивных преобразований предоставляет возможность применять этот алгоритм для булевых функций достаточно большой размерности.

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


Mych I. A. Generalized conjunctive transformations and their usage in the theory of twomeaning logics functions. – Manuscript.

Dissertation for the scientific degree of candidate of physics-mathematical sciences on speciality 01.05.01 – theoretical basis of informatics and cybernatics. – Institute of cybernatics named after V.M.Glushkov, NAN of Ukraine, Kyiv, 2001.

The scientific research is dedicated to the issue of taking into consideration and the investigation of peculiarities of one of the neftogonal signal transformations with the full defined field which is called the generalized conjunctive transformation, and to the development of methods and effective algorithms to make a number of sums in the twomeaning logics function theory on the basis of the peculiarities under investigation.

New methods of polynominal presentation of the twomeaning logics functions are proposed. On the ground of introduced notice of I-monotone Boulean function the methods of recognition and minimization of homogenious Boulean functions were worked out. The algorithm of construction of shortened DNF on the basis of algorithm division in the given multitude of Boulean set on which the function takes meaning 1, of maximum I-monotone submultitude is proposed. The efficacy of proposed algorithms is reached by the opportunity of usage of quick generalized conjunctive transformation for the transformational matrix is not being built and because of that the quantity of necessary arithmetic operations reduces greatly.

Key words: generalized conjunctive transformation, quick transformations, canonic polynom, monotone, homogeneity, minimization of the Boulean functions.