Класи Поста булевих ф-й. Теорема про повноту. Теорема Поста

Клас кон*юнкцій, що є замиканням множ. операцій . Клас диз*юнкцій що є замиканням множ. операцій . Клас U ф-й одної змінної, що містить тільки константи.

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

Теорема Поста: Для того щоб система була повною, необхідно і достатньо, щоб вона містила хоча б одну нелінійну ф-ю, немонотонну, ф-я яка не зберігатиме 0 та не зберігає 1.

 

37.Алгебраїчне задання булевих ф-й. ДДНФ.

Алгебраїчна форма задання булевих функцій — це форма подання логічної функції у вигляді поліному з коефіцієнтами виду 0 і 1

Досконалою диз’юнктивною нормальною формою (ДДНФ)називається формула що зображенна у вигляді диз’юнкції конституент 1 даної функції (містить у елемент кон’юнкції стільки змінних скільки їх містить сама функція).

38. Алгоритм переходу від табличного задання до алгебраїчного.

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

 

39.Геометричне подання булевих ф-й від двох та трьох змінних. Позначимо через Е ⁿ безліч всіх наборів (α ₁,..., α _η), що складаються з чисел нуль і одиниця. Безліч Е ⁿ називається n-мірним кубом, а набір (α _1,..., α _η) - вершинами куба. Нехай σ _1,..., σ _r - фіксований набір чисел з 0 і 1. Безліч всіх вершин (α ₁,..., α _η) куба Е ⁿ таких, що α _{i 1} = σ _1, α _{i 2} = σ _2,..., Α _ir = Σ _r, 1 <i ₁ <i ₂ <... <i _r, називається (n - r) - Мірної гранню. Очевидно, що (n - r)-мірна грань є (n - r) - подкубом куба Е ^n.

 

 

40. Застосування булевих ф-й до аналізу перемикальних схем. Булевою функцією f (x ₁, x ₂,..., x_n) називається довільна функція n змінних, аргументи якої x ₁, x ₂,..., x_n і сама функція f приймає значення 0 або 1, тобто x_i {0, 1}, i = 1, 2,..., n; f (x ₁, x ₂,..., x_n) {0, 1}.

Однією з найважливіших інтерпретацій теорії булевих функцій є теорія перемикальних функцій. Будь-яка булева функція може бути представлена таблицею, у лівій частині якої перераховані всі набори змінних а в правій частині – значення функції. Для формування стовпця значень змінних зручний лексико-графічний порядок, відповідно до якого кожен наступний набір значень виходить із попереднім додатком 1 у двійковій системі числення, Булевих функцій двох змінних – 16 (2² при n = 2). Ті з них, які мають спеціальні назви, x ₁V x ₂ – диз’юнкція; x ₁& x ₂ – кон’юнкція; x ₁É x ₂ – імплікація; x ₁~ x ₂ – еквівалентність;

 

41Функціональні відношення

Відображення назив. А сюр*активним, якщо (Якщо відобр. F сюр*єктивне то для хоча б один прообраз а з А.

Ін*активним (взаємно однозначним), якщо для тобто двом різним прообразам відповідають різні образи.

Бієктивне – це взаємно однозначне відобр. множ. А на множ. В. Якщо відображення f бієктивне, то для .

 

42 ДНФ для мулевих ф-й.
(диз*активною норм. формою назив. формула, що зображена у вигляді диз*юнкції елементарних кон*юнкцій.

43 ДДНФ для бул. ф-й та її власт.

ДДНФ(досконала диз*юктивна норм. форма) містить у елементарній кон*юнкції стільки змінних скільки їх має сама ф-я.

Власт.:

44 Мінімізаці булевих ф-й. Карти Карно.

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

Карти Карно розглядається як перебудована відповідним чиом табл. істинності ф-ї.