Равносильность формул.
Определение:
Будем называть две формулы α и β равносильными, если при любых значениях x1, x2,…, xn, где x1, x2,…, xn – совокупность всех переменных, входящих в α и β, эти формуы принимают одинаковые значения.
Между понятием равносильности и знаком эквивалентности ~ существует следующая связь: если формулы α и β равносильны, то формула α~β принимает значение истина при всех значениях переменных, и обратно: если формула α~β принимает значение истина при всех значениях переменных, то формулы α и β равносильны.
Справедливость этого утверждения вытекает из определения операции эквивалентности ~.
Примеры равносильных формул:
¬(¬(X))≡X – закон двойного отрицания
XVY≡YVX – коммутативность
(XΛY)ΛZ≡XΛ(YΛZ) - ассоциативность
XVY≡YVX - ассоциативность
(XVY)VZ≡XV(YVZ) - ассоциативность
XΛ(YVZ)≡(XΛY)V(XΛZ) - дистрибутивность
XV(YΛZ)≡(XVY)Λ(XVZ) - дистрибутивность
XV(XΛY)≡X – закон поглощения
XΛ(XVY)≡X – закон поглощения
¬(XVY)≡¬XΛ¬Y – закон Де Моргана
¬(XΛY)≡¬XV¬Y – закон Де Моргана
XVX≡X - идемпотентность
XV¬X≡И – закон исключения
XΛX≡X - идемпотентность
XΛ¬X≡Л – закон противоречия
XΛИ≡X – закон сокращения
XVЛ≡X – закон сокращения
Соотношения 1-17 легко проверяются на основании определения операций ¬, Λ, V. Соотношения равносильности позволяют производить над формулами преобразования, приводящие их к более простому или более удобному виду.
Определение:
Система элементов, на которых определены действия сложения, умножения и отрицания, удовлетворяющая зависимостям(1-17), называется алгеброй Буля.
Логические операции ¬, Λ, V, →, ~ -не являются независимыми друг от друга. Одни из них можно выражать через другие так, что при этом получаются равносильные формулы.
X~Y≡(X→Y)Λ(Y→X)
Доказывается на основании определения действий →, ~ и Λ.
X~Y≡(¬XVY)Λ(¬YVX)
X~Y≡XΛYV¬XΛ¬Y
Все операции посредством равносильных выражений можно заменить двумя: V и ¬ или Λ и ¬.
Замечание:
Если формула α содержит только операции ¬, Λ, V, то на основании закона Де Моргана ее можно преобразовать к такому виду, что знаки отрицания будут относится только к элементарным высказываниям.
XV¬XΛY≡XVY
¬XVXΛY≡¬XVY
XΛ(¬XVY)≡XΛY
¬XΛ(XVY)≡¬XVY
1.3. Закон двойственности.
Рассмотрим формулы, которые содержат только операции ¬, Λ, V. Будем говорить , что операция Λ двойственна операции V и наоборот.
Определение:
Формулы α и α* называются двойственными, если одна получается из другой заменой каждой операции на двойственную.
Из законов Д Моргана легко вывести следующее положение: если формулы α(x1, x2,…, xn) и α*( x1, x2,…, xn) двойственна, а x1, x2,…, xn – элементарные высказывания, то ¬ α(x1, x2,…, xn) равносильно α*( x1, x2,…, xn).
Отсюда вытекает Закон двойственности:
Если формулы α и β равносильны, то двойственные им формулы α* и β* также равносильны.
α≡β => α*≡β*
1.4. Проблема разрешения.
Определение:
Будем называть формулу тождественно истинной, если она при всех значениях входящих в нее переменных высказываний принимает значение истина.
Определение:
Будем называть формулу выполнимой, если она принимает значение истина при некоторых значениях входящих в нее переменных высказываний.
Определение:
Будем называть формулу невыполнимой или тождественно ложной, если она при всех значениях входящих в нее переменных высказываний принимает значение ложь.
Поставим перед собой задачу: указать единый алгоритм, позволяющий для каждой формулы выяснить, является она тождественно истинной или нет? Также решается выполнимость. Возьмем, к примеру, α и решим, является ли ¬α тождественно истинной. Если ¬α - тождественно истинна, следовательно α – тождественно ложна, то есть невыполнимая, а если ¬α – не является тождественно истинной, следовательно, α не тождественно ложна и значит выполнима. Поставленная задача называется проблемой разрешения, которая легко решается для алгебры высказываний.
К примеру, возьмем функцию α(x1, x2,…, xn), которая, как и ее переменные x1, x2,…, xn может принимать только два значения. Имеем 2n комбинаций значений переменных x1, x2,…, xn. Мы можем вычислить значение функции α для каждой комбинации, подставив вместо переменных их значения, и тогда можно выяснить тождественно истинная функция или нет. Но этот способ не рационален, так как число испытаний очень велико. Существует другой способ: привидение формул к нормальной форме.
Определение:
Будем называть элементарной конъюнкцией (соответственно – элементарной дизъюнкцией) произведение (сумму) переменных и их отрицаний.
Теорема 1:
Элементарная дизъюнкция тождественно истинная тогда и только тогда когда содержит некоторые элементарные высказывание вместе с его отрицанием.
Теорема 2:
Элементарная конъюнкция тождественно ложна тогда и только тогда когда содержит некоторое элементарное высказывание вместе с его отрицанием.
Определение:
Формула, равносильная исходной формуле и представляющая собой дизъюнкцию элементарных конъюнкций, называется дизъюнктивной нормальной формой (ДНФ) исходной формулы.
Определение:
Формула. равносильная исходной формуле и представляющая собой конъюнкцию элементарных дизъюнкций, называется конъюнктивной нормальной формой (КНФ) исходной формулы.
Для любой формулы существует КНФ (ДНФ), то есть любая формула высказываний может быть приведена к КНФ (ДНФ) за конечное число конечных преобразований, используя алгебру высказываний.
Замечание:
Для каждой формулы α существует не одна ДНФ и не одна КНФ.