Нормальные формы формул алгебры высказываний.

Отношение равносильности является отношением эквивалентности на множестве всех формул F_АВ, которое разбивает это множество на классы эквивалентности , определяемые формулами .

Из лемм следует, что для каждой формулы можно указать равносильные ей формулы специального вида, содержащие только символы логических операций .

Определение. Литерой называется пропозициональная переменная X или ее отрицание X . Для обозначения литеры используется символ X^, где {0,1} и по определению , .

Определение. Конъюнктом (соответственно, дизъюнктом) называется литера или конъюнкция (соответственно, дизъюнкция) литер.

Конъюнкт (дизъюнкт) называется совершенным, если он содержит все пропозициональные переменные рассматриваемой формулы.

Определение. Конъюнктивной нормальной формой (сокращенно КНФ) называется дизъюнкт или конъюнкция дизъюнктов. Дизъюнктивной нормальной формой (сокращенно ДНФ) называется конъюнкт или дизъюнкция конъюнктов.

При этом КНФ (соответственно, ДНФ) называется совершенной, если совершенны все ее дизъюнкты (соответственно, конъюнкты).

Теорема 1. Любая формула равносильна некоторой ДНФ и некоторой КНФ.

Теорема 2. Любая выполнимая формула равносильна формуле вида , где дизъюнкция берется по всем упорядоченным наборам {0,1}ⁿ, удовлетворяющим условию .

Такая формула определяется однозначно (с точностью до порядка членов конъюнкций и дизъюнкций) и называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ) формулы .

Теорема 3. Любая опровержимая формула равносильна формуле вида , где конъюнкция берется по всем упорядоченным наборам {0,1}ⁿ, удовлетворяющим условию .

Такая формула определяется однозначно (с точностью до порядка членов конъюнкций и дизъюнкций) и называется совершенной конъюнктивной нормальной формой (сокращенно СКНФ) формулы .

Логическое следование формул.

Определение. Формула называется логическим следствием формул , если при любой подстановке в эти формулы вместо их переменных конкретных высказываний из истинности высказываний следует истинность высказывания .

Символическое обозначение - называется логическим следованием.

Формулы называются посылками и формула – следствием логического следования .

Определение. Множество формул называется противоречивым, если из него логически следует любая (в том числе и тождественно ложная) формула . Символически это записывается .