Логика высказываний

1.

Логика высказываний
Логика высказываний, называемая также пропозициональной логикой - раздел
математики и логики, изучающий логические формы сложных высказываний, построенных из
простых или элементарных высказываний с помощью логических операций.
Высказываниями принято считать такие предложения (написанные на "словесном"
либо математическом языке), о которых можно сказать одно из двух: либо они являются
истинными, либо ложными.
С математическими высказываний проще всего: они всегда имеют либо значение
"истина", либо значение "ложь". Для высказываний, сделанных на "словесном" языке, понятия
"истинности" и "ложности" несколько более расплывчаты. Однако, например, такие словесные
формы, как "Иди домой" и "Идѐт ли дождь?", не являются высказываниями. Поэтому понятно,
что высказываниями являются такие словесные формы, в которых что-либо
утверждается. Не являются высказываниями вопросительные или восклицательные
предложения, обращения, а также пожелания или требования. Их невозможно оценить
значениями "истина" и "ложь".
Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает
их истинностное значение, то есть является ли высказывание истинным или ложным.
Логические операции над высказываниями
Итак, высказывания можно рассматривать как величину, которая может принимать два
значения: "истина" и "ложь".
Например, даны суждения: "собака - животное", "Париж - столица Италии", "3 < 5", "в
каждом треугольнике биссектриса делит противоположную сторону на две равные части".
Первое из этих высказываний может быть оценено символом "истина", второе - "ложь",
третье - "истина" и четвѐртое - "ложь". Такая трактовка высказываний составляет предмет
алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A, B,
..., а их значения, то есть истину и ложь, соответственно И и Л. В обычной речи употребляются
связи между высказываниями "и", "или" и другие.
Эти связи позволяют, соединяя между собой различные высказывания, образовывать
новые высказывания - сложные высказывания. Например, связка "и". Пусть даны
высказывания: "π больше 3" и высказывание "π меньше 4". Можно организовывать новое сложное высказывание "π больше 3 и π меньше 4". Высказывание "если π иррационально, то π²
тоже иррационально" получается связыванием двух высказываний связкой "если - то". Наконец,
мы можем получить из какого-либо высказывания новое - сложное высказывание - отрицая
первоначальное высказывание.
Рассматривая высказывания как величины, принимающие значения И и Л, мы определим
далее логические операции над высказываниями, которые позволяют из данных высказываний
получать новые - сложные высказывания.
Пусть даны два произвольных высказывания A и B.
1. Логическая операция конъюнкция - представляет собой образование нового
высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда,
когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний
связкой "и".
Таблица истинности для конъюнкции:
A B A∧B
И
И
И
И
Л
Л
Л
И
Л
Л
Л
Л
2. Логическая операция дизъюнкция, выражаемая в виде A ∨ B, определяется
следующим образом: она истинна тогда и только тогда, когда хотя бы одно из первоначальных
1

2.

высказываний истинно. В обычной речи эта операция соответствует соединению высказываний
связкой "или". Однако здесь мы имеем не разделительное "или", которое понимается в смысле
"либо-либо", когда A и B не могут быть оба истинны. В определении логики
высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при
истинности обоих высказываний A и B.
Таблица истинности для дизъюнкции:
A B A∨B
И
И
И
И
Л
И
Л
И
И
Л
Л
И
И
И
И
Л
Л
Л
И
И
Л
Л
Л
3. Логическая операция, выражаемая в виде A → B; полученное таким образом
высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой,
B - следствием, а высказывание A → B - следованием, называемая также импликацией. В
обычной речи эта операция соответствует связке "если - то": "если A, то B". Но в определении
логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно
высказывание B. Это обстоятельство можно кратко сформулировать так: "из ложного следует
всѐ, что угодно". В свою очередь, если A истинно, а B ложно, то всѐ высказывание A → B
ложно. Оно будет истинным тогда и только тогда, когда и A, и B истинны. Кратко это можно
сформулировать так: "из истинного не может следовать ложное".
Таблица истинности для следования (импликации):
A B A→B
И
4. Логическая операция над одним высказыванием - отрицание высказывания A
обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также
верхнего надчѐркивания над A). ¬A есть высказывание, которое ложно, когда A истинно, и
истинно, когда A ложно.
Таблица истинности для отрицания:
A ¬A
Л И
И Л
5. Логическая операция эквивалентность обозначается A ↔ B. Полученное таким
образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба
истинны или оба ложны.
Таблица истинности для эквивалентности:
A B A→B B→A A↔B
И
И
И
И
И
И
Л
Л
И
Л
Л
И
И
Л
Л
Л
Л
И
И
И
В большинстве языков программирования есть специальные символы для обозначения
логических значений высказываний, записываются они почти во всех языках как true (истина) и
false (ложь).
2

3.

Подытожим вышесказанное. Логика высказываний изучает связи, которые полностью
определяются тем, каким образом одни высказывания строятся из других, называемых
элементарными. Элементарные высказывания при этом рассматриваются как целые, не
разложимые на части.
Систематизируем в таблице ниже названия, обозначения и смысл логических операций
над высказываниями (они нам вскоре вновь понадобятся для решения примеров).
Название
Связка
Обозначение
операции
не
¬
отрицание
и
конъюнкция
или
дизъюнкция
если
то...
...,
тогда
только
тогда
и
импликация
эквивалентность
Для логических операций верны законы алгебры логики, которые можно использовать
для упрощения логических выражений. При этом следует отметить, что в логике высказываний
отвлекаются от смыслового содержания высказывания и ограничиваются рассмотрением его с
той позиции, что оно либо истинно, либо ложно.
Пример 1. Вычислите логические значения следующих высказываний:
1) (2 = 2) И (7 = 7);
2) Не(15 < 3);
3) ("Сосна" = "Дуб") ИЛИ ("Вишня" = "Клѐн");
4) Не("Сосна" = "Дуб");
5) (Не(15 < 3)) И (10 > 20);
6) ("Глаза даны, чтобы видеть") И ("Под третьим этажом находится второй этаж");
7) (6/2 = 3) ИЛИ (7*5 = 20).
Решение.
1) Значение высказывания в первых скобках равно "истина", значение выражения во
вторых скобках - также истина. Оба высказывания соединены логической операцией "И"
(смотрим правила для этой операции выше), поэтому логическое значение всего данного
высказывания - "истина".
2) Значение высказывания в скобках - "ложь". Перед этим зтим высказыванием стоит
логическая операция отрицания, поэтому логическое значение всего данного высказывания "истина".
3) Значение высказывания в первых скобках - "ложь", значение высказывания во вторых
скобках - также "ложь". Высказывания соединены логической операцией "ИЛИ" и ни одно из
высказываний не имеет значения "истина". Поэтому логическое значение всего данного
высказывания - "ложь".
4) Значение высказывания в скобках - "ложь". Перед этим высказыванием стоит
логическая операция отрицания. Поэтому логическое значение всего данного высказывания "истина".
5) В первых скобках отрицается высказывание во внутренних скобках. Это
высказывание во внутренних скобках имеет значение "ложь", следовательно, его отрицание
будет иметь логическое значение "истина". Высказывание во вторых скобках имеет значение
"ложь". Два этих высказывания соединены логической операцией "И", то есть получается
"истина И ложь". Следовательно, логическое значение всего данного высказывания - "ложь".
6) Значение высказывания в первых скобках - "истина", значение высказывания во
вторых скобках - также "истина". Два этих высказывания соединены логической операцией "И",
3

4.

то есть получается "истина И истина". Следовательно, логическое значение всего данного
высказывания - "истина".
7) Значение высказывания в первых скобках - "истина". Значение высказывания во
вторых скобках - "ложь". Два этих высказывания соединены логической операцией "ИЛИ", то
есть получается "истина ИЛИ ложь". Следовательно, логическое значение всего данного
высказывания - "истина".
Пример 2. Запишите с помощью логических операций следующие сложные
высказывания:
1) "Пользователь не зарегистрирован";
2) "Сегодня воскресенье и некоторые сотрудники находятся на работе";
3) "Пользователь зарегистрирован тогда и только тогда, когда отправленные
пользователем данные признаны годными".
Решение.
1) p - одиночное высказывание "Пользователь зарегистрирован", логическая
операция:
;
2) p - одиночное высказывание "Сегодня воскресенье", q - "Некоторые сотрудники
находятся на работе", логическая операция:
;
3) p - одиночное высказывание "Пользователь зарегистрирован", q - "Отправленные
пользователем данные признаны годными", логическая операция:
.
Формулы логики высказываний
Понятие логической формы сложного высказывания уточняется с помощью
понятия формулы логики высказываний.
В примерах 1 и 2 мы учились записывать с помощью логических операций сложные
высказывания. Вообще-то они называются формулами логики высказываний.
Для обозначения высказываний, как и упомянутом примере, будем продолжать
использовать буквы
p, q, r, ..., p1, q1, r1, ...
Эти буквы будут играть роль переменных, принимающих в качестве значений
истинностные значения "истина" и "ложь". Эти переменные называются также
пропозициональными переменными. Мы будем далее называть их элементарными
формулами или атомами.
Для построения формул логики высказываний кроме указанных выше букв
используются знаки логических операций
~, ∧, ∨, →, ↔,
а также символы, обеспечивающие возможность однозначного прочтения формул - левая
и правая скобки.
Понятие формулы логики высказываний определим следуюшим образом:
1) элементарные формулы (атомы) являются формулами логики высказываний;
2)
если A и B формулы
логики
высказываний,
то ~A, (A ∧ B), (A ∨ B), (A → B),(A ↔ B) тоже являются формулами логики высказываний;
3) только те выражения являются формулами логики высказываний, для которых это
следует из 1) и 2).
Определение формулы логики высказываний содержит перечисление правил
образования этих формул. Согласно определению, всякая формула логики высказываний либо
есть атом, либо образуется из атомов в результате последовательного применения правила 2).
Пример 3. Пусть p - одиночное высказывание (атом) "Все рациональные числа являются
действительными", q - "Некоторые действительные числа - рациональные числа", r "некоторые рациональные числа являются действительными". Переведите в форму словесных
высказываний следующие формулы логики высказываний:
1)
;
2)
;
3)
;
4

5.

4)
5)
;
;
6)
.
Решение.
1) "нет действительных чисел, которые являются рациональными";
2) "если не все рациональные числа являются действительными, то нет рациональных
чисел, являющихся действительными";
3) "если все рациональные числа являются действительными, то некоторые
действительные числа - рациональные числа и некоторые рациональные числа являются
действительными";
4) "все действительные числа - рациональные числа и некоторые действительные числа рациональные числа и некоторые рациональные числа являются действительными числами";
5) "все рациональные числа являются действительными тогда и только тогда, когда не
имеет место быть, что не все рациональные числа являются действительными";
6) "не имеет места быть, что не имеет место быть, что не все рациональные числа
являются действительными и нет действительных чисел, которые являются рациональными или
нет рациональных чисел, которые являются действительными".
Число скобок в формулах логики высказываний можно уменьшить, если принять, что
1) в сложной формуле будем опускать внешнюю пару скобок;
2) упорядочим знаки логических операций "по старшинству":
↔, →, ∨, ∧, ~ .
В этом списке знак ↔ имеет самую большую область действия, а знак ~ - самую
маленькую. Под областью действия знака операции понимаются те части формулы логики
высказываний, к которым применяется (на которые действует) рассматриваемое вхождение
этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые
можно восстановить, учитывая "порядок старшинства". А при восстановлении скобок сначала
расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы
продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.
Пример 4. Восстановите скобки в формуле логики высказываний B ↔ ~ C ∨ D ∧ A.
Решение. Скобки восстанавливаются пошагово следующим образом:
B ↔ (~ C) ∨ D ∧ A
B ↔ (~ C) ∨ (D ∧ A)
B ↔ ((~ C) ∨ (D ∧ A))
(B ↔ ((~ C) ∨ (D ∧ A)))
Не всякая формула логики высказываний может быть записана без скобок. Например, в
формулах А → (B → C) и ~ (A → B) дальнейшее исключение скобок невозможно.
Тавтологии и противоречия
Логические тавтологии (или просто тавтологии) - это такие формулы логики
высказываний, что если буквы произвольным образом заменить высказываниями (истинными
или ложными), то в результате всегда получится истинное высказывание.
Так как истинность или ложность сложных высказываний зависит лишь от значений, а
не от содержания высказываний, каждому из которых соответствует определѐнная буква, то
проверку того, является ли данное высказывание тавтологией, можно подставить следующим
способом. В исследуемом выражении на место букв подставляются значения 1 и 0
(соответственно "истина" и "ложь") всеми возможными способами и с использованием
логических операций вычисляются логические значения выражений. Если все эти значения
равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даѐт 0, то
это не тавтология.
5

6.

Таким образом, формула логики высказываний, которая принимает значение "истина"
при
любом
распределении
значений
входящих
в
эту
формулу
атомов,
называется тождественно истинной формулой или тавтологией.
Противоположный смысл имеет логическое противоречие. Если все значения
высказываний равны 0, то выражение есть логическое противоречие.
Таким образом, формула логики высказываний, которая принимает значение "ложь" при
любом распределении значений входящих в эту формулу атомов, называется тождественно
ложной формулой или противоречием.
Кроме тавтологий и логических противоречий существуют такие формулы логики
высказываний, которые не являются ни тавтологиями, ни противоречиями.
Пример 5. Составьте таблицу истинности для формулы логики высказываний
и определите, является ли она тавтологией, противоречием или ни тем, ни другим.
Решение. Составляем таблицу истинности:
И
И
И
И
И
И
Л
Л
Л
И
Л
И
Л
И
И
Л
Л
Л
Л И
В значениях импликации не встречаем строку, в которой из "истины" следует "ложь".
Все значения исходного высказывания равны "истине". Следовательно, данная формула логики
высказываний является тавтологией.
**Заставляем компьютер понимать "если ..., то..."
То, что мы называем логическими операциями, впервые появилось предположительно в
Древней Греции для доказательства философских постулатов. А в наше время логические
операции наиболее широко применяются в компьютерной технике. Но при всѐм этом
компьютер "не умеет" выполнять логическую операцию импликации. Она компьютеру "не
понятна". Есть, однако, способ заставить компьютер понимать условие "если ..., то",
соответствующее, как известно, импликации. Для этого вместо составного оператора "если p,
то q" нужно использовать составной оператор "не p или q". То есть,
вместо
.
Как видно ниже, таблица истинности для такой замещающей логической операции
идентична таблице истинности для импликации.
И
И
И
И
Л
Л
Л
И
И
Л
Л
И
Пример 6. Перепишите формулу логики высказываний
использования импликации и эквиваленции, пользуясь тождеством
де Моргана:
без
и законами
;
.
Решение.
Заменяем импликацию между двумя парами скобок, отрицая самый левый знак
отрицания:
.
Убираем эквиваленцию между p и q и между q и не r:
6

7.

.
Используя закон де Моргана, немного упрощаем и окончательно получаем:
.
Посылки и выводы. Валидный и не валидный аргумент
Пусть есть высказывания, которые можно назвать посылками. Пусть также есть
высказывание, которое можно назвать выводом. Словосочетание "можно назвать" используется
при условии, что посылки связываются с выводом. То есть, из посылок логически следует
вывод. Тогда, если посылки имеют значения "истина" и вывод тоже имеет значение "истина", то
аргумент является валидным. Если же посылки имеют значения "истина", а вывод имеет
значение "ложь", то аргумент не является валидным. Синонимы понятия "валидность" (в
рассматриваемом здесь значении) - "логическая правильность", "резонность".
Пример валидного аргумента:
Посылка. A и B - программисты
Посылка. A и B разрабатывают программы для бухгалтеров
Вывод. Есть программисты, которые разрабатывают программы для бухгалтеров
То есть, из посылок логически следует вывод.
Пример не валидного аргумента:
Посылка. Запись числа может содержать запятую
Посылка. В предложении может быть запятая
Вывод. Есть числа, которые называются предложениями
То есть, из посылок логически не следует вывод.
Пример 7. Проверьте валидность аргумента, если
Посылка.
Посылка.
Вывод.
Решение. Составляем таблицу истинности:
И
И
Л
И
И
И
И
Л
Л
Л
Л
И
Л
И
И
И
И
Л
Л
Л
И
И
И
И
В третьей строке обе посылки истинны, а вывод - ложный. Следовательно, аргумент не
валидный. Таким образом, в аналогичных задачах подозрительными являются те строки, в
которых все посылки истинны. Если вывод также истинный, то аргумент валидный, если
ложный, то аргумент не валидный, как в этом примере. Если же посылки или обе ложны, или
ложна одна из них, то такие строки не играют роли в проверке аргумента на валидность, каким
бы ни было значение вывода.
7