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

• Название: Далі Назад Перехід від одної форми до іншої Сигнал, вироблений одним логічним елементом, можна подавати на вхід іншого елемента, це дає можливість утворювати ланцюжки з окремих логічних елементів функціональні схеми
• Дата: 20.10.2022
• Размер: 0.55 Mb.
• Имя файла: Способи уявлення булевих функцій (1).pptx
• Тип: Документы; #744843

Логічні основи цифрових обчислювальних машин

Логічні схеми

ДДНФ

ДКНФ

Карти Карно

Далі

Назад

Перехід від одної

форми до іншої

• Сигнал, вироблений одним логічним елементом, можна подавати на вхід іншого елемента, це дає можливість утворювати ланцюжки з окремих логічних елементів - функціональні схеми.
• Функціональна (логічна) схема - це схема, що складається з логічних елементів, яка виконує певну функцію. 
• Аналізуючи функціональну схему, можна зрозуміти, як працює логічний пристрій, тобто дати відповідь на питання : яку функцію вона виконує.

Логічні схеми

• Важливою формою опису функціональних схем є структурна формула. 

Покажемо на прикладах.

Приклад 1:

Логічні схеми

Приклад 2:

Логічні схеми

Домашнє завдання

• Побудувати функціональну схему

 

Логічні схеми

Констітуентою 1(мінтермом) називається функція, що приймає значення 1 тільки на єдиному наборі.

• Констітуента 1 записується як кон'юнкція різних булевих змінних, деякі з них можуть бути з запереченнями.
• Наприклад:

- є констітуентою 1 змінних х1, х2, х3 на єдиному наборі 101, а на інших наборах ця констітуента дорівнює 0 ().

- є констітуентою 1 змінних х1, х2, х3 на єдиному наборі 010, а на інших наборах ця констітуента дорівнює 0 ( =1).

 

ДДНФ

ДКНФ

Оскільки диз'юнкція дорівнює 1, коли хоча б одна з змінних приймає значення 1, то:

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

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

ДДНФ

ДКНФ

Констітуентою 0 (макстермом) називається функція, що приймає значення 0 тільки на єдиному наборі.

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

• Наприклад,

- є констітуентою 0 змінних х1, х2, х3 на єдиному наборі 010, а на інших наборах ця констітуента дорівнює 0 ( ).

- є констітуентою 0 змінних х1, х2, х3 на єдиному наборі 101, а на інших наборах ця констітуента дорівнює 0 (=0).

 

ДДНФ

ДКНФ

Оскільки кон'юнкція дорівнює 0, коли хоча б одна з змінних приймає значення 0, то:

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

Така форма уявлення булевої функції називається кон'юнктивною нормальною формою (КНФ).

ДДНФ

ДКНФ

Рангом констітуенти 1 або констітуенти 0 називається кількість змінних, вхідних у неї.

Рангом функції називається кількість змінних від який вона залежить.

Диз'юнктивна нормальна форма уявлення функцій називається досконалою (ДДНФ), якщо :

• ранг (r) усіх констітуент 1 дорівнює рангу функції
• констітуенти 1 не містять однакових змінних
• констітуенти 1 не містять змінну і її інверсію
• жодна констітуента 1 не повторюється

ДДНФ

ДКНФ

Кон'юнктивна нормальна форма уявлення функцій називається досконалою (КДНФ), якщо :

• ранг (r) усіх констітуент 0 дорівнює рангу функції
• констітуенти 0 не містять однакових змінних;
• констітуенти 0 не містять змінну і її інверсію;
• жодна констітуента 0 не повторюється.

ДДНФ

ДКНФ

Домашнє завдання

Побудувати функціональні схеми

ДДНФ

ДКНФ

Карта Карно - графічне уявлення всіх мінтермов (елементарних кон'юнкцій) для даного числа змінних.

• Кожен мінтерм зображується у вигляді клітки так, щоб мінтерми в сусідніх клітках карти Карно відрізнялися значенням тільки однієї змінної (00-01).
• У Картах Карно сусідніми являються також і сусідні стовпці і рядки.

Визначення функції у вигляді ДКНФ і ДДНФ аналогічно таблиці істинності.

Функція задається шляхом встановлення в відповідні клітки 1 для мінтермів і 0 для макстермів.

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

ДДНФ

ДКНФ

ДДНФ

ДКНФ

Карта Карно 2 змінних

ДДНФ

ДКНФ

Карта Карно

 

 

1

А

 

В

A	B	A B
0	0	0
0	1	0
1	0	0
1	1	1

0

0

0

1

Карта Карно 3 змінних

ДДНФ

ДКНФ

 

 

1

х1х2

х3

000

 

 

 

001

010

011

110

111

100

101

 

х3

х1х2

х3

000

 

001

010

011

110

111

100

101

Карта Карно 3 змінних

ДДНФ

ДКНФ

 

 

1

х1х2

х3

0

 

 

 

0

1

0

1

1

0

0

Х1	Х2	Х3	F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

ДДНФ

010

111

110

Карта Карно 4 змінних

ДДНФ

ДКНФ

 

 

01

х1х2

х3х4

0000

 

 

 

0001

0100

0101

1100

1101

1000

1001

11

10

0011

0010

0111

0110

1111

1110

1011

1010

Карта Карно 4 змінних

ДДНФ

ДКНФ

 

х3

 

х1х2

х3х4

0

1

4

5

12

13

8

9

3

2

7

6

15

14

11

10

х4

Домашнє завдання

Заповнити карту Карно

ДДНФ

ДКНФ

ДДНФ

ДКНФ

,

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

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

,

 

ДДНФ

ДКНФ

,

,

Число таких перетворень для кожної кон'юнкції дорівнює:

2 r - k ,

де r - ранг функції,

k- ранг кон'юнкції

Наприклад:

ДДНФ

ДКНФ

,

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

,

 

Наприклад: