Каждая логическая формула может изучаться алгебраически путем приведения ее к нормальной форме. Возможно приведение к двум нормальным формам – конъюнктивной нормальной форме (КНФ) и дизъюнктивной нормальной форме (ДНФ).
Конъюнктивная нормальная форма – это конъюнкция конечного числа дизъюнкций, т. е. формула вида (L1Ù¼ÙLn)= ÙLi , где Li – дизъюнкты.
Дизъюнктивная нормальная форма – это дизъюнкция конечного числа конъюнкций, т. е. формула вида (L1Ú¼ÚLn)=ÚLi, где Li – конъюнкты.
В исчислении высказываний доказана теорема о том, что любая формула имеет логически эквивалентную ей нормальную форму. Привести формулу к нормальной форме можно с помощью алгоритма нормализации.
Алгоритм нормализации
1. Исключение операций равносильности и импликации:
а) (XºY) заменяется на (XÉY)Ù(YÉX);
б) (UÉV) заменяется на (┐U Ú V).
2. Продвижение знака ┐ до высказываний (по законам де Моргана) и погашения двойных отрицаний.
3. Применение законов дистрибутивности, в результате – получение КНФ или ДНФ.
4. Удаление общезначимых дизъюнктов (дизъюнктов, содержащих рÚ┐р) и повторяющихся литер, в результате – получение приведенной нормальной формы (КНФ или ДНФ).
После приведения к нормальной форме можно решить вопрос общезначимости. Дизъюнкт общезначим тогда и только тогда, когда он содержит пару противоположных литер. КНФ общезначима тогда и только тогда, когда все ее дизъюнкты – общезначимы.
Пример.Привести формулу (pÉ(qÉr))É((pÙs)Ér) к КНФ.
1. (pÉ(qÉr)) É((pÙs)Ér);
2. (pÉ(ù qÚr)) É((pÙs)Ér);
3. (ù pÚ(ù qÚr)) É((pÙs)Ér);
4. (ù pÚ(ù qÚr)) É(ù (pÙs)Úr);
5. (ù pÚ(ù qÚr)) É(ù p ÚùsÚr);
6. (ù pÚù qÚr)Ù(ù pÚù sÚr);
7. ù (ù pÚù qÚr)Ú(ù pÚù sÚr);
8. (pÙqÙù r) Ú (ù pÚù sÚr);
9. ((pÚù p)Ù(qÚù p)Ù(ù rÚù p))Ú(ù sÚr);
10. (pÚù pÚù sÚr) Ù (qÚù pÚù sÚr) Ù (ùrÚù pÚù sÚr);
11. (qÚù pÚù sÚr).
Формула ложна при q=F, r=F, p=T, s=T.
Таким образом, проблема общезначимости КНФ сводится к проверке общезначимости каждого дизъюнкта, более интересна проблема выполнимости.