імені Н.Г. Чернишевського
Кафедра геометрії
курсова робота
Мінімальні форми булевих многочленів
м. Саратов 2009
зміст
Введення
Основні поняття булевої алгебри
1.1 Основні етапи розвитку булевої алгебри
1.2 Основні визначення булевої алгебри
1.3 Мінімальні форми булевих многочленів
II.Решеніе мінімальних форм булевих многочленів з
допомогою методу Куайна - Мак-Класкі
Висновок
Список використаних джерел.
ВСТУП
Булеві алгебри - це грати особливого типу, які застосовуються при дослідженні логіки (причому як логіки людського мислення, так і цифровий комп'ютерної логіки), а також перемикальних схем. Це останнє додаток було ініційовано К. Шенноном, що показало, що фундаментальні властивості електричних мереж, які з бістабільних елементів, можуть бути виражені за допомогою булевих алгебр. Поряд з Шенноном піонерами у застосуванні теорії булевих алгебр для вирішення завдань релейної техніки в 1936-1938 рр.. були російський математик В.І. Шестаков і японці А. Накасіма і М. Ханзава. Відзначимо також, що ще в 1910 р. відомий фізик П. Еренфест в рецензії на російський переклад книги Л. Кутюра «Алгебра логіки» вказав на потенційну застосовність булевої логіки до проектування автоматичних телефонних станцій, сформулювавши питання про реалізованим булевих функцій і мінімізації схем.
Метою даної курсової роботи є вивчення булевої алгебри та застосування мінімальних форм булевих многочленів до розв'язання задач.
Курсова робота складається з вступу, трьох розділів, висновків та списку використаних джерел.
У вступі описана актуальність теми, сформульована мета, дана структура курсової роботи.
У першому розділі дано основні визначення та основні поняття булевої алгебри.
У другому розділі дається визначення мінімальних форм булевих многочленів та намічено курс подальшого дослідження.
Третя глава присвячена застосуванню мінімальних форм булевих многочленів до розв'язання задач.
У висновку сформульовані основні висновки до роботи.
I. ОСНОВНІ ПОНЯТТЯ Булевой АЛГЕБРИ
1.1 Основні етапи розвитку булевої алгебри.
У 1847 році Дж. Буль написав маленьку, але епохальну книгу «математичний аналіз логіки», в якій логіка трактувалася як чисто формальна система; інтерпретація в звичайній мові прийшла пізніше. Буль писав, що математика характеризується своєю формою, але не змістом. У своїй подальшій книзі «Дослідження законів мислення» (1854) він увів поняття булевої алгебри.
Булеве числення логіки зосереджено на формальній трактуванні логіки за допомогою математичних (особливо алгебраїчних) методів і на описі логічних тотожностей. Дотримуючись Булю, школа англійських математиків, а також Шредер, Уайтхед розробили аксіоматику операцій кон'юнкції, диз'юнкції, заперечення, з іншого боку, Пірс і Шредер створили аксіоматику порядку, використовуючи відношення включення в якості фундаментального поняття. У 1904 році Хантінгтон досліджував дві системи аксіом і почав трактувати булеві алгебри як самостійні математичні структури, не обов'язково пов'язані з логікою.
Буль використовував дистрибутивність перетину щодо об'єднання, яку ще до нього зазначив Ламберт. Буль працював з множинами. Позначаючи перетин х і у через ху, а об'єднання - через х + у, якщо х і у диз'юнктів. Подібно Лейбніца, він інтерпретував ставлення включення х Í у як ху = х, що легко давало можливість отримати класичні правила силогізму. Потім Джевонс розповсюдив операцію об'єднання на довільні х і у; Де Морган і, пізніше, Пірс довели співвідношення подвійності, звані законами де Моргана.
Більшість логіків дев'ятнадцятого століття не висловлювало великого інтересу до застосування в математиці своїх знахідок. Однією з причин цього була відсутність кванторів, введених пізніше Фреге і Пірсом. Пеана, серед інших, увів символи È, Ç, - для об'єднання, перетину і вирахування множин. Після книги ван дер Варден по сучасній алгебрі поняття універсальної алгебри було вже не за горами. Біркгоф розвинув концепцію «алгебри», відправляючись від підходів ван дер Варден, і взяв назву «універсальна алгебра» з книги Уайтхеда. в 1934 році, будучи в Геттінгені, Маклейн також висловлював деякі думки про універсальну алгебрі, але не опублікував їх. Одна з найбільш фундаментальний статей з теорії решіток була надрукована Оре в 1935 році. Наступні роки ознаменувалися цілим рядом досліджень в області, як теорії, так і додатків решіток, наприклад, в теорії груп, проектованій геометрії, квантової механіки, функціональному аналізі, теорії міри та інтегрування.
У 1933 - 1937 рр.. М. Стоун отримав важливі результати про булевих алгебрах, які він інтерпретував як спеціальні кільця, а саме як булеві кільця, де була застосовна теорія ідеалів. Інші фундаментальні питання, які розглядалися Стоуном, - це питання про подання булевих алгебр і додатки булевих алгебр в топології. З тих пір теорія решіток перетворилася на цілком життєздатну, сильну і самостійну дисципліну.
1.2 Основні визначення і поняття булевої алгебри
Визначення: Булевой алгеброю (позначимо В) називається непорожня безліч елементів з двома бінарними операціями «+», «*» і однією унарні операції «` », а так само спеціальними елементами 0 і 1, якщо виконуються такі властивості:
1. A + b = b + a, "a, b B
2. A * b = b * a, "a, b B
3. A + (b * c) = (a + b) * (A + c)
4. A * (B + c) = (a * b) + (a * c)
5. A + 0 = a, a * 1 = a. (Тотожність)
6. A + a `= 1, a * A `= 0. (Доповнюваність)
Ця система аксіом є повною і незалежною.
Приклад 1: Нехай безліч В - це безліч В = {1,0} на якому задані дві бінарні операції:
| + | 1 | 0 | * | 1 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 0 | 0 | 0 |
Приклад 2: Безліч дільників числа 70: <1,2,5, 7,10,14,35,70>
1. A + b = НСД (a, b)
2. A * b = НОК (a, b)
3. A ` = 70 / a
Визначення: Нехай З - непорожня підмножина безлічі В. Кажуть, що С - підалгебр алгебра В, якщо вона сама є алгеброю з тими ж операціями.
Підмножина С - є підалгебр алгебра В Û З замкнуто щодо трьох операцій.
Приклад 3: Якщо С = <1,2,35,70> замкнуто щодо операцій «+», «*», «` », тоді С є підалгебр алгебра В.
Визначення: Дві булеві алгебри В і В ` ізоморфні: В ~ В `, якщо існує взаємно-однозначна функція f: B ® B`, така, що:
1. F (a + b) = f (a) + f (b)
2. F (a * b) = f (a) * f (b)
3. F (a `) = (f (a))`
Для булевої алгебри справедливі принципи дуальності.
Основні теореми абстрактної булевої алгебри.
1. Ідемпотентний закон: a + a = a, a * a = a.
2. Граничний закон: a + 1 = 1, a + 0 = a.
3. Абсорбційний закон: a + (a * b) = a, a * (a + b) = a.
4. Асоціативний закон: a + (b + c) = (a + b) + c, a * (b * c) = (a * b) * c.
5. Єдиність доповнення: якщо $ x: a + X = 1, a * X = 0, то x = A `.
6. Інволютивних закон: ((a `))` = a Þ 0 ` = 1, 1 ` = 0.
7. Закон де Моргана: (a + b) `= a` * b `, (a * b)` = a `+ b`.
Булева алгебра як грати.
Оскільки для булевої алгебри справедливі асоціативний, комутативними і абсорбційний закони, то згідно з визначенням булева алгебра є грати. У цій решітці
"А, а + 1 = 1 Þ а £ 1, а * 0 = 0 Þ 0 £ а.
Таким чином У є обмежена решітка, крім того аксіоми (2) і (4) вказують на те, що грати дистрибутивний та доповнена. І навпаки, будь-яка обмежена, дистрибутивна і доповнена решітка є булева алгебра.
Визначення: Булева алгебра - це обмежена, дистрибутивна і доповнена решітка.
Ми можемо ввести на булевої алгебри ставлення часткового порядку. Вважаємо, що a £ b Û
a Ú b = B, a Ù b = A.
Теорема. У булевої алгебри такі вирази еквівалентні:
1) a + B = B
2) a * B = A
3) a `+ b = 1
4) a * B `= 0.
Доказ.
1. Доведемо еквівалентність (1) та (3)
а) Нехай (1) вірно, тоді
a ` + b = a `+ (A + b) = (A ` + a) + b = 1 + b = 1;
b) Нехай (3) правда, тоді
a + b = (a `+ b) * (a + b) = b * (a + a`) = b * 1 = b;
2. Доведемо еквівалентність (3) і (4)
a) Нехай (3) правда, тоді
0 = 1 ` = (A ` + b) ` = (A `)` * b ` = a * b `;
b) Нехай (1) вірно, тоді
1 = 0 ` = (A + b `)` = a ` + (B `)` = a ` + b;
3. Доведемо еквівалентність (2) і (4)
a) Нехай (2) правда, тоді
a * b ` = (A * b) * b ` = a * (B * b `) = a * 0 = 0;
b) Нехай (4) правда, тоді
a * b = a * b + 0 = a * b + a * b `= a * (b + b`) = a * 1 = a;
Тоді вирази (1), (2), (3), (4) еквівалентні.
Приклад 1. Розглянемо алгебру множин - модель булевої алгебри.
А £ У якщо А Ì В.1. А Ú В = В
2. А Ù В = А
3. А Ú В = U
4. А Ù В `= Æ
Будь-яка кінцева булева алгебра може містити лише 2 в ступені n елементів, де n - Натуральне число.
Приклад 2. 1) Безліч дільників 70-ти D = <1,2,5,7,10,14,35,70>. Безліч A = <2,5,7>-безліч атомів решітки D.
10 = 2 Ú 5
14 = 2 Ú 7
35 = 5 Ú 7
70 = (2 Ú 5) Ú 7
70
10
1
2) Безліч А = {2,5,7}
Ставлення вкладеності.
{2,5,7}
{2,5} {2,7} {5,7}
Æ
Ці грати ізоморфна попередньої.
Алгебра множин і алгебра висловлювань є моделями абстрактної булевої алгебри. Всі абстрактні булеві алгебри (які складаються з однакового числа елементів) ізоморфні.
1.3 Мінімальні форми булевих многочленів
Визначення. Поняття булева многочлена визначається рекурсивно. Нехай Х n = {X 1, ..., x n} - множина з n символів (званих невідомими або змінними), яке не містить символів 0 і 1. Булеві многочлени над Х n суть об'єкти, які можуть бути отримані послідовним застосуванням наступних правил:
(I) х 1, х 2, ..., х n, 0,1 - булеві многочлени;
(II) якщо p і q - булеві многочлени, то такими є і
(P) Ù (q), (p) Ú (q), (p) ¢.
Позначимо множину всіх бульових многочленів над Х n через Р n.
Приклад. Ось кілька прикладів булевих многочленів над {х 1, х 2}: 0,1, х 1, х 2, х 1 Ù х 2, х 1 Ú х 2, х 1 ¢, х 1 ¢ Ù х 2.
Так як будь-який логічний многочлен над x 1, ..., x n модно розглядати як логічний многочлен над x 1, ..., x n, x n +1, ми маємо
Р 1 Ì Р 2 Ì ... Ì Р n Ì Р n +1 Ì ...
Логічний многочлен можна спростити за допомогою аксіом булевої алгебри. У процесі спрощення часто важко вирішити, які аксіоми і в якому порядку повинні бути використані. Але існують деякі систематичні методи спрощення булевих многочленів. Недоліком більшості цих методів є можливість їх практичного впровадження, коли число змінних занадто велике. Відповідна проблематика в теорії булевих алгебр носить загальну назву проблема оптимізації або мінімізації булевих многочленів; вона важлива для таких додатків, як спрощення перемикальних схем.
Визначення. Назвемо літералом будь-яку змінну х i і її доповнення х i ¢, а також 0 і 1. Під твором розуміється твір декількох літералів, тобто логічний многочлен, в якому немає знаку +. Диз'юнктивні виразом чи просто вираженням назвемо буле многочлен, що є сумою добутків. Складові в такому виразі назвемо диз'юнктів.
Обговорюючи спрощення булевих многочленів, ми обмежимося важливим випадком відомості диз'юнктивних виразів до «мінімальним виразами» щодо спеціального умови мінімальності. Позначимо через d f загальне число літералів у вираженні f, а через e f - число диз'юнктів. Ми говоримо, що вираз f простіше вираження j, якщо d f £ d g, e f £ e g і хоча б одне з цих нерівностей суворе. Вираз f називається мінімальним, якщо не існує вираження, яке було б еквівалентно f і простіше f. Таким чином, ми будемо шукати «найкоротший» вираз з найменшим можливим числом літералів, яке було б еквівалентно f. Таке мінімальне вираження не завжди визначено однозначно. Я опишу один з декількох існуючих методів спрощення. Він заснований на роботі Куайна і був поліпшений Мак-Класкі, тому називається методом Куайна - Мак-Класкі.
Визначення. Многочлен p тягне многочлен q, якщо для будь-яких b 1, ...., B n Î У
р в (b 1, ..., b n) = 1 тягне q в (b 1, ..., b n) = 1;
в цьому випадку р називається импликантой для q. Простим импликантой многочлена р називається твір
Приклад. Твір х 1 х 3 є подпроізведеніем як х 1 х 2 х 3, так і х 1 х 2 ¢ х 3, і спричиняє вираз
Теорема. Будь-який многочлен р Î P n еквівалентний сумі всіх своїх простих импликантой.
Вираз, що є сумою простих импликантой для р, називається непріводімим, якщо воно еквівалентно р, але перетинає бути таким, якщо видалити хоча б один доданок. Мінімальна вираз повинен бути непріводімим. Тому, щоб визначити мінімальну вираз, ми знаходимо все Непріводімие вираження, а серед них шукаємо вираз з найменшим числом літералів. Викладемо тепер належить Куайну метод визначення простих импликантой.
Прості імпліканти виходять з диз'юнктивної нормальної форми d булева многочлена р застосуванням (зліва направо) правила
yz + yz ¢ ~ y,
коли це можливо. Більш загально, ми використовуємо правило
(*)
де
і 
- Твору. наступний приклад допоможе зрозуміти сенс описуваної процедури.
Приклад. Нехай р - логічний многочлен, має таку діз'юнктівную нормальну форму:
d = wxyz '+ wxy' z '+ wx' yz + wx 'yz' + w 'x' yz + w 'x' yz '+ w' x 'y' z
Ми використовуємо правило і закони Ідемпотентний для тих (із загального числа ( 
) = 21) пар диз'юнктів в d, для яких це можливо, тим самим «укорочуючи» твору. наприклад, переви і другий диз'юнктів при використанні (*) дають wxz '. Якщо в процесі спрощення складові використовуються хоча б один раз, то воно позначається. Так як знак + стоїть замість Ú, вираз може бути використано будь-яке число раз, але позначається не більше одного разу. Таким чином, всі помічені твори містять більш короткі твори і тому не можуть бути простими импликантами. У цілому в першому раунді цього процесу ми переходимо
від wxyz 'і wxy' z 'до wxz'
від wx 'yz і wx' yz 'до wx' y
від wxyz 'і wx' yz 'до wyz'
від w 'x' yz і w 'x' yz 'до w' x 'y
від w 'x' yz і w 'x' y 'z до w' x 'z
від wx 'yz і w' x 'yz до x' yz
від wx 'yz' і w 'x' yz 'до x' yz '
Тут використані, і тому повинні бути позначені, всі сім доданків.
Загалом, ця процедура повторюється знову і знову з використанням тільки помічених виразів (які стають коротше). Інші твори суть прості імпліканти і залишаються незмінними.
У нашому прикладі другий раунд спрощення здійснює перехід
від wx 'y і w' x 'y до x' y
від x 'yz і x' yz 'до x' y
Чотири вираження - wx 'y, w' x 'y, x' yz, x 'yz' - позначені. Інші твори, а саме wxz ', wyz', w 'x' z не можуть бути спрощений. отже, р еквівалентно такій сумі простих импликантой:
р ~ wxz '+ wyz' + w 'x' z + x 'y.
Як вже було сказано, Мак-Класкі поліпшив це метод. Щоб описати покращений алгоритм, використовуємо многочлен
d = wxyz '+ wxy' z '+ wx' yz + wx 'yz' + w 'x' yz + w 'x' yz '+ w' x 'y' z
Крок 1. Вважаючи змінні впорядкованими за алфавітом (або за номерами), поставимо у відповідність кожного твору послідовність символів з {0, 1, -}: замість x i 'і x i запишемо 0 і 1 відповідно, а замість опущених змінних запишемо рисочку. Наприклад, замість w 'x' y 'z запишемо 0001, а замість w' x 'z - 00-1.
Крок 2. Твори, що розглядаються як трійчастий n-ки, розбиваються на класи еквівалентності відповідно до числа одиниць. Впорядкуємо класи за зростанням цього числа. У нашому прикладі:
w 'x' y 'z 0 0 0 1
w 'x' yz '0 0 1 0
w 'x' yz 0 0 1 1
wx 'yz '1 0 1 0
wx 'yz 1 0 1 1
wxyz '1 1 1 0
wxy 'z '1 1 0 0
Крок 3. Використовуючи правило (*), потрібно складати тільки твори з сусідніх класів, тобто коли числа одиниць у відповідних послідовностях відрізняються лише на 1. При цьому ми повинні порівнювати висловлювання з сусідніх класів, які мають риски в одних і тих самих позиціях. Якщо два таких вираження відрізняються точно в одній позиції, то вони мають вигляд р = i 1 i 2 ... i r ... i n і q = i 1 i 2 ... i r '... i n, де все i k лежать у {0, 1, -}, а i r лежить у {0, 1}. Тоді (*) зводить p, q до i 1 i 2 ... i r -1 - i r +1 ... i n, причому p і q повинні бути позначені . У розглянутому прикладі це дає такі четвірки (мітки відносяться до наступного раунду, тоді як у попередньому списку всі твори слід позначити):
0 0 - 1
0 0 1 - ü
- 0 1 0 ü
- 0 1 1 ü
1 0 1 - ü
1 - 1 0
1 1 - 0
Помічені вирази не є простими импликантами і в другому раунді цього кроку дають єдине вираження
- 0 1 -
Отже, ми знайшли всі прості імпліканти, а саме
0 0 1 - w'x'z
- 0 1 0 wyz '
- 0 1 1 wxz '
1 0 1 - x'y
Так як сума всіх простих импликантой необов'язково є мінімальним вираженням, алгоритм потребує виконання ще одного кроку.
Крок 4. У силу теореми сума всіх простих импликантой для р еквівалентна р. тому для кожного доданка диз'юнктивної нормальної форми d многочлена р повинен існувати простий импликант, що є твором цього доданка. для виявлення виник відповідності зручно використовувати таблицю простих импликантой. стовпці цієї таблиці індексуються диз'юнктів з d, а рядки - простими импликантами, обчисленими в кроці 3. на перетині i - го рядка і j-го стовпця ставиться хрестик û, якщо простій импликант з i - го рядка є подпроізведеніем твори з j-го стовпця. Кажуть, що один твір покриває, якщо перше є подпроізведеніем другого. Для того, щоб знайти суму простих импликантой, яка буде еквівалентна d, ми з безлічі всіх простих импликантой вибираємо підмножина таким чином, щоб кожний доданок у d покривалося принаймні одним импликантой з підмножини. Тоді мінімальної формою буде сума простих импликантой з найменшим числом членів і найменшим числом літер. Простий импликант називається головним членом, якщо він покриває твір, не покривається ніяким іншим простим импликантой; сума всіх головних членів називається ядром. спочатку ми знаходимо ядро, потім позначаємо через q 1, ..., q k твори, що не покриваються простими импликантами з ядра; прості імпліканти, що не входять в ядро, позначимо через р 1, ..., р m. Далі формуємо таблицю, стовпці якої індексуються елементами q i, а рядки - елементами р i. Хрестик û на місці (i, j) вказує, що р i покриває q j.
Тепер утворюємо твір сум. Кожен співмножник відповідає одному з q j і є сумою тих р i, який покривають цей q j. Використовуючи закони булевої алгебри, ми перетворимо цей вираз у найпростішу можливу суму творів. Кожне з цих творів являє підмножина елементів р i, які покривають всі q j. Далі розглядаємо твори з найменшим числом співмножників. З цих найкоротших творів вибираємо ті, що містять найменшу загальне число літералів. Тепер кожне з отриманих творів переписуємо у вигляді суми складових його простих импликантой, складаємо з ядром, отримуючи мінімальну суму творів, еквівалентну р.
II. РІШЕННЯ МІНІМАЛЬНИХ форми Булевой многочленів ЗА ДОПОМОГОЮ МЕТОДУ Куайн - МАК-Класкі
Завдання. Визначимо форму булева многочлена р, заданого у диз'юнктивній нормальній формі
d = v 'w' x 'y' z '+ v' w 'x' yz '+ v' w 'xy' z '+ v' w 'xyz' + v 'wx' y 'z + v' wx ' yz '+ v' wxy 'z + v' wxyz '+ v' wxyz + vw 'x' y 'z' + vw 'x' y 'z + vw' xy 'z + vwx' yz '+ vwxy' z ' + vwxyz '+ vwxyz
Рішення:
Кроки 1 і 2
Крок 3. Комбінація рядків (i) і (j) дає скорочення, вказане в рядку (i) (j):
Повторення цього кроку з новими рядками дає нам
Позначки «пташкою» ü та літерами зроблені після процесу спрощення. знайдені прості імпліканти позначені літерами А, В, ... J.
Крок 4. Формуємо таблицю простих импликантой, де індекси стовпців - доданки з d - представлені у вигляді двійкових стовпців.
У наших коротких позначеннях ядро, тобто сума головних членів, є D + H + G + B + E + A. Єдиним твір, не покриваються ядро, є (4); це і є q 1. Простими импликантами p i, що не входять в ядро, є С, F, I, J. Нова таблиця має вигляд
Це означає, що ми отримуємо дві мінімальні фори:
(I) D + H + G + B + E + A + I, якщо використовувати I, і
(Ii) D + H + G + B + E + A + J, якщо вибрати J.
У звичайних позначеннях мінімальна форма (i) така:
v 'w' z '+ v' wy 'z + vw' y 'z + wyz' + vwxz '+ wxy + vw' x 'y'.
ВИСНОВОК
За результатами проведеного курсового дослідження за темою «Мінімальні форми булевих многочленів» можна зробити наступні висновки.
При всій простоті своїй аксіоматики теорія булевих алгебр дуже змістовна. Ми знаходимо в ній чимало важких і глибоких проблем, багато з яких ще не вирішені. Ці проблеми дуже різні, вони стикаються з логікою і теорією множин, з дослідженнями та аналізом. Така велика кількість точок дотику із суміжними математичними дисциплінами ріднить теорію булевих алгебр з функціональним аналізом, до якого вона близька і за своїм загальним математичного стилю.
Існують різні методи знаходження мінімальних форм булевих многочленів. У своїй роботі я досліджувала один з методів - метод Куайна - Мак-Класкі. Він призначений для знаходження безлічі простих импликант для функцій, заданих сукупністю наборів, на яких функція дорівнює одиниці, або диз'юнктивної досконалої нормальною формою. Уміння мінімізувати логічні функції має величезне значення при проектуванні пристроїв цифрової електроніки.
СПИСОК ВИКОРИСТОВУЮТЬСЯ ДЖЕРЕЛ
1. Владимиров Д.А., Булеві алгебри - М., Видавництво «Наука» 1969.
2. Дискретна математика і математичні питання кібернетики - під загальною редакцією С.В. Яблонського та О.Б. Лупанова - М., «Наука», 1974.
3. Лідл Р., Пільц Г., «Прикладна абстрактна алгебра» - Єкатеринбург, «Видавництво уральського університету» 1996.
4. www.exponenta.ru/educat/systemat/1006/2_tutorials/bin_log.asp
5. www.intuit.ru/department/hardware/archsys/keywords.2.html
Вираз, що є сумою простих импликантой для р, називається непріводімим, якщо воно еквівалентно р, але перетинає бути таким, якщо видалити хоча б один доданок. Мінімальна вираз повинен бути непріводімим. Тому, щоб визначити мінімальну вираз, ми знаходимо все Непріводімие вираження, а серед них шукаємо вираз з найменшим числом літералів. Викладемо тепер належить Куайну метод визначення простих импликантой.
Прості імпліканти виходять з диз'юнктивної нормальної форми d булева многочлена р застосуванням (зліва направо) правила
yz + yz ¢ ~ y,
коли це можливо. Більш загально, ми використовуємо правило
де
Приклад. Нехай р - логічний многочлен, має таку діз'юнктівную нормальну форму:
d = wxyz '+ wxy' z '+ wx' yz + wx 'yz' + w 'x' yz + w 'x' yz '+ w' x 'y' z
Ми використовуємо правило
від wxyz 'і wxy' z 'до wxz'
від wx 'yz і wx' yz 'до wx' y
від wxyz 'і wx' yz 'до wyz'
від w 'x' yz і w 'x' yz 'до w' x 'y
від w 'x' yz і w 'x' y 'z до w' x 'z
від wx 'yz і w' x 'yz до x' yz
від wx 'yz' і w 'x' yz 'до x' yz '
Тут використані, і тому повинні бути позначені, всі сім доданків.
Загалом, ця процедура повторюється знову і знову з використанням тільки помічених виразів (які стають коротше). Інші твори суть прості імпліканти і залишаються незмінними.
У нашому прикладі другий раунд спрощення здійснює перехід
від wx 'y і w' x 'y до x' y
від x 'yz і x' yz 'до x' y
Чотири вираження - wx 'y, w' x 'y, x' yz, x 'yz' - позначені. Інші твори, а саме wxz ', wyz', w 'x' z не можуть бути спрощений. отже, р еквівалентно такій сумі простих импликантой:
р ~ wxz '+ wyz' + w 'x' z + x 'y.
Як вже було сказано, Мак-Класкі поліпшив це метод. Щоб описати покращений алгоритм, використовуємо многочлен
d = wxyz '+ wxy' z '+ wx' yz + wx 'yz' + w 'x' yz + w 'x' yz '+ w' x 'y' z
Крок 1. Вважаючи змінні впорядкованими за алфавітом (або за номерами), поставимо у відповідність кожного твору послідовність символів з {0, 1, -}: замість x i 'і x i запишемо 0 і 1 відповідно, а замість опущених змінних запишемо рисочку. Наприклад, замість w 'x' y 'z запишемо 0001, а замість w' x 'z - 00-1.
Крок 2. Твори, що розглядаються як трійчастий n-ки, розбиваються на класи еквівалентності відповідно до числа одиниць. Впорядкуємо класи за зростанням цього числа. У нашому прикладі:
w 'x' y 'z 0 0 0 1
w 'x' yz '0 0 1 0
w 'x' yz 0 0 1 1
wx 'yz '1 0 1 0
wx 'yz 1 0 1 1
wxyz '1 1 1 0
wxy 'z '1 1 0 0
Крок 3. Використовуючи правило (*), потрібно складати тільки твори з сусідніх класів, тобто коли числа одиниць у відповідних послідовностях відрізняються лише на 1. При цьому ми повинні порівнювати висловлювання з сусідніх класів, які мають риски в одних і тих самих позиціях. Якщо два таких вираження відрізняються точно в одній позиції, то вони мають вигляд р = i 1 i 2 ... i r ... i n і q = i 1 i 2 ... i r '... i n, де все i k лежать у {0, 1, -}, а i r лежить у {0, 1}. Тоді (*) зводить p, q до i 1 i 2 ... i r -1 - i r +1 ... i n, причому p і q повинні бути позначені . У розглянутому прикладі це дає такі четвірки (мітки відносяться до наступного раунду, тоді як у попередньому списку всі твори слід позначити):
0 0 - 1
0 0 1 - ü
- 0 1 0 ü
- 0 1 1 ü
1 0 1 - ü
1 - 1 0
1 1 - 0
Помічені вирази не є простими импликантами і в другому раунді цього кроку дають єдине вираження
- 0 1 -
Отже, ми знайшли всі прості імпліканти, а саме
0 0 1 - w'x'z
- 0 1 0 wyz '
- 0 1 1 wxz '
1 0 1 - x'y
Так як сума всіх простих импликантой необов'язково є мінімальним вираженням, алгоритм потребує виконання ще одного кроку.
Крок 4. У силу теореми сума всіх простих импликантой для р еквівалентна р. тому для кожного доданка диз'юнктивної нормальної форми d многочлена р повинен існувати простий импликант, що є твором цього доданка. для виявлення виник відповідності зручно використовувати таблицю простих импликантой. стовпці цієї таблиці індексуються диз'юнктів з d, а рядки - простими импликантами, обчисленими в кроці 3. на перетині i - го рядка і j-го стовпця ставиться хрестик û, якщо простій импликант з i - го рядка є подпроізведеніем твори з j-го стовпця. Кажуть, що один твір покриває, якщо перше є подпроізведеніем другого. Для того, щоб знайти суму простих импликантой, яка буде еквівалентна d, ми з безлічі всіх простих импликантой вибираємо підмножина таким чином, щоб кожний доданок у d покривалося принаймні одним импликантой з підмножини. Тоді мінімальної формою буде сума простих импликантой з найменшим числом членів і найменшим числом літер. Простий импликант називається головним членом, якщо він покриває твір, не покривається ніяким іншим простим импликантой; сума всіх головних членів називається ядром. спочатку ми знаходимо ядро, потім позначаємо через q 1, ..., q k твори, що не покриваються простими импликантами з ядра; прості імпліканти, що не входять в ядро, позначимо через р 1, ..., р m. Далі формуємо таблицю, стовпці якої індексуються елементами q i, а рядки - елементами р i. Хрестик û на місці (i, j) вказує, що р i покриває q j.
Тепер утворюємо твір сум. Кожен співмножник відповідає одному з q j і є сумою тих р i, який покривають цей q j. Використовуючи закони булевої алгебри, ми перетворимо цей вираз у найпростішу можливу суму творів. Кожне з цих творів являє підмножина елементів р i, які покривають всі q j. Далі розглядаємо твори з найменшим числом співмножників. З цих найкоротших творів вибираємо ті, що містять найменшу загальне число літералів. Тепер кожне з отриманих творів переписуємо у вигляді суми складових його простих импликантой, складаємо з ядром, отримуючи мінімальну суму творів, еквівалентну р.
II. РІШЕННЯ МІНІМАЛЬНИХ форми Булевой многочленів ЗА ДОПОМОГОЮ МЕТОДУ Куайн - МАК-Класкі
Завдання. Визначимо форму булева многочлена р, заданого у диз'юнктивній нормальній формі
d = v 'w' x 'y' z '+ v' w 'x' yz '+ v' w 'xy' z '+ v' w 'xyz' + v 'wx' y 'z + v' wx ' yz '+ v' wxy 'z + v' wxyz '+ v' wxyz + vw 'x' y 'z' + vw 'x' y 'z + vw' xy 'z + vwx' yz '+ vwxy' z ' + vwxyz '+ vwxyz
Рішення:
Кроки 1 і 2
| 0 одиниць | 0 0 0 0 0 | ü | (1) |
| 1 одиниця | 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 | ü ü ü | (2) (3) (4) |
| 2 одиниці | 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 | ü ü ü ü | (5) (6) (7) (8) |
| 3 одиниці | 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 | ü ü ü ü ü | (9) (10) (11) (12) (13) |
| 4 одиниці | 0 1 1 1 1 1 1 1 1 0 | ü ü | (14) (15) |
| 5 одиниць | 1 1 1 1 1 | ü | (16) |
| (1) (2) (1) (3) (1) (4) | 0 0 0 - 0 0 0 - 0 0 - 0 0 0 0 | ü ü J |
| (2) (5) (2) (7) (3) (5) (4) (8) | 0 0 - 1 0 0 - 0 1 0 0 0 1 - 0 1 0 0 0 - | ü ü ü I |
| (5) (10) (6) (9) (7) (10) (7) (12) (8) (11) | 0 - 1 1 0 0 1 - 0 1 0 1 - 1 0 - 1 0 1 0 1 0 - 0 1 | ü H ü ü G |
| (9) (14) (10) (14) (10) (15) (12) (15) (13) (15) | 0 1 1 - 1 0 1 1 1 - - 1 1 1 0 1 1 -1 0 1 1 1 - 0 | F ü ü ü Е |
| (14) (16) (15) (16) | - 1 1 1 1 1 1 1 1 - | ü ü |
Повторення цього кроку з новими рядками дає нам
| (1) (2) (3) (5) | 0 0 - - | D |
| (2) (5) (7) (10) | 0 - - 1 0 | C |
| (7) (10) (12) (15) | - 1 - 1 0 | B |
| (10) (15) (14) (16) | - 1 1 1 - | A |
Крок 4. Формуємо таблицю простих импликантой, де індекси стовпців - доданки з d - представлені у вигляді двійкових стовпців.
| (1) 0 0 0 0 0 | (2) 0 0 0 1 0 | (3) 0 0 1 0 0 | (4) 1 0 0 0 0 | (5) 0 0 1 1 0 | (6) 0 1 0 0 1 | (7) 0 1 0 1 0 | (8) 1 0 0 0 1 | (9) 0 1 1 0 1 | (10) 0 1 1 1 0 | (11) 1 0 1 0 1 | (12) 1 1 0 1 0 | (13) 1 1 1 0 0 | (14) 0 1 1 1 1 | (15) 1 1 1 1 0 | (16) 1 1 1 1 1 | |
| -111 - А | û | û | û | û | ||||||||||||
| -1-10 У | û | û | û | û | ||||||||||||
| 0 - 10 С | û | û | û | û | ||||||||||||
| 00 - 0 D | û | û | û | û | ||||||||||||
| 111 - 0 E | û | û | ||||||||||||||
| 011-1 F | û | û | ||||||||||||||
| 10-01 G | û | û | ||||||||||||||
| 01-01 H | û | û | ||||||||||||||
| 1000 - I | û | û | ||||||||||||||
| -0000 J | û | û |
| (4) 1 0 0 0 0 | |
| 0 - - 1 0 С | |
| 0 1 1 - 1 F | |
| 1 0 0 0 - I | û |
| - 0 0 0 0 J | û |
(I) D + H + G + B + E + A + I, якщо використовувати I, і
(Ii) D + H + G + B + E + A + J, якщо вибрати J.
У звичайних позначеннях мінімальна форма (i) така:
v 'w' z '+ v' wy 'z + vw' y 'z + wyz' + vwxz '+ wxy + vw' x 'y'.
ВИСНОВОК
За результатами проведеного курсового дослідження за темою «Мінімальні форми булевих многочленів» можна зробити наступні висновки.
При всій простоті своїй аксіоматики теорія булевих алгебр дуже змістовна. Ми знаходимо в ній чимало важких і глибоких проблем, багато з яких ще не вирішені. Ці проблеми дуже різні, вони стикаються з логікою і теорією множин, з дослідженнями та аналізом. Така велика кількість точок дотику із суміжними математичними дисциплінами ріднить теорію булевих алгебр з функціональним аналізом, до якого вона близька і за своїм загальним математичного стилю.
Існують різні методи знаходження мінімальних форм булевих многочленів. У своїй роботі я досліджувала один з методів - метод Куайна - Мак-Класкі. Він призначений для знаходження безлічі простих импликант для функцій, заданих сукупністю наборів, на яких функція дорівнює одиниці, або диз'юнктивної досконалої нормальною формою. Уміння мінімізувати логічні функції має величезне значення при проектуванні пристроїв цифрової електроніки.
СПИСОК ВИКОРИСТОВУЮТЬСЯ ДЖЕРЕЛ
1. Владимиров Д.А., Булеві алгебри - М., Видавництво «Наука» 1969.
2. Дискретна математика і математичні питання кібернетики - під загальною редакцією С.В. Яблонського та О.Б. Лупанова - М., «Наука», 1974.
3. Лідл Р., Пільц Г., «Прикладна абстрактна алгебра» - Єкатеринбург, «Видавництво уральського університету» 1996.
4. www.exponenta.ru/educat/systemat/1006/2_tutorials/bin_log.asp
5. www.intuit.ru/department/hardware/archsys/keywords.2.html