Объектами алгебры высказываний
являются высказывания. Высказывание – это истинное или ложное повествовательное предложение. Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием. Например, предложение «Луна – спутник Земли» есть простое высказывание, предложение «Не сорить!» не является высказыванием.
Высказывания обозначаются большими буквами латинского алфавита. Если высказывание
A истинно, то пишут A = 1, если ложно, то используют запись A = 0. Как и в других алгебрах, в алгебре высказываний над ее объектами (высказываниями) определены действия, выполняя которые получают новые высказывания. Объединение двух высказываний в одно при помощи союза «И» называется операцией логического умножения. Полученное таким образом высказывание называется логическим произведением. Например, высказывание A – «В лесу растут грибы», высказывание B – «Льюис Кэрролл – математик», составим произведение этих высказываний AB – «В лесу растут грибы и Льюис Кэрролл – математик». Истинность произведения высказываний зависит от истинности перемножаемых высказываний и может быть определена с помощью следующей таблицы:
|
А |
В |
АВ |
|
1 |
1 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
|
0 |
0 |
0 |
Объединение двух высказываний в одно с помощью союза «ИЛИ», употребляемого в неисключающем смысле, называется операцией логического сложения. Например, высказывание A – «Декабрь – зимний месяц», В – «Летом иногда идет дождь», определим высказывание A+B – «Декабрь – зимний месяц или летом иногда идет дождь». Установить истинность логической суммы можно с помощью следующей таблицы:
|
А |
В |
А+В |
|
1 |
1 |
1 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
0 |
0 |
0 |
Операция логического отрицания осуществляется над одним высказыванием. Выполнить операцию логического отрицания (обозначается 
) – значит получить из данного высказывания новое, присоединяя слова «неверно, что …» ко всему высказыванию. Истинность высказывания 
определяется таблицей:
 |
 |
|
1 |
0 |
|
0 |
1 |
Пользуясь определенными выше операциями, можно из простых высказываний образовывать сложные. Например, всевозможные значения для высказывания 
можно записать в виде таблицы
|
A |
B |
 |
 |
 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
1 |
Тождественные высказывания. Эквивалентные высказывания. Формулы Августа де Моргана. Среди высказываний особое место занимают те, в таблице истинности которых либо одни единицы, либо только нули. Это означает, что высказывание либо всегда истинно, либо ложно, независимо от истинности входящих в него высказываний. Например, высказывание 
всегда истинно, а высказывание 
всегда ложно. Доказать это можно составив таблицу истинности этих высказываний.
Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными.
Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем:
, 
. Среди высказываний встречаются такие, таблицы истинности которых совпадают. Эти высказывания называются эквивалентными. Эквивалентными являются, например, высказывания 
и 
(то есть 
). Это можно проверить составив таблицы истинности этих высказываний:
|
A |
B |
 |
 |
 |
 |
 |
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
Операции алгебры высказываний обладают следующими важными свойствами:
| Логическое умножение: | Логическое сложение: |
| A·B = B·A | A + B = B + A |
| (AB)C = A(BC) | (A + B)+ C = A + (B + C) |
| A·A = A | A + A = A |
| A·1 = A | A + 1 = 1 |
| A·0 = 0 | A + 0 = A |
| A(B + C) = AB + AC | A + BC = (A + B)(A + C)A + BC = (A + B)(A + C) |
 |
 |
Отрицание: 
Формулы, выделенные жирным шрифтом, называются формулами Августа де Моргана (1806–1871). Используя эти формулы, можно, в частности, преобразовывать высказывания: сложные заменять более простыми.
В алгебре высказываний, как и в другой алгебре, возможны тождественные преобразования, но логическое сложение и умножение обладают специфическими свойствами
A + A = A, AA = A, A + 1 = A. Это приводит к необычности действий над многочленами алгебры высказываний. Пусть нужно перемножить два сложных высказывания:
(
A + B)(A + C) = AA + AC + AB + BC = A + AB + AC + BC. Рассмотрим теперь два первых слагаемых A + AB = A(1 + B) = A1 = A и аналогично A+ AC = A. Таким образом, окончательно получаем (A + B)(A + C) = A+ BC. Преобразование A + AB = A очень часто встречается в алгебре высказываний и называется «поглощение». Есть еще один вид столь же часто встречающегося тождественного преобразования, которое называется «склеивание».
Суть его состоит в следующем:
(склеивание произошло по символу B). Соответственно для сложного высказывания 
склейку можно произвести по символу 
, то есть имеет место тождественное преобразование 
. Решение логических задач. Рассмотренных выше законы алгебры высказываний могут быть применены к решению логических задач Например:
Задача:
Алеша, Боря и Гриша откопали древний сосуд. О том, где и когда он был изготовлен, каждый из школьников высказал по два предположения:
Алеша: «Это сосуд греческий и сосуд изготовлен в
V веке»;
Боря: «Это сосуд финикийский и сосуд изготовлен в
III веке»;
Гриша: «Это не греческий сосуд и изготовлен он в
IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном их двух своих предположений. Где и в каком веке изготовлен сосуд?
Решение:
Введем обозначения простых высказываний:
«Это сосуд греческий»
– 
; «Это сосуд финикийский» – F; «Сосуд изготовлен в V веке» – 5; «Сосуд изготовлен в III веке» – 3; «Сосуд изготовлен в IV веке» – 4. Можно составить формулы высказываний каждого из школьников с учетом высказывания учителя. Формула Алешиного высказывания имеет вид G5. Учитель сказал, что Алеша прав только в одном из своих утверждений, поэтому либо G = 1, либо 5 = 1. Истинным будет высказывание 
, то есть высказывание «Сосуд греческий и изготовлен не в 5 веке или сосуд не греческий и изготовлен в 5 веке». Аналогично, высказывание Бори можно представить формулой 
и высказывание Гриши формулой 
. Полученные формулы можно рассматривать как логические уравнения и решать систему: 
. Первое высказывание умножается на второе: 
. Произведение 
– ложно потому, что сосуд не может быть изготовлен одновременно в Греции и Финикии, произведение 
– ложно потому, что сосуд не может быть изготовлен одновременно в 3 и 5 вв. После исключения этих высказываний получается следующее уравнение: 
. Это уравнение умножается на третье логическое уравнение составленной системы: 
. Высказывания 
исключены как ложные. Из полученного высказывания 
следует, что «Сосуд изготовлен в Финикии и сосуд изготовлен в 5 веке». Это утверждение согласуется с данными поставленной задачи.
На примере решения логической задачи продемонстрирована смысловая взаимосвязь входящих в сложное высказывание простых высказываний. В состав сложных высказываний могут входить взаимосвязанные по смыслу высказывания, однако Высказывания могут быть и противоречивыми. Таким образом, одним из применений алгебры высказываний является использование ее для анализа сложных
, а подчас противоречивых текстов. Алгебра высказываний позволяет научиться моделировать простейшие мыслительные процессы. «Методы эти позволяют Вам обрести ясность мысли, способность находить собственное оригинальное решение трудных задач, вырабатывают у Вас привычку к систематическому мышлению и, что особенно ценно, умение обнаруживать логические ошибки, изъяны и пробелы тех, кто не пытался овладеть привлекательным искусством логики. Попытайтесь. Вот все, о чем я прошу вас», – Льюис Кэрролл (псевдоним Чарльза Лютвиджа Доджсона (1832–1898)) – известный английский математик и литератор. Анна Чугайнова
Касаткин В.Н., Верлань А.Ф. Секреты кибернетики. Киев, «Радянська школа», 1971
Возлинская М.В. Нестандартная математика в школе. Москва, «Лайда», 1993
Логика и комбинаторика. Составитель А.А. Егоров. Приложение к журналу КВАНТ, 2002, № 5