Дайте визначення дкнф та опишіть правила її утворення.

Досконалою кон'юнктивною нормальною формою (ДКНФ) логічної функції називають такий її вираз, який містить елементарні диз'юнкції одного рангу, пов'язані кон'юнкцією. Правила утворення ДКНФ n аргументів такі:

• За кожним набором двійкових змінних, за яких функція набуває значення 0, скласти елементарні диз'юнкції (макстерми).

• В елементарні диз'юнкції записати неінвертованими змінні, задані нулем у таблиці істинності, а інвертованими - ті змінні, які в таблиці істинності задані одиницею. Здобуті суми називають конституентами нуля.

• Елементарні диз'юнкції об'єднати знаком кон'юнкції.

35. Умовне графічне позначення функцій АБО, І, НЕ та їх запис.

f₈ = х₁ х₂ (логічна сума, диз’юнкція) операція АБО (OR)

f₂ = х₁·x₂, x₁x₂, логічний добуток (кон’юнкція) операція І (AND).

f ₁₁ = ₂ інверсія х₂ НЕ (NOT). За допомогою цих 3 операцій можна здійснити всі операції.

36. О пишіть функції Даггера та Шеффера. Наведіть графічні зображення.

f₉ = функція Даггера, операція АБО - НЕ.

f₁₅ = = функція Шеффера І – НЕ.

37. Які з основних законів алгебри логіки Вам відомі. Опишіть їх.

Основні закони алгебри логіки:

1. асоціативний (сполучний) закон: (х₁·х₂)·х₃ = х₁·(х₂·х₃); (х₁+х₂)+х₃=х₁+(х₂+х₃)=х₁+х₂+х₃.

2. дистрибутивний (розподільчий) закон: (х₁+х₂)х₃ = х₁·х₃+х₂·х₃;

3. комутативний (переставний) закон: х₁·х₂ = х₂·х₁; х₁+х₂=х₂+х₁.

4. Основні співвідношення для інверсії:

5. Закон подвійного заперечення:

38. Що відображають теореми булевої алгебри.

Теорема розкладання (розвинення):

;

;

;

;

.

39. Сформулюйте закони де Моргана, поглинання та склеювання.

Перетворення де Моргана застосовується дія переходу від диз’юнкції до кон’юнкції і навпаки.

Закони де Моргана (закони інверсії):

а) для двох змінних , тобто інверсія кон'юнкції є диз'юнкцією інверсій; тобто інверсія диз'юнкції є кон'юнкцією інверсій;

б) для n змінних

Закони поглинання:

а(а + b) = а; а(а + b)(a + с)...(а + w) = а;

а + ab = а; а + ab + ас + ... + аw = а;

; .

Закони склеювання (поширення)

; .

Закони узагальненого склеювання

; ;

;