Курсова робота на тему: «МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ. СКОРОЧЕННІ, ТУПІКОВІ, МІНІМАЛЬНІ ФОРМИ ТА СПОСОБИ ЇХ ПОБУДОВИ»

Зміст

Вступ ………………………………………………………………………….….. 3

  1. Основні поняття …………………………………………………………… 4
  2. Мінімізація булевих функцій методом карт Карно …………………….. 8
  3. Мінімізація булевих функцій методом Квайна — Мак-Класкі ……… 16

    Висновоки ………………………………………………………………………. 26

    Список використаної літератури ………………………………………………. 27

     

    ВСТУП

    Булева алгебра – це гратки особливого типу, які застосовуються при дослідженні логіки (причому як логіки людського мислення, так і цифрової комп’ютерної логіки), а також переключальних схем. Останнє додаток було ініційовано К. Шенноном, що показало, що фундаментальні властивості електричних мереж, що складаються з бістабільних елементів, можуть бути виражені за допомогою булевої алгебри. Поряд з Шенноном в застосуванні теорії бульових алгебр для вирішення задач релейнї техніки в 1936-1938 рр.. працювали російський математик В.І. Шестаков і японці А. Накасіма і М. Ханзава. Відзначимо також, що ще в 1910 р. відомий фізик П. Еренфеста в рецензії на російський переклад книги Л. Кутюр «Алгебра логіки» вказав на потенційну можливість застосування булевої логіки до проектування автоматичних телефонних станцій, сформулювавши питання про реалізованості бульових функцій та мінімізації схем.

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

    Курсова робота складається з вступу, трьох розділів, висновку і списку використаних джерел.

    Обєктом даного дослідження є булеві функції.

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

    У першому розділі дані основні визначення й основні поняття булевої алгебри.

    У другому розділі дається визначення мінімальних форм бульових многочленів і намічений курс подальшого дослідження.

    Третій розділ присвячений застосуванню мінімальних форм булевих многочленів до розв’язання задач.

    У висновку сформульовані основні висновки до роботи.

  4. Основні поняття

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

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

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

    Визначення

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

    Мінтерми функції є її імплікантами, елементарні кон’юнкції, що входять до складу ДНФ функції, також є її імплікантами.

    Визначення

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

    Набір імплікант, складових ДНФ функції, є її покриттям. Набір всіх конституент одиниці функції, що входять до її ДДНФ, є покриттям даної функції.

    Будь-яку елементарну кон’юнкцію А, що входить до складу елементарної кон’юнкції В і містить менше змінних, ніж кон’юнкція В, називають власною частиною кон’юнкції В, і вважають, що кон’юнкція А покриває кон’юнкцію В.

    Визначення

    Простою імплікантою функції f називається така кон’юнкція-імпліканта, що ніяка її власна частина не є імплікантою даної функції.

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

    Визначення

    Диз’юнкція всіх простих імплікант функції називається її скороченою ДНФ (СДНФ).

    Визначення

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

    Визначення

    Тупиковою ДНФ називається ДНФ даної булевої функції, що складається тільки з простих імплікант.

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

    Визначення

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

    Для знаходження множини простих імплікант функції, що задана СДНФ, використовуються такі очевидні перетворення формул булевої алгебри, які традиційно називаються «операціями».

    Операція неповного диз’юнктивного склеювання:


    Операція диз’юнктивного поглинання:


    Виконання двох зазначених операцій послідовно зображує виконання операції повного диз’юнктивного склеювання:


    Тут А — деяка елементарна кон’юнкція змінних, х — булева змінна.

    Приклад. Нехай є функція f, що задана ДДНФ:

    .

    Виконаємо операції повного склеювання таким чином:




    Виконаємо тепер операції склеювання іншим способом:


    В обох випадках одержані тупикові ДНФ функції f(x, у, z). Друга тупикова ДНФ простіша за першу, оскільки містить меншу кількість символів змінних і знаків операцій. Побудуємо таблицю істинності функції f(x, у, z) та її трьох імплікант, що входять до складу ДНФ (таблиця 1).

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Minim Bul Funk (666.2 KiB, Завантажень: 8)

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Minim Bul Funk (193.3 KiB, Завантажень: 2)

Сторінка: 1 2 3 4 5 6 7
завантаження...
WordPress: 23.52MB | MySQL:26 | 0,333sec