Список літератури. 2. Новиков Ф.А. Дискретная математика для программистов

Основна

1. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.116-137.

2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.88-91.

3. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.504-522.

Додаткова

4. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. - С.19-23.

5. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.47-50.

Для практичних занять

6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.25-27.

7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.20-38.

Лекція 24. Булева алгебра. Спрощення. Подвійність

Вступ

Лекція має за мету навести основні поняття булевої алгебри. Розглянути шістнадцять властивостей операцій булевого базису {Ù, Ú, ù}, спрощення запису формул, подвійність формул булевої алгебри, подвійні і самоподвійні функції. Звернено увагу до булевої алгебри множин і булевої алгебри двійкових векторів, уведено поняття ізоморфних алгебр.

У лекції присутні чотири підрозділи:

24.1. Булева алгебра

24.2. Спрощення запису формул

24.3. Подвійність формул булевої алгебри

24.4. Булева алгебра множин

24.1. Булева алгебра

Нехай задана деяка множина М и набір операцій Ф, що виконуються на цій множини Ф = {j₁, j₂,..., j_n}, тоді двійка множин А = (М, Ф) називається алгеброю. Множина М називається основною, чи несучою множиною. Множина Ф називається сигнатурою операцій, чи просто сигнатурою.

Визначення. Булевою алгеброю В = (М, {Ú, Ù, ù} 0, 1) називається множина М с двома бінарними операціями “Ú” і “Ù”, однією унарною операцією інверсії “ù” у сигнатурі і двома відзначеними елементами (універсальними границями) “0” і “1”, причому для будь-яких x₁, x₂, x₃, що належать множині M, набір операцій відповідає наступним тотожностям.

Основні тотожності булевої алгебри

1. x₁Ùx₂=x₂Ùx₁; x₁Úx₂=x₂Úx₁;
комутативність

2. x₁Ù(x₂Ùx₃)=(x₁Ùx₂)Ùx₃; x₁Ú(x₂Úx₃)=(x₁Úx₂)Úx₃;
асоціативність

3. x₁Ù(x₂Úx₃)=(x₁Ùx₂)Ú(x₁Ùx₃); x₁Ú(x₂Ùx₃)=(x₁Úx₂)Ù(x₁Úx₃);
дистрибутивність;

4. x₁Ù0=0; x₁Ú0=x₁;
x₁Ù1=x₁; x₁Ú1=1;
`0=1; `1=0;

універсальні границі;

5. x₁Ùx₁=x₁; x₁Úx₁=x₁;
ідемпотентність;

6. x₁Ù`x<sub>1</sub>=0; x<sub>1</sub>Ú`x₁=1;
ù(`x)=x;
доповнення і інволютивність

7. x₁Ù(x₁Úx₂)=x₁; x₁Ú(x₁Ùx₂)=x₁;
поглинання;

8. (x₁Ùx₂)Ú(x₁Ù`x<sub>2</sub>)=x<sub>1</sub>; (x<sub>1</sub>Ùx<sub>2</sub>)Ú(x<sub>1</sub>Ù`x₂)=x₁;
Блейка-Порецького;

9. x₁Ù(`x<sub>1</sub>Úx<sub>2</sub>)=x<sub>1</sub>Ùx<sub>2</sub>; x<sub>1</sub>Ú(`x₁Ùx₂)=x₁Úx₂;
(x₁Ùx₃)Ú(x₂Ù`x<sub>3</sub>)= (x<sub>1</sub>Úx<sub>3</sub>)Ù(x<sub>2</sub>Ú`x₃)=
=(x₁Ùx₃)Ú(x₂Ù`x<sub>3</sub>)Ú(x<sub>1</sub>Ùx<sub>2</sub>); =(x<sub>1</sub>Úx<sub>3</sub>)Ù(x<sub>2</sub>Ú`x₃)Ù(x₁Úx₂);

склеювання;

10. ù(x₁Ùx₂)=`x<sub>1</sub>Ú`x₂; ù(x₁Úx₂)=`x<sub>1</sub>Ù`x₂;
де Моргана

Крім десяти основних тотожностей необхідно визначити теореми підстановки (11-14) і теореми розкладання (15, 16), що можуть скоріше привести до мінімальної формули.

11. x_i×f(x₁, x₂,..., x_i,`x_i,..., x_n)=x_i×f(x₁, x₂,..., 1, 0,..., x_n);

12. `x<sub>i</sub>×f(x<sub>1</sub>, x<sub>2</sub>,..., x<sub>i</sub>,`x_i,..., x_n)=`x_i×f(x₁, x₂,..., 0, 1,..., x_n);

13. x_iÚf(x₁, x₂,..., x_i,`x_i,..., x_n)=x_iÚf(x₁, x₂,..., 0, 1,..., x_n);

14. `x<sub>i</sub>Úf(x<sub>1</sub>, x<sub>2</sub>,..., x<sub>i</sub>,`x_i,..., x_n)=`x_iÚf(x₁, x₂,..., 1, 0,..., x_n)

15. f(x₁, x₂,…, x_i,…, x_n)=(x_i×f(x₁, x₂,…,1,…, x_n))Ú(`x_i f(x₁, x₂,…, 0,…, x_n));

16. f(x₁, x₂,…, x_i,…, x_n)=(x_iÚf(x₁, x₂,…, 0,…, x_n))×(`x_iÚf(x₁, x₂,…, 1,…, x_n))

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

Інший метод заснований на еквівалентних перетвореннях з використанням доведених раніше тотожностей булевої алгебри.

Приклад. а) идемпотентність (збереження ступеня):

хÚх=(хÚх)×1=(хÚх)(хÚ ` х)=хÚ(х× ` х)=хÚ0=х;

б) поглинання:

хÚх×у=(х×1)Ú(х×у)=х×(1Úy)=x 1=х

в) Блейка-Порецького:

хÚ ` х×у=(хÚ ` х)×(хÚу)=1×(хÚy)=хÚy

24.2. Спрощення запису формул

З таблиці булевих функцій від двох змінних можна побачити, що між функціями є залежність у_і=`y_15-i , де 0 £ і £ 15. На підставі цього можна записати співвідношення

для констант:
0=`1 і 1=`0;

для БФ від однієї змінної:
х= ù(`х);

для БФ від двох змінних:
х₁×х₂=ù(х₁/х₂);
х₁х₂=ù(` х<sub>1</sub>+х<sub>2</sub>);
х<sub>1</sub>Åх<sub>2</sub>=ù(х<sub>1</sub>~х<sub>2</sub>);
х<sub>1</sub>Úх<sub>2</sub>=ù(х<sub>1</sub>¯х<sub>2</sub>);
`х₁х₂=ù(х₁+х₂);
х₁®`х<sub>2</sub>=`х₁+`х<sub>2</sub>);
`х₁+х₂=ù(х₁х₂);
х₁~х₂=ù(х₁Åх₂);
х₁¯х₂=ù(х₁Úх₂);
х₁+х₂=ù(`х₁х₂).

З наведених залежностей випливає, що будь-яка функція двох змінних, включаючи і константи, виражається в аналітичному вигляді через сукупність із шести функцій, що містить заперечення і будь-які функції із зазначених пар {у₀, у₁₅}, {y₁, y₁₄}, {y₂, y₁₃}, {y₄, y₁₁}, {y₆, y₉},
{y₇, y₈} і що є надлишковою.

Легко довести, що

ù(х₁®х₂)=х₁`х₂;

ù(х₁~х₂)=(х₁Ú`х<sub>2</sub>)(`х₁Úх₂).

Сукупність можна скоротити до чотирьох функцій: “константи 0”, заперечення ²`х², диз'юнкції ²x₁Úx₂² і кон’юнкції ²х₁×х₂². Ці чотири функції також можуть бути скорочені – із законів де-Моргана і інволютивності (подвійного заперечення).

Таким чином, виконуються тотожності:

х₁Úх₂=ù(`х<sub>1</sub>×`х₂);

х₁×`х₁=0;

ù(х₁Ú`х₁)=0;

х₁×х₂=ù(`х<sub>1</sub>Ú`х₂).

Звідси випливає, що булеві функції виконуються через заперечення і кон’юнкцію чи заперечення і диз'юнкцію.

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

Приклад. (х₁Úх₂)Ú(х₃Úх₄)=х₁Úх₂Úх₃Úх₄

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

Приклад. ù (хÚу)×z=xÚy×z=(`x `y) z=`x `y z.

24.3. Подвійність формул булевої алгебри

У булевій алгебрі має місце принцип подвійності. Взаємно подвійними операціями є диз'юнкція і кон'юнкція. Заміняючи в деякій формулі кожну операцію на подвійну їй, одержуємо подвійну формулу.

Приклад. Формула (х₁Úх₂)×(х₃Úх₄)
Подвійна формула (х₁×х₂)Ú(х₃Úх₄).

Визначення. Таблиця істинності подвійної функції f^Ú виходить заміною значень змінних і значень самої функції f у таблиці істинності вихідної функції f на протилежні, тобто 0®1, 1®0.

Приклад. х₁ х₂ f=x₁Úx₂ x₁ x₂ f^Ú =x₁×x₂

0 0 0 1 1 1

0 1 1 1 0 0

1 0 0 0 1 0

1 1 1 0 0 0

Залишається тільки перевернути отриману таблицю для зростання значень аргументів зверху вниз.

X₁ x₂ f^Ú =x₁×x₂

0 0 0

0 1 0

1 0 0

1 1 1

Формула чи функція, рівносильна своїй подвійній функції, називається самоподвійною.

Приклад. у₁=х₁×х₂Úх₁×х₃Úх₂×х₃ та y₂=(х₁Úх₂)×(х₁Úх₃)×(х₂Úх₃) – подвійні і рівносильні функції, тобто y=у₁=у₂ – самоподвійна функція.

Теорема. Якщо формули f₁ чи f₂ рівносильні, то і подвійні їм формули f₁^Ú і f₂^Ú також рівносильні, і навпаки.

f₁=f₂Ûf₁^Ú=f₂^Ú

Приклад. хÚ(хÙу)=х Û хÙ(хÚу)=х
хÚ(`хÙу)=хÚу Û хÙ(`хÚу)=хÙу.

Теорема. (принцип подвійності): Якщо в булевій формулі f замінити кон'юнкції на диз’юнкції, «0» на «1», «1» на «0», то одержимо формулу f^Ú, подвійну вихідної.

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

24.4. Булева алгебра множин

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

Нехай задана деяка множина М.

Визначення. Алгебра А=(В(М), {È, Ç,ù} називається булевою алгеброю множин над множиною М, тип булевої алгебри множин - (2, 2, 1).

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

Нехай визначена взаємно однозначна відповідність між множиною В(М), де М={m₁, m₂,..., m_n} і множиною двійкових векторів Вn
розмірності n: G: В(М)ÛВn

Підмножині М¢ÍМ відповідає двійковий вектор b=(b₁,b₂,.., b_n), де b_i=1, якщо m_iÎM¢, і b_i = 0, якщо m_iÏM¢ для деякого m_iÎM.

Нехай на множини двійкових векторів Вn визначена булева алгебра вигляду: А¢=(Вn,{Ú, Ù, ù}, при цьому операції для будь-яких векторів s=<s₁, s₂,..., s_n> і t=<t₁, t₂,..., t_n> визначаються в такий спосіб:

1. sÚt=<s₁Út₁, s₂Út₂,..., s_nÚt_n>

2. sÙt=<s₁Ùt₁, s₂Ùt₂,..., s_n Ùt_n>

3. `s=<`s₁,`s<sub>2</sub>,..., `s_n>.

Операції над векторами s і t називаються порозрядними логічними операціями над двійковими векторами.

Приклад. s=10110; t=00101;

sÚt=10111; ` s=01001;

sÙt=00100; ` t=11010.

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

Ця алгебра ізоморфна булевій алгебрі множин, це дозволяє замінити теоретико-множинні операції об'єднання, перетинання, доповнення над системами множин порозрядними логічними операціями над двійковими векторами, реалізованими на ЕОМ: G: АÞA¢, G^-1: А¢ÞA.

Приклад. М={m₁, m₂, m₃, m₄}; M₁={m₁, m₂, m₃}; M₂={m₂, m₃, m₄};

ù M₁={m₄}; ù M₂={m₁}; M₁ÇM₂={m₂, m₃}; M₁ÈM₂=
={m₁, m₂; m₃, m₄};

AÞA¢:

M₁Þb₁=<1, 1, 1, 0>; M₂Þb₂=<0, 1, 1, 1>;

ù M₁Þù b₁=<0, 0, 0, 1>; ù M₂Þù b₂=<1, 0, 0, 0>;

M₁ÇM₂Þb₁Ùb₂=<0, 1, 1, 0>; M₁ÈM₂Þb₁Úb₂=<1, 1, 1, 1>.

Контрольні запитання

1. Що називається булевою алгеброю, основною множиною та сигнатурою булевої алгебри?

2. Які десять основних тотожностей існують?

3. Які шість теорем розкладення і підстановки існують?

4. Як доказати тотожність булевих формул на підставі таблиць істинності?

5. Як доказати тотожність булевих формул на підставі еквівалентних перетворень?

6. Які еквівалентні дії для функцій від двох змінних можна виконувати при спрощенні булевих формул?

7. Які булеві функції є подвійними, яка різниця між подвійними та самоподвійними булевими функціями?

8. У чому полягає принцип подвійності?

9. Чому можна казати, що алгебра множин є булевою, що необхідно для булевої алгебри?

10. Що є булевою алгеброю двійкових векторів?

11. Які алгебри можна назвати ізоморфними?