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

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

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

Мета лекції
Отримання знань щодо алгебри логіки

Питання, що будуть розглянуті
1.
Логічні (булеві) функції.
2.
Алгебра логіки.
3.
Повні набори функцій
4.
Канонічні форми булевих функцій.
5.
Спрощення формул. Утворення скороченої ДНФ
методом Квайна

1.
Логічні (булеві) функції

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

Вступ до алгебри логіки
Математична логіка
є
сучасний вид формальної
логіки,
науки,
що вивчає
умовиводи з
точки зору
їхнього формального створення
Основи математичної
логіки закладено в
таких працях англійського математика
Джорджа
Буля
(1815
–
1864) як
«Математичний аналіз логіки»
(1847)
і
«Закони мислення»
(1854), де він уперше виклав алгебру логіки
–
алгебру
Буля

Логічні (булеві) змінні
Означення 1.1. Логічними (булевими) змінними в
булевій алгебрі називають величини, які
незалежно від їхньої конкретної суті можуть
набувати лише двох значень.

Логічні (булеві) змінні
Ці значення
будемо позначати
нулем (0) й
одиницею (1),
маючи на увазі, що 0 і 1
це
формальні символи, що не мають
арифметичного змісту
, а зображують будь
-
які
змінні, що набувають лише двох значень,
наприклад „ТАК” і „НІ”, „ІСТИННО” (І) –
„ХИБНО” (Х)
і т.д.
Якщо змінна має одиничне значення, то записуємо
x=1
, а якщо нульове, то
x=0.

Булева функція
Як у звичайній алгебрі будуються функції від
дійсних чисел, так і від булевих змінних можна будувати
функції.
Означення 1.2.
Булевою, або логічною, функцією
називають функцію
)
,
,
,
(
2 1
n
x
x
x
f

, яка, як і її
n
аргументів, може набувати лише двох значень: 0 або 1.

Сфери застосування булевих функцій
●
В обчислювальній техніці булеві функції
застосовуються для:
■
опису алгоритмів,
■
засобів цієї техніки
–
дискретних пристроїв, які
призначаються для перетворення дискретної інформації,
що розкладається на елементарні одиниці –
біти, які в
пристроях реалізуються сигналами, що описуються
двійковими змінними –
булевими.
●
Для вирішення деяких економічних задач
●
Для вирішення задач цілочисельного
програмування

Кортеж
Означення 1.3. Сукупність значень аргументів
)
,...,
,
(
2 1
n
x
x
x
називається кортежем або набором.
Функція
)
,...,
,
(
2 1
n
x
x
x
f
, що залежить від
n
аргументів,
називається n -місною і є повністю визначеною, якщо
задано її значення для всіх наборів
)
,...,
,
(
2 1
n
x
x
x
(кортежів)
значень аргументів.

Терм
Кожному кортежу можна поставити у відповідність терм - довільний елементарний добуток двійкових змінних
m
m
x
x
x
x
t

1 2
1


. Якщо в кортежі
1

j
x
, то в термі замість
j
x записується змінна
j
x , а якщо
0

j
x
, то
j
x .

Терм.Приклад
Терму
5 4
3 2
1
x
x
x
x
x
відповідає кортеж, в якому
1
,
1
,
0
,
0
,
1 5
4 3
2 1





x
x
x
x
x

Терм. Додаткова інформація
Будь-яке ціле невід’ємне число можна записати у вигляді суми
0 1
1 2
2 1
1
r
g
r
g
r
g
r
g
N
n
n
n
n









, де r – основа системи числення;
i
g
– співмножник, що набуває значень від 0 до
1

r
(
n
i
,...,
2
,
1

).
Кількість доданків визначається розрядністю чисел.

Терм. Додаткова інформація
Кортеж значень аргументів логічної функції можна розглядати як запис цілого додатного числа у двійковій системі числення (
2

r
); тоді
0
x
– розряд одиниць,
1
x
– розряд двійок,
2
x
– розряд четвірок.
0 1
2 2
10 2
1 1
0 2
1 101 5







0 1
2 3
2 10 2
1 2
1 2
1 2
1 1111 15









0 1
2 3
4 2
10 2
0 2
0 2
0 2
0 2
1 10000 16












Терм. Додаткова інформація
0 1
2 2
10 2
1 1
0 2
1 101 5







0 1
2 3
2 10 2
1 2
1 2
1 2
1 1111 15









0 1
2 3
4 2
10 2
0 2
0 2
0 2
0 2
1 10000 16











Десятковий еквівалент двійкового подання числа називається номером кортежу. Таким чином, перше число має номер кортежу 5, друге – 15, а третє – 16.

Основні способи подання булевих
функцій

вербальний ( або словесний)– це словесний опис значень, яких набуває функція на певному кортежі змінних,

аналітичний–опис її аналітичним виразом
(формулою),

табличний–подання за допомогою таблиці відповідності (істинності).

Аналітичний спосіб. Приклад
c
b
a
abc
abc
f
x
x
x
x
x
x
x
x
f





)
(
);
(
,
)
,
,
(
2 1
3 2
2 1
3 2
1 1

Табличний спосіб. Приклад
В лівій частині Таблиці переписані всі можливі значення її аргументів
n
x
x
x
,
,
,
2 1

, тобто всі можливі кортежі, а правою частиною є стовпець значень функції, який відповідає цим наборам
Таблиця 1.1
1
x
2
x
)
, x
f(x
2 1
0 0
0 0
1 0
1 0
0 1
1 1

Набір функції
Означення 1.4. Набір значень змінних (кортеж), на
якому функція набуває значення
1
)
,
,
,
(
2 1

n
x
x
x
f

,
називається одиничним набором функції f , множина
усіх одиничних наборів, називається одиничною
множиною функції f .
Так
саме
набір
аргументів,
на
якому
0
)
,
,
,
(
2 1

n
x
x
x
f

, називається нульовим набором функції
f , а множина нульових наборів – нульовою множиною.

Булеві функції однієї змінної
Загальна таблиця істинності (відповідності) для булевих функцій однієї змінної має вигляд табл.1.2.
Виходячи з того, що на кожному з двох можливих значень змінної функція набуває одного з двох можливих значень, очевидно, що існують
4 2
2

різних булевих функцій від однієї булевої змінної. Всі вони наведені в табл.1.2.
Таблиця 1.2
x
(x)
f
y
1 1

(x)
f
y
2 2

(x)
f
y
3 3

(x)
f
y
4 4

0 1
0 1
0 1
1 0
0 1

Булеві функції однієї змінної
Таблиця 1.2
x
(x)
f
y
1 1

(x)
f
y
2 2

(x)
f
y
3 3

(x)
f
y
4 4

0 1
0 1
0 1
1 0
0 1
Функції
1
y
та
2
y
є функціями - константами:
)
(
1
x
f
– абсолютно істинна (константа одиниці);
)
(
2
x
f
– абсолютно хибна (константа нуль),
)
(
3
x
f
– логічне заперечення, або
НІ, або інверсія x (читається як «не x », зображається як
x
або x

), це єдина нетривіальна функція;
)
(
4
x
f
– змінна x
(повторює значення змінної x і тому збігається з нею).

Область визначення логічної функції
Областю визначення логічної (булевої) функції n аргументів є сукупність
n
2 булевих кортежів.
Це положення очевидне з погляду інтерпретації набору двійковим поданням n -розрядного числа (кількість додатних n -розрядних двійкових чисел дорівнює
n
2 ).

Область визначення логічної функції.
Приклад
Булева функція двох аргументів є повністю визначеною, якщо задано її значення в кожному з чотирьох можливих наборів (
4 2
2

), тобто на наборах 00, 01, 10, 11 або на кортежах з номерами 0, 1, 2, 3.
Булева функція трьох аргументів (
8 2
3

) у восьми наборах також буде повністю визначеною, тобто на кортежах з номерами 0, 1, 2, 3, 4, 5, 6, 7.
Булева функція n аргументів є повністю визначеною, якщо задано всі її значення в кожному з
n
2 наборів.

Кількість булевих функцій.
Можна довести, що число усіх функцій
)
,
,
,
(
2 1
n
x
x
x
f

, що залежать від n змінних
n
x
x
x
,
,
,
2 1

дорівнює
n
2 2 .
Всього булевих функцій від двох аргументів – 16, від трьох – 256, від чотирьох – 65536.

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

Елементарні функції алгебри логіки
Приклади елементарних функцій однієї змінної наведено в табл.1.2.
У табл.1.3. подано 16 функцій двох змінних, з яких шість
0 16

(a,b)
f
,
a
(a,b)
f

11
,
b
(a,b)
f

13
,
a
(a,b)
f

12
,
b
(a,b)
f

14
,
1 15

(a,b)
f
, є константами або функціями одного аргументу.
Інші 10 функцій залежать від двох аргументів і мають свої загальноприйняті позначення та назви, зазначені в табл.1.3.

Функції двох змінних
Таблиця 1.3
а
0 0
1 1
b
Позначення функції
Найменування функції
0 1
0 1
b
a
ab
b
a
f
&
1




Кон’юнкція (логічне множення)
0 0
0 1
b
a
b
a
f




2
Диз’юнкція (логічне додавання)0 0
1 1
1
b
a
f


3
Імплікація (від a до b)
1 1
0 1
b
a
f


4
Обернена імплікація (від b до a )
1 0
1 1

Функції двох змінних
Таблиця 1.3
а
0 0
1 1
b
Позначення функції
Найменування функції
0 1
0 1
b
a
b
a
f




5
Рівносильність
1 0
0 1
b
a
b
a
f




6
Нерівносильність
(додавання за модулем 2)
0 1
1 0
b
a
b
a
f
|
7



Функція Шеффера (інверсія кон’юнкції)
1 1
1 0
b
a
b
a
f




8
Функція стрілка Пірса –
Вебба (інверсія диз’юнкції)
1 0
0 0

Функції двох змінних
Таблиця 1.3
а
0 0
1 1
b
Позначення функції
Найменування функції
0 1
0 1
b
a
f


9
Інверсія імплікації (функція заборони за b)
0 0
1 0
b
a
f


10
Інверсія оберненої
імплікації (функція заборони за a )
0 1
0 0
a
f

11
Повторення а (змінна a )
0 0
1 1
a
f

12
Інверсія а
1 1
0 0

Функції двох змінних
Таблиця 1.3
а
0 0
1 1
b
Позначення функції
Найменування функції
0 1
0 1
b
f

13
Повторення b (змінна b)
0 1
0 1
b
f

14
Інверсія b
1 0
1 0
1 15

f
Одинична функція
(константа 1)
1 1
1 1
0 16

f
Нульова функція
(константа 0)
0 0
0 0

Функція Шеффера (штрих Шеффера)
Функція Шеффера (штрих Шеффера) – це функція
)
,
(
7
b
a
f
, яка є хибною тоді і тільки тоді, коли a і b є
істинними.
Умовне позначення цієї функції
b
a
b
a
b
a
f



|
)
,
(
7
Німецький математик Д.Шеффер на основі цієї функції створив алгебру, названу алгеброю Шеффера.
Функція
)
,
(
7
b
a
f
є універсальною (або складає повну систему функцій), тобто функцією, за допомогою якої можна представити будь-яку логічну функцію двох змінних.

Функція (стрілка) Пірса
-
Вебба
Функція стрілка Пірса-Вебба – це функція
)
,
(
8
b
a
f
, що є істинною тоді і тільки тоді, коли a і b є хибними.
Умовне позначення цієї функції
b
a
b
a
f


)
,
(
8
Математики Ч.Пірс та Д.Вебб, які незалежно один від одного вивчали властивості цієї функції, створили алгебру, названу алгеброю Пірса – Вебба.
Функція
)
,
(
8
b
a
f
також є універсальною.

2. Алгебра логіки

Поняття формули в алгебрі логіки
Як і в алгебрі висловлень, так і в алгебрі логіки, виходячи з елементарних функцій, можна будувати формули.
Літери, якими позначаються булеві змінні, позначки логічних операцій та дужки складають алфавіт алгебри логіки. За допомогою елементів алфавіту можна будувати формули алгебри логіки.

Поняття формули в алгебрі логіки
Означення 1.5. Вираз, який складається з літер
булевих змінних, позначок логічних операцій та дужок є
формулою алгебри логіки, якщо він задовольняє наступним
умовам:
1) Будь-яка логічна змінна
x
є формулою;
2) Якщо x і y - формули, то
))
((
)),
((
y
x
y
x


а
також x і y , які з’єднані будь-якою операцією з табл.1.3,
є формулою;
3) Інших формул немає.

Приклади формул в алгебрі логіки
Приклад 1.2. Такі вирази є формулами:

)
)
)
(((
2 1
2 1
x
x
x
x


,

))
(
(
3 1
1
x
x
x

,

)))
)(
((
(
2 3
3 2
1
x
x
x
x
x



, а ці вирази не є формулами:

xy
AB(
(
– незакриті дужки;

y
b


– відсутній символ булевої змінної;

y
x

– відсутній символ булевої змінної.

Приклади формул в алгебрі логіки