Равносильные формулы. Формулы алг логики

Приведем определение формулы алгебры логики.

1) каждая «элементарная» булева функция – формула;

2) если некоторое выражение N есть формула, то тоже формула;

3) если некоторые выражения M и N есть формулы, то выражения , , , тоже формулы;

4) других формул, кроме построенных по п.п.1), 2), 3), нет.

Две формулы N и M называются равносильными, если они определяют одну и ту же булеву функцию (запись N = M будет означать, что формулы N и M равносильны)

Очевидно, что отношение равносильности формул алгебры логики является:

1) рефлексивным, т.е. N = N для любой формулы N;

2) симметричным, т.е. если N = M, то M = N для любых формул N и M;

3) транзитивным, т.е. если N = M и M = J, то N = J для любых формул N,M,J.

Законы алгебры логики

1) – закон тождества; – закон противоречия; – закон исключительного третьего; – закон двойного отрицания; , – законы идемпотентности; , – законы коммутативности; , – законы дистрибутивности; , – законы ассоциативности;

2) , – законы де Моргана; , , , , – законы поглощения; , – законы склеивания.

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

 

Множество булевых функций, рассматриваемое вместе с операциями отрицания, конъюнкции и дизъюнкции, называют булевой алгеброй.

Теорема 1 Если формулы алгебры логики N и M равносильны, то и двойственные им формулы N^* и M^* равносильны.

НОРМАЛЬНЫЕ ФОРМЫ

Пусть G – параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x ^G = 1, тогда и только тогда, когда
x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . Например, конъюнкция (в которой G₂ = G₁ = 0, G₃ = G₄ = 1) равна 1 только в случае, когда x ₁ = x ₂ = 0, x ₃ = x ₄ = 1.

Теорема 1 Всякая булева функция f(x₁,x₂,…,x_n) может быть представлена в следующей форме:

, (3.1)

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

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

Для того что бы построить СДНФ необходимо: Для каждой такой строки образуем конъюнкцию и затем все полученные конъюнкции соединяем знаком дизъюнкции.

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

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

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

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

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

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

Теорема 4 Формула алгебры логики тогда и только тогда является тождественно истинной, когда каждая дизъюнкция в ее конъюнктивной нормальной форме содержит некоторую переменную вместе с ее отрицанием.

Теорема 5 Формула алгебры логики тогда и только тогда является тождественно ложной, когда каждая конъюнкция в ее дизъюнктивной форме содержит некоторую переменную вместе с ее отрицанием.