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

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

Приклад 1.3. Функція, яку реалізує формула
)
)
)
(((
2 1
2 1
1
x
x
x
x
F



будується за три кроки (табл.1.5):
1.
);
(
2 1
x
x
2.
);
)
((
1 2
1
x
x
x

3.
)
)
)
(((
1 2
1 2
1
F
x
x
x
x



Таблиця 1.5
1
x
2
x
2 1
x
x
1 2
1
)
(
x
x
x

)
)
)
(((
2 1
2 1
1
x
x
x
x
F



0 0
0 0
0 0
1 0
0 1
1 0
0 1
1 1
1 1
1 1

Зв’язок між функцією та формулою в
алгебрі логіки
Означення 1.6. Якщо формула
)
,
,
,
(
2 1
n
x
x
x
F

описує
функцію
)
,
,
,
(
2 1
n
x
x
x
f

, то кажуть, що формулі
)
,
,
,
(
2 1
n
x
x
x
F

відповідає функція
)
,
,
,
(
2 1
n
x
x
x
f

або
формулі
F
зіставлена функція f .
Якщо функція f відповідає формулі
F
, то кажуть також, що формула
F
реалізує функцію f

Зв’язок між функцією та формулою в
алгебрі логіки
Формула
ab
b
a
F

)
,
(
1
реалізує функцію
)
,
(
1
b
a
f
Це видно з табл.1.7 а.
Таблиця 1.7 а
a
b
ab
0 0
0 0
1 0
1 0
0 1
1 1

Зв’язок між функцією та формулою в
алгебрі логіки. Приклад
Формула
ab
b
a
F

)
,
(
1
реалізує функцію
)
,
(
1
b
a
f
. Це видно з табл.1.7 а. Таку ж таблицю істинності має й функція, яка відповідає формулі
)
)
)
(((
)
,
(
2
b
a
b
a
b
a
F


, тобто й формула
)
,
(
2
b
a
F
реалізує функцію
)
,
(
2
b
a
f
, (див. табл.1.7 б.).
Таблиця 1.7 а
Таблиця 1.7 б
a
b
ab
a
b
)
)
)
(((
b
a
ab
0 0
0 0
0 0
0 1
0 0
1 0
1 0
0 1
0 0
1 1
1 1
1 1

Рівносильні формули
Таким чином, різні формули можуть реалізувати одну й ту ж саму функцію. Більш того, таких формул чимала кількість.
Адже, наприклад, всього функцій від двох змінних
існує 16, а формул, які їм відповідають, велика кількість.
Проте, всі формули, які відповідають одній і тій самій функції, мають одну і ту саму таблицю істинності.
Про такі формули кажуть, що вони рівносильні.

Еквівалентність формул
Означення 1.7. Формули
)
,
,
,
(
2 1
1
n
x
x
x
F

та
)
,
,
,
(
2 1
2
n
x
x
x
F

називаються еквівалентними (або
тотожними, або рівносильними), якщо є рівними
функції
1
f
та
2
f
, що реалізовані відповідно формулами
1
F і
2
F , тобто
2 1
f
f

. Тоді запис
2 1
F
F

означає, що
1
F
й
2
F
– еквівалентні формули.

Закони булевої алгебри
Закони булевої алгебри аналогічні законам алгебри
висловлень.

Універсальність функції Шефера
Функція Шеффера – це функція, що може бути виражена співвідношенням
2 1
2 1
|
x
x
x
x

Для цієї функції справджуються такі властивості:
1.
x
x
x

|
;
3.
1
|

x
x
;
5.
1 0
|

x
;
2.
x
x

1
|
;
4.
1 0
|

x
;
6.
x
x

1
|

Універсальність функції Шефера
Для функції Шеффера справджується тільки властивість комутативності
1 2
2 1
|
|
x
x
x
x

і не справджується властивість асоціативності:
3 2
1 3
2 1
|
)
|
(
)
|
(
|
x
x
x
x
x
x


Універсальність функції Шефера
З основних властивостей функції Шеффера можна дістати такі формули перетворення:












)
|
(
|
)
|
(
|
|
)
|
(
|
)
|
(
|
2 2
1 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x

Універсальність функції стрілки
Пірса
-
Вебба

Універсальність функції стрілки
Пірса
-
Вебба
На підставі цих аксіом можна встановити, що для функції стрілка Пірса-Вебба справджується тільки властивість комутативності:
1 2
2 1
x
x
x
x




Універсальність функції стрілки
Пірса
-
Вебба
Функції І, АБО, НІ виражаються через функцію стрілка Пірса-Вебба таким чином:
















);
(
)
(
);
(
)
(
2 1
2 1
2 1
2 2
1 1
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x

3. Повні набори функцій

Повні набори функцій
Як видно з вищенаведеного, одна й теж сама логічна функція може бути задана декількома формулами, які містять різні набори логічних операцій.
Існують набори логічних функцій, за допомогою яких можна виразити будь-яку іншу функцію алгебри логіки .
Такі набори (системи) називаються повними
системами функцій алгебри логіки, або базисами.

Повні набори функцій
Означення
1.12.
Система
булевих
функцій
називається функціонально повною, якщо будь-яка булева
функція може бути записана у вигляді формули через
функції цієї системи.
Як приклад повної системи, можна навести систему, яку складають всі булеві функції. Кількість функцій –
n
2 2
Так, усі 16 функцій двох змінних утворюють повну систему.
Повні набори (системи) функцій характеризуються певним набором властивостей функцій, які є її складовими.

Повні набори функцій
Твердження :
Будь-яка функція алгебри логіки може бути задана формулою за допомогою диз’юнкції та заперечення, або кон’юнкції та заперечення, причому в будь-якому випадку необхідні дві операції.

Повні набори функцій
Таким чином, для доведення функціональної повноти будь-якої системи функцій достатньо показати, як можна виразити за допомогою функцій цієї системи.

Повні набори функцій
Система, яка складається із однієї операції штрих
Шиффера є повною.
Система, яка складається із однієї операції стрілка Пірса є повною.

4. Канонічні форми булевих функцій

Тотожно істинна формула
Означення 1.13. Формула називається тотожно
істинною, якщо вона при всіх значеннях змінних, що
входять у неї, набуває значення 1.
Приклади тотожно істинних формул:
)
(
)
,
(
);
(
)
,
(
;
)
(
3 2
1
y
y
x
x
y
x
F
x
y
x
y
x
F
x
x
x
F









Тотожно хибна та здійсненна формули
Означення 1.14. Формула називається тотожно
хибною, якщо вона при всіх значеннях змінних, що входять
у неї, набуває значення 0.
Приклади тотожно хибної формули є
x
x
x
F

)
(
Означення 1.15. Формула називається здійсненною
(нейтральною), якщо вона не є тотожно істинною або
тотожно хибною.

Проблема розв’язуваності
Проблема розв’язуваності: задати єдиний спосіб
(алгоритм), який дає змогу для кожної формули з’ясувати, чи є вона здійсненною, тобто чи не є вона тотожною 0 або
1.

Проблема розв’язуваності
Нехай формула
)
,
,
,
(
2 1
n
x
x
x
F

, що виражає деяку функцію n змінних
n
x
x
x
,
,
,
2 1

При цьому як змінні
n
x
x
x
,
,
,
2 1

так і функція
F
можуть набувати лише двох значень, число ж можливих комбінацій значень змінних є скінченим і дорівнює
n
2
Для кожної такої комбінації можна визначити значення формули
F
Знаючи ці її значення для кожної комбінації змінних
n
x
x
x
,
,
,
2 1

можна встановити, здійсненна чи ні функція.

Проблема розв’язуваності
Викладений спосіб, дає принципове вирішення проблеми розв’язуваності, але при великій кількості
змінних він практично нездійсненний через величезне число можливих наборів значень змінних.
Існує інший спосіб, що ґрунтується на зведенні
формул до нормальної форми. Якщо у процесі такого зведення формула не перетворюється на тотожні 0 або 1, то це свідчить про її здійсненність.

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

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

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

Диз’юнктивна нормальна форма
Будь-яку логічну функцію можна представити у вигляді ДНФ, тому що ДНФ утворюється за допомогою системи операцій
}
,
,
{



, яка є повною.
Будь-яка логічна функція має не єдину ДНФ.

Диз’юнктивна нормальна форма.
Приклад
Розглянемо вище наведену формулу і застосуємо закон дистрибутивності кон’юнкції відносно диз’юнкції, але справа наліво, тобто
)
(
c
b
a
ac
ab



. Отримаємо:
3 0
3 2
0 2
1 3
0 3
2 0
3 0
3 2
1 0
3 2
0 3
2 1
0 2
)
1
(
)
,
,
,
(
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









Ми отримали ще одну ДНФ функції
)
(x
f
, яка є коротшою за попередню.

Диз’юнктивна нормальна форма.
Приклад
Можна отримати і інші ДНФ тієї самої функції f :
1 1
3 1
0 3
1 0
3 2
1 0
3 2
1 0
1 1
1 1
3 0
1 1
3 2
0 3
0 3
2 0
3 0
3 2
0 3
2 1
0 2
)
(
)
(
0 1
1
)
,
,
,
(
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



















Це ще одна ДНФ однієї і тієї самої функції. Цей процес можна продовжувати.

Диз’юнктивна нормальна форма
Як бачимо, для будь-якої логічної функції можна утворити велику кількість формул у вигляді ДНФ.
Але є така ДНФ, яка єдина для будь-якої логічної функції.

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

Досконала диз’юнктивна нормальна
форма
Будь-яка логічна функція, за виключенням константи «0», має одну ДДНФ і кілька ДНФ.
Будь-яка ДНФ утворюється внаслідок більшого або меншого скорочення ДДНФ, причому від будь-якої ДНФ
можна перейти до ДДНФ.
Такий перехід називається «розгортанням».

Досконала диз’юнктивна нормальна
форма. Приклад
Отримаємо ДДНФ розглянутої функції:







3 2
1 0
1 1
3 2
0 3
0 3
2 1
0 3
2 0
3 2
1 0
4
)
(
)
,
,
,
(
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
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
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
3 1
0 3
1 0
3 2
1 0
3 2
1 0
3 2
1 0
1 1
3 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
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x






























