Представление логических операций

Пусть дана некоторая совокупность высказываний (q₁,q₂,..q_n ) каждое из которых может быть истинно или ложно. Всю совокупность высказываний можно рассматривать как кортеж или вектор. Если над этими высказываниями произвести логические операции, то получим некоторое новое высказывание q Î {1,0}. Поэтому при выполнении операций над (n – м) числом высказываний получим функцию:

q = f (q₁, q₂, …, q_n) , (1)

которую называют булевой функцией. Особенность этой функции состоит в том, что как аргумент q_i , так и сама функция могут принимать одно из двух значений на множестве {1,0}. Для представления функций используют три способа.

1. В виде формулы вида (1).

2. Табличный способ, как, например, для операции конъюнкции

3. В виде графической схемы

Алгебра логики

Исчисление высказываний оперирует с формулами алгебры логики.

1. Двойственность формул булевой алгебры.

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

x Ù ( y Ú z Ù ( k Ú m ) ) ® x Ú y Ù ( z Ú k Ù m ).

На основе законов де Моргана выводится положение, по которому, если формула и существующая ей двойственная формула равны, то формулы

.

Нормальные формы

В булевой алгебре существуют два вида нормальных форм. Это

- дизъюнктивная нормальная форма (ДНФ) и

- конъюнктивная нормальная форма (КНФ). Дадим их определения.

Дизъюнктивная нормальная форма ¾ это дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию отдельных переменных или их отрицаний, входящих в заданный член не более одного раза.

Конъюнктивная нормальная форма ¾ это конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию отдельных переменных или их отрицаний, входящих в заданный член не более одного раза.

Любая заданная формула приводится к нормальной форме по следующему алгоритму:

1. По законам де Моргана формула преобразуется к такому виду, чтобы операция отрицания относилась только к одному элементу

, .

2. На основе распределительного закона свести исходную формулу к дизъюнкции конъюнкций или конъюнкции дизъюнкций

( x Ú y ) Ù z = ( x Ù z ) Ú ( y Ù z ) , ( x Ù y ) Ú z = ( x Ú z ) Ù ( y Ú z ).

3. Полученное выражение упрощают, используя тождества и законы булевой алгебра

, , , .

Пример:

Получили дизъюнктивную нормальную форму. Слагаемыми ДНФ являются элементарные конъюнкции, состоящие в общем случае из n переменных. Каждое слагаемое называется минитермом n-го ранга, где n указывает количество переменных в нём. В данном примере триминитерма; xy – минитерм 2-го ранга (у него две переменных), xyz и yzv – минитермы 3-го ранга (в каждом из них по три переменных).

Приведем теперь это выражение к КНФ:

Полученное выражение представляет собой конъюнкцию от дизъюнкций. Здесь каждый сомножитель является макситермом 2-го ранга, т.к. в них в каждом сомножителе по две переменных.

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