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

Загрузка...

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

згідно рівності

Перевагою використання швидких перетворень є значне зменшення числа необхідних для обчислення арифметичних операцій, при цьому немає потреби будувати саму матрицю . Очевидно, що для обчислення за допомогою звичайного матричного добутку потрібно виконати елементарних операцій, а за допомогою швидких узагальнених кон’юнктивних перетворень – .

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

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

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

За допомогою проведених експериментальних досліджень було показано, що одна і та ж бульова функція може бути -монотонною для декількох різних між собою наборів , а також, що існують бульові функції, які не є - монотонними для жодного .

При проведенні досліджень з використанням ЕОМ по визначенню ефективності запропонованого алгоритму побудови скороченої ДНФ здійснювалось порівняння часу роботи розробленої програми алгоритму з часом роботи програми алгоритму Мак-Класки для функцій різної розмірності. Отримані результати дають підставу зробити висновок, що розроблений алгоритм є досить ефективний, оскільки для більшості із розглянутих функцій, вибір яких проводився за датчиком випадкових чисел, цей час є набагато менший (для деяких функцій на порядок). Крім цього розроблена програма вимагає набагато менших затрат оперативної пам’яті при своїй роботі.


ВИСНОВКИ


  • Введено в розгляд узагальнені кон’юнтивні перетворення в -мірному просторі дискретних сигналів над полем дійсних чисел. Однією з основних властивостей цих матриць є можливість їх факторизації, що дозволяє ввести в розгляд швидкі узагальнені кон’юнктивні перетворення при реалізації яких на ЕОМ можна обійтись як без побудови самої матриці так і набагато зменшити кількість необхідних арифметичних операцій.

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

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

  • Наведені теореми, які дають можливість знаходити максимальні та мінімальні елементи частково впорядкованої на основі відношення підмножини множини бульових векторів. Ці теореми зокрема використовуються в алгоритмі виділення в заданій множині її максимальної -монотонної підмножини .



    ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО

    В ТАКИХ ПРАЦЯХ


  • Трофимлюк О.Т., Мич І.А. Однорідні та -монотонні бульові функції // Науковий вісник УжДУ. Сер. матем.– 1997.– №2.– С.108-113.

  • Трофимлюк О.Т., Мич І.А. Узагальнені кон’юнктивні перетворення дискретних сигналів та їх застосування // Обробка сигналів і зображень та розпізнавання образів: Тези допов. конф.– Київ, 1998.– С.35-36.

  • Мич І.А., Трофимлюк О.Т. Застосування узагальнених кон’юнктивних перетворень в теорії бульових функцій // Вісник державного університету “Львівська політехніка”. Прикладна математика.– №337.– Львів, 1998.– С.47-49.

  • Трофимлюк О.Т., Мич І.А. Критерій -монотонності бульових функцій // Науковий вісник УжДУ. Сер. матем.– 1998.– №3.– С.190-193.

  • Трофимлюк О.Т., Мич І.А. Частково впорядковані множини бульових векторів // Науковий вісник УжДУ. Сер. матем.– 1999.– №4.– С.124-126.

  • Мич І.А. Модифікований критерій -монотонності бульових функцій // Науковий вісник УжДУ. Сер. матем.– 1999.– №4.– С.118-119.

  • Трофимлюк О.Т., Мич І.А. Узагальнені кон’юнктивні перетворення скінченомірного простору дискретних сигналів // Тези доп. Міжнар. наук.-практ. конф. “Інформатизація діяльності підприємств малого та середнього бізнесу: механізм, порблеми, розвиток”, спец. випуск журналу Науковий вісник УжДУ. Сер. екон. – 2000.– №5.– С.109-112.

  • Мич І.А., Трофимлюк О.Т. Побудова множини простих імплікант бульової функції // Моделювання та оптимізація складних систем: Тези допов. конф. – Київ, 2001.– С.51-53.


    МИЧ І.А. Узагальнені кон’юнктивні перетворення та їх застосування в теорії функцій двозначної логіки.– Рукопис.

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

    Дисертаційна робота присвячена


  •