Лекция 3. Таблицы истинности и исчисление высказываний

Логика

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

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

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

Но было ли этого достаточно? Немецкий философ и математик Готлоб Фреге так не считал. Фреге стремился достичь еще двух целей.

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

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

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

Логики и философы сходятся во мнении, что Фреге удалось достичь своей второй цели, но не удалось достичь первой. В лекции 15 мы увидим, почему Фреге потерпел неудачу в своем первом проекте.

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

Синтаксис исчисления высказываний

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

Исчисление высказываний -- это система доказательств. Его самые фундаментальные компоненты называются атомами или атомными формулами. Атом -- это одна из букв $p$ , $q$ , $r$ или атом, соединенный с апострофом, например $p′$ . Молекула или молекулярная формула -- это результат соединения нескольких формул одной из логических констант $\lor$ , $\&$ , $\sim$ , $\to$ , $\leftrightarrow$ . БНФ исчисления высказываний приведена ниже.

\begin{aligned} <sentence> &:= <molecule> | <atom> \\ <molecule> &:= (^\wedge<sentence> \lor <sentence>^\wedge) \\ &| (^\wedge<sentence> \& <sentence>^\wedge) \\ &| (^\wedge <sentence> \to <sentence>^\wedge) \\ &| (^\wedge <sentence> \leftrightarrow <sentence>^\wedge) \\ &| (^\wedge \sim <sentence>^\wedge) \\ <atom> &:= p | q | r | <atom>^\wedge\prime \\ \end{aligned}

Упражнение 3.1. Приведите несколько примеров предложений исчисления высказываний.

В логике правильно сформированные предложения системы часто называют правильно построенными формулами этой системы (англ. well-formed formulae, сокр. wff), или просто формулами. Следовательно, упражнение 3.1 требует, чтобы вы нашли несколько формул исчисления высказываний.

Каждая молекулярная формула имеет главную связку, которая является одной из логических констант $\lor$ , $\&$ , $\sim$ , $\to$ , $\leftrightarrow$ . Основная связка -- это константа, которая склеивает всю формулу. Таким образом, в выражении $(p \& (q \lor r))$ основной связкой является $\&$ -- так как $\&$ соединяет вместе два компонента, которые образуют целую формулу. В случае с выражением $(\sim (p \to q))$ основным связующим элементом является $\sim$ .

Формула, главная связка которой $\&$ , -- это конъюнкция. Формула, главная связка которой $\lor$ , -- дизъюнкция. Формула c главной связкой $\to$ является импликацией. Формула, главная связка которой $\leftrightarrow$ -- эквивалентность; и формула, основной связкой которой является $\sim$ -- это отрицание.

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

$(p \lor (\sim q))$
$(p \leftrightarrow q)$
$(p \leftrightarrow (\sim q))$
$(p \& (q \lor (\sim p)))$

Семантика исчисления высказываний

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

Таким образом, если мы возьмем символ $p$ и назначим ему высказывание "Папа Римский живет в Ватикане", то полученная интерпретация будет моделью, поскольку Папа действительно живет в Ватикане.

Символ $\sim$ (называется тильда) интерпретируется имеющий значение нет. Следовательно, хотя фраза "Папа Римский живет в Ватикане" -- это модель для $p$ , она является контрмоделью для $(\sim p)$ . Интерпретируя $p$ как "Папа Римский живет в Ватикане", формула $(\sim p)$ интерпретируется как утверждение, что Папа не живет в Ватикане.

Фактически в целом мы можем сказать, что интерпретация $M$ -- это модель для формулы $\mathscr{W}$ , когда $M$ является контрмоделью для $(\sim \mathscr{W})$ ; также интерпретация $M$ является контрмоделью для $\mathscr{W}$ , когда $M$ является моделью для $(\sim \mathscr{W})$ .

Символ $\lor$ (называется вель) интерпретируется как или. Таким образом $(p \lor q)$ читается как "p или q". Опять же, это открытое предложение, которое не является ни истинным, ни ложным, поскольку $p$ и $q$ являются переменными. Интерпретация является моделью $(p \lor q)$ , когда она является моделью для $p$ , или $q$ , или обоих атомов одновременно.

Таким образом, интерпретация $p$ как "Папа Римский живет в Нью-Йорке" и $q$ как "Все треугольники имеют три стороны" дает интерпретацию, которая является моделью $(p \lor q)$ , поскольку "Все треугольники имеют три стороны" верно. Однако, если бы мы интерпретировали $p$ как "Папа Римский живет в Нью-Йорке", а $q$ как "Все прямоугольники имеют пять сторон", тогда интерпретация была бы контрмоделью, потому что оба эти утверждения ложны.

Символ $\&$ (называется амперсанд) интерпретируется как и. Таким образом $(p \& q)$ читается как "р и q". Интерпретация является моделью $(p \& q)$ , когда она является моделью и для $p$ , и для $q$ .

Таким образом, интерпретация $p$ как "Папа Римский живет в Нью-Йорке" и $q$ как "Все треугольники имеют три стороны" дает интерпретацию, которая является контрмоделью $(p \& q)$ , поскольку "Папа Римский живет в Нью-Йорке" является ложным утверждением. Однако, если бы мы интерпретировали $p$ как "Папа Римский живет в Ватикане", а $q$ как "Все прямоугольники имеют четыре стороны", тогда интерпретация была бы моделью, потому что оба эти утверждения верны.

Символ $\to$ (называется знак материальной импликации) интерпретируется как означающий если ... то. Таким образом $(p \to q)$ читается как "если р, то q". Интерпретация является моделью $(p \to q)$ , когда она является контрмоделью для $p$ или моделью для $q$ .

Таким образом, интерпретация $p$ как "Папа Римский живет в Нью-Йорке" и q как "Все треугольники имеют три стороны" дает интерпретацию, которая является моделью $(p \to q)$ , поскольку "Папа Римский живет в Нью-Йорке" является контрмоделью для $p$ . Однако, если бы мы интерпретировали $p$ как "Папа Римский живет в Ватикане" и $q$ как "Все прямоугольники имеют пять сторон", тогда интерпретация была бы контрмоделью для $(p \to q)$ .

Наконец, символ $\leftrightarrow$ (называется знак би-импликации) интерпретируется как означающий тогда и только тогда, когда. Интерпретация является моделью $(p \leftrightarrow q)$ , когда она является моделью для $p$ и моделью для $q$ , или же контрмоделью для $p$ и контрмоделью для $q$ .

Таким образом, интерпретация $p$ как "Папа Римский живет в Нью-Йорке" и $q$ как "Все треугольники имеют три стороны" дает интерпретацию, которая является контрмоделью $(p \leftrightarrow q)$ , поскольку "Папа Римский живет в Нью-Йорке" является контрмоделью $p$ , а "Все треугольники имеют три стороны" -- это модель для $q$ . Однако, если бы мы интерпретировали $p$ как "Папа Римский живет в Нью-Йорке" и $q$ как "Все прямоугольники имеют пять сторон", интерпретация была бы моделью для $(p \leftrightarrow q)$ .

Упражнение 3.3. Присвоим $p$ высказывание "Водород тяжелее железа", а $q$ присвоим высказывание "Кислород -- это газ". Укажите, является ли такая интерпретация моделью или контрмоделью для следующих формул:

$(p \lor (\sim q))$
$(p \leftrightarrow q)$
$(p \leftrightarrow (\sim q))$
$(p \& (q \lor (\sim p)))$

Таблицы истинности и тавтологии

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

Примерами тавтологий являются $(p \lor (\sim p))$ и $(q \to (p \to q))$ . Оказывается, что какое высказывание мы бы ни связали с атомами этих предложений, получающаяся в результате интерпретация является моделью.

Примерами контртавтологий являются $(p \& (\sim p))$ и $(p \leftrightarrow (\sim p))$ . Оказывается, что какое высказывание мы бы ни связали с атомами этих предложений, получающаяся в результате интерпретация является контрмоделью.

При вычислении того, является ли интерпретация моделью или нет, нам на самом деле не нужно знать смысл высказываний, используемых в интерпретации -- только то, истинны они или ложны. То есть все, что нам нужно знать -- истинность используемых высказываний. Этот факт лежит в основе механической проверки тавтологий, разработанной американским философом Чарльзом Сандерсом Пирсом.

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

Пирс писал много: его рукописи, многие из которых остаются неопубликованными, насчитывают около 100 000 страниц. Он внес вклад в философию, математику, логику и науку. Несмотря на свой талант, Пирс за всю свою жизнь так и не добился того признания, которого заслуживал. Он умер от рака в 1914 году -- слишком бедный, чтобы иметь возможность платить за дрова для обогрева комнаты, в которой он лежал. Он разработал метод таблиц истинности, который мы изучим в этой лекции.

Если мы рассмотрим логическую связку $\lor$ , как в формуле $(p \lor q)$ , то есть только 4 возможных формы интерпретации:

И $p$ , и $q$ означают истинные высказывания.
$p$ означает истинное высказывание, а $q$ -- ложное.
$p$ означает ложное высказывание, а $q$ -- истинное.
И $p$ , и $q$ означают ложные высказывания.

В каждом случае мы можем вычислить, является ли формула $(p \lor q)$ истинной при интерпретации или нет. Таким образом, в случае 1 $(p \lor q)$ верна при интерпретации. В случае 2 $(p \lor q)$ также верна, как и в случае 3, тогда как в последнем случае 4 формула $(p \lor q)$ неверна.

Один из способов резюмировать эти аспекты $\lor$ -- написать таблицу истинности для этой связки. Буква $t$ используется для обозначения истины, а буква $f$ -- для обозначения лжи.

(p \lor q) \\ \begin{array}{ccc} t & t & t \\ t & f & t \\ f & t & t \\ f & f & f \end{array}

В первой строке указано, что если $p$ и $q$ дано значение истинности $t$ (истина), то $(p \lor q)$ получает значение истинности $t$ (истина). Аналогичным образом остальные три строки описывают свойства $\lor$ . Вот таблицы истинности для других связок.

$(p \& q)$

$(p \to q)$

$(p \leftrightarrow q)$

$(\sim p)$

$\begin{array}{ccc} t & t & t \\ t & f & f \\ f & t & f \\ f & f & f \end{array}$

$\begin{array}{ccc} t & t & t \\ t & f & f \\ f & t & t \\ f & f & t \end{array}$

$\begin{array}{ccc} t & t & t \\ t & f & f \\ f & t & f \\ f & f & t \end{array}$

$\begin{array}{cc} f & t \\ t & f \end{array}$

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

Для этого мы сначала записываем формулу, а затем слева от нее записываем все атомы в ней. Итак, предположим, мы хотим показать, что $(p \lor (\sim p))$ -- это тавтология. Записываем

\begin{array}{c|cccc} p & (p & \lor & (\sim & p)) \\ \hline t & \\ f & \end{array}

Есть только две возможности: либо $p$ назначено истинное высказывание, либо $p$ присвоено ложное высказывание. Итак, под списком атомов (состоящих из $p$ и ничего другого) мы пишем $t$ и $f$ , чтобы показать оба эти два варианта.

Затем напротив каждой из этих двух возможностей мы вычисляем значение истинности формулы при такой интерпретации. В первой строке мы записываем значения $p$ в соответствии с нашей интерпретацией. Это значение $t$ (истина).

\begin{array}{c|cccc} p & (p & \lor & (\sim & p &)) \\ \hline t & t & & & t \\ f & \end{array}

Из таблицы истинности для $\sim$ мы знаем, что если $p$ задано значение $t$ , то $(\sim p)$ назначается значение $f$ . Мы пишем $f$ под $\sim$ , чтобы показать это.

\begin{array}{c|cccc} p & (p & \lor &(\sim & p & )) \\ \hline t & t & & f & t \\ f & \end{array}

Затем, используя таблицу истинности для $\lor$ , мы определяем значение, которое будет записано под основной связкой $\lor$ . Поскольку одна сторона выражения, $p$ , задана как $t$ , значение, присвоенное $(p \lor (\sim p))$ , должно быть $t$ . Мы подчеркиваем этот результат, потому что мы обнаружили, что интерпретация, назначающая $p$ истинное утверждение, делает все выражение $(p \lor (\sim p))$ истинным.

\begin{array}{c|cccc} p & (p & \lor &(\sim & p &)) \\ \hline t & t & \underline{t} & f & t \\ f & \end{array}

Если мы таким же образом заполним следующую строку, мы завершим приведенную ниже таблицу истинности.

\begin{array}{c|cccc} p & (p & \lor (& \sim & p &)) \\ \hline t & t & \underline{t} & f & t \\ f & f & \underline{t} & t & f \end{array}

Наша таблица истинности показывает, что $(p \lor (\sim p))$ всегда оказывается истинным, независимо от того, каково значение истинности высказывания, интерпретирующего $p$ . Следовательно, $(p \lor (\sim p))$ -- тавтология.

Теперь вы должны понимать таблицу истинности для $(q \to (p \to q))$ . Точно так же эта формула тоже является тавтологией.

\begin{array}{cc|ccccc} p & q & (q & \to & (p & \to & q &)) \\ \hline t & t & t & \underline{t} & t & t & t \\ t & f & f & \underline{t} & t & f & f \\ f & t & t & \underline{t} & f & t & t \\ f & f & f & \underline{t} & f & t & f \\ \end{array}

Следующая таблица истинности показывает, что $(p \& (\sim p))$ является контртавтологией.

\begin{array}{c|cccc} p & (p & \& &(\sim & p)) \\ \hline t & t & \underline{f} & f & t \\ f & f & \underline{f} & t & f \\ \end{array}

Эта таблица истинности показывает, что $(p \lor (\sim q))$ не является ни тавтологией, ни контртавтологией.

\begin{array}{cc|cccc} p & q & (p & \lor & (\sim & q &)) \\ \hline t & t & t & \underline{t} & f & t \\ t & f & f & \underline{t} & t & f \\ f & t & f & \underline{f} & f & t \\ f & f & f & \underline{t} & t & f \\ \end{array}

Упражнение 3.4. Используйте таблицы истинности, чтобы классифицировать следующие формулы как тавтологии, контртавтологии или ни то, ни другое.

$(p \& (q \lor (\sim r)))$
$((p \to (q \to r)) \to ((p \to q) \to (p \to r)))$
$((p \to (\sim p)) \to p)$
$(p \leftrightarrow (\sim p))$

Дальнейшее чтение

Есть много введений в логику: Copi и Cohen (2003), Diller (1990), Hodges (1977), Lemmon (1998), Mendelson (2009) -- все это хорошие варианты. Силлогистическая логика описана в Popkin и Stroll (1993).

PreviousЛекция 2. Семантика и доказательство

Last updated 4 years ago

Was this helpful?