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

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

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

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

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

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

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

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

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

Примеры высказываний:

1) сегодня понедельник;

2) Егору 4 года;

3) идёт дождь;

4) 3+4=7;

5) 1+1=5.

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

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

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

Примеры сложных высказываний:

1) сегодня не понедельник;

2) идёт дождь и на небе облачно;

3) если сегодня рабочий день, то нам надо идти на работу;

4) 2х=2 тогда и только тогда, когда х=1;

5) если x=2 и y=3, то x+y=100.

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

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

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

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

При этом эквиваленция истинна, когда "если p, то q и если q, то p", то есть

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

Отрицание ("НЕ")

ЛИ
ИЛ

Конъюнкция ("И")

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

Таким образом, значение операции конъюнкции принимает значение "истина" только в том случае, когда истинны оба аргумента, иначе значение "ложь".

Дизъюнкция ("ИЛИ")

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

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

Импликация ("если ..., то...")

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

Таким образом, значение операции импликации может быть "ложь" лишь только в том случае, когда левый аргумент - "истина", а правый аргумент "ложь". То есть, из истины не может следовать ложь.

Эквиваленция ("тогда и только тогда...")

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

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

Пример 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. Проверьте валидность аргумента, если

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

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

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

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