Еквівалентні перетворення - перетворення, які використовують еквівалентні співвідношення і правило заміни.
Два правила заміни:
1. Правило підстановки формули f замість змінної х. При підстановці формули f замість змінної х все входження змінної х у вихідне співвідношення повинні бути одночасно замінені формулою f.
2. Правило заміни подформул. Якщо будь-яка формула f. описує функцію # 966 ;. містить f1 як подформули, то заміна f1 на еквівалентну f2 (f1 = f2) не змінить функції # 966; .
Основні еквівалентні співвідношення (закони) в булевої алгебри.
Асоціативність кон'юнкції і диз'юнкції:
Комутативність кон'юнкції і диз'юнкції:
Дистрибутивність кон'юнкції щодо диз'юнкції:
Дистрибутивність диз'юнкції відносно кон'юнкції:
Закон подвійного заперечення:
Властивості констант 0 і 1:
Правила де Моргана:
Закон виключеного третього:
Основні еквівалентні співвідношення (1) - (10) відрізняються тим, що вони не виводяться один з одного і цих співвідношень досить для виконання будь-яких еквівалентних перетворень.
Для спрощення формул так само використовуються наступні еквівалентні співвідношення, що виводяться з основних за допомогою еквівалентних перетворень:
Приведення до диз'юнктивній нормальній формі.
Елементарна кон'юнкція - кон'юнкція змінних або їх заперечень, в якій кожна змінна зустрічається не більше одного разу.
Диз'юнктивна нормальна форма (ДНФ) - формула, що має вигляд диз'юнкції елементарних кон'юнкція.
Приведення формули до ДНФ здійснюється в 4 етапи:
1. всі заперечення «спустити» до змінних за допомогою (6) і (8);
2. розкрити дужки за допомогою (1), (3), (4);
3. видалити зайві кон'юнкції і повторення змінних в кон'юнкції з допомогою (5), (9), (10);
4. видалити константи за допомогою (7).
Процедура приведення ДНФ до СДНФ полягає в розщепленні (використанні (12) у зворотний бік) кон'юнкція, які містять не всі змінні.
Приведення до кон'юнктивній нормальній формі.
Елементарна диз'юнкція - диз'юнкція змінних або їх заперечень, в якій кожна змінна зустрічається не більше одного разу.
Кон'юнктивна нормальна форма (КНФ) - кон'юнкція елементарних диз'юнкцій.
Нехай ДНФ F має вигляд F = k1 Úk2 Ú...Úkm. де k1, k2, ..., km - елементарні кон'юнкції. Приведення ДНФ до КНФ складається з двох кроків:
1. Застосувати до F правило подвійного заперечення і привести до ДНФ k ¢ 1 Ú k ¢ 2 Ú... k ¢ p де k ¢ 1 Ú k ¢ 2 Ú... k ¢ p - елементарні кон'юнкції. тоді
2. За допомогою правил де Моргана звільнитися від другого заперечення і перетворити заперечення елементарних кон'юнкція в елементарні диз'юнкції D1, D2, ... Dp Тоді
Досконала КНФ (СКНФ) - КНФ, кожна елементарна диз'юнкція якої містить всі змінні.