Визначення 1.Елементарной диз'юнкція п змінних називається диз'юнкція змінних або їх від-ріцаній.
Елементарна диз'юнкція п змінних може бути записана у вигляді:
Визначення 2.Кон'юнктівной нормальною формою (КНФ) формули А називається рівносильна їй форму-ла, що є кон'юнкцію елементарних диз'юнкцій.
Для будь-якої формули алгебри логіки шляхом рівносильний-них перетворень можна отримати її КНФ, причому не єдину.
Наприклад, для формули маємо:
А так як. то КНФ.
Визначення 3. КНФ А називається досконалою кон'юнктівной нормальною формою формули А (СКНФ А), якщо для неї виконані умови:
1. Всі елементарні диз'юнкції, що входять до КНФ А. різні.
2. Всі елементарні диз'юнкції, що входять до КНФ А, містять всі змінні.
3. Кожна елементарна диз'юнкція, що входить в КНФ А. не містить двох однакових змінних.
4. Кожна елементарна диз'юнкція, що входить в КНФ А, не містить змінну і її заперечення.
Можна довести, що кожна не тотожне істин-ва формула має єдину СКНФ.
Один із способів отримання СКНФ складається в викорис-танні таблиці істинності для формули А.
Дійсно, отримавши за допомогою таблиці істин-ності СДНФ А. ми отримаємо СКНФ А. взявши заперечення. тобто СКНФ.
Інший спосіб отримання СКНФ, який використовує рав-носильні перетворення, полягає в наступному:
1. Шляхом рівносильних перетворень формули А отримують одну з КНФ А.
2. Якщо в отриманій КНФ А що входить в неї еле-плементарним диз'юнкція В не містить змінну xi, то, використовуючи равносильность, елементарний-ву диз'юнкцію В замінюють на дві елементарні діз'-юнкціі і кожна з яких містить змінну xi.
3. Якщо в КНФ А входять дві однакових елементарний-них диз'юнкції В, то зайву можна відкинути, користуючись рівносильно ВВВ.
4. Якщо деяка елементарна диз'юнкція, вхо-дящая в КНФ А, містить змінну хi двічі, то зайву можна відкинути, користуючись рівносильно.
5. Якщо деяка елементарна диз'юнкція, вхо-дящая в КНФ А. містить змінну хi і її негативні-ня, то і, отже, вся елементарна диз'юнкція має значення 1, а тому її можна від-кинути, як одиничний член кон'юнкції.
Ясно, що після описаної процедури буде отри-на СКНФ А.
Наприклад, для формули КНФ.
Так як обидві елементарні диз'юнкції різні і містять всі змінні (х і у), то перше і друге усло-вия СКНФ А виконані.
Елементарна диз'юнкція містить пере-менную х двічі, але. і тому КНФ; причому жодна з елементарних діз'-юнкцій не містить змінну і її заперечення. Зна-чит, тепер виконані всі умови СКНФ А. і, следо-вательно, СКНФ.
Всі формули алгебри логіки діляться на три класи:
1) тотожне справжні,
2) тотожно хибні і
Визначення тотожно істинною і тотожно хибною формул дані вище.
Формулу А називають здійсненним, якщо вона прий-томить значення «істина» хоча б на одному наборі зна-ний входять до неї змінних і не є Тожде-ного істинної.
У зв'язку з цим виникає завдання: до якого класу належить дана формула?
Це завдання носить назву проблеми розв'язання.
Очевидно, проблема можливості розв'язання алгебри логіки можна вирішити.
Дійсно, для кожної формули алгебри логи-ки може бути записана таблиця істинності, яка і дасть відповідь на поставлене запитання.
Однак практичне використання таблиці істин-ності для формули А (х1, х2. Хп) при великих п зат-руднітельно.
Існує інший спосіб, що дозволяє, що не викорис-чаплі таблиці істинності, визначити, до якого класу належить формула А. Цей спосіб заснований на приведе-ванні формули до нормальної формі (КНФ або ДНФ) і використанні алгоритму, який дозволяє визначити, чи є дана формула тотожно істинною чи не є. Одночасно з цим вирішується питання про те, чи буде формула А здійсненним.
Припустимо, що ми маємо критерій тотожний-ної істинності для формул алгебри логіки. Рассмот-рим механізм його застосування.
Застосуємо критерій тотожною істинності до формули А. Якщо виявиться, що формула А - тотожне справжня, то задача вирішена. Якщо ж виявиться, що фор-мула А не тотожне справжня, то застосуємо крите-рій тотожною істинності до формули. Якщо ока-жется, що формула А - тотожне справжня, то ясно, що формула - тотожне помилкова, і задача вирішена.
Якщо ж формула не тотожне справжня, то осту-ється єдино можливий результат: формула А ви-полніма.
Встановимо тепер критерій тотожною істин-ності довільної формули алгебри логіки. З цією метою попередньо сформулюємо і доведемо кри-терій тотожною істинності елементарної діз'-юнкціі.
Теорема 1. Для того, щоб елементарна діз'юнк-ція була тотожно істинною, необхідно і доста-точно, щоб в ній містилася змінна і її отри-цаніе.
Доведення. Необхідність. Нехай елементарна диз'юнкція тотожно істинна, але в неї одновремен-но не входить деяка змінна і її заперечення. При-дамо кожної змінної, що входить в елементарну диз'юнкцію без знака заперечення, значення брехня, а кожної змінної, що входить в елементарну диз'юнкцію під знаком заперечення - значення «істина». Тоді, оче-видно, вся елементарна диз'юнкція прийме значення брехня, що суперечить умові.
Достатність. Нехай тепер елементарна діз'юн-кція містить змінну і її заперечення. Так як . то і вся елементарна диз'юнкція буде тож-дественно істинної.
Критерій тотожною істинності елементарної диз'юнкції дозволяє сформулювати і довести критерії тотожною істинності довільної фор-мули алгебри логіки.
Теорема 2. Для того, щоб формула алгебри логи-ки А була тотожно істинна, необхідно і дос-таточно, щоб будь-яка елементарна диз'юнкція, вхо-дящая в КНФ А, містила змінну і її негативні-ня.
Доказательство.Необходімость. Нехай А - Тожде-ного істинна. Тоді і КНФ А - тотожне істин-на. Але КНФ Аа1 А2 . Ап, де А, - елементарні диз'юнкції (i = 1,2. N). Так як КНФ А 1, то А i 1 (i = 1,2. N). Але тоді за теоремою 1 кожна елементарна-ва диз'юнкція Ai містить змінну і її негативні-ня.
Достатність. Нехай будь-яка елементарна діз'-юнкція Ai. що входить в КНФ А, містить змінну і її заперечення. Тоді по теоремі 1 (i = 1,2. N). При цьому і КНФ.
Наприклад, з'ясуємо, чи є формула тотожно істинною.
Так як, то ясно, що кожна елементарна диз'юнкція і. що входить в КНФ А, містить змінну і її заперечення. Отже, A 1.
Аналогічно можна встановити критерій Тожде-жавної хибності формули алгебри логіки, викорис-чаплі її ДНФ.
Теорема 3. Для того, щоб елементарна кон'юн-кція була тотожно хибною, необхідно і доста-точно, щоб в ній містилася змінна і її отри-цаніе.
Теорема 4. Для того, щоб формула алгебри логіки А була тотожно хибною, необхідно і достатній-але, щоб будь-яка кон'юнкція, що входить в ДНФ А, содер-жала змінну і її заперечення.