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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технических деталей. ( Май 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Логическая формула, верная во всех возможных интерпретациях Эта статья включает в себя список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Ноябрь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Философ Людвиг Витгенштейн впервые применил этот термин к дублированию логики высказываний в 1921 году, заимствуя его из риторики , где тавтология - это повторяющееся утверждение. В логике формула выполнима, если она верна хотя бы при одной интерпретации, и, таким образом, тавтология - это формула, отрицание которой невыполнимо. Неудовлетворительные утверждения, выраженные как через отрицание, так и через подтверждение, формально известны как противоречия . Формула, не являющаяся ни тавтологией, ни противоречием, называется логически случайной . Такую формулу можно сделать истинной или ложной на основе значений, присвоенных ее пропозициональным переменным. Вдвойное обозначение турникета используется для обозначения того, что S - тавтология. Тавтология иногда обозначается «V pq », а противоречие - «O pq ». Тройник символ иногда используются для обозначения произвольной тавтологии, с двойным символом ( константа ' лжи ) , представляющей собой произвольное противоречие; в любом символизме значение истинности « истина » может быть заменено тавтологией , которая символизируется, например, «1». ^{[1] [2]}${\ displaystyle \ vDash S}$${\displaystyle \top }$${\displaystyle \bot }$

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

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

История [ править ]

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

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

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

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

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

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

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

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

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

Фон [ править ]

Логика высказываний начинается с пропозициональных переменных , элементарных единиц, которые представляют конкретные высказывания. Формула состоит из пропозициональных переменных , соединенных логических связок, построенных таким образом , что истинность общей формулы может быть выведена из истинности или ложности каждого переменные. Оценка является функцией , которая присваивает каждому пропозициональной переменной либо Т (к истине) или 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.${\displaystyle (A\land B)}$

Определение и примеры [ править ]

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

• ${\displaystyle (A\lor \lnot A)}$(« А или не А »), закон исключенной середины . Эта формула имеет только одну переменную пропозициональную, . Любая оценка для этой формулы должна, по определению, присваивать A одно из значений истинности, истинное или ложное , и присваивать A другое значение истинности. Например, «Кот черный или кот не черный».${\displaystyle \lnot }$
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$(«если A подразумевает B , то не- B подразумевает не- A », и наоборот), который выражает закон противопоставления . Например: «Если это книга, она синего цвета; если не синяя, это не книга».
• ${\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}$(«если нет - А подразумевает и В, и его отрицание не - В , тогда не - А должно быть ложным, тогда А должно быть истинным»), этот принцип известен как reductio ad absurdum . Например: «Если не синий, это книга, если не синий, это тоже не книга, значит, он синий».
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$(«если не оба A и B , то не A или не 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 ⁿ различных оценок. Следовательно, задача определения, является ли формула тавтологией, является конечной и механической: нужно только оценить истинность формулы при каждой из ее возможных оценок. Один из алгоритмических методов проверки того, что каждая оценка делает формулу истинной, - это составить таблицу истинности , включающую все возможные оценки. ^[3]

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

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

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

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

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

Также возможно определить дедуктивную систему (т. Е. Систему доказательств) для логики высказываний как более простой вариант дедуктивных систем, используемых для логики первого порядка (об одной такой системе см. Клини 1967, раздел 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 S}$${\displaystyle A}$${\displaystyle S}$

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

Замена [ править ]

Существует общая процедура, правило подстановки , которое позволяет создавать дополнительные тавтологии из данной тавтологии (Kleene 1967 sec. 3). Предположим , что S является тавтологией и для каждой пропозициональной переменной A в S фиксированном предложении S выбран. Тогда предложение, полученное заменой каждой переменной 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-полна . Текущие исследования сосредоточены на поиске алгоритмов, которые хорошо работают с определенными классами формул или в среднем быстро завершаются, даже если некоторые входные данные могут потребовать гораздо больше времени.${\displaystyle \lnot S}$

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

Фундаментальное определение тавтологии находится в контексте логики высказываний. Однако это определение можно распространить на предложения в логике первого порядка (см. Enderton (2002, стр. 114) и Kleene (1967 sec. 17–18)). Эти предложения могут содержать кванторы, в отличие от предложений логики высказываний. В контексте логики первого порядка поддерживается различие между логической валидностью , предложениями, истинными в каждой модели, и тавтологиями , которые являются надлежащим подмножеством логических валидностей первого порядка. В контексте логики высказываний эти два термина совпадают.

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

На естественном языке [ править ]

В естественных языках некоторые очевидные тавтологии, как в некоторых банальностях , на практике могут иметь нетавтологическое значение. ^[4] В английском языке «это то, что есть» используется в значении «это невозможно изменить». ^[5] На тамильском языке поверхностная тавтология vantaalum varuvaan буквально означает «если он придет, он придет», но обычно означает «он просто может прийти». ^[6]

См. Также [ править ]

Нормальные формы [ править ]

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

Связанные логические темы [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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