1:6 Кон’юнктивна нормальна форма та довершена кон’юнктивна нормальна форма. Їх властивості.

Елементарна кон’юнкція (диз’юнкція) – кон’юнкція (диз’юнкція)

кількох аргументів, кожний з яких може одноразово входити до неї зі знаком

інверсії або без нього. Наприклад, — елементарні

кон’юнкції — елементарні диз’юнкції.

Диз’юнкція кількох елементарних кон’юнкцій називається диз’юнктив-

ною нормальною формою (ДНФ).

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

кон’юнктивною нормальною формою (КНФ). Наприклад, –

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

Нехай функція має вигляд КНФ, причому кожний її диз’юнктивний член містить усі n аргументів. У цьому разі кожна диз’юнкція – це конституента нуля, а форма функції називається довершеною кон’юнктивною нормальною

формою (ДКНФ).

Конституента нуля для третього набору аргументів (див. табл. 1.1) має

вигляд , для четвертого – , для п’ятого – . Вираз функції у ДКНФ записують у вигляді кон’юнкції цих конституент:

Функцію, що задана у КНФ, можна розгорнути у ДКНФ, таким чином:

- у кожну елементарну диз’юнкцію увести відсутні змінні шляхом

додаванням нуля у вигляді aa , де а – відсутня змінна;

- виконати перетворення за дистрибутивним (1.4) і комутативним

(1.2) законами;

- вилучити однакові диз’юнкції застосуванням закону повторення

(1.5).

Виконаємо процедуру розгортання функції, поданої у КНФ:

Довершена кон’юнктивна нормальна форма функції має такі

властивості:

1) якщо для будь-якого набору аргументів функція дорівнює нулеві,

то тільки один з членів ДКНФ набуває нульового значення;

2) якщо функція для певного набору аргументів дорівнює одиниці, то жоден з членів ДКНФ не дорівнює нулеві.

1:7 Функції однієї змінної.

Логічна функція n змінних повністю визначається таблицею істинності.

Конкретні значення функції для кожного набору аргументів визначають одну

з можливих функцій n змінних. Якщо врахувати, що для кожного з наборів змінних (аргументів) функція може набути двох значень (0 або 1), то

загальну кількість N функцій n змінних можна визначити як кількість

двійкових розрядних чисел, тобто .

Кількість функцій N є скінченною, але вона дуже швидко зростає зі

збільшенням кількості змінних n. Наприклад, якщо n = 5, кількість функцій

перебільшує п’ять мільярдів. Тому логічні функції від великої кількості змінних зручніше подавати у формі функцій від функцій, тобто застосовувати принцип суперпозиції, який полягає у підставлянні у функцію нових функцій замість аргументів. Нехай, наприклад, є функції двох змінних f1 (а, b), f2 (с, d), f3 (e, h). Тоді вразі підставляння e = f1 (а, b), h = f2 (с, d) отримаємо функцію чотирьох змінних f3 [f1 (а, b), f2 (с, d)].

Найважливіше значення в алгебрі логіки мають функції однієї та двох

змінних.

Розглянемо спочатку функції однієї змінної а. Кількість таких функцій

Складемо таблицю істинності (табл. 1.2) і визначимо за нею

кожну з цих функцій.

Таблиця 1.2. Таблиця істинності функцій однієї змінної

1. Вираз функції f1 можна отримати, подавши її у ДКНФ,

Ця функція тотожно дорівнює нулеві незалежно від значення змінної а і

називається нульовою.

2. Функція f2 у ДДНФ або ДКНФ має вигляд f2 = а і називається

повторенням а.

3. Функція – це інверсія а.

4. Функція не залежить від значення а і називається

одиничною. Одиничну та нульову функції називають також функціями-

константами.

1.8

1.9

1.10

1.11

1.12

1.13

1.14

1.15