Кон'юнктивна нормальна форма (КНФ) і диз'юнктивна нормальна форма (ДНФ) є основними формами представлення логічних виразів. Вони дозволяють представити будь-яку булеву функцію у вигляді кон'юнкції (КНФ) або диз'юнкції (ДНФ) логічних змінних і їх заперечень. Складання КНФ і ДНФ по таблиці істинності є одним з основних методів вирішення логічних задач і побудови логічних ланцюгів.
Складання КНФ і ДНФ по таблиці істинності починається з аналізу значень виходу функції на різних поєднаннях значень вхідних змінних. Для кожного рядка таблиці істинності, в якій функція приймає значення "1", складається відповідний член КНФ або ДНФ. У КНФ використовуються кон'юнкції, а в ДНФ – диз'юнкції, які об'єднуються між собою логічним або.
Складання КНФ і ДНФ по таблиці істинності є процесом, який вимагає уважності і точності. Для успішного складання КНФ і ДНФ необхідно чітко розуміти, які значення змінних призводять до результату "1" і як об'єднувати їх за допомогою логічних операцій. У цій статті ми розглянемо, як скласти КНФ і ДНФ по таблиці істинності на прикладі конкретної булевої функції.
Опис таблиці істинності
Таблиця істинності має наступну структуру:
- Перший рядок таблиці містить заголовки стовпців, які позначають змінні, що входять у вираз, і сам вираз.
- Наступні рядки таблиці містять комбінації значень істини для змінних та значення істини для вираження.
У таблиці істинності кожна змінна може приймати лише два можливі значення-true (1) або false (0). Кількість рядків таблиці істинності визначається кількістю змінних у виразі і дорівнює 2^n, де n - кількість змінних.
Значення істинності для виразу визначається на основі логічних операцій, що застосовуються до змінних у виразі. Кожна комбінація значень змінних відповідає одному рядку таблиці істинності. Значення істинності для вираження обчислюється шляхом застосування логічних операцій до значень змінних.
Таблиця істинності дозволяє аналізувати і обчислювати значення істинності для складних логічних виразів, а також використовувати її для складання КНФ (кон'юктивної нормальної форми) і ДНФ (диз'юнктивної нормальної форми) для цих виразів.
Значення змінних
Для складання КНФ і ДНФ по таблиці істинності важливо визначити значення змінних, для яких таблиця істинності була побудована.
У цьому контексті змінні часто позначаються великими літерами латинського алфавіту, наприклад A, B, C і так далі.
Кожна змінна може приймати лише два значення: справжнє значення 1 або помилкове значення 0.
Значення змінних в таблиці істинності можуть бути задані у вигляді набору комбінацій 0 і 1, де кожна комбінація відповідає певному набору значень змінних.
Значення змінних є основними будівельними блоками при складанні КНФ і ДНФ по таблиці істинності, оскільки саме вони визначають умови, при яких вираз буде істинним або хибним.
Розглянемо приклад. Скажімо, у нас є таблиця істинності з двома змінними A і B:
| А | В | Результат |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Тут змінні A і b приймають значення 0 або 1 залежно від відповідної комбінації. Результат відповідної комбінації буде дорівнює 1 або 0 в залежності від логічного виразу, яке задано.
Для складання КНФ і ДНФ необхідно уважно проаналізувати значення змінних в таблиці істинності і використовувати їх для створення відповідного логічного виразу.
Значення функції
Записуючи таблицю істинності, ми можемо побачити, як змінюються значення функції при різних комбінаціях значень змінних. Кожен рядок таблиці істинності відповідає одній комбінації значень змінних.
Наприклад, розглянемо функцію " і "(логічне"і"). У таблиці істинності для цієї функції значення функції дорівнюють 1 тільки в разі, якщо обидва значен
Складання КНФ
Кон'юнктивна нормальна форма (КНФ) являє собою вираз логічної функції, що складається з кон'юнкцій (логічних "і") елементарних висловлювань або їх заперечень. Складання КНФ по таблиці істинності допомагає спростити і аналізувати складні логічні функції.
Для складання КНФ по таблиці істинності необхідно:
- Розглянути рядки таблиці істинності, в яких значення функції дорівнює 1.
- У кожній з цих рядків скласти кон'юнкцію елементарних висловлювань або їх заперечень.
- Об'єднати отримані кон'юнкції в один вираз, використовуючи диз'юнкцію (логічне "або").
Наприклад, розглянемо наступну таблицю істинності:
| A | B | C | F(A, B, C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
З таблиці видно, що значення функції F дорівнюють 1 в рядках 2, 3 і 4. Складаємо кон'юнкції для цих рядків:
- (Не A) і (не B) і C
- (Не A) і B і (не C)
- (не A) і B і C
Об'єднуємо отримані кон'юнкції за допомогою диз'юнкції:
(не A) і (не B) і C або (Не A) і B і (не C) або (Не A) і B і C
Таким чином, КНФ для даної функції дорівнює виразу (не A) і (не B) і C або (Не A) і B і (не C) або (Не A) і B і C.
Виключення значень 0
При складанні КНФ (кон'юктивної нормальної форми) і ДНФ (диз'юнктивної нормальної форми) по таблиці істинності, часто виникає необхідність виключити значення 0.
Для виключення значень 0 з таблиці істинності, слід виконувати наступні кроки:
- Проаналізуйте таблицю та знайдіть рядки, де значення функції дорівнює 0.
- Для кожної знайденої рядки, виключіть її з подальшого використання при складанні КНФ і ДНФ.
Якщо після виключення значень 0 у таблиці істинності залишилися рядки, то ви можете використовувати залишилися рядки для складання КНФ і ДНФ.
Приведення до елементарних кон'юнкцій
Основна ідея приведення до елементарних кон'юнкцій полягає в розкладанні складного логічного виразу на прості, елементарні логічні змінні і їх заперечення, пов'язані операторами кон'юнкції і диз'юнкції.
Для приведення до елементарних кон'юнкцій можна використовувати таблицю істинності логічного виразу. Спочатку визначте значення логічних змінних для яких даний вираз істинно, а потім розкладіть вираз на кон'юнкцію елементарних кон'юнкцій з використанням операторів кон'юнкції і диз'юнкції.
Приведення до елементарних кон'юнкцій дозволяє спростити подальшу роботу з логічними виразами, так як елементарні кон'юнкції можуть бути розглянуті незалежно один від одного і можуть бути використані для побудови більш складних логічних виразів.
Складання ДНФ
Процес складання ДНФ по таблиці істинності слід наступним крокам:
- Визначте кількість змінних: Подивіться на таблицю істинності та визначте, скільки змінних бере участь у виразі.
- Визначте рядки, де вираз є істинним: Подивіться на таблицю істинності і виділіть рядки, в яких вираз приймає значення "1" (істина).
- Складіть кон'юнкції для цих рядків: Для кожного рядка, в якому вираз істинний, складіть кон'юнкцію змінних або їх заперечень. Кожна кон'юнкція буде представляти окремий доданок ДНФ.
- Об'єднайте всі кон'юнкції: Об'єднайте всі кон'юнкції, складені на попередньому кроці, використовуючи символ "або" ("∨"). Це і буде підсумкова ДНФ.
Наприклад, розглянемо таблицю істинності:
| p | q | r | Вираження |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
Використовуючи запропоновані кроки, можна скласти ДНФ:
- Для першого рядка таблиці істинності (p = 0, q = 0, r = 0) отримуємо кон'юнкцію !p∧!q∧!r.
- Для другого рядка (p=0, q=0, r=1) отримуємо кон'юнкцію !p∧!q∧r.
- Для четвертого рядка (p = 0, q=1, r=1) отримуємо кон'юнкцію !p∧q∧r.
Підсумкова ДНФ буде виглядати наступним чином:
Таким чином, ми отримали ДНФ, яка дозволяє представити всі можливі комбінації значень змінних, при яких вираз стає істинним.
Виключення значень 1
При складанні КНФ і ДНФ по таблиці істинності можливі випадки, коли деякі значення змінних виключаються. Зокрема, значення змінних, при яких функція приймає значення 1, можуть бути виключені з КНФ або ДНФ.
Для виключення значень 1 необхідно в таблиці істинності перевірити, які комбінації змінних призводять до значення 1 для функції. Потім можна скласти КНФ або ДНФ, виключаючи ці комбінації.
Наприклад, нехай задана функція f (x, y, z) = x ∨ (y ∧ z).
| x | y | z | f(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
У цьому прикладі функція f приймає значення 1 для комбінацій (0, 0, 1), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0) і (1, 1, 1). Для виключення цих значень з КНФ або ДНФ потрібно використовувати операції заперечення, кон'юнкції і диз'юнкції.
Таким чином, виключаючи значення 1, можна більш компактно представити функцію в КНФ або ДНФ, що може бути корисно при спрощенні булевих виразів і оптимізації логічних схем.
Приведення до елементарних диз'юнкцій
Кроки для приведення логічного виразу до елементарних диз'юнкцій:
- Записуємо таблицю істинності для даної логічної функції.
- Обчислюємо логічний вираз в кожному рядку таблиці істинності, де результат функції дорівнює істині (1).
- Для кожного рядка, де виходить істина, складаємо диз'юнкцію (логічне або) елементарних логічних змінних, використовуючи заперечення для змінних, які дорівнюють ложі (0).
- З'єднуємо всі елементарні диз'юнкції за допомогою логічного і (кон'юнкції).
Нехай дана логічна функція F(a, b, c) = a∧(b∨c). Складемо таблицю істинності для цієї функції:
| a | b | c | F(a, b, c) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
З таблиці істинності видно, що функція F дорівнює істині тільки в четвертому рядку. Відповідно, елементарна диз'юнкція для цього рядка буде дорівнює b∨c. тому логічний вираз F(A, b, c) = a∧(b∨c) можна представити у вигляді КНФ, привівши його до елементарних диз'юнкцій:
КНФ: F(a, b, c) = (¬a∧b∧¬c) ∨ (¬a∧b∧c)
Таким чином, приведення логічної функції до елементарних диз'юнкцій дозволяє більш компактно представити її у вигляді КНФ, спрощуючи вираз і аналіз логічних операцій.
Приклад
Розглянемо кілька прикладів складання КНФ і ДНФ по таблиці істинності.
Приклад 1:
Розглянемо таблицю істинності наступного виразу:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Для складання КНФ необхідно взяти рядки таблиці, в яких значення функції дорівнює 0, і об'єднати їх за допомогою логічного або. В даному випадку КНФ буде виглядати так:
F = (~A & ~B & ~C) | (A & ~B & C) | (A & B & C)
Для складання ДНФ потрібно взяти рядки таблиці, в яких значення функції дорівнює 1, і об'єднати їх за допомогою логічного і. в даному випадку ДНФ буде виглядати так:
F = (A & C) | (B & C) | (~A & ~B & C) | (~A & ~B & ~C)
Приклад 2:
Розглянемо таблицю істинності наступного виразу:
| P | Q | R | G |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
КНФ для даного виразу буде виглядати так:
G = (~P & ~Q & ~R) | (~P & Q & ~R) | (P & ~Q & ~R) | (P & Q & ~R)
ДНФ для даного виразу буде виглядати так:
G = (~P & ~Q & R) | (~P & Q & R) | (P & ~Q & R) | (P & Q & R)