Тавтология (логика)

В логике утверждение, которое всегда истинно.

В математической логике тавтология (от древнегреческого : ταυτολογία ) — это формула , которая истинна независимо от интерпретации ее составляющих терминов , при этом только логические константы имеют фиксированное значение. Например, формула, которая гласит: «мяч зеленый или мяч не зеленый», всегда истинна, независимо от того, что такое мяч и независимо от его цвета. Тавтология обычно, хотя и не всегда, используется для обозначения действительных формул пропозициональной логики .

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

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

Обозначение двойного турникета используется для указания того, что S является тавтологией. Тавтология иногда обозначается как "V pq " , а противоречие как "O pq ". Символ тройника иногда используется для обозначения произвольной тавтологии, при этом двойной символ ( falsum ) представляет произвольное противоречие; в любой символике тавтология может быть заменена на значение истины " true ", как, например, обозначается как "1". ^[1] ${\displaystyle \vDash S}$ ${\displaystyle \top }$ ${\displaystyle \bot }$

Тавтологии являются ключевым понятием в пропозициональной логике , где тавтология определяется как пропозициональная формула, которая истинна при любой возможной булевой оценке ее пропозициональных переменных . ^[2] Ключевым свойством тавтологий в пропозициональной логике является то, что существует эффективный метод проверки того, всегда ли выполняется данная формула (эквивалентно, является ли ее отрицание невыполнимым).

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

История

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

В 1800 году Иммануил Кант писал в своей книге «Логика» :

Тождество понятий в аналитических суждениях может быть как явным ( explicita ), так и неявным ( implicita ). В первом случае аналитические предложения являются тавтологичными.

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

В 1884 году Готтлоб Фреге в своих Grundlagen предположил , что истина является аналитической, если она может быть выведена с помощью логики. Однако он поддерживал различие между аналитическими истинами (т. е. истинами, основанными только на значениях их терминов) и тавтологиями (т. е. утверждениями, лишенными содержания).

В своем Tractatus Logico-Philosophicus в 1921 году Людвиг Витгенштейн предположил, что утверждения, которые могут быть выведены с помощью логической дедукции, являются тавтологичными (пустыми по смыслу), а также аналитическими истинами. Анри Пуанкаре сделал похожие замечания в Science and Hypothesis в 1905 году. Хотя Бертран Рассел сначала выступал против этих замечаний Витгенштейна и Пуанкаре, утверждая, что математические истины не только нетавтологичны, но и синтетически , позже он высказался в их пользу в 1918 году:

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

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

Многие логики в начале 20-го века использовали термин «тавтология» для любой формулы, которая является универсально допустимой, будь то формула пропозициональной логики или логики предикатов . В этом широком смысле тавтология — это формула, которая истинна при всех интерпретациях , или которая логически эквивалентна отрицанию противоречия. Тарский и Гёдель следовали этому использованию, и оно появляется в учебниках, таких как учебник Льюиса и Лэнгфорда. ^[3] Такое широкое использование термина сегодня менее распространено, хотя некоторые учебники продолжают его использовать. ^{[4] [5]}

Современные учебники чаще ограничивают использование «тавтологии» действительными предложениями пропозициональной логики или действительными предложениями предикатной логики, которые могут быть сведены к пропозициональным тавтологиям путем подстановки. ^{[6] [7]}

Фон

Пропозициональная логика начинается с пропозициональных переменных , атомарных единиц, которые представляют конкретные пропозиции. Формула состоит из пропозициональных переменных, связанных логическими связками, построенными таким образом, что истинность общей формулы может быть выведена из истинности или ложности каждой переменной. Оценка — это функция, которая присваивает каждой пропозициональной переменной либо T (для истинности), либо F (для ложности). Таким образом, используя пропозициональные переменные A и B , бинарные связки и представляющие дизъюнкцию и конъюнкцию соответственно, и унарную связку, представляющую отрицание , можно получить следующую формулу: . ${\displaystyle \lor }$ ${\displaystyle \land }$ ${\displaystyle \lnot }$ ${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$

Оценка здесь должна назначить каждому из A и B либо T, либо F. Но независимо от того, как это назначение сделано, общая формула получится верной. Ибо если первый дизъюнкт не удовлетворяется конкретной оценкой, то A или B должно быть назначено F, что сделает один из следующих дизъюнктов назначенным T. В естественном языке либо оба A и B истинны, либо по крайней мере один из них ложен. ${\displaystyle (A\land B)}$

Определение и примеры

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

Во многих из следующих примеров A представляет утверждение «объект X связан», B представляет «объект X — книга», а C представляет «объект X находится на полке». Без конкретного референтного объекта X соответствует утверждению «все связанные вещи — книги». ${\displaystyle A\to B}$

• ${\displaystyle (A\lor \lnot A)}$(" A или не A "), закон исключенного третьего . Эта формула имеет только одну пропозициональную переменную, A. Любая оценка для этой формулы должна, по определению, присвоить A одно из значений истинности true или false и присвоить A другое значение истинности. Например, "Кот черный или кот не черный". ${\displaystyle \lnot }$
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$(«если А подразумевает В , то не -В подразумевает не- А », и наоборот), что выражает закон противопоставления . Например, «Если это переплетено, то это книга; если это не книга, то это не переплетено» и наоборот.
• ${\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}$(«если не- A подразумевает как B , так и его отрицание не- B , тогда не- A должно быть ложным, тогда A должно быть истинным»), что является принципом, известным как reductio ad absurdum . Например, «Если это не связано, мы знаем, что это книга, если это не связано, мы знаем, что это также не книга, поэтому оно связано».
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$(«если не оба А и В , то не- А или не- В », и наоборот), который известен как закон Де Моргана . «Если это не является одновременно книгой и переплетом, то мы уверены, что это не книга или что это не переплет» и наоборот.
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}$(«если A подразумевает B , а B подразумевает C , то A подразумевает C »), что является принципом, известным как гипотетический силлогизм . «Если это переплетено, то это книга, а если это книга, то она на той полке, поэтому если это переплетено, то она на той полке».
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$(«если хотя бы одно из A или B истинно, и каждое из них подразумевает C , то C также должно быть истинным»), что является принципом, известным как доказательство по случаям . «Связанные вещи и книги находятся на этой полке. Если это либо книга, либо она синяя, она находится на этой полке».

Минимальная тавтология — это тавтология, которая не является примером более короткой тавтологии.

• ${\displaystyle (A\lor B)\to (A\lor B)}$является тавтологией, но не минимальной, поскольку является конкретизацией . ${\displaystyle C\to C}$

Проверка тавтологий

Проблема определения того, является ли формула тавтологией, является фундаментальной в пропозициональной логике. Если в формуле встречается n переменных, то для формулы существует 2 ⁿ различных оценок. Следовательно, задача определения того, является ли формула тавтологией, является конечной и механической: нужно только оценить истинностное значение формулы при каждой из ее возможных оценок. Один алгоритмический метод проверки того, что каждая оценка делает формулу истинной, заключается в создании таблицы истинности , которая включает все возможные оценки. ^[2]

Например, рассмотрим формулу

${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).}$

Существует 8 возможных оценок для пропозициональных переменных A , B , C , представленных первыми тремя столбцами следующей таблицы. Остальные столбцы показывают истинность подформул формулы выше, достигая кульминации в столбце, показывающем истинность исходной формулы под каждой оценкой.

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

Также возможно определить дедуктивную систему (т. е. систему доказательств) для пропозициональной логики как более простой вариант дедуктивных систем, используемых для логики первого порядка (см. Kleene 1967, Sec 1.9 для одной из таких систем). Доказательство тавтологии в соответствующей системе вывода может быть намного короче полной таблицы истинности (формула с n пропозициональными переменными требует таблицы истинности с 2 ⁿ строками, что быстро становится невозможным по мере увеличения n ). Системы доказательств также требуются для изучения интуиционистской пропозициональной логики, в которой метод таблиц истинности не может быть использован, поскольку закон исключенного третьего не предполагается.

Тавтологический подтекст

Говорят, что формула R тавтологически подразумевает формулу S , если каждая оценка, которая делает R истинной, также делает S истинным. Такая ситуация обозначается . Это эквивалентно тому, что формула является тавтологией (Kleene 1967, стр. 27). ${\displaystyle R\models S}$ ${\displaystyle R\to S}$

Например, пусть будет . Тогда не является тавтологией, потому что любая оценка, которая делает ложным, сделает ложным. Но любая оценка, которая делает истинным, сделает истинным, потому что является тавтологией. Пусть будет формулой . Тогда , потому что любая оценка, удовлетворяющая , сделает истинным — и, таким образом, сделает истинным. ${\displaystyle S}$ ${\displaystyle A\land (B\lor \lnot B)}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B\lor \lnot B}$ ${\displaystyle R}$ ${\displaystyle A\land C}$ ${\displaystyle R\models S}$ ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle S}$

Из определения следует, что если формула является противоречием, то тавтологически подразумевает каждую формулу, потому что нет оценки истинности, которая заставляет быть истинным, и поэтому определение тавтологической импликации тривиально выполняется. Аналогично, если является тавтологией, то тавтологически подразумевается каждой формулой. ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

Замена

Существует общая процедура, правило подстановки , которое позволяет строить дополнительные тавтологии из заданной тавтологии (Kleene 1967 sec. 3). Предположим, что S является тавтологией и для каждой пропозициональной переменной A в S выбрано фиксированное предложение S _A. Тогда предложение, полученное путем замены каждой переменной A в S соответствующим предложением S _A, также является тавтологией.

Например, пусть S будет тавтологией:

${\displaystyle (A\land B)\lor \lnot A\lor \lnot B}$.

Пусть S _A будет и пусть S _B будет . ${\displaystyle C\lor D}$ ${\displaystyle C\to E}$

Из правила замены следует, что предложение:

${\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}$

также является тавтологией.

Семантическая полнота и обоснованность

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

Эффективная проверка и проблема булевой выполнимости

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

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

Однако как эффективная процедура таблицы истинности ограничены тем фактом, что количество оценок, которые необходимо проверить, увеличивается как 2 ^k , где k — количество переменных в формуле. Этот экспоненциальный рост длины вычислений делает метод таблиц истинности бесполезным для формул с тысячами пропозициональных переменных, поскольку современное вычислительное оборудование не может выполнить алгоритм за приемлемый период времени.

Проблема определения, существует ли какая-либо оценка, которая делает формулу истинной, — это проблема булевой выполнимости ; проблема проверки тавтологий эквивалентна этой проблеме, поскольку проверка того, что предложение S является тавтологией, эквивалентна проверке того, что не существует оценки, удовлетворяющей . Проблема булевой выполнимости является NP-полной , и, следовательно, тавтология является ко-NP-полной . Широко распространено мнение, что (эквивалентно для всех NP-полных проблем) ни один алгоритм с полиномиальным временем не может решить проблему выполнимости, хотя некоторые алгоритмы хорошо работают на специальных классах формул или быстро завершаются во многих случаях. ^[8] ${\displaystyle \lnot S}$

Тавтологии против валидностей в логике первого порядка

Фундаментальное определение тавтологии дано в контексте пропозициональной логики. Однако это определение может быть распространено на предложения в логике первого порядка . ^[9] Эти предложения могут содержать квантификаторы, в отличие от предложений пропозициональной логики. В контексте логики первого порядка проводится различие между логическими обоснованностями , предложениями, которые истинны в каждой модели, и тавтологиями (или тавтологическими обоснованностями ), которые являются собственным подмножеством логических обоснованностей первого порядка. В контексте пропозициональной логики эти два термина совпадают.

Тавтология в логике первого порядка — это предложение, которое может быть получено путем взятия тавтологии пропозициональной логики и равномерной замены каждой пропозициональной переменной формулой первого порядка (одна формула на пропозициональную переменную). Например, поскольку является тавтологией пропозициональной логики, является тавтологией в логике первого порядка. Аналогично, в языке первого порядка с унарными символами отношения R , S , T следующее предложение является тавтологией: ${\displaystyle A\lor \lnot A}$ ${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$

${\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx)).}$

Он получается путем замены на , на и на в пропозициональной тавтологии: . ${\displaystyle A}$ ${\displaystyle \exists xRx}$ ${\displaystyle B}$ ${\displaystyle \lnot \exists xSx}$ ${\displaystyle C}$ ${\displaystyle \forall xTx}$ ${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}$

Не все логические обоснования являются тавтологиями в логике первого порядка. Например, предложение:

${\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx}$

верно в любой интерпретации первого порядка, но оно соответствует пропозициональному предложению , которое не является тавтологией пропозициональной логики. ${\displaystyle A\to B}$

Тавтологии в неклассических логиках

Является ли данная формула тавтологией, зависит от формальной системы логики, которая используется. Например, следующая формула является тавтологией классической логики, но не интуиционистской логики :

${\displaystyle \neg \neg A\to A}$

Смотрите также

Нормальные формы

• Алгебраическая нормальная форма
• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма
• Оптимизация логики

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

Ссылки

1. Weisstein, Eric W. "Тавтология". mathworld.wolfram.com . Получено 14 августа 2020 г.
2. "тавтология | Определение и факты". Encyclopedia Britannica . Получено 2020-08-14 .
3. Льюис, CI; Лэнгфорд, CH (1959). Символическая логика (2-е изд.). Дувр.
4. Хедман, Шон (2004). Первый курс логики . Oxford University Press. стр. 63.
5. Раутенберг, Вольфганг (2010). Краткое введение в математическую логику . Springer. стр. 64.
6. Эндертон, Герберт (2001). Математическое введение в логику . Academic Press. стр. 88.
7. Хинман, Питер (2010). Основы математической логики . Springer. стр. 98.
8. См . SAT-решатель для справки.
9. "Новые члены". Naval Engineers Journal . 114 (1): 17–18. Январь 2002. doi :10.1111/j.1559-3584.2002.tb00103.x. ISSN  0028-1425.

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

• Бохеньский, Дж. М. (1959) Précis of Mathematical Logic , перевод с французского и немецкого изданий Отто Берда, Дордрехт , Южная Голландия : D. Reidel .
• Эндертон, Х. Б. (2002) Математическое введение в логику , Harcourt / Academic Press , ISBN 0-12-238452-0 . 
• Клини, С. К. (1967) Математическая логика , переиздано в 2002 г., Dover Publications , ISBN 0-486-42533-9 . 
• Рейхенбах, Х. (1947). Элементы символической логики , переиздано в 1980 г., Дувр, ISBN 0-486-24004-5 
• Витгенштейн, Л. (1921). «Logisch-philosophiche Abhandlung», Annalen der Naturphilosophie (Лейпциг), т. 14, стр. 185–262, переиздано в английском переводе как Tractatus logico-philosophicus , Нью-Йорк и Лондон , 1922 г.

Внешние ссылки

• «Тавтология», Энциклопедия математики , EMS Press , 2001 [1994]