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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

Задний план

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

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

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

Эта статья или раздел могут быть написаны в стиле слишком абстрактный быть легко понятным широкая аудитория. Пожалуйста улучшить это путем определения технической терминологии и добавления примеров. (Май 2020 г.)

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

• ${displaystyle (Alor lnot A)}$ ("А или нет А"), закон исключенного среднего. Эта формула имеет только одну пропозициональную переменную, А. Любая оценка по этой формуле должна по определению присваивать А одна из истинных ценностей правда или ложный, и назначить ${displaystyle lnot}$А другое значение истины.
• ${displaystyle (A o B) Leftrightarrow (lnot B o lnot A)}$ ("если А подразумевает B, то не-B подразумевает не-А", и наоборот), что выражает закон противопоставление.
• ${displaystyle ((lnot A o B) land (lnot A o lnot B)) o A}$ ("если не-А подразумевает как B и его отрицание не-B, то не-А должно быть ложным, тогда А должно быть правдой "), принцип, известный как сокращение до абсурда.
• ${displaystyle lnot (Aland B) Leftrightarrow (lnot Alor lnot B)}$ ("если не оба А и B, то не-А или нет-B", и наоборот), который известен как Закон де Моргана.
• ${displaystyle ((A o B) земля (B o C)) o (A o C)}$ ("если А подразумевает B и B подразумевает C, тогда А подразумевает C"), который известен как принцип силлогизм.
• ${displaystyle ((Alor B) земля (A o C) земля (B o C)) o C}$ ("если хотя бы один из А или B верно, и каждый подразумевает C, тогда C также должно быть правдой "), который известен как принцип доказательство по делам.

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

• ${displaystyle (Alor B) o (Alor B)}$ это тавтология, но не минимальная, потому что это реализация ${displaystyle C o C}$.

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

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

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

${displaystyle ((Aland B) o C) Leftrightarrow (A o (B o C)).}$

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

${displaystyle A}$	${displaystyle B}$	${displaystyle C}$	${displaystyle Aland B}$	${displaystyle (Aland B) o C}$	${displaystyle B o C}$	${displaystyle A o (B o C)}$	${displaystyle ((Aland B) o C) Leftrightarrow (A o (B o C))}$
Т	Т	Т	Т	Т	Т	Т	Т
Т	Т	F	Т	F	F	F	Т
Т	F	Т	F	Т	Т	Т	Т
Т	F	F	F	Т	Т	Т	Т
F	Т	Т	F	Т	Т	Т	Т
F	Т	F	F	Т	F	Т	Т
F	F	Т	F	Т	Т	Т	Т
F	F	F	F	Т	Т	Т	Т

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

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

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

Формула р говорят тавтологически подразумевают формула S если каждая оценка, которая вызывает р быть правдой также вызывает S быть правдой. Эта ситуация обозначается ${displaystyle Rmodels S}$. Это эквивалентно формуле ${displaystyle R o S}$ быть тавтологией (Клини, 1967, с. 27).

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

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

Замена

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

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

${displaystyle (Aland B) lor lnot Alor lnot B}$.

Позволять S_А быть ${displaystyle Clor D}$ и разреши S_B быть ${displaystyle C o E}$.

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

${displaystyle ((Clor D) land (C o E)) lor lnot (Clor D) lor lnot (C o E)}$

это тоже тавтология. В свою очередь, значение истинности может быть заменено тавтологией »правда ".

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

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

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

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

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

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

Проблема определения того, существует ли какая-либо оценка, которая делает формулу верной, заключается в Проблема логической выполнимости; проблема проверки тавтологий эквивалентна этой проблеме, потому что проверка того, что предложение S тавтология эквивалентна проверке того, что не существует оценки, удовлетворяющей ${displaystyle lnot S}$. Известно, что проблема булевой выполнимости имеет вид НП завершена, и широко распространено мнение, что нет полиномиальный алгоритм который может это выполнить. Следовательно, тавтология совместно NP-полный. Текущие исследования сосредоточены на поиске алгоритмов, которые хорошо работают с определенными классами формул или в среднем быстро завершаются, даже если некоторые входные данные могут потребовать гораздо больше времени.

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

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

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

${displaystyle (((существует xRx) land lnot (exists xSx)) o forall xTx) Leftrightarrow ((существует xRx) o ((lnot exists xSx) o forall xTx)).}$

Получается заменой ${displaystyle A}$ с ${displaystyle существует xRx}$, ${displaystyle B}$ с ${displaystyle lnot существует xSx}$, и ${displaystyle C}$ с ${displaystyle forall xTx}$ в пропозициональной тавтологии ${displaystyle ((Aland B) o C) Leftrightarrow (A o (B o C))}$.

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

${displaystyle (forall xRx) o lnot существует xlnot Rx}$

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

На естественном языке

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

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

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

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

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

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

использованная литература

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

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

внешняя ссылка

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