Высказывание. Операции над высказываниями. Булева алгебра высказываний

Алгебра высказываний.
Основным понятием в этом параграфе является высказывание. В определении, которое следует далее, мы используем интуитивные представления о том, что есть истина и что - ложь.
Определение 3.1. Высказывание - это повествовательное предложение, о котором мож¬но сказать, истинно оно или ложно.
Рассмотрим следующие предложения.
1) 2 + 2 = 4.
2) Для любого х из R выполняется неравенство х2 + 1 < 0.
3) Город Москва является столицей России.
4) Если x R, то x2 - 1 < 0.
5) Длина отрезка меньше площади треугольника.
Предложения 1) и 3) - истинные высказывания; 2) - ложное высказывание; предложения 4) и 5) не являются высказываниями.
Пусть А - множество всех высказываний, Е2 = {0,1}. Определим отображение â : А —> Е2 следующим образом: â = 0, если a - ложное высказывание; â = 1, если а - истинное высказывание. При этом â назовем значением истинности высказывания а.
Определение 3.2. Выск-ия а и b будем называть равносильными и писать а ≡ b, если â = .
Заметим, что это определение - естественно, так как при рассмотрении высказываний нас не интересует содержательная часть, заключенная в предложении, а интересует только значение его истинности.
На множестве всех высказываний с помощью значений истинности определим следующие операции, которые называют логическими.
Определение 3.3. Отрицанием высказывания а называется высказывание, обозначае¬мое , определяемое следующей таблицей:

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

Определение 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 равносильностей для булевых операций.
Теорема 3.6. Справедливы следующие 19 равносильностей для булевых операций алгебры высказываний:
• 1) ≡ а - закон двойного отрицания;
• 2) a b≡ b  a,
• 3) а b ≡ b а - законы коммутативности;
• 4) a  (b  c) ≡ (a  b)  с,
• 5) а  (b  с) ≡ (а  b)  с - законы ассоциативности;
• 6) a  (bc) ≡ (a b)  (a с),
• 7) а  (b  с)≡ (а  b)  (а  с) - законы дистрибутивности;
• 8) a  a ≡ а,
• 9) а  а ≡ а - законы идемпотентности;
• 10) ≡  ,
• 11) ≡  - законы де Моргана;
• 12) a  1 ≡ а,
• 13) а 1 ≡ 1,
• 14) a  0 ≡ 0,
• 15) а 0 ≡ а - законы нуля и единицы;
• 16) а (a b) ≡ а,
• 17) а  (а  b) ≡ а - законы поглощения;
• 18) а  ≡ 0 - закон противоречия;
• 19) a = 1 - закон исключения третьего.
Любую из перечисленных равносильностей получаем с помощью таблиц истинности, определяющих булевы операции.
Кроме булевых, в алгебре высказываний определяются еще две очень важные логические операции: импликация и эквиваленция. Если а = (-----), b = (***) - высказывания, то импликации этих высказываний соответствует конструкция (если(-----),то(***)), а эквиваленции соответствует конструкция ((-----)тогда и только тогда, когда(***)).
а b а → b
0 0 1
0 1 1
1 0 0
1 1 1
Определение 3.7. Импликацией высказываний а и b называется высказывание, обозна¬чаемое а→bи определяемое следующей таблицей:
Очевидны следующие свойства импликации высказываний:
1) a →b≠ b→a;
2) a →a≡1;
3) 0 →a≡1;
4) 1 →a≡a
5) a →1≡1
6) a→0≡

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

Очевидны следующие свойства эквиваленции высказываний:
1) a~b ≡ b~a ≡ ~ ;
2) a ~ 1 ≡ а;
3) a ~ 0 ≡ а.

Теорема 3.9. Справедливы следующие равносильности:
1) а→b ≡ b;
2) а ~ b ≡ (а → b)  (b → а) ≡ (а  b)  (а  b).
а b а ~ b
0 0 1
0 1 0
1 0 0
1 1 1

Теорема легко доказывается с помощью таблиц истинности, определяющих операции.

Powered by Drupal - Design by artinet