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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

В 1930-е годы была разработана формализация семантики логики высказываний в терминах истинностных присвоений. Термин «тавтология» стал применяться к тем пропозициональным формулам, которые истинны независимо от истинности или ложности их пропозициональных переменных. В некоторых ранних книгах по логике (например, «Символическая логика» К.И. Льюиса и Лэнгфорда, 1932) этот термин использовался для обозначения любого утверждения (в любой формальной логике), которое является универсально действительным. В последующих презентациях (таких как Стивен Клини 1967 и Герберт Эндертон 2002) принято использовать тавтологию для обозначения логически обоснованной пропозициональной формулы, но сохранять различие между «тавтологией» и «логически достоверной» в контексте первого подхода. логика порядка (см. ниже) .

Фон

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

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

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

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

• ${\displaystyle (A\lor \lnot 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}$(«если не- А подразумевает и В , и его отрицание не- В , то не- А должно быть ложным, тогда А должно быть истинным»), который является принципом, известным как доведение до абсурда . Например: «Если это не синий, то это книга, если он не синий, то это тоже не книга, поэтому он синий».
• ${\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 пропозициональными переменными требует таблицы истинности с 2n ^{строками} , что быстро становится невозможным по мере увеличения n ). Системы доказательств также необходимы для изучения интуиционистской логики высказываний, в которой метод таблиц истинности не может быть использован, поскольку не предполагается закон исключенного третьего.

Тавтологический смысл

Говорят, что формула R тавтологически подразумевает формулу S, если каждая оценка, которая делает R истинным, также делает S истинным. Обозначается эта ситуация . Это эквивалентно тому, что формула является тавтологией (Клин, 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}$

Замена

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

Например, пусть S — тавтология:

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

Пусть S _A будет и пусть SB _будет . ${\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-полна . Текущие исследования сосредоточены на поиске алгоритмов, которые хорошо работают с особыми классами формул или в среднем быстро завершают работу, хотя некоторые входные данные могут привести к тому, что они займут гораздо больше времени. ${\displaystyle \lnot S}$

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

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

Тавтология в логике первого порядка — это предложение, которое можно получить, взяв тавтологию логики высказываний и равномерно заменив каждую пропозициональную переменную формулой первого порядка (одна формула на каждую пропозициональную переменную). Например, поскольку это тавтология логики высказываний, это тавтология и логики первого порядка. Аналогично, в языке первого порядка с символами унарного отношения 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}$

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

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

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

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

Рекомендации

1. Вайсштейн, Эрик В. «Тавтология». mathworld.wolfram.com . Проверено 14 августа 2020 г.
2. "Тавтология | Определение и факты" . Британская энциклопедия . Проверено 14 августа 2020 г.
3. "Тавтология (логика)" . Википедия.орг .
4. «Новые участники». Журнал военно-морских инженеров . 114 (1): 17–18. Январь 2002 г. doi :10.1111/j.1559-3584.2002.tb00103.x. ISSN  0028-1425.

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

• Боченский, Дж. М. (1959) Краткое описание математической логики , перевод с французского и немецкого изданий Отто Берда, Дордрехт , Южная Голландия : Д. Рейдель .
• Эндертон, HB (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]