АЛГЕБРА ВЫСКАЗЫВАНИЙ

1. Объекты алгебры высказываний
2. Тождественные высказывания. Эквивалентные высказывания
3. Таблицы истинности

Объекты алгебры высказываний. Операции над высказываниями. Таблицы истинности.

Алгебра – это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры – натуральные числа, а операции – сложение и умножение, то это алгебра натуральных чисел. Действия с направленными отрезками (векторами) изучает векторная алгебра. Объектами алгебры высказываний являются высказывания.
Высказывание – это истинное или ложное повествовательное предложение. Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием.
Например, предложение «Луна – спутник Земли» есть простое высказывание, предложение «Не сорить!» не является высказыванием.
Высказывания обозначаются большими буквами латинского алфавита. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0. Как и в других алгебрах, в алгебре высказываний над ее объектами (высказываниями) определены действия, выполняя которые получают новые высказывания.
Объединение двух высказываний в одно при помощи союза «И» называется операцией логического умножения.
Полученное таким образом высказывание называется логическим произведением. Например, высказывание A – «В лесу растут грибы», высказывание B – «Льюис Кэрролл – математик», составим произведение этих высказываний AB – «В лесу растут грибы и Льюис Кэрролл – математик».
Истинность произведения высказываний зависит от истинности перемножаемых высказываний и может быть определена с помощью следующей таблицы:


Объединение двух высказываний в одно с помощью союза «ИЛИ», употребляемого в неисключающем смысле, называется операцией логического сложения. Например, высказывание A – «Декабрь – зимний месяц», В – «Летом иногда идет дождь», определим высказывание A+B – «Декабрь – зимний месяц или летом иногда идет дождь». Установить истинность логической суммы можно с помощью следующей таблицы:


Операция логического отрицания осуществляется над одним высказыванием. Выполнить операцию логического отрицания (обозначается ) – значит получить из данного высказывания новое, присоединяя слова «неверно, что …» ко всему высказыванию.
Истинность высказывания определяется таблицей:

Тождественные высказывания. Эквивалентные высказывания. Формулы Августа де Моргана.

Среди высказываний особое место занимают те, в таблице истинности которых либо одни единицы, либо только нули. Это означает, что высказывание либо всегда истинно, либо ложно, независимо от истинности входящих в него высказываний. Например, высказывание всегда истинно, а высказывание всегда ложно. Доказать это можно составив таблицу истинности этих высказываний.
Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными.
Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем: , . Среди высказываний встречаются такие, таблицы истинности которых совпадают. Эти высказывания называются эквивалентными. Эквивалентными являются, например, высказывания и (то есть ). Это можно проверить составив таблицы истинности этих высказываний:


Операции алгебры высказываний обладают следующими важными свойствами:
Логическое умножение и логическое сложение:
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 веке». Это утверждение согласуется с данными поставленной задачи.

Полезная страничка

Приложение :