Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum
.pdf12. Системи булевих функцiй
Незалежна система булевих |
будь-яка з ф-й з не може бути |
|||||||
функцiй |
виражена через iншi функцiї |
|||||||
|
|
|
|
|
|
|
|
|
Повна система булевих ф-й |
будь-яка булева функцiя є супер- |
|||||||
|
позицiєю функцiй з |
|
||||||
|
|
|
|
|
|
|
|
|
Монотонна булева функцiя |
1 ≤ 1, . . . , < |
|||||||
|
( 1, . . . , ) ≤ ( 1, . . . , ) |
|||||||
Лiнiйна булева функцiя |
можливе |
зображення |
||||||
|
( 1, 2, . . . , ) = |
|
||||||
|
= 0 1 1 . . . |
|||||||
Самодвоїста булева функцiя |
двоїста сама собi: ( 1, . . . , ) = |
|||||||
|
|
|
|
|
|
|
|
|
|
= ( |
|
, . . . , |
|
) |
|
||
|
1 |
|
|
|||||
Булева функцiя що зберiгає 0 |
(0, . . . , 0) ≡ 0 |
|
||||||
Булева функцiя що зберiгає 1 |
(1, . . . , 1) ≡ 1 |
|
||||||
Класи Поста |
|
|
|
|
|
|
|
|
|
|
|||||||
- клас усiх лiнiйних булевих функцiй |
|
|||||||
|
|
|||||||
- клас усiх монотонних булевих функцiй |
|
|||||||
|
|
|||||||
- клас усiх самодвоїстих булевих функцiй |
|
|||||||
|
|
|||||||
0 - клас усiх булевих функцiй, що зберiгають 0 |
|
|||||||
|
|
|||||||
1 - клас усiх булевих функцiй, що зберiгають 1 |
|
|||||||
|
|
|||||||
Критерiй Поста |
система булевих функцiй є пов- |
|||||||
|
ною тодi i тiльки тодi, коли в нiй |
|||||||
|
є: |
|
||||||
|
|
|
|
|
|
|
|
|
a) хоча б одна нелiнiйна функцiя; б) хоча б одна немонотонна функцiя; в) хоча б одна несамодвоїста функцiя; г) хоча б одна функцiя, що не зберiгає 0; д) хоча б одна функцiя, що не зберiгає 1.
20
13. Мiнiмiзацiя булевих функцiй
Iмплiканта булевої функцiї |
→ ≡ 1 |
|||
Проста iмплiканта булевої |
при видаленi будь-якої букви з |
|||
функцiї |
вона перестає бути iмплiкантою |
|||
|
|
|
|
|
Скорочена ДНФ булевої фун- |
складається з простих iмплiкант |
|||
кцiї |
функцiї |
|||
|
|
|
|
|
Ядрова iмплiканта булевої |
при видаленi iмплiканти з ДНФ |
|||
функцiї |
отримуємо ДНФ, не рiвносильну |
|||
|
|
|
|
|
Мiнiмальна ДНФ булевої фун- |
має найменшу кiлькiсть символiв |
|||
кцiї |
з усiх з ДНФ функцiї |
|||
|
|
|
|
|
Глуха ДНФ булевої функцiї |
ДНФ iз простих iмплiкант, вида- |
|||
|
лення з якої будь-якої кон’юнкцiї |
|||
|
порушує рiвносильнiсть цiєї ДНФ |
|||
|
булевiй функцiї |
|||
|
|
|
|
|
Складнiсть ДНФ |
Кiлькiсть символiв змiнних у |
|||
|
ДНФ |
|||
|
|
|
|
|
Формула неповного склею- |
( ) ( |
|
) ≡ |
|
|
||||
вання |
( ) ( |
|
) |
|
|
21
14. Основи теорiї графiв
Граф |
= ( , ) - геометрична конфi- |
|
гурацiя, що складається з вершин, |
|
сполучених ребрами |
|
|
Множина вершин |
= { 1, . . . , } |
Множина ребер |
= { 1, . . . , } |
Порядок графу |
кiлькiсть вершин графу | | |
Сумiжнi вершини |
вершини, сполученi ребром: = |
|
( , ) |
|
|
Повний граф |
граф, у якого кожнi двi вершини |
|
сумiжнi |
|
|
Шлях |
послiдовнiсть ребер 1, 2, . . . , |
|
така, що та +1 мають спiльну |
|
вершину |
|
|
Цикл |
шлях, початкова вершина якого |
|
спiвпадає з кiнцевою |
|
|
Ейлерiв шлях (цикл) |
шлях (цикл), коже ребро якого |
|
з’являється лише один раз |
|
|
Iнцидентнi вершина та ребро |
вершина , сполучена з ре- |
|
бром |
|
( : = ( , )) |
Степiнь вершини |
кiлькiсть ребер, iнцидентних вер- |
|
шинi |
|
|
Матриця сумiжностi |
= || , ||; , – кiлькiсть ребер, |
|
iнцидентних одночасно та |
22
Матриця iнцидентностi |
= || , ||; , коли -та вершина |
||
|
iнцидентна -му ребру, та , = 0, |
||
|
якщо нi |
|
|
|
|
|
|
Iзоморфнi графи та |
графи, мiж |
множинами |
вершин |
|
яких можна |
встановити |
бiєкцiю, |
|
яка зберiгає сумiжнiсть вершин |
||
|
|
||
Iзольована вершина |
вершина, не сполучена з жодною |
||
|
iншою |
|
|
|
|
||
Зв’язний граф |
будь-якимi двi вершини графа |
||
|
з’єднує ланцюг |
|
|
|
|
||
Ейлерiв граф |
в графi iснує ейлерiв цикл |
||
|
|
||
Напiвйлерiв граф |
в графi iснує незамкнений ейлерiв |
||
|
ланцюг |
|
|
|
|
||
Зв’язний граф Ейлерiв кожна його вершина має парну степiнь |
|||
Орiєнтований граф (орграф) |
граф, ребрам якого (дугам) при- |
||
|
своєно напрямок |
|
|
|
|
||
Петля орграфу |
дуга, що починається i закiнчує- |
||
|
ться в тiй самiй вершинi |
|
|
|
|
||
Матриця сумiжностi |
= || , ||; , – кiлькiсть ребер, |
||
|
що починаються з та закiнчую- |
||
|
ться в |
|
|
|
|
||
Матриця iнцидентностi ор- |
= || , ||; , = −1 коли -та вер- |
||
графу |
шина – початок -ї дуги; , = −1, |
||
|
якщо кiнець; , = 2, якщо -a ду- |
||
|
га є петлею |
|
|
|
|
|
|
23
Турнiр |
повний орграф |
|
|
|
|
Дерево |
зв’язний граф, який не мiстить ци- |
|
|
|
клiв |
|
|
|
Основнi властивостi дерев |
|
|
|
|
|
1. |
дерево не має циклiв та мiстить | | − 1 ребер; |
|
2. |
видалення будь-якого ребра порушить зв’язнiсть; |
|
|
|
|
3. |
додавання будь-якого ребра породить цикл; |
|
|
|
|
4. |
будь-якi двi вершини пов’язанi рiвно одним шляхом. |
|
|
|
|
Реберний пiдграф ( ′, ′) |
пiдграф графа ( , ) такий, що |
|
|
|
′ , ′ , причому ′ скла- |
|
|
дається з кiнцевих вершин ребер |
|
|
′ |
Остовне дерево графа ( , ) |
пiдграф ′( , ′) графа ( , ), |
|
|
|
який є деревом |
|
|
|
24
15. Основи теорiї груп
Бiнарна операцiя |
математичний об’єкт, що складає- |
|
ться з двох величин i певної дiї над |
|
ними |
|
|
Нейтральний елемент |
елемент , для якого * = |
|
= * = для будь-якого |
Обернений елемент до |
елемент −1, для якого * −1 = |
|
= −1 * = для будь-якого |
Замкнутiсть вiдносно опе- |
, : * |
рацiї * |
|
Магма |
базова алгебраїчна структура, що |
|
складається з множини та замкну- |
|
тої бiнарної операцiєї |
|
|
Напiвгрупа |
асоцiативна магма |
|
|
Моноїд |
напiвгрупа з нейтральним елемен- |
|
том |
|
|
Група |
моноїд з оберненим елементом |
|
|
Iзоморфiзм груп та |
бiєкцiя : → , для якої |
|
, : ( ) * ( ) = ( * ) |
Пiдгрупа |
пiдмножина групи , що є гру- |
|
пою вiдносно операцiї, яка задає |
|
|
Лiвий (правий) сумiжний |
= { : } ( = { : |
клас по пiдгрупi групи |
}) |
Циклiчна група |
група, породжена своїм елементом |
|
|
Порядок елемента |
найменше додатнє число ( ) = |
|
таке, що = |
25
ЗАНЯТТЯ 1
Елементи алгебри висловлювань
Навчальнi задачi
№ 1.1. Побудувавши таблицю iстинностi, перевiрити, чи буде формула
( ) → ( → ) тавтологiєю.
Розв’язок. Для перевiрки, будуємо таблицi iстинностi виразiв ,
→ , та власне самої формули.
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
a |
b |
|
→ |
( ) → ( → ) |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
Значення стовпчикiв 3 та 4 будуються на основi значень стовпчикiв 1 та 2. Значення стовпчика 5 будується на основi значень стовпчикiв 3 та 4. Так як стовпчик 5 мiстить лише iстиннi значення, то запропонована формула є тавтологiєю, тобто завжди iстинна.
№ 1.2. Побудувавши таблицi iстинностi, перевiрити, чи будуть формули
→ та еквiвалентними.
26
Розв’язок. Будуємо вiдповiднi таблицi iстинностi та перевiряємо запропоноване твердження
1 |
2 |
3 |
|
4 |
5 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
→ |
|
|
|
|
|
|
||||||
1 |
1 |
0 |
|
1 |
1 |
|||
|
|
|
|
|
|
|||
1 |
0 |
0 |
|
0 |
0 |
|||
|
|
|
|
|
|
|||
0 |
1 |
1 |
|
1 |
1 |
|||
|
|
|
|
|
|
|||
0 |
0 |
1 |
|
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
Стовпчик 3 будується на основi значень стовпчика 1. Стовпчик 4 обчислюється за значеннями стовпчикiв 1 та 2, а стовпчик 5 - за значеннями стовпчикiв 2 та 3. Так як стовпчики 4 та 5 таблицi iстинностi спiвпадають, то можна зробити висновок, що наведена рiвносильнiсть правильна.
№ 1.3. За допомогою таблиць iстинностi перевiрити, яка з рiвносильностей iстинна: ( → ) ≡ чи ( → ) ≡
Розв’язок. Для перевiрки, будуємо таблицi iстинностi трьох виразiв:
( → ), та .
1 |
2 |
3 |
|
4 |
|
5 |
6 |
|
7 |
|
|
8 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
→ |
|
|
|
|
|
|
|
|
|
|
|
|
→ |
|
|
||||||||||||
1 |
1 |
0 |
|
0 |
|
1 |
0 |
|
0 |
|
|
0 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
1 |
0 |
0 |
|
1 |
|
0 |
1 |
|
1 |
|
|
0 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
0 |
1 |
1 |
|
0 |
|
1 |
0 |
|
0 |
|
|
1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
0 |
0 |
1 |
|
1 |
|
1 |
0 |
|
0 |
|
|
0 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Стовпчик 3 побудовано на основi значень стовпчика 1, а стовпчик 4 - на основi стовпчика 2. Стовпчик 6 обчислено на основi стовпчика 5,
27
який, в свою чергу, обраховано на основi стовпчикiв 1 та 2. Значення в стовпчику 7 обчислюється за значеннями стовпчикiв 1 та 4, а значення в стовпчику 8 - на основi стовпчикiв 2 та 3. Так як стовпчики 6 та 7 спiвпадають, а 6 та 8 нi, робимо висновок, що правдива перша рiвносильнiсть.
№ 1.4. За допомогою перетворень алгебри логiки довести, що вираз iз задачi 1.1 є тавтологiєю.
Розв’язок. Перш за все, перепишемо дану формулу, використовуючи лише кон’юнкцiю, диз’юнкцiю та заперечення. Так як ≡ ( ) ( ) та → ≡ , то
( ) → ( → ) ≡ (( ) ( )) ( ).
Далi застосовуємо правила де Моргана для перетворення заперечень:
(( ) ( )) ( ) ≡ (( ) ( )) ( ) ≡ (( ) ( )) ( ).
За дистрибутивним законом, перемножаємо вирази у перших дужках:
(( ) ( )) ( ) ≡ (( ) ) (( ) )) ( ) ≡
≡ ( ) ( ) ( ) ( ) ( ).
Так як ≡ 0 (закон суперечностi), а 0 ≡ (закон нуля та одиницi), то ( ) та останнiй вираз можна переписати як
( ) ( ) ( ).
За правилом де Моргана, ( ) ≡ ( ), а за законом виключення третього
( ) ( ) ( ) ≡ ( ) ( ) ( ) ≡ 1 ( ).
28
Остаточно, за законом нуля та одиницi маємо, що
1 ( ) ≡ 1,
тобто задана формула дiйсно є тавтологiєю.
№ 1.5. За допомогою перетворень алгебри висловлювань довести рiвносильнiсть: ≡ ( → ) ( → ).
Розв’язок. Записуємо обидвi частини рiвностi через кон’юнкцiю, ди-
з’юнкцiю та заперечення:
( ) ≡ ( ) ( ), ( → ) ( → ) ≡ ( ) ( ).
Перетворюємо останнiй вираз за дистрибутивним законом:
( ) ( ) ≡ (( ) ) (( ) ) ≡ ( ) ( ) ( ) ( ).
За законом суперечностi та законом нуля та одиницi, отримаємо
( ) ( ) ( ) ( ) = ( ) 0 0 ( ) ≡ ( ) ( ),
що спiвпадає з представленням еквiваленцiї за допомогою кон’юнкцiї, диз’юнкцiї та iмплiкацiї.
Задачi для аудиторної та домашньої роботи
№ 1.6. Побудувати таблицi iстинностi для формул:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. |
( → ) ( → ( )); |
4. |
(( ) → ) → ( → ); |
||||||||||||
2. |
|
|
→ ( |
|
)) → ( ); |
5. |
( → ( )) → (( → ) → |
||||||||
( |
|
|
|||||||||||||
|
|||||||||||||||
3. |
( ( → )) → |
|
; |
|
( → )); |
||||||||||
|
6. |
|
|
|
|
|
|
→ ) ). |
|||||||
|
|
|
|
|
|
|
|
( ( |
|
)) (( |
|
||||
|
|
|
|
|
|
|
|
|
29