1.5.3. Конституенти нуля. Досконалі кон’юнктивні та шефферові нормальні форми
Як зазначалося, з допомогою СДНФ і СВНФ найпростіше виражаються функції, які у векторі істинності переважають нулі. Якщо у векторі істинності більше одиниць, то використовують аналогічні досконалі кон'юнктивні та шефферові форми, в яких як внутрішні функції входять конституенти нуля.
Визначення.Нехай на наборіn=(1>, . нуляфункціїfназвемо диз'юнкцію виду
Аналогічношеферової конституентою нуляфункціїfназвемо підстановку видуS = (х11, ., хnn)
Як диз'юнктивна, і шефферова конституенти нуля, відповідні наборуn, приймають значення 0 лише у ньому. На решті наборів вони рівні 1.
Приклад 3.Побудувати всі диз'юнктивні та шефферові конституенти нуля функції, заданої таблицею істинності.
Рішення. Функція набирає значення 0 на наборах (0, 1, 0), (0, 1, 1), (1, 0, 1). На наборі (0, 1, 0) диз'юнктивна конституента нуля Д1= хуz,на наборі (0, 1, 1) Д2=хуz,на наборі (1, 0, 1) Д3=хуz.У таблиці додатково вказані вектори істинності конституент Д1 - Д3. Кожна з них виділяє рівно один із нулів у векторі істинності вихідної функції.
Шефферові конституенти отримуємо з Д1 - Д3, інвертуючи внутрішні змінні в них та замінюючи диз'юнкцію функцією Шеффера. У результаті отримаємо:S1= (х, у,z);S2= (х, у,z);S3= (х,у,z).Оскільки перетворення еквівалентне, векториістинностіS1 -S3 збігаються з векторами для Д1 - Д3.
Визначення.Довершеною кон'юнктивною нормальною формою(СКНФ) булевої функціїf (хn)називають вираз виду:
деD1 . ,Dр- диз'юнктивні конституенти нуля функції.
Довершеною шеферовою нормальною формою(СШНФ) булевої функціїf(хn) називають вираз виду:
СКНФ, як і всі КНФ, є функціями в базисному наборі.СШНФ можна поряд з основним уявленням задати в однофункціональному базисному наборі.
Приклад 4.Побудувати СКНФ та СШНФ (для кожного з базисних наборів та ) функціїf= (11001011) з Прикладу 3.
1. Диз'юнктивні конституенти нуля Д1 - Д3 знайдені в Прикладі 3. СКНФ отримуємо, логічно помножуючи їх:
2. Шефферові конституентиS1 -S3 також були знайдені в Прикладі 3. СШНФ в базисному наборі отримуємо, підставляючиS1 -S3 у функцію Шеффера з наступним її инвертированием:
СШНФ у базисному наборі має вигляд:
Шукані форми побудовані.
СКНФ і СШНФ існують лише для функцій, не рівних тотожній одиниці. У разі, коли вектор істинності функції має лише один нуль, її СКНФ та СШНФ є виродженими.
Розглянуті вище ДНФ, КНФ, ВНФ та ШНФ допускають не єдине уявлення функцій. Досконалі форми є їх окремими випадками.