Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum
.pdfx |
y |
f(y,y,g) |
y |
y |
g(x,y,x) |
x |
y |
x |
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
Видiлений жирним шрифтом буде задавати функцiю ( , ). Отже,
( , ) = (1010).
№ 13.2. Довизначити функцiї ( , , ) = (−101 − −0−), ( , , ) = (−−−0 −101), ( , , ) = (0 −01 −−0−) так, щоб , , . Дкщо побудова неможлива, довести це.
Дослiдити, чи будуть належати отриманi функцiї до класiв 0 та 1.
Розв’язок. Складемо таблицю значень даних функцiй.
x |
y |
z |
f |
g |
h |
|
|
|
|
|
|
0 |
0 |
0 |
- |
- |
0 |
0 |
0 |
1 |
1 |
- |
- |
0 |
1 |
0 |
0 |
- |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
- |
- |
- |
1 |
0 |
1 |
- |
1 |
- |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
- |
1 |
- |
|
|
|
|
|
|
Розглянемо спочатку функцiю ( , , ). Оскiльки (1, 1, 0) = 0, то, щоб бути монотонною, на всiх “менших” (1, 1, 0) наборах вона теж має дорiвнювати 0, тобто (0, 0, 0) = (1, 0, 0) = 0. Далi, оскiльки (0, 0, 1) = 1, то (1, 0, 1) = (1, 1, 1) = 1 для виконання монотонностi. Отже, ( , , ) =
130
(01010101). Очевидно, що 0 та 1, адже (0, 0, 0) = 0 та
(1, 1, 1) = 1.
Розглянемо тепер функцiю ( , , ). Щоб дана функцiя була лiнiй-
ною, потрiбно, щоб
( , , ) = 0 1 2 3 .
Пiдставивши набори, на яких функцiя визначена, отримаємо систему рiвнянь
|
|
0 2 3 = 0 |
|
|
||||||
|
|
0 |
|
1 |
|
3 = 1 |
|
|
||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
2 = 0 |
|
|
||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
2 |
|
3 = 1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З третього та |
четвертого рiвняння видно, що |
|
= 1. Пiдставляючи |
|||||||
|
|
|
|
|
|
|
|
3 |
|
|
це значення у систему, маємо |
|
|
|
|
|
|
|
|||
|
|
|
0 2 = 1 |
|
|
|
||||
|
|
|
0 |
|
1 = 0 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 2 = 0. |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
Отримаємо 2 = 0, 0 = 1, 1 = 1.
Отже, ( , , ) = 1 - лiнiйна булева функцiя.
Оскiльки (0, 0, 0) = 1 0 0 = 1, то / , а в силу того, що
(1, 1, 1) = 1 1 1 = 1 1.
Розглянемо функцiю ( , , ). Для того, щоб ця функцiя була самодвоїстою, вона має давати протилежнi результати на двоїстих наборах.
Так як набори (0, 0, 0) та (1, 1, 1) самодвоїстi, а (0, 0, 0) = 1, то
(1, 1, 1) = 1. Аналогiчно (0, 0, 1) = (1, 1, 0) = 1, (1, 0, 1) = (0, 1, 0) = 1. Отже, ( , , ) = (01010101). Також, 0 та 1.
131
№ 13.3. Довести, що iмплiкацiю (→) не можна виразити через кон’юнкцiю ( ) та диз’юнкцiю ( ).
Розв’язок. Припустимо, що це можливо, тобто → ≡ ( , ), де
( , ) - булева функцiя, яка мiстить лише кон’юнкцiю та диз’юнкцiю. Оскiльки 0 0 ≡ 0 та 0 0 ≡ 0, то (0, 0) ≡ 0. Але 0 → 0 ≡ 1, тому рiвнiсть ( , ) = → неможлива.
№ 13.4. Дослiдити незалежнiсть системи функцiй {, ¬}
Розв’язок. Перевiримо функцiї системи на належнiсть до класiв Поста.
Функцiя ( ) = = 1 належить до класу . Перевiримо, чи функцiя ( , ) = є лiнiйною. Якби це було так, то функцiю можна було б задати у виглядi = 0 1 2 .
При = = 0 0 0 = 0 = 0, звiдки 0 = 0.
При = 1, = 0 1 0 = 0 = 0 1, звiдки 1 = 0. При = 0, = 1 0 1 = 0 = 0 2, звiдки 2 = 0.
Отже, = 0 0 0 = 0, що неможливо. Отже, не належить класу . А, оскiльки клас функцiонально замкнений, то функцiю не можна виразити через функцiю ¬, тому цi функцiї незалежнi.
Навпаки, функцiя ( , ) = монотонна, оскiльки приймає найбiльше значення на наборi (1, 1): (1, 1) = 1, отже, . Оскiльки
1 ≡ 0 < 1, то заперечення ¬ не є монотонною функцiєю. В силу функцiональної замкненостi класу i того, що ¬ / заперечення не може бути виражене через кон’юнкцiю.
Отже, система функцiй {¬, } є незалежною.
№ 13.5. Дослiдити на повноту систему функцiй {, ¬}
132
Розв’язок. Дослiдимо функцiї системи на належнiсть до класiв Поста.
Розглянемо спочатку кон’юнкцiю. В силу тотожностей 0 0 ≡ 0 та
1 1 ≡ 1 маємо, що 0 та 1. В попередньому прикладi доведено, що / та . Перевiримо кон’юнкцiю на самодвоїстiсть. Маємо
( ) ≡ ≡ ̸= .
Отже, кон’юнкцiя не самодвоїста, тобто / .
Розглянемо тепер заперечення. З рiвностей 0 ≡ 1, 1 ≡ 0 бачимо, що
¬ / 0 та ¬ / 1. За попереднiм прикладом ¬ та ¬ / . Очевидно,
що заперечення самодвоїсте, адже ≡ .
Складемо таблиц, в якiй запишемо належнiсть кожної з функцiй системи до класiв Поста.
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
+ |
+ |
– |
+ |
– |
¬ |
– |
– |
+ |
– |
+ |
Бачимо, що в кожному стовпцi є хоча б один мiнус. Отже, за критерiєм Поста система є повною.
Задачi для аудиторної та домашньої роботи
№ 13.6. Знайти таблицю значень булевої функцiї ( , ), яка є суперпозицiєю функцiй та , де
1 = (01101000); 2 = (10010100); 3 = (00011001); 4 = (10001100);
5 = (00111000); 6 = (01101011); 7 = (01001010); 8 = (01111001);
9 = (01011001); 10 = (10100111).
133
1.( , ) = 2( , 1( , , ), );
2.( , ) = 1( , 2( , , ), );
3.( , ) = 3( , 5( , , ), );
4.( , ) = 3( , 2( , , ), );
5.( , ) = 4( , 3( , , ), );
6.( , ) = 2( , 3( , , ), );
7.( , ) = 5( , , 2( , , ));
8.( , ) = 5( 4( , , ), , );
9.( , ) = 3( , , 2( , , ));
10.( , ) = 4( , , 3( , , ));
11.( , ) = 2( , 4( , , ), );
12.( , ) = 5( , , 7( , , ));
13.( , ) = 9( , , 8( , , ));
14.( , ) = 7( , , 5( , , ));
15.( , ) = 8( , , 7( , , ));
16.( , ) = 7( , 1( , , ), );
17.( , ) = 5( , 9( , , ), );
18.( , ) = 5( , 10( , , ), );
19.( , ) = 10( , 9( , , ), );
20.( , ) = 10( 7( , , ), , ).
21.( , ) = 7( 10( , , ), , ).
22.( , ) = 8( 9( , , ), , )).
23.( , ) = 5( 8( , , ), , ).
24.( , ) = 5( 6( , , ), , ).
25.( , ) = 5( 3( , , ), , ).
26.( , ) = 4( , , 10( , , )).
27.( , ) = 2( 9( , , ), , ).
28.( , ) = 10( , , 8( , , )).
29.( , ) = 7( , 3( , , ), ).
№ 13.7. Довизначити функцiїї ( , , ), ( , , ) та ( , , ) так, щоб
, , . Якщо побудова неможлива, довести це. Дослiдити належнiсть побудованих функцiй до 0 та 1.
1. = (− − −10 − −−), = (1 − − − 001−), = (00 − −01 − −);
134
2.= (− − −1 − 01−), = (− − −11 − 01), = (−0 − −10 − 1);
3.= (−0 − − − −1−), = (10 − 1 − 0 − −), = (010 − 0 − −−);
4.= (− − −1 − 10−), = (1 − 01 − − − 0), = (− − 01 − −10);
5.= (− − 0 − −1 − −), = (−10 − −0 − 1), = (−0 − 1 − 0 − 1);
6.= (−1 − 10 − −−), = (0 − − − 110−), = (−11 − 0 − −0);
7.= (−0 − 0 − −1−), = (− − −00 − 10), = (−0 − −01 − 1);
8.= (−10 − −1 − −), = (01 − 0 − 1 − −), = (1 − − − 010−);
9.= (− − −10 − 0−), = (0 − 10 − − − 1), = (0 − −0 − 11−);
10.= (−0 − − − −10), = (0 − 0 − − − 11), = (0 − 01 − −0−);
11.= (1 − −10 − −−), = (− − 110 − 1−), = (− − 01 − −11);
12.= (1 − 0 − −1 − −), = (− − 010 − 0−), = (−01 − 1 − −0);
13.= (10 − − − −1−), = (−11 − 0 − 0−), = (00 − 0 − 1 − −);
14.= (− − −10 − −0), = (1 − − − 110−), = (−101 − − − 0);
15.= (− − 0 − −1 − 0), = (−01 − 1 − −0), = (−0 − −01 − 1);
16.= (−0 − − − 01−), = (1 − −0 − 1 − 1), = (11 − 0 − 0 − −);
17.= (− − 110 − −−), = (− − 0 − 00 − 1), = (11 − 1 − 1 − −);
18.= (−10 − −1 − −), = (− − −110 − 1), = (10 − −10 − −);
19.= (−0 − −1 − 1−), = (0 − −1 − 0 − 0), = (1 − 01 − −1−);
135
20.= (− − −10 − 0−), = (− − 1 − 11 − 0), = (− − −0 − 101);
21.= (− − 00 − 1 − −), = (− − −001 − 0), = (−0 − −01 − 1);
22.= (−01 − − − 1−), = (0 − − − 001−), = (1 − −0 − 01−);
23.= (−10 − −1 − −), = (−10 − 0 − −1), = (−0 − 1 − 1 − 0);
24.= (−1 − 10 − −−), = (−0 − 10 − 10), = (0 − −1 − 01−);
25.= (−0 − 0 − −1−), = (0 − −1 − 10−), = (− − 10 − −00);
26.= (−1 − 10 − −−), = (10 − 0 − 1 − −), = (1 − 11 − −1−);
27.= (− − 00 − 1 − −), = (−01 − 0 − 1−), = (1 − −0 − 10−);
28.= (−0 − −100−), = (10 − −0 − 1−), = (−010 − − − 1);
29.= (− − −100 − −), = (−1 − −010−), = (11 − 1 − 1 − −).
№13.8. Виразити за допомогою суперпозицiй:
1. |
i → через та ¬; |
7. |
через штрих Шеффера; |
|||||
2. |
i → через та ¬; |
8. |
|
через штрих Шеффера; |
||||
3. |
i через → та ¬; |
|
|
|||||
9. |
→ через штрих Шеффера; |
|||||||
4. |
¬ через → та 0; |
|||||||
10. |
¬ через штрих Шеффера; |
|||||||
5. |
¬ |
через |
|
та 1; |
||||
|
|
|
|
|
|
|||
6. |
через →; |
11. |
↓ через ¬ та . |
|||||
№ 13.9. Довести, що не можна виразити за допомогою суперпозицiй:
136
1. |
¬ через та ; |
7. |
¬ через , та →; |
|||
2. |
¬ через та →; |
8. |
¬ через , та ; |
|||
3. |
¬ через та ; |
9. |
¬ через , та →; |
|||
4. |
¬ через та →; |
10. |
¬ через , та →; |
|||
5. |
¬ через та ; |
11. |
¬ через , , та →; |
|||
6. |
¬ через → та ; |
12. |
через та →. |
|||
№ 13.10. Дослiдити систему функцiй на незалежнiсть: |
||||||
1. |
{¬, }; |
9. |
{ , |}; |
|||
2. |
{¬, }; |
10. |
, |
; |
||
|
|
|
|
{ |} |
|
|
3. |
{ , }; |
11. |
{→, }; |
|||
4. |
{ , }; |
|||||
12. |
{→, |}; |
|||||
5. |
{ , }; |
|||||
13. |
{→, ↓}; |
|||||
6. |
{ , }; |
|||||
|
|
|
||||
7. |
, |
; |
14. |
{¬, |}; |
||
|
{ →} |
|
|
|
|
|
8. |
{ , ↓}; |
|
15. |
{¬, ↓}. |
||
№ 13.11. Дослiдити систему функцiй на незалежнiсть: |
||||||
1. |
{ , ¬}; |
|
3. |
{¬, →}; |
||
2. { , }; |
4. {¬, }; |
137
5.{→, };
6.{ , , ¬};
7.{ , →, ¬};
8.{ , , ¬};
9.{ , →, ¬};
10.{ , , ¬};
11.{→, , ¬};
12.{ , , →};
13.{ , , };
14.{ , , 0};
15.{ , , 1};
16.{ , , 1};
17.{ , , 1};
18.{ , →, 1};
19.{→, 0};
20.{|};
21.{↓};
22.{ , , 1};
23.{ , , 0};
24.{¬, };
25.{ , , 0};
26.{ , , 0};
27.{ , →, 0};
28.{ , →};
29.{ , }.
138
ЗАНЯТТЯ 14
Мiнiмiзацiя булевих функцiй
Навчальнi задачi
№ 14.1. Для заданої функцiї ( , , , ) = 1101 1010 1101 1100 записати ДДНФ та ДКНФ i знайти скорочену ДНФ методом Квайна.
Розв’язок. Зобразимо таблицю значень функцiї у виглядi карти Карно.
|
|
|
|
|
|
|
|
|
|
|
|
zw |
|
00 |
01 |
11 |
10 |
|
|
|
|
|
||||
|
xy |
|
|
|||||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
00 |
|
1 |
1 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
01 |
|
1 |
0 |
0 |
1 |
|||
|
|
|
|
|
|
|
|
|
11 |
|
1 |
1 |
0 |
0 |
|||
|
|
|
|
|
|
|
|
|
10 |
|
1 |
1 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
Знайдемо ДДНФ даної функцiї. Для цього оберемо тi значення змiнних, для яких функцiя приймає значення 1, для всiх таких комбiнацiй складемо кон’юнкцiї змiнних, ставлячи заперечення над змiнною, якщо та рiвна 0. Диз’юнкцiя всiх таких кон’юнкцiй i буде ДДНФ функцiї.
139