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

Загрузка...

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

побудови поліноміальних представлень функцій двозначної логіки, які в роботі названі -канонічними поліномами;

  • введено поняття -поліноміальної ДНФ бульової функції;

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

  • розроблено алгоритм побудови для заданої множини бульових векторів її так званої максимальної -монотонної підмножини ;

  • побудовано методи розпізнавання та мінімізації однорідних бульових функцій;

  • розроблено алгоритм побудови множини простих імплікант заданої бульової функції.


    Особистий внесок здобувача. Результати дисертаційних досліджень отримані автором особисто і у співпраці з науковим керівником.

    В працях, опублікованих у співавторстві, автору належить в: [1] – формулювання і доведення лем 1, 2, 3 та доведення теореми 1; [2] – введення поняття відношення часткового порядку, породженого заданим бульовим вектором , формулювання властивості 5 матриці узагальненого кон’юнктивного перетворення, доведення теорем 2 та 3; [3] – формули швидких узагальнених кон’юнктивних перетворень, теореми 2 та 3; [4] – формулювання та доведення наведеної леми та критерію -монотонності бульових функцій (необхідність); [5] – доведення теорем та опис алгоритму побудови максимальної -монотонної підмножини заданої множини бульових векторів.


    Апробація результатів дисертації. Основні результати роботи доповідалися на IV Всеукраїнській міжнародній конференції “Оброблення сигналів і зображень та розпізнавання образів “Укробраз-1998” (Київ, 1998 р.), на міжнародній конференції “Розробка та застосування математичних методів у науково-технічних дослідженнях” (Львів, 1998 р.), на міжнародній науково-практичній конференції “Інформатизація діяльності підприємств малого та середнього бізнесу: механізм, проблеми, розвиток” (Ужгород, 2000 р.), на міжнародній конференції “Моделювання та оптимізація складних систем” (Київ, 2001 р.), на науковому семінарі відділів 100 та 105 Інституту кібернетики ім. В.М.Глушкова НАН України, на семінарах кафедри кібернетики та прикладної математики а також на підсумкових наукових конференціях професорсько-викладацького складу математичного факультету Ужгородського національного університету в 1994-2001 роках.


    Публікації. Основні результати роботи опубліковано у восьми роботах, які наведено у списку використаних джерел.


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

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

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

    Практичне значення отриманих результатів. Основні положення дисертації включені до програм курсів за вибором “Теорія функцій двозначної логіки” та “Елементи теорії дискретних сигналів”, які читаються на кафедрі кібернетики та прикладної математики в Ужгородському національному університеті відповідно для спеціальностей 6.080101 – “математика” та 7.080201 – “прикладна математика”.


    Об’єм та структура роботи. Робота складається зі вступу, семи розділів, висновків, списку використаних джерел, що включає 73 найменувань. Загальний обсяг дисертації складає 112 сторінок, робота містить 2 таблиці.




    ОСНОВНИЙ ЗМІСТ РОБОТИ


    У вступі обґрунтовано актуальність теми дисертації, сформульовані мета та задачі роботи, наведено загальну характеристику роботи та одержані в ній наукові результати досліджень.

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

    У розділі 2 введено в розгляд матриці узагальненого кон’юнктивного перетворення дискретних сигналів. Кожна така матриця породжена заданим вектором , де – -а декартова степінь множини . Матриця може бути представлена у вигляді кронекерівського добутку матриць 2-о порядку. Стовпці матриці є значеннями частково впорядкованої множини елементарних кон’юнкцій, побудованих на основі вектора , на множині . Матричний добуток названо узагальненим кон’юнктивним перетворенням функції з міткою . Основною властивістю матриці є можливість її факторизації, тобто представлення у вигляді звичайного добутку слабозаповнених матриць порядку , де . Це, в свою чергу, дозволяє розробити алгоритм швидких узагальнених кон’юнктивних перетворень для знаходження матричного добутку , де –-вимірний вектор-стовпець, який задає деяку, необов’язково бульову, функцію (дискретний сигнал), визначену на множині . Це перетворення визначається


  •