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

Логика высказываний. Тавтологии. Предпосылки и выводы

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

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

Тавтологии и противоречия

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

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

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

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

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

Например, даны суждения: "собака - животное", "Париж - столица Италии", "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. Пусть p - одиночное высказывание "Все рациональные числа являются действительными", q - "Некоторые действительные числа - рациональные числа", r - "некоторые рациональные числа являются действительными". Переведите в форму словесных высказываний данные логические операции:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Решение.

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

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

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

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

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

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

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

1) "Иван не любит Марью";

2) "сегодня суббота, но я должен идти в школу";

3) "трава мокрая тогда и только тогда, когда шёл дождь".

Решение.

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

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

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

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

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

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

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

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

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

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

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

;

.

Решение.

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

.

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

.

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

.

Тавтологии и противоречия

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

Так как истинность или ложность сложных высказываний зависит лишь от значений, а не от содержания высказываний, каждому из которых соответствует определённая буква, то проверку того, является ли данное высказывание тавтологией, можно подставить следующим способом. В исследуемом выражении на место букв подставляются значения 1 и 0 (соответственно "истина" и "ложь") всеми возможными способами и с использованием логических операций вычисляются логические значения выражений. Если все эти значения равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даёт 0, то это не тавтология.

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

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

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

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

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

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

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

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

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

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

Валидный и не валидный аргумент

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

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

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

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

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

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

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

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

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

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

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

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