Лекція 3 Алгебра логіки Терновой Максим Юрійович к т. н., с н. с., доцент кафедри інформаційно

• Название: Лекція 3 Алгебра логіки Терновой Максим Юрійович к т. н., с н. с., доцент кафедри інформаційно
• Дата: 18.05.2019
• Размер: 1.3 Mb.
• Имя файла: L_3.pdf
• Тип: Лекція; #77617
• страница: 3 из 4

Спосіб «розгортання» ДНФ до вигляду
ДДНФ деякої функції, що залежить від
n
змінних
Він полягає в наступному:
1. Виділити всі доданки (елементарні кон’юнкції), в яких менше за n співмножників.
2. Кожний з цих доданків помножити на співмножник
(
i
i
x
x

), який дорівнює одиниці, де
i
x – відсутня в доданку змінна.
3. Повторювати п.2, доки всі доданки не задовольнятимуть умові наявності
n
співмножників.
Цей принцип отримання ДДНФ застосовний тільки до формул, які мають вигляд ДНФ.

Ще один спосіб «розгортання»,
виходячи з табличного представлення
Він містить кроки:
1. Побудова таблиці істинності функції
)
,...,
,
(
2 1
n
x
x
x
f
;
2. Для кожного набору значень аргументів (кортежу), на якому
1
)
,...,
,
(
2 1

n
x
x
x
f
, в ДДНФ додається елементарна кон’юнкція
n
x
x
x

,...,

,

2 1
, де







,...,
2
,
1
,
0
кортежі
в якщо
,
;
1
кортежі
в якщо
,

n
і
х
x
х
x
x
і
i
і
i
i
Тобто ДДНФ має стільки доданків у вигляді елементарних кон’юнкцій, скільки одиниць є в стовпці функції.

Спосіб «розгортання», виходячи з
табличного представлення. Приклад
Повернемось до розглянутої нами функції
3 0
3 2
1 0
3 2
0 3
2 1
0
)
,
,
,
(
x
x
x
x
x
x
x
x
x
x
x
x
x
f



Побудуємо її таблицю істинності (табл.1.21).
Таблиця 1.21
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x
3 2
1 0
x
x
x
x
3 2
0
x
x
x
f
1
2
3
4
5
6
7
8
9
10
11
0 0 0
0 1 1 1
0 0
0 0
0 0 0
1 1 1 0
0 0
0 0
0 0 1
0 1 0 1
0 0
0 0
0 0 1
1 1 0 0
0 0
0 0
0 1 0
0 0 1 1
0 0
0 0

Спосіб «розгортання», виходячи з
табличного представлення. Приклад
(Продовження)Таблиця 1.21
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x
3 2
1 0
x
x
x
x
3 2
0
x
x
x
f
1
2
3
4
5
6
7
8
9
10
11
0 1 0
1 0 1 0
0 0
0 0
0 1 1
0 0 0 1
0 0
0 0
0 1 1
1 0 0 0
0 0
0 0
1 0 0
0 1 1 1
0 0
0 0
1 0 0
1 1 1 0
0 1
1 1

Спосіб «розгортання», виходячи з
табличного представлення. Приклад
(Продовження)Таблиця 1.21
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x
3 2
1 0
x
x
x
x
3 2
0
x
x
x
f
1
2
3
4
5
6
7
8
9
10
11
1 0 1
0 1 0 1
1 0
0 1
1 0 1
1 1 0 0
0 0
1 1
1 1 0
0 0 1 1
0 0
0 0
1 1 0
1 0 1 0
0 0
1 1
1 1 1
0 0 0 1
1 0
0 1

Спосіб «розгортання», виходячи з
табличного представлення. Приклад
Будуємо ДДНФ за «одиницями» в стовпці функції
(останньому стовпці). Це кортежі з номерами 0, 10, 11, 13,
14, 15(винесені в табл. 1.21_1)
Таблиця 1.21_1
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x
3 2
1 0
x
x
x
x
3 2
0
x
x
x
f
1
2
3
4
5
6
7
8
9
10
11
1 0 0
1 1
1 0
0 1
1 1
1 0 1
0 1
0 1
1 0
0 1
1 0 1
1 1
0 0
0 0
1 1
1 1 0
1 0
1 0
0 0
1 1
1 1 1
0 0
0 1
1 0
0 1
1 1 1
1 0
0 0
0 0
1 1

Спосіб «розгортання», виходячи з
табличного представлення. Приклад
Таблиця 1.21_1
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x
3 2
1 0
x
x
x
x
3 2
0
x
x
x
f
1
2
3
4
5
6
7
8
9
10
11
1 0 0
1 1
1 0
0 1
1 1
1 0 1
0 1
0 1
1 0
0 1
1 0 1
1 1
0 0
0 0
1 1
1 1 0
1 0
1 0
0 0
1 1
1 1 1
0 0
0 1
1 0
0 1
1 1 1
1 0
0 0
0 0
1 1
Отримуємо:
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
)
,
,
,
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f






Вона збігається з отриманою раніше в прикладі.

Елементарна диз’юнкція
Означення 1.19. Логічна сума будь-якої кількості
різних незалежних змінних, що входять із запереченням або
без нього, називається елементарною диз’юнкцією.
Звідси випливає, що
)
(
3 2
0
x
x
x


,
)
(
3 2
1 0
x
x
x
x



й
)
(
0 1
0
x
x
x


– елементарні диз’юнкції.
Аналогічно до попереднього
r
x
x
x
F




2 1
- елементарна диз’юнкція рангу
r

Кон’юктивна нормальна форма
Означення 1.20. Якщо яку-небудь функцію задано
формулою у вигляді кон’юнкції елементарних диз’юнкцій,
то функцію задано її кон’юктивною нормальною формою
(КНФ).
Наприклад КНФ функції:
).
)(
)(
(
)
,
,
,
(
3 0
3 2
1 0
3 2
0 3
2 1
0
x
x
x
x
x
x
x
x
x
x
x
x
x
f







Будь-яка логічна функція, за виключенням рівної константі 1, може бути задана і своєю довершеною
кон’юктивною нормальною формою (ДКНФ).

Довершена кон’юктивна нормальна
форма
Означення 1.21. ДКНФ логічної функції називається
її КНФ, що задовольняє такі умови:
1) в ній немає двох однакових співмножників;
2) жоден зі співмножників не містить двох однакових
доданків;
3) жоден зі співмножників не містить якої-небудь
змінної разом з її запереченням;
4) кожен співмножник містить як складову
i
x
або
i
x
для будь-якого
n
i
,
,
2
,
1


.

Довершена кон’юктивна нормальна
форма
Все сказане стосовно ДДНФ можна аналогічно застосувати і для ДКНФ.
Будь-яка логічна функція має єдину ДКНФ.
Цю ДКНФ можна отримати двома способами:

способом „розгортання”;

за допомогою таблиць істинності.

Спосіб «розгортання» КНФ деякої
функції до вигляду ДКНФ
Він полягає в наступному:
1.
Виділити всі співмножники
(елементарні диз’юнкції), в яких менше за n доданків.
2. До кожного з цих співмножників додати доданок
i
i
x
x
, який дорівнює нулю і не змінює значення початкового співмножника, де
i
x – відсутня в початковому співмножнику змінна.
3. Повторювати п.2, поки всі співмножники не задовольнятимуть умову наявності n доданків.
Підкреслимо, що цей спосіб отримання ДКНФ застосовний тільки до формул, які мають вигляд КНФ.

Спосіб «розгортання» КНФ деякої
функції до вигляду ДКНФ. Приклад

































































)
)(
)(
)(
(
)
(
)
)(
(
)
)(
)(
(
)
)(
)(
(
)
0
)(
)(
0
(
)
)(
)(
(
)
,
,
,
(
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
2 2
3 1
0 2
2 3
1 0
3 2
1 0
3 2
1 0
3 2
1 0
1 1
3 0
3 2
1 0
1 1
3 2
0 3
0 3
2 1
0 3
2 0
3 0
3 2
1 0
3 2
0 3
2 1
0
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
).
)(
(
3 2
1 0
3 2
1 0
x
x
x
x
x
x
x
x








Спосіб «розгортання» за табличним
поданням функції
Він містить такі кроки:
1. побудова таблиці істинності
)
,...,
,
(
2 1
n
x
x
x
f
;
2. для кожного набору значень аргументів (кортежу), на якому
0
)
,...,
,
(
2 1

n
x
x
x
f
в ДКНФ додається елементарна диз’юнкція вигляду:
n
x
x
x



2 1



, де







,
,
2
,
1
;
1
кортежі
в якщо
,
;
0
кортежі
в якщо
,

n
i
x
x
x
x
x
i
i
i
i
i


Спосіб «розгортання» за табличним
поданням функції. Приклад
Розглянемо ту саму функцію, що і в попередньому прикладі
Побудуємо її таблицю істинності (табл.1.22)
Таблиця 1.22
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x


3 2
1 0
x
x
x
x



3 0
x
x

)
,
,
,
(
3 2
1 0
x
x
x
x
f
0 0
0 0
1 1
1 1
1 0
0 0
0 0
1 1
1 0
0 1
1 0
0 0
1 0
1 0
1 1
1 0
0 0
0 1
1 1
0 0
1 1
1 1
0 1
0 0
0 1
1 1
1 0
0 0
1 0
1 0
1 0
0 1
1 0
0 1
1 0
0 0
1 1
1 0
0 0
1 1
1 0
0 0
1 0
1 0

Спосіб «розгортання» за табличним
поданням функції. Приклад
(Продовження) Таблиця 1.22
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x


3 2
1 0
x
x
x
x



3 0
x
x

)
,
,
,
(
3 2
1 0
x
x
x
x
f
1 0
0 0
1 1
1 1
1 1
1 1
0 0
1 1
1 0
1 1
1 1
1 0
1 0
1 0
1 1
1 1
1 1
0 1
1 1
0 0
1 1
1 1
1 1
0 0
0 1
1 1
1 1
1 1
1 0
1 0
1 0
1 1
1 1
1 1
1 0
0 0
1 1
1 1
1 1
1 1
1 0
0 0
1 1
1 1

Спосіб «розгортання» за табличним
поданням функції. Приклад
Будуємо ДКНФ за „нулями” функції(табл.1.22_1):
).
)(
)(
)(
(
)
)(
)(
(
)
,
,
,
(
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
3 2
1 0
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
























Таблиця 1.22_1
0
x
1
x
2
x
3
x
1
x
2
x
3
x
3 2
0
x
x
x


3 2
1 0
x
x
x
x



3 0
x
x

)
,
,
,
(
3 2
1 0
x
x
x
x
f
0 0
0 0
1 1
1 1
1 0
0 0
0 0
1 1
1 0
0 1
1 0
0 0
1 0
1 0
1 1
1 0
0 0
1 0
0 0
1 1
1 1
0 0
0 1
0 1
0 1
0 0
1 1
0 0
1 1
0 0
0 1
1 1
0 0
0 1
1 1
0 0
0 1
0 1
0

5. Спрощення формул

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

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

Операції повного склеювання та
поглинання
Операція повного склеювання:
x
y
y
x
y
x
xy




)
(
, де два члени xy і
y
x
склеюються за змінною y .
Операція поглинання:
x
y
x
xy
x




)
1
(
, член xy поглинається членом x .

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

Метод Квайна. 1 етап. Початкове
скорочення формули.
Цей етап містить три кроки:
1. Провести в ДДНФ функції
)
,...,
,
(
2 1
n
x
x
x
f
всі можливі операції попарного склеювання за однією змінною
її доданків. У результаті утворяться добутки – кон’юнкції
)
1
(

n
-го рангу. Після цього виконати операції поглинання.
2. Провести можливі склеювання членів
)
1
(

n
-го рангу, потім поглинання. Утворяться кон’юнкції
)
2
(

n
-го рангу.
3. Виконати операції склеювання членів
)
2
(

n
-го рангу, одержати кон’юнкції
)
3
(

n
-го рангу і т.д.