Компьютеры
и программирование

Логика высказываний: теория и применение. Примеры решений задач

Логика высказываний: определение и применение

Логика высказываний, называемая также пропозициональной логикой - раздел математики и логики, изучающий логические формы сложных высказываний, построенных из простых или элементарных высказываний с помощью логических операций.

Высказываниями принято считать такие предложения (написанные на "словесном" либо математическом языке), о которых можно сказать одно из двух: либо они являются истинными, либо ложными.

Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает их истинностное значение, то есть является ли высказывание истинным или ложным.

Логика высказываний широко применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений "ложь" или "истина", от которых зависит ход дальнейшего исполнения программы. В простейших случаях, в небольших программах, в которых задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, "флаг" ("flag") и подразумевается, что "флаг поднят", когда значение этой переменной - "истина" и "флаг опущен", когда значение этой переменной - "ложь". Однако в программах большого объёма, в которых несколько или даже много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

Например, может быть объявлена логическая переменная с именем "ПользовательЗарегистрирован" (или его англоязычный аналог), имеющим форму высказывания, которой может быть присвоено логическое значение "истина" при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения тех или иных переменных может меняться в зависимости от того, какое логическое значение ("истина" или "ложь") имеет переменная "ПользовательЗарегистрирован". В других случах переменной, например, с именем "ДоДняХОсталосьБолееТрёхДней", может быть присвоено значение "Истина" до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на "ложь" и от значения этой переменной зависит ход дальнейшего исполнения программы.

Если в программе используются несколько логических переменных, имена которых имеют форму высказываний, и из них строятся более сложные высказывания, то намного проще разрабатывать программу, если перед её разработкой записать все операции с высказываний в виде формул, применяемых в логике высказываний, чем мы в ходе этого урока и займёмся.

Логика высказываний часто рассматривается в общефилософском контексте и в контексте исследования различных вопросов философии.

Логические операции над высказываниями

Для математических высказываний всегда можно сделать выбор между двумя различными альтернативами "истина" и "ложь", а для высказываний, сделанных на "словесном" языке, понятия "истинности" и "ложности" несколько более расплывчаты. Однако, например, такие словесные формы, как "Иди домой" и "Идёт ли дождь?", не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается. Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями "истина" и "ложь".

Высказывания же, напротив, можно рассмотривать как величину, которая может принимать два значения: "истина" и "ложь".

Например, даны суждения: "собака - животное", "Париж - столица Италии", "3 < 5", "в каждом треугольнике биссекрисса делит противоположную сторону на две равные части".

Первое из этих высказываний может быть оценено символом "истина", второе - "ложь", третье - "истина" и четвёртое - "ложь". Такая трактовка высказываний составляет предмет алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A, B, ..., а их значения, то есть истину и ложь, соответственно И и Л. В обычной речи употребляются связи между высказываниями "и", "или" и другие.

Эти связи позволяют, соединяя между собой различные высказывания, образовывать новые высказывания - сложные высказывания. Например, связка "и". Пусть даны высказывания: "π больше 3" и высказывание "π меньше 4". Можно организовывать новое - сложное высказывание "π больше 3 и π меньше 4". Высказывание "если π иррационально, то π² тоже иррационально" получается связыванием двух высказываний связкой "если - то". Наконец, мы можем получить из какого-либо высказывания новое - сложное высказывание - отрицая первоначальное высказывание.

Рассматривая высказывания как величины, принимающие значения И и Л, мы определим далее логические операции над высказываниями, которые позволяют из данных высказываний получать новые - сложные высказывания.

Пусть даны два произвольных высказывания A и B.

1. Первая логическая операция над этими высказываниями - конъюнкция - представляет собой образование нового высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой "и".

Таблица истинности для конъюнкции:

ABA ∧ B
ИИИ
ИЛЛ
ЛИЛ
ЛЛЛ

2. Вторая логическая операция над высказываниями A и B - дизъюнкция, выражаемая в виде A ∨ B, определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой "или". Однако здесь мы имеем не разделительное "или", которое понимается в смысле "либо-либо", когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B.

Таблица истинности для дизъюнкции:

ABA ∨ B
ИИИ
ИЛИ
ЛИИ
ЛЛЛ

3. Третья логическая операция над высказываниями A и B, выражаемая в виде A → B; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой, B - следствием, а высказывание A → B - следованием, называемая также импликацией. В обычной речи эта операция соответствует связке "если - то": "если A, то B". Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B. Это обстоятельство можно кратко сформулировать так: "из ложного следует всё, что угодно". В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A, и B истинны. Кратко это можно сформулировать так: "из истинного не может следовать ложное".

Таблица истинности для следования (импликации):

ABA → B
ИИИ
ИЛЛ
ЛИИ
ЛЛИ

4. Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также верхнего надчёркивания над A). ~ A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

AA
ЛИ
ИЛ

5. И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B. Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.

Таблица истинности для эквивалентности:

ABA → BB → AA ↔ B
ИИИИИ
ИЛЛИЛ
ЛИИЛЛ
ЛЛИИИ

В большинстве языков программирования есть специальные символы для обозначения логических значений высказываний, записываются они почти во всех языках как true (истина) и false (ложь).

Подытожим вышесказанное. Логика высказываний изучает связи, которые полностью определяются тем, каким образом одни высказывания строятся из других, называемых элементарными. Элементарные высказывания при этом рассматриваются как целые, не разложимые на части.

Систематизируем в таблице ниже названия, обозначения и смысл логических операций над высказываниями (они нам вскоре вновь понадобятся для решения примеров).

СвязкаОбозначениеНазвание операции
неотрицание
иконъюнкция
илидизъюнкция
если ..., то...импликация
тогда и только тогдаэквивалентность

Для логических операций верны законы алгебры логики, которые можно использовать для упрощения логических выражений. При этом следует отметить, что в логике высказываний отвлекаются от смыслового содержания высказывания и ограничиваются рассмотрением его с той позиции, что оно либо истинно, либо ложно.

Пример 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) Значение высказывания в первых скобках - "истина", значение высказывания во вторых скобках - также "истина". Два этих высказывания соединены логической операцией "И", то есть получается "истина И истина". Следовательно, логическое значение всего данного высказывания - "истина".

7) Значение высказывания в первых скобках - "истина". Значение высказывания во вторых скобках - "ложь". Два этих высказывания соединены логической операцией "ИЛИ", то есть получается "истина ИЛИ ложь". Следовательно, логическое значение всего данного высказывания - "истина".

Пример 2. Запишите с помощью логических операций следующие сложные высказывания:

1) "Пользователь не зарегистрирован";

2) "Сегодня воскресенье и некоторые сотрудники находятся на работе";

3) "Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными".

Решение.

1) p - одиночное высказывание "Пользователь зарегистрирован", логическая операция: ;

2) p - одиночное высказывание "Сегодня воскресенье", q - "Некоторые сотрудники находятся на работе", логическая операция: ;

3) p - одиночное высказывание "Пользователь зарегистрирован", q - "Отправленные пользователем данные признаны годными", логическая операция: .

Формулы логики высказываний

Понятие логической формы сложного высказывания уточняется с помощью понятия формулы логики высказываний.

В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания. Вообще-то они называются формулами логики высказываний.

Для обозначения высказываний, как и упомянутом примере, будем продолжать использовать буквы

pqr, ..., p1q1r1, ...

Эти буквы будут играть роль переменных, принимающих в качестве значений истинностные значения "истина" и "ложь". Эти переменные называются также пропозициональными переменными. Мы будем далее называть их элементарными формулами или атомами.

Для построения формул логики высказываний кроме указанных выше букв используются знаки логических операций

~, ∧, ∨, →, ↔,

а также символы, обеспечивающие возможность однозначного прочтения формул - левая и правая скобки.

Понятие формулы логики высказываний определим следуюшим образом:

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) ;

6) .

Решение.

1) "нет действительных чисел, которые являются рациональными";

2) "если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными";

3) "если все рациональные числа являются действительными, то некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными";

4) "все действительные числа - рациональные числа и некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными числами";

5) "все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными";

6) "не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными".

Пример 4. Составьте таблицу истинности для формулы логики высказываний , которую в таблице можно обозначить f.

Решение. Составление таблицы истинности начинаем с записи значений ("истина" или "ложь") для одиночных высказываний (атомов) p, q и r. Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно "лжи" тогда, когда из "истины" следует "ложь".

pqrf
ИИИИИИИИ
ИИЛИИИЛИ
ИЛИИЛЛЛЛ
ИЛЛИЛЛИИ
ЛИИЛИЛИИ
ЛИЛЛИЛИЛ
ЛЛИИИИИИ
ЛЛЛИИИЛИ

Заметим, что никакой атом не имеет вида ~A, (A ∧ B), (A ∨ B), (A → B), (A ↔ B). Такой вид имеют сложные формулы.

Число скобок в формулах логики высказываний можно уменьшить, если принять, что

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций "по старшинству":

↔, →, ∨, ∧, ~ .

В этом списке знак ↔ имеет самую большую область действия, а знак ~ - самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая "порядок старшинства". А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 5. Восстановите скобки в формуле логики высказываний 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, то это не тавтология.

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

Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.

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

Кроме тавтологий и логических противоречий существуют такие формулы логики высказываний, которые не являются ни тавтологиями, ни противоречиями.

Пример 6. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

ИИИИИ
ИЛЛЛИ
ЛИЛИИ
ЛЛЛЛИ

В значениях импликации не встречаем строку, в которой из "истины" следует "ложь". Все значения исходного высказывания равны "истине". Следовательно, данная формула логики высказываний является тавтологией.

Пример 7. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

ИИИИИИ
ИИЛИЛЛ
ИЛИЛИИ
ИЛЛЛЛИ
ЛИИЛИИ
ЛИЛЛЛИ
ЛЛИЛИИ
ЛЛЛЛЛИ

Среди значений данного высказывания одно - "ложь", остальные - "истина". Следовательно, данная формула логики высказываний не является ни тавтологией, ни противоречием.

Заставляем компьютер понимать "если ..., то..."

То, что мы называем логическими операциями, впервые появилось предположительно в Древней Греции для доказательства философских постулатов. А в наше время логические операции наиболее широко применяются в компьютерной технике. Но при всём этом компьютер "не умеет" выполнять логическую операцию импликации. Она компьютеру "не понятна". Есть, однако, способ заставить компьютер понимать условие "если ..., то", соответствующее, как известно, импликации. Для этого вместо составного оператора "если p, то q" нужно использовать составной оператор "не p или q". То есть, вместо .

Как видно ниже, таблица истинности для такой замещающей логической операции идентична таблице истинности для импликации.

ИИИ
ИЛЛ
ЛИИ
ЛЛИ

Пример 8. Перепишите формулу логики высказываний без использования импликации и эквиваленции, пользуясь тождеством и законами де Моргана:

;

.

Решение.

Заменяем импликацию между двумя парами скобок, отрицая самый левый знак отрицания:

.

Убираем эквиваленцию между p и q и между q и не r:

.

Используя закон де Моргана, немного упрощаем и окончательно получаем:

.

Посылки и выводы. Валидный и не валидный аргумент

Пусть есть высказывания, которые можно назвать посылками. Пусть также есть высказывание, которое можно назвать выводом. Словосочетание "можно назвать" используется при условии, что посылки связываются с выводом. То есть, из посылок логически следует вывод. Тогда, если посылки имеют значения "истина" и вывод тоже имеет значение "истина", то аргумент является валидным. Если же посылки имеют значения "истина", а вывод имеет значение "ложь", то аргумент не является валидным. Синонимы понятия "валидность" (в рассматриваемом здесь значении) - "логическая правильность", "резонность".

Пример валидного аргумента:

  • Посылка. A и B - программисты
  • Посылка. A и B разрабатывают программы для бухгалтеров
  • Вывод. Есть программисты, которые разрабатывают программы для бухгалтеров

То есть, из посылок логически следует вывод.

Пример не валидного аргумента:

  • Посылка. Запись числа может содержать запятую
  • Посылка. В предложении может быть запятая
  • Вывод. Есть числа, которые называются предложениями

То есть, из посылок логически не следует вывод.

Пример 9. Проверьте валидность аргумента, если

  • Посылка.
  • Посылка.
  • Вывод.

Решение. Составляем таблицу истинности:

ИИЛИИИ
ИЛЛЛЛИ
ЛИИИИЛ
ЛЛИИИИ

В третьей строке обе посылки истинны, а вывод - ложный. Следовательно, аргумент не валидный. Таким образом, в аналогичных задачах подозрительными являются те строки, в которых все посылки истинны. Если вывод также истинный, то аргумент валидный, если ложный, то аргумент не валидный, как в этом примере. Если же посылки или обе ложны, или ложна одна из них, то такие строки не играют роли в проверке аргумента на валидность, каким бы ни было значение вывода.