3. Аналітичне подання функцій алгебри логіки

Існує багато способів задання логічних функцій. Раніше ми розглядали табличний спосіб, при якому кожному набору значень змінних в таблиці істин­ності вказується значення логічної функції. Даний спосіб наглядний, але при аналізі властивостей функцій алгебри логіки не компактний. Простіше корис­ту­ватися аналітичним записом у вигляді формул.

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

Розглянемо фіксований набір змінних {х₁, х₂, …, х_n}, на якому задано функцію алгебри логіки. Оскільки довільна змінна х_і = {0, 1}, то набір значень змінної практично є двійковим числом. Приймаємо, що номером набору буде довільне двійкове число і, яке отримуємо наступним чином:

і = 2^n-1х₁ + 2^n-2х₂ + … + х_n.

Нехай функція f_і (x₁, x₂, …, х_n):

f_і =

Функцію f_і називають термом.

Диз’юнктивний терм (макстерм) – терм, що з’єднує всі змінні, подані в прямій або інверсній формі, знаком диз’юнкції (інакше кажучи «конституента нуля»).

Приклад 1: f₇ =  х₂  х₃  х₄, , f₂ = х₁ 

Кон'юнктивний терм (мінтерм) – терм, що зв’язує змінні, подані в пря­мій або інверсній формі, знаком кон’юнкції (інакше кажучи «конституанта одиниці»). Позначається мін терм наступним чином:

f_і =

Приклад: f₁ = х₁х₂х₃х₄; f₀ = .

Ранг терма r визначається кількістю змінних, які входять в даний терм.

Приклад: для мінтерма f₀= ранг r = 4, для макстерма f₂ = х₁ - r = 2.

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

Значення функції f, які відповідають кожному і-му набору, позначені через f₁, f₂, f₃, f₄. Подання функції f у ДДНФ є диз’юнктивною сумою мінтермів, які відповідають наборам змінних, для яких f_і = 1:

f ₉ = f₀ m₀ f₁ m₁ f₂ m₂ f₃ m₃ = 1 m₀ 0 m₁ 0 m₂  m₃

= m₀ + m₃ =  х₁х₂.

Подання функції у ДКНФ записується у вигляді:

f ₉ = (f₀  М₀) (f₁  М₁) (f₂  М₂) (f₃  М₃) = (1М₀)(0М₁)(0М₂)(1М₃)

= М₁М₂ = (х₁)(х)

Таблиця 4.

х1	х2	f	fі	Мінтерм	Макстерм
0	0	1	f0 = 1	m0 =	М0 = х1
0	1	0	f1 = 0	m1 = х2	М1 = х1
1	0	0	f2 = 0	m2 = х1	М2 = х2
1	1	1	f3 = 1	m2 = х1х2	М2 = 

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

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

1. , Х₁Х₂, Х₁Х₂ (булевий базис, надмірний).

2. , Х₁Х₂.

3. , Х₁Х₂.

4. 

5. та інші.