ДМ_МУ_САМ РАБ

2. Що називається порядком операції? Наведіть приклади унарнох,

бінарної, n-арної операції.

3.Що називається оператором?

4.Що являють собою форми запису infix, prefix, postfix. Наведіть приклади. Чому форма запису infix менш зручна для автоматичної обробки?

5.Які операції можна та зручно задавати за допомогою таблиць?

6.Дайте визначення властивостей асоціативності, дистрибутивності та комутативності операцій. Наведіть приклади.

7.Дайте визначення алгебраїчної структури.

8.Що називається підструктурою алгебраїчної структури? Яким відношенням пов’язані множини-носії алгебраїчної структури та її підструктури? Наведіть приклади підструктур.

9.Дайте визначення гомоморфізму та ізоморфізму. Чим вони відрізняються?

10.Наведіть приклади ізоморфних алгебраїчних структур.

11.Дайте визначення півгрупи, моноїду і групи.

12.Наведіть приклади групи.

13.Яка група називається абелевою? Наведіть приклади.

4.4 Змістовий модуль 4 «Основи математичної логіки. Двійкова логіка. Булеві функції та перетворення»

4.4.1 Перелік тем змістовного модуля 4

Під час вивчення змістового модуля 4 розглядаються такі теми:

тема 1 «Булеві функції (основні поняття). Булева алгебра»;

тема 2 «Нормальні форми булевих функцій»;

тема 3 «Мінімізація булевих функцій»;

тема 4 «Алгебра Жегалкіна»;

тема 5 «Функціональна повнота наборів булевих функцій»;

тема 6 «Логічні схеми»;

тема 7 «Багатозначна логіка».

4.4.2 Тема 1 «Булеві функції (основні поняття). Булева алгебра»

Вивчення теми 1 «Булеві функції (основні поняття). Булева алгебра» пов’язане із розглядом таких питань [1-9, 13-16, 18-23]: булеві змінні та

31

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

принцип двоїстості; закони і тотожності булевої алгебри; еквівалентні перетворення формул булевої алгебри.

Основними поняттями і визначеннями теми «Булеві функції (основні поняття). Булева алгебра», які надаються в [1-9, 14-16, 20, 22], є: булеві змінні;

булеві функції; номери булевих функцій та інтерпретацій; інтерпретація булевої функції; n-мірний булевий куб; область визначення булевої функції;

таблиця істинності (відповідності) булевої функції; заперечення, кон’юнкція, диз’юнкція, еквіваленція, імплікація, стрілка Пірса, штрих Шеффера; булева формула; суперпозиція булевих функцій; пріоритет операцій булевої алгебри; інфіксний запис формул; еквівалентні формули та перетворення булевих функцій; двоїста функція; самодвоїста функція; принцип двоїстості; двохелементна булева алгебра; алгебра логіки; еквівалентні (рівносильні)

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

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

1.Які змінні називаються булевими або логічними змінними?

2.Яка функція називається логічною (булевою, перемикальною)?

3.Наведіть приклади завдання (використання) булевих змінних у мовах програмування.

4.Як називається сукупність конкретних значень аргументів булевої

функції?

5.Скільки елементів-слів містить n-мірний булевий куб?

6.Що являє собою область визначення та область значень булевої

функції?

7.Як визначити число всіх булевих функцій, що залежать від n

змінних?

8.Перелічить способи задання булевих функцій.

9.Що являє собою таблиця істинності (відповідності) булевої функції. Назвіть правила її побудови.

10.Перелічить булеві функції від однієї змінної, від двох змінних.

11.Яким чином визначається номер булевої функції? Як визначається номер інтерпретації?

32

12.Дайте визначення формули для задання булевої функції. Що таке суперпозиція булевих функцій?

13.Які знаки використовуються при побудові формул? Який пріоритет визначений для операцій алгебри логіки?

14.Який запис формул називається інфіксним? Наведіть приклади.

15.Чим відрізняється табличний і формульний спосіб задання булевих функцій? У яких випадках застосовується кожний з них?

16.Які формули називаються рівносильними або еквівалентними?

17.Перелічить основні методи визначення рівносильності формул.

18.Надайте визначення двоїстої і самодвоїстої функції.

19.Яким чином формується таблиця істинності двоїстої функції?

20.Сформулюйте принцип двоїстості булевих функцій.

21.Надайте визначення двохелементної булевої алгебри та алгебри

логіки.

22.Перелічить основні закони булевої алгебри.

23.Яким способом можна довести закони булевої алгебри.

24.Сформулюйте і запишіть тотожності для законів булевої алгебри.

4.4.4 Тема 2 «Нормальні форми булевих функцій»

Вивчення теми 2 «Нормальні форми булевих функцій» пов’язане із розглядом таких питань [1-9, 13-16, 18-23]: основні поняття і визначення, які пов’язані з «нормальною формою» булевої функції; досконала диз’юнктивна і досконала кон’юнктивна нормальні форми (ДДНФ і ДКНФ) булевої функції;

теореми про диз’юнктивне і кон’юнктивне розкладання булевої функції за змінними; правила переходу від таблиць істинності булевої функції до ДДНФ і ДКНФ булевої функції; правила переходу від довільних формул булевої функції до ДДНФ і ДКНФ.

Основними поняттями і визначеннями теми «Нормальні форми булевих функцій», які надаються в [1-9, 14-16, 20, 22], є: елементарна кон’юнкція;

елементарна диз’юнкція; ДНФ; конституента одиниці (мінтерм n-го рангу); ДДНФ; КНФ; конституента нуля (макстерм n-го рангу); ДКНФ.

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

1.На прикладі булевих функцій опишіть поняття «нормальна форма»

функції.

33

2.Що являє собою елементарна кон’юнкція, елементарна диз’юнкція?

3.Яка формула називається диз’юнктивною нормальною формою, кон’юнктивною нормальною формою булевої функції?

4.Дайте визначення поняттям мінтерм, макстерм, конституента одиниці, конституента нуля.

5.Що таке досконала нормальна форма і які властивості в неї є?

6.Скільки є різних конституент одиниці та нуля для функції n змінних f (x1, x2 ,..., xn )?

7.Скільки ДНФ і скільки СДНФ може мати булева функція?

8.Запишіть формули диз’юнктивного розкладання булевих функцій від

n змінних за k (k n) змінними, за всіма n змінними, за однією змінною.

9.Запишіть формули кон’юнктивного розкладання булевих функцій від

nзмінних за k (k n) змінними, за всіма n змінними, за однією змінною.

10.Опишіть алгоритми переходу від таблиці істинності булевої функції до ДДНФ і ДКНФ.

11.Сформулюйте правила перетворення довільної формули алгебри логіки в нормальну форму з використанням законів булевої алгебри.

4.4.6 Тема 3 «Мінімізація булевих функцій»

Вивчення теми 3 «Мінімізація булевих функцій» пов’язане із розглядом таких питань [1-9, 13-16, 18-23]: основні поняття і визначення, які використовуються при мінімізації булевих функцій; оцінка форми булевої функції за допомогою індексу (коефіцієнта) простоти; задача мінімізації булевих функцій в аналітичній і геометричній формі (задача про покриття); основні підходи для розв’язання задачі мінімізації булевих функцій у сучасній теорії й практиці алгебри логіки; операції диз’юнктивного і кон’юнктивного склеювання і поглинання; аналіз деяких аналітичних і геометричних методів одержання мінімальних ДНФ (КНФ) (метод Квайна-Мак-Класки, метод Порецького-Блейка, метод мінімізуючих карт (діаграми Карно-Вейча), метод багатомірних кубів та ін.); методика використання мінімізуючих карт (методика діаграм Карно і Вейча).

Основними поняттями і визначеннями теми «Мінімізація булевих функцій», які надаються в [1-9, 14-16, 20, 22], є: булевий базис; індекс (коефіцієнт) простоти; імпліканта; повна система імплікант; власна частина кон’юнкції; проста імпліканта; скорочена, тупикова ДНФ; мінімальна ДНФ (МДНФ); імпліцента, проста імпліцента, повна система імпліцент, скорочена,

34

тупикова КНФ; мінімальна КНФ (МКНФ); неповне диз’юнктивне склеювання; диз’юнктивне поглинання; повне диз’юнктивне склеювання; неповне кон’юнктивне склеювання; кон’юнктивне поглинання; повне кон’юнктивне склеювання; мінімізуючі карти (діаграми Карно-Вейча).

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

1.Що являє собою булевий базис? Чим обумовлений вибір базису при проектуванні логічних схем?

2.Що являє собою індекс (коефіцієнт) простоти? Наведіть приклади індексів простоти.

3.Які існують підходи для розв’язання задач мінімізації булевих функцій в аналітичному виді?

4.Запишіть формули операцій диз’юнктивного склеювання і поглинання.

5.Запишіть формули операцій кон’юнктивного склеювання і поглинання.

6.Дайте визначення термінам «імпліканта», «імпліцента», «проста імпліканта», проста «імпліцента».

7.Що являє собою скорочена ДНФ і скорочена КНФ?

8.Дайте визначення тупикової ДНФ. Скільки тупикових ДНФ може

мати булева функція?

9.Яка із ДНФ (КНФ) називається мінімальною ДНФ (мінімальною

КНФ)?

10.Що являють собою карти Карно (діаграми Вейча)?

11.Назвіть правило склеювання комірок і запису мінімальної ДНФ при використанні карт (діаграм) Карно.

12.Як здійснюється побудова карти Карно для функції п’яти змінних?

13.Опишіть особливості мінімізації булевих функцій на множині КНФ із використанням мінімізуючих карт.

14.Яким чином здійснюється мінімізація частково визначених функцій?

4.4.8Тема 4 «Алгебра Жегалкіна»

Вивчення теми 4 «Алгебра Жегалкіна» пов’язане із розглядом таких питань [1, 3, 4, 13, 20-23]: визначення алгебри Жегалкіна, структура і тотожності алгебри Жегалкіна; поліном Жегалкіна та правило його побудови;

35

зображення диз’юнкції і заперечення поліномом Жегалкіна; визначення лінійної функції; метод невизначених коефіцієнтів, який можна використовувати для знаходження полінома Жегалкіна заданої булевої функції.

Основними поняттями і визначеннями теми «Алгебра Жегалкіна», які надаються в [1, 3, 4, 20, 22, 23], є: алгебра Жегалкіна, поліном Жегалкіна, довжина полінома Жегалкіна, ранг елементарної кон’юнкції, лінійна булева функція.

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

1.Запишіть і поясніть структуру алгебри Жегалкіна.

2.Перелічить основні закони і тотожності алгебри Жегалкіна.

3.Дайте визначення поняттю поліному Жегалкіна.

4.Дайте визначення лінійності булевої функції.

5.Наведіть приклади лінійних і нелінійних функцій двох змінних.

4.4.10Тема 5 «Функціональна повнота наборів булевих функцій»

Вивчення теми 5 «Функціональна повнота наборів булевих функцій» пов’язане із розглядом таких питань [1, 3, 4, 8, 13, 16, 20-23]: типи булевих функцій; функції, що зберігають 0 і функції, що зберігають 1; монотонність булевих функцій, способи визначення монотонності булевих функцій;

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

Основними поняттями і визначеннями теми «Функціональна повнота наборів булевих функцій», які надаються в [1, 3, 4, 8, 16, 20, 22], є: функція, що зберігає 0; функція, що зберігає 1; монотонна булева функція; замкнення множини A булевих функцій; замкнений клас; класи Поста; функціонально повна система функцій; функціонально повна система функцій у слабкому у слабкому розумінні; мінімально повний базис; нескоротна система булевих функцій.

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

1.Перелічить основні типи булевих функцій.

2.Дайте визначення булевих функцій, що зберігають 0 і 1.

36

3.Яка кількість всіх булевих функцій n змінних зберігає константу 0 і

константу 1?

4.Яка функція називається монотонною булевою функцією?

5.Як, аналізуючи диз’юнктивну нормальну форму булевої функції, можна визначити, монотонна функція, чи ні?

6.Перелічить найважливіші замкнені класи булевих функцій.

7.Яка система булевих функцій називається функціонально повною?

8.Сформулюйте теорему про повноту двох систем булевих функцій.

9.Наведіть визначення функціональної повноти в слабкому розумінні.

10.Яка повна система булевих функцій є нескоротною.

11.Сформулюйте теорему Поста про повноту булевих функцій.

4.4.12 Тема 6 «Логічні схеми. Синтез комбінаційних схем»

Вивчення теми 6 «Логічні схеми. Синтез комбінаційних схем» пов’язане із розглядом таких питань [1, 7, 16, 20, 22]: логічні схеми (ланцюги) у

комп’ютерах та інших електронних пристроях; основні логічні елементи для побудови логічних схем; математичний апарат для аналізу та синтезу логічних схем; повнота набору логічних елементів; аналіз та синтез логічних схем.

Основними поняттями і визначеннями теми «Логічні схеми. Синтез комбінаційних схем», які надаються в [1, 7, 16, 20, 22], є: логічна схема, логічний елемент; входи логічної схеми, вихід логічної схеми; графічні символи для зображення логічних елементів, повний набір логічних елементів.

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

1.Що є основою для побудови логічних схем?

2.Як булева алгебра зв’язана з проектуванням логічних ланцюгів?

3.Нарисуйте графічні позначення основних логічних елементів.

4.Який набір логічних елементів називається повним?

5.Якому набору логічних елементів слід віддати перевагу під час розв’язання конкретної задачі?

6.Охарактеризуйте основні задачі, що виникають при дослідженні логічних ланцюгів.

7.У чому полягає аналіз логічних ланцюгів?

8.Яким чином здійснюється синтез логічних ланцюгів?

37

4.4.14 Тема 6 «Багатозначна логіка»

Вивчення теми 6 «Багатозначна логіка» пов’язане із розглядом таких питань [1, 16, 22]: виникнення багатозначних логік; значення істинності висловлення; алфавіт багатозначної логіки; унарні і бінарні функції; повна система функцій багатозначної логіки.

Основними поняттями і визначеннями теми «Багатозначна логіка», які надаються в [1, 16, 20], є: двозначна логіка, m-значна логіка, багатозначна логіка, таблиця істинності у багатозначній логіці, значення істинності висловлення р, алфавіт k-значної логіки, повна система функцій багатозначної логіки.

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

1.Що розуміють під багатозначною логікою?

2.Які існують різновиди багатозначних логік?

3.Скільки різних визначень кон’юнкції існує у чотиризначній логіці?

4.Дайте визначення поняттю значення істинності висловлення.

5.Сформулюйте визначення алфавіту k-значної логіки.

6.Скільки існує різних функцій k-значної логіки від n змінних?

7.Запишіть формули основних унарних функцій k-значної логіки.

8.Назвіть найважливіші бінарні функції k-значної логіки.

9.Яка система функцій k-значної логіки називається повною?

4.5 Змістовий модуль 5 «Логіка висловлень і логіка предикатів»

4.5.1 Перелік тем змістовного модуля 5

Під час вивчення змістового модуля 5 розглядаються такі теми:

тема 1 «Висловлення. Алгебра висловлень»;

тема 2 «Обчислення висловлень»;

тема 3 «Предикати. Алгебра предикатів»;

тема 4 «Обчислення предикатів».

38

4.5.2 Тема 1 «Висловлення. Алгебра висловлень»

Вивчення теми 1 «Висловлення. Алгебра висловлень» пов’язане із розглядом таких питань [1, 3, 4, 6-8, 13, 16, 18-23]: елементарні висловлення (атоми); логічні зв’язки і формули логіки висловлень; побудова складних формул логіки висловлень (молекул), логіка висловлень та її закони, ізоморфність алгебри логіки і логіки висловлень; пріоритет операцій алгебри висловлень; інтерпретація формул логіки висловлень, правильні міркування; логічна еквівалентність і логічний наслідок.

Основними поняттями і визначеннями теми «Висловлення. Алгебра висловлень», які надаються в [1,3,4,6-8,16,18-20,22], є: висловлення; атом;

висловлювальна змінна; істиннісне значення; множина істиннісних значень; логічні зв’язки; формула логіки висловлень (молекула); заперечення висловлення; кон’юнкція, диз’юнкція, імплікація висловлень; засновок (умова, антецедент); логічний наслідок (висновок, консеквент); правильно побудована формула; логіка висловлень; інтерпретація висловлення; тотожно істинна формула; тотожно хибна формула; незагальнозначуща (несуперечлива)

формула; правильне міркування; логічна еквівалентність.

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

1.Який вид речень моделює формальна логіка?

2.Дайте визначення поняття «висловлення».

3.Дайте визначення поняття «алгебра логіки висловлень».

4.Які висловлення називаються атомами?

5.Що в логіці висловлень називають логічними зв’язками?

6.Що в логіці висловлень називають молекулами?

7.Дайте характеристику алфавіту логіки висловлень.

8.Що мають на увазі в логіці висловлень під правильно побудованою формулою?

9.Дайте визначення логічного наслідку одного (декількох) висловлень.

10.Покажіть, що алгебра логіки і логіка висловлень є ізоморфними.

11.Яка формула називається тавтологією, тотожно хибною формулою,

несуперечливою формулою?

12.Яке міркування називається правильним?

13.Перелічить найбільш важливі тавтології.

39

14.Які формули називаються рівносильними? Наведіть приклади рівносильних формул.

15.Що являє собою обчислення висловлень?

16.Поясніть поняття мови, аксіом і правил висновку обчислення висловлень.

17.Наведіть приклади аксіом обчислення висловлень.

18.Яким чином будується дедуктивний висновок?

19.Дайте стислу характеристику основних правил дедуктивного

висновку.

20.Перелічить правила дедуктивних висновків логіки висловлень.

21.У чому полягає повнота і несуперечність обчислення висловлень?

22.Дайте визначення незалежної системи аксіом.

23.Сформулюйте теорему дедукції.

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

4.5.4 Тема 2 «Обчислення висловлень»

Вивчення теми 2 «Обчислення висловлень» пов’язане із розглядом таких питань [1, 3, 4, 6-8, 13, 16, 18-23]: обчислення висловлень (мова, система аксіом і правила висновку); повнота і несуперечність обчислення висловлень; вивідність в обчисленні висловлень (дедуктивний висновок, правила підстановки і відділення); різні аксіоматизації обчислення висловлень; деякі прийоми доведення в обчисленні висловлень.

Основними поняттями і визначеннями теми «Обчислення висловлень», які надаються в [1, 3, 4, 6-8, 16, 18-20, 22], є: обчислення висловлень; мова обчислення висловлень; аксіоми обчислення висловлень; висновок в обчисленні висловлень; теорема дедукції; правила висновку; дедуктивний висновок; правило відділення; правило підстановки; несуперечливе логічне обчислення; незалежна система аксіом.

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

1.Що являє собою обчислення висловлень?

2.Поясніть поняття мови, аксіом і правил висновку обчислення висловлень.

3.Наведіть приклади аксіом обчислення висловлень.

4.Яким чином будується дедуктивний висновок?

40