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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

Предыстория

Основная статья: Пропозициональная логика

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

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

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

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

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

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

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

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

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

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

$((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).$

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

$A$	$B$	$C$	$A\land B$	$(A\land B)\to C$	$B\to C$	$A\to (B\to C)$	$((A\land B)\to C)\Leftrightarrow (A\to (B\to C))$
Т	Т	Т	Т	Т	Т	Т	Т
Т	Т	Ф	Т	Ф	Ф	Ф	Т
Т	Ф	Т	Ф	Т	Т	Т	Т
Т	Ф	Ф	Ф	Т	Т	Т	Т
Ф	Т	Т	Ф	Т	Т	Т	Т
Ф	Т	Ф	Ф	Т	Ф	Т	Т
Ф	Ф	Т	Ф	Т	Т	Т	Т
Ф	Ф	Ф	Ф	Т	Т	Т	Т

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

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

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

Основная статья: Тавтологическое следствие

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

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

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

Замена

Основная статья: Экземпляр замены

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

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

$(A\land B)\lor \lnot A\lor \lnot B$.

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

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

$((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)$

тоже тавтология.

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

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

проверка и проблема

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

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

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

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

первого

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

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

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

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

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

$(\forall xRx)\to \lnot \exists x\lnot Rx$

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

См. также

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

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

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

• Булева алгебра
• Логический домен
• Булева функция
• Противоречие
• Ложь (логика)
• Силлогизм
• Список логических символов

• Логический синтез
• Логическое следствие
• Логический график
• Логическая истина
• Пустая правда

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

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

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

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