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

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 519.713

АВТОРЕФЕРАТ

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

УЗАГАЛЬНЕНІ КОН'ЮНКТИВНІ ПЕРЕТВОРЕННЯ ТА ЇХ ЗАСТОСУВАННЯ В ТЕОРІЇ ФУНКЦІЙ ДВОЗНАЧНОЇ ЛОГІКИ

01.05.01 - теоретичні основи інформатики та кібернетики

МИЧ Ігор Андрійович

Київ - 2001

Дисертацією є рукопис.

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

Науковий керівник: кандидат фізико-математичних наук, доцент ТРОФИМЛЮК Олег Тимофійович,

Ужгородський національний університет.

Офіційні опоненти:

доктор фізико-математичних наук, професор ГУПАЛ Анатолій Михайлович, Науково-учбовий центр прикладної інформатики НАН України, директор,

кандидат фізико-математичних наук, АКСЬОНОВА Людмила Олександрівна Київський національний технічний український університет "КПІ", старший науковий співробітник.

Провідна установа: Київський національний університет ім. Т.Шевченка кафедра математичної інформатики.

Захист відбудеться 23.11.2001 р. о 14 год. на засіданні спеціалізованої вченої ради при Інституті кібернетики імені В.М.Глушкова НАН України за адресою: 03680, МСП, Київ 187, проспект Академіка Глушкова, 40

З дисертацією можна ознайомитися у бібліотеці інституту.

Автореферат розісланий 22.10.2001 року.

Учений секретар

спеціалізованої вченої ради СИНЯВСЬКИИ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

дискретний бульовий канонічний логіка

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

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

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

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

Досягнення поставленої мети пов'язується з розв'язанням слідуючих задач:

введення в розгляд та дослідження властивостей узагальнених кон'юнктивних перетворень;

побудова алгоритмів виконання швидких узагальнених кон'юнктивних перетворень дискретних сигналів;

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дана робота виконувалась в рамках тематики наукових досліджень кафедри кібернетики та прикладної математики Ужгородського національного університету на протязі 1994-2001 років.

Наукова новизна одержаних результатів. При виконанні роботи:

введено в розгляд узагальнені кон'юнктивні перетворення дискретних сигналів, визначених на множині , де розглянуто властивості цих перетворень;

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

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

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

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

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

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

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

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

В працях, опублікованих у співавторстві, автору належить в: [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-о порядку. Стовпці матриці є значеннями частково впорядкованої множини елементарних кон'юнкцій, побудованих на основі вектора , на множині . Матричний добуток названо узагальненим кон'юнктивним перетворенням функції з міткою . Основною властивістю матриці є можливість її факторизації, тобто представлення у вигляді звичайного добутку слабозаповнених матриць порядку , де . Це, в свою чергу, дозволяє розробити алгоритм швидких узагальнених кон'юнктивних перетворень для знаходження матричного добутку , де --вимірний вектор-стовпець, який задає деяку, необов'язково бульову, функцію (дискретний сигнал), визначену на множині . Це перетворення визначається згідно рівності

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

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

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

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Запропоновано нові методи побудови поліноміальних представлень функцій двозначної логіки. На основі введеного поняття -монотонної бульової функції розроблено методи розпізнавання і мінімізації однорідних бульових функцій. Розроблено алгоритм побудови скороченої ДНФ на основі алгоритму виділення в заданій множині бульових наборів, на яких фукція приймає значення 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.

Размещено на Allbest.ru