Лекция 3. Таблицы истинности и исчисление высказываний
Last updated
Last updated
Логика -- это исследование аргументов. Таким образом, она имеет древнюю историю, уступающую по древности только математике. Мы знаем, что древние индийские писатели, писавшие на санскрите, писали книги по этой теме, а буддисты изучали логику, чтобы улучшить ум. Но на Западе именно Аристотелю приписывают то, что он первым попытался кодифицировать правила правильного рассуждения.
Влияние Аристотеля было огромным. Средневековые схоласты тщательно тренировались в аристотелевской логике и вели дебаты, в которых от участников требовалось вести обсуждение с помощью аргументов специфичной формы, называемых силлогизмами.
Однако логике в ее современном виде лишь чуть более 130 лет. Современная логика -- продукт процесса самоанализа математики, начавшегося в девятнадцатом веке. Продолжая аналогию с предыдущей лекцией, математика росла подобно древнему городу, здания возводились по мере необходимости, не задумываясь о том, как они связаны со своими предшественниками. В девятнадцатом веке несколько ведущих математиков заинтересовались систематизацией того, что уже было известно. Их видение состояло в том, чтобы переупорядочить обширный математический мегаполис в точную и упорядоченную систему, в которой математические истины следовали бы из основных предположений теории чисел. К середине девятнадцатого века Дедекинд и другие уже проделали большую работу, чтобы воплотить этот проект -- арифметизацию математики -- в реальность.
Но было ли этого достаточно? Немецкий философ и математик Готлоб Фреге так не считал. Фреге стремился достичь еще двух целей.
Первая цель заключалась в том, чтобы свести теорию чисел к чему-то еще более простому -- теории множеств (подробнее об этом см. Лекцию 12 и далее). Фундаментальные принципы счета и сложения можно рассматривать как следствия обращения с числами как с определенными типами множеств. Программа логицизма Фреге заключалась в сведении математики к логике и теории множеств.
Вторая цель Фреге состояла в том, чтобы создать формальную нотацию для логики, в которой можно было бы записать все математические аргументы.
Эта нотация должна была быть настолько точной, чтобы можно было проверить, просто взглянув на расположение символов на странице, верно или нет математическое доказательство. Действительно, вклад Фреге был настолько велик, что доказательства, записанные в его нотации, могли быть проверены на правильность с помощью машины, соответствующим образом запрограммированной с помощью правил Фреге. Это было достижением, выходящим далеко за рамки силлогистической логики Аристотеля, и поэтому работа Фреге вызвала ренессанс в изучении логики после 2000 лет застоя.
Логики и философы сходятся во мнении, что Фреге удалось достичь своей второй цели, но не удалось достичь первой. В лекции 15 мы увидим, почему Фреге потерпел неудачу в своем первом проекте.
Современная логика начинается с публикации Begriffsschrift Фреге в 1879 году, где была представлена его новая нотация. Современные логики не используют его довольно неуклюжие двумерные обозначения, поэтому мы будем использовать современную нотацию в этой книге.
Логическая система, которую оставил нам Фреге, состоит из двух частей: первое называется исчислением высказываний (также иногда называемым сентенциальной логикой), а второе - исчислением предикатов (также называемым логикой первого порядка). В следующих нескольких лекциях мы будем касаться только исчисления высказываний.
Упражнение 3.1. Приведите несколько примеров предложений исчисления высказываний.
В логике правильно сформированные предложения системы часто называют правильно построенными формулами этой системы (англ. well-formed formulae, сокр. wff), или просто формулами. Следовательно, упражнение 3.1 требует, чтобы вы нашли несколько формул исчисления высказываний.
Упражнение 3.2. Подчеркните основные связки в следующих формулах:
Чтобы дать интерпретацию формулам исчисления высказываний, нам нужно сопоставить высказывания атомам в формуле. Высказывание -- это предложение, которое либо истинно, либо ложно.
Поскольку исчисление высказываний -- это система доказательств, у него есть общезначимые и контрзначимые формулы. Общезначимые формулы называются тавтологиями, а контрзначимые -- контртавтологиями.
При вычислении того, является ли интерпретация моделью или нет, нам на самом деле не нужно знать смысл высказываний, используемых в интерпретации -- только то, истинны они или ложны. То есть все, что нам нужно знать -- истинность используемых высказываний. Этот факт лежит в основе механической проверки тавтологий, разработанной американским философом Чарльзом Сандерсом Пирсом.
Чарльз Сандерс Пирс родился в семье профессора Бенджамина Пирса и остается одним из самых выдающихся интеллектуалов, когда-либо рожденных в Америке.
Пирс писал много: его рукописи, многие из которых остаются неопубликованными, насчитывают около 100 000 страниц. Он внес вклад в философию, математику, логику и науку. Несмотря на свой талант, Пирс за всю свою жизнь так и не добился того признания, которого заслуживал. Он умер от рака в 1914 году -- слишком бедный, чтобы иметь возможность платить за дрова для обогрева комнаты, в которой он лежал. Он разработал метод таблиц истинности, который мы изучим в этой лекции.
Чтобы показать, что формула является тавтологией, мы должны показать, что независимо от значений истинности, присвоенных атомам, формула оказывается истинной.
Если мы таким же образом заполним следующую строку, мы завершим приведенную ниже таблицу истинности.
Упражнение 3.4. Используйте таблицы истинности, чтобы классифицировать следующие формулы как тавтологии, контртавтологии или ни то, ни другое.
Есть много введений в логику: Copi и Cohen (2003), Diller (1990), Hodges (1977), Lemmon (1998), Mendelson (2009) -- все это хорошие варианты. Силлогистическая логика описана в Popkin и Stroll (1993).
Исчисление высказываний -- это система доказательств. Его самые фундаментальные компоненты называются атомами или атомными формулами. Атом -- это одна из букв, , или атом, соединенный с апострофом, например . Молекула или молекулярная формула -- это результат соединения нескольких формул одной из логических констант , , , , . БНФ исчисления высказываний приведена ниже.
Каждая молекулярная формула имеет главную связку, которая является одной из логических констант, , , , . Основная связка -- это константа, которая склеивает всю формулу. Таким образом, в выражении основной связкой является -- так как соединяет вместе два компонента, которые образуют целую формулу. В случае с выражением основным связующим элементом является .
Формула, главная связка которой , -- это конъюнкция. Формула, главная связка которой , -- дизъюнкция. Формула c главной связкой является импликацией. Формула, главная связка которой -- эквивалентность; и формула, основной связкой которой является -- это отрицание.
Таким образом, если мы возьмем символ и назначим ему высказывание "Папа Римский живет в Ватикане", то полученная интерпретация будет моделью, поскольку Папа действительно живет в Ватикане.
Символ (называется тильда) интерпретируется имеющий значение нет. Следовательно, хотя фраза "Папа Римский живет в Ватикане" -- это модель для , она является контрмоделью для . Интерпретируя как "Папа Римский живет в Ватикане", формула интерпретируется как утверждение, что Папа не живет в Ватикане.
Фактически в целом мы можем сказать, что интерпретация -- это модель для формулы , когдаявляется контрмоделью для ; также интерпретация является контрмоделью для , когда является моделью для .
Символ (называется вель) интерпретируется как или. Таким образом читается как "p или q". Опять же, это открытое предложение, которое не является ни истинным, ни ложным, поскольку и являются переменными. Интерпретация является моделью , когда она является моделью для , или , или обоих атомов одновременно.
Таким образом, интерпретация как "Папа Римский живет в Нью-Йорке" и как "Все треугольники имеют три стороны" дает интерпретацию, которая является моделью, поскольку "Все треугольники имеют три стороны" верно. Однако, если бы мы интерпретировали как "Папа Римский живет в Нью-Йорке", а как "Все прямоугольники имеют пять сторон", тогда интерпретация была бы контрмоделью, потому что оба эти утверждения ложны.
Символ (называется амперсанд) интерпретируется как и. Таким образом читается как "р и q". Интерпретация является моделью , когда она является моделью и для , и для .
Таким образом, интерпретация как "Папа Римский живет в Нью-Йорке" и как "Все треугольники имеют три стороны" дает интерпретацию, которая является контрмоделью , поскольку "Папа Римский живет в Нью-Йорке" является ложным утверждением. Однако, если бы мы интерпретировали как "Папа Римский живет в Ватикане", а как "Все прямоугольники имеют четыре стороны", тогда интерпретация была бы моделью, потому что оба эти утверждения верны.
Символ (называется знак материальной импликации) интерпретируется как означающий если ... то. Таким образом читается как "если р, то q". Интерпретация является моделью , когда она является контрмоделью для или моделью для .
Таким образом, интерпретация как "Папа Римский живет в Нью-Йорке" и q как "Все треугольники имеют три стороны" дает интерпретацию, которая является моделью , поскольку "Папа Римский живет в Нью-Йорке" является контрмоделью для . Однако, если бы мы интерпретировали как "Папа Римский живет в Ватикане" и как "Все прямоугольники имеют пять сторон", тогда интерпретация была бы контрмоделью для .
Наконец, символ (называется знак би-импликации) интерпретируется как означающий тогда и только тогда, когда. Интерпретация является моделью , когда она является моделью дляи моделью для, или же контрмоделью для и контрмоделью для .
Таким образом, интерпретациякак "Папа Римский живет в Нью-Йорке" и как "Все треугольники имеют три стороны" дает интерпретацию, которая является контрмоделью , поскольку "Папа Римский живет в Нью-Йорке" является контрмоделью, а "Все треугольники имеют три стороны" -- это модель для. Однако, если бы мы интерпретироваликак "Папа Римский живет в Нью-Йорке" и как "Все прямоугольники имеют пять сторон", интерпретация была бы моделью для.
Упражнение 3.3. Присвоимвысказывание "Водород тяжелее железа", а присвоим высказывание "Кислород -- это газ". Укажите, является ли такая интерпретация моделью или контрмоделью для следующих формул:
Примерами тавтологий являются и . Оказывается, что какое высказывание мы бы ни связали с атомами этих предложений, получающаяся в результате интерпретация является моделью.
Примерами контртавтологий являются и . Оказывается, что какое высказывание мы бы ни связали с атомами этих предложений, получающаяся в результате интерпретация является контрмоделью.
Если мы рассмотрим логическую связку, как в формуле, то есть только 4 возможных формы интерпретации:
И, иозначают истинные высказывания.
означает истинное высказывание, а-- ложное.
означает ложное высказывание, а-- истинное.
И, иозначают ложные высказывания.
В каждом случае мы можем вычислить, является ли формулаистинной при интерпретации или нет. Таким образом, в случае 1верна при интерпретации. В случае 2 также верна, как и в случае 3, тогда как в последнем случае 4 формуланеверна.
Один из способов резюмировать эти аспекты-- написать таблицу истинности для этой связки. Буква используется для обозначения истины, а буква-- для обозначения лжи.
В первой строке указано, что если и дано значение истинности (истина), то получает значение истинности (истина). Аналогичным образом остальные три строки описывают свойства . Вот таблицы истинности для других связок.
Для этого мы сначала записываем формулу, а затем слева от нее записываем все атомы в ней. Итак, предположим, мы хотим показать, что -- это тавтология. Записываем
Есть только две возможности: либоназначено истинное высказывание, либоприсвоено ложное высказывание. Итак, под списком атомов (состоящих изи ничего другого) мы пишем и, чтобы показать оба эти два варианта.
Затем напротив каждой из этих двух возможностей мы вычисляем значение истинности формулы при такой интерпретации. В первой строке мы записываем значенияв соответствии с нашей интерпретацией. Это значение(истина).
Из таблицы истинности длямы знаем, что еслизадано значение, тоназначается значение. Мы пишемпод, чтобы показать это.
Затем, используя таблицу истинности для, мы определяем значение, которое будет записано под основной связкой. Поскольку одна сторона выражения,, задана как, значение, присвоенное, должно быть. Мы подчеркиваем этот результат, потому что мы обнаружили, что интерпретация, назначающаяистинное утверждение, делает все выражение истинным.
Наша таблица истинности показывает, чтовсегда оказывается истинным, независимо от того, каково значение истинности высказывания, интерпретирующего . Следовательно,-- тавтология.
Теперь вы должны понимать таблицу истинности для. Точно так же эта формула тоже является тавтологией.
Следующая таблица истинности показывает, чтоявляется контртавтологией.
Эта таблица истинности показывает, чтоне является ни тавтологией, ни контртавтологией.
