Любая формула алгебры высказываний определяет двузначную функцию, аргументы которой принимают только два значения – 0 или 1. Каждая функция может быть задана большим количеством различных по виду формул. Поэтому их трудно сравнивать, переходить от формулы к записи функции в таблицу истинности. Формулы могут значительно различаться по сложности. Канонические формы – это запись формул функций по единым правилам. Такие формы называют совершенными. Различают дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ).

Пусть дана некая таблица истинности. Понятно, что существует бесконечно много равносильных формул алгебры высказываний, имеющих эту таблицу истинности. Приведем два способа нахождения двух таких формул через дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) на конкретном примере:

   Дана таблица истинности для переменных Аi и функции F.

   Формулы F по пути ДНФ и F по пути КНФ равносильны, так как имеют одну и ту же таблицу истинности, но удобнее строить формулу, где количество строк будет задействовано меньше. В данном случае это F по пути ДНФ.

   Пример 7. Дан фрагмент таблицы истинности выражения F. Каким может быть выражение F?

   Решение:

  1. Для определения, по какому пути находить формулу по ДНФ или КНФ - анализируем значение выражения F, на количество 0 и 1. Количество «0» – 2 , Количество «1» – 1, значит по ДНФ
  2. Отметим строки, где F=1 (№ 2)
  3. Для этой строки составим собственную формулу (истинную), используя операцию конъюнкцию и отрицание.

   Так как строка у нас одна, мы опускаем пункт: «получить искомую формулу – взять дизъюнкцию всех этих формул», а значит – это искомая функция.