Шпаргалка (Архив шпаргалок для РК и экзамена), страница 3

Заметим, что отрицание - это унарная операция, определенная на множестве высказыва­ний А и соответствующая конструкции = {Не ... }, если а = {…} - высказывание. Далее на множестве высказываний А определим бинарные операции.

Определение 3.4. Конъюнкцией высказываний аиb называется высказывание, обозна­чаемое а b или а ∙ b и определяемое таблицей:

О

0	0	0
0	1	0
1	0	0
1	1	1

чевидны следующие свойства конъюнкции:

1. а b≡ b а- коммутативность;

2. а (b с) = (а b) с - ассоциативность;

3. a 1 ≡а;

4. a 0 ≡ 0;

5. a a ≡ а.

Заметим, что здесь, и в дальнейшем символом 0 мы обозначаем ложное высказывание, а символом 1 - истинное. Конъюнкция, логическое умножение, соответствует союзу "и" в

русском языке. Например, если высказывание а ≡ (− − −), b ≡ (***), то высказывание

а b = ((− − −) и (* * *)).

Определение 3.5. Дизъюнкцией высказываний а и b называется высказывание, обозна­чаемое а b и определяемое следующей таблицей истинности:

а	b	а b
0	0	0
0	1	1
1	0	1
1	1	1

Очевидны следующие свойства дизъюнкции:

1) а b = b а - коммутативность;

2) а (b с) ≡ (а b) с - ассоциативность;

3) a 1 ≡ 1; 4) a 0 ≡ а; 5) a a ≡ а.

Дизъюнкция, логическое сложение, соответствует союзу "или" в русском языке. Если вы­сказывание а = (-----), высказывание b = (***), то высказывание а b = ((-----)или(***)).

Определенные нами на множестве высказываний А операции: отрицание, конъюнкция, дизъюнкция, - называются булевыми операциями. Алгебраическая структура (А, , , ) называется булевой алгеброй, так как в ней выполняются следующие 19 равносильностей для булевых операций.

. Нормальные формы в алгебре высказываний: СДНФ, СКНФ.

СДНФ

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

f(x₁,x₂,..,x_n)  (x₁^1.x₂^2…^.x_n^n),

_сн(₁,₂,..,_n ) | f(₁,₂,..,_n)1 - СДНФ данной формулы.

Пусть f(x₁,x₂,..,x_n) - формула в алгебры высказываний

Разложим эту формулу по переменной x₁

Тогда: f(x₁,x₂,..,x_n)_снизу(₁E₂) x₁^1(₁,x₂,..,x_n)  (разложим по x₂ и подставим в разложение)   _снизу (₁E₂)( _снизу (₂E₂) x₁^1.x₂^2f(₁,₂,x₃,..,x_n))…и т.д. 

  _снизу (₁,₂,..,_n ) x₁^1.x₂^2…^.x_n^n f(₁,₂,..,_n),

где f(₁,₂,..,_n) - 0 or 1

Мы можем опустить те слагаемые, для которых f(₁,₁,..,_n)0, и получим

f(x₁,x₂,..,x_n) _снизу [(₁,₂,..,_n) | f(₁,₂,..,_n)1] x₁^1.x₂^2…^.x_n^n

СКНФ, КНФ, ДНФ

Теорема: Для любой формулы в алгебры высказываний, отличной от тождественно истинной существует ее представление в виде:

f(x₁,x₂,..,x_n) (x₁^1x₂^2…x_n^n) _снизу [(₁,₂,..,_n) | f(₁,₂,..,_n)0] - СКНФ данной формулы.

При доказательстве используем принцип двойственности

СКНФ->СДНФ Двойной двойственностью:

f(x₁,x₂,..,x_n)(f*( x₁,x₂,..,x_n))*[не явл.≡0=>СДНФ](x₁^1.x₂^2…^.x_n^n)*≡

(₁,₂,..,_nE₂)|f*(₁,₂,..,_n)1

≡ [f(x₁,x₂,..,x_n)]  x₁^1x₂^2…x_n^n,

(₁,₂,..,_n)|f(₁,₂,..,_n)0

Пр: x₁→x₂ ≡ ( x₂) [CКНФ] ≡ (x₂ )x₂(x₁ )≡

≡ x₂ x₁x₂ x₂ ≡ x₂ x₁x₂ [СДНФ]

КНФ, ДНФ

Обозначим V={x₁,x₁,x₂,x ₂,..,x_n,x_n}

Элементарная конъюнкция - конъюнкция всех элементов множества υ  V

По опр: ДНФ –дизъюнкция элементарных конъюнкций

Пр: x₁x₂x₃

Аналогично:

Элементарная дизъюнкция - дизъюнкция всех элементов множества υ  V

КНФ – конъюнкция элементарных дизъюнкций.

Змч.: СДНФ является ДНФ, СКНФ является КНФ