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

редактировать

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

Философ Людвиг Витгенштейн впервые применил этот термин к избыточности логики высказываний в 1921 году, заимствуя из риторики, где тавтология - повторяющееся утверждение. В логике формула выполнима, если она истинна хотя бы при одной интерпретации, и, таким образом, тавтология - это формула, отрицание которой неудовлетворительно. Неудовлетворительные утверждения, выраженные как через отрицание, так и через подтверждение, формально известны как противоречия. Формула, которая не является ни тавтологией, ни противоречием, называется логически случайной. Такая формула может быть сделана истинной или ложной на основе значений, присвоенных ее пропозициональным переменным. двойной турникет обозначение ⊨ S {\ displaystyle \ vDash S}\ vDash S используется для обозначения того, что S является тавтологией. Тавтология иногда символизируется «Vpq», а противоречие - «Opq». тройник символ ⊤ {\ displaystyle \ top}\ top иногда используется для обозначения произвольной тавтологии с двойным символом ⊥ {\ displaystyle \ bot}\ bot (falsum ), представляющее произвольное противоречие; в любом символизме значение истинности «истина » может быть заменено тавтологией, что, например, символизируется «1».

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

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

Содержание
  • 1 История
  • 2 Предпосылки
  • 3 Определение и примеры
  • 4 Проверка тавтологий
  • 5 Тавтологический смысл
  • 6 Замена
  • 7 Семантическая полнота и обоснованность
  • 8 Эффективная проверка и проблема логической выполнимости
  • 9 Тавтологии и валидности в логике первого порядка
  • 10 На естественном языке
  • 11 См. Также
    • 11.1 Нормальные формы
    • 11.2 Связанные логические темы
  • 12 Ссылки
  • 13 Дополнительная литература
  • 14 Внешние ссылки
История

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

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

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

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

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

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

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

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

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

Предпосылки

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

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

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

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

  • (A ∨ ¬ A) {\ displaystyle (A \ lor \ lnot A)}(A \ lor \ lnot A) («A or not A»), закон исключенного среднего. Эта формула имеет только одну пропозициональную переменную A. Любая оценка этой формулы должна, по определению, присваивать A одно из истинных значений, истинное или ложное, и присваивать ¬ {\ displaystyle \ lnot}\ lnot A другое значение истинности.
  • (A → B) ⇔ (¬ B → ¬ A) {\ displaystyle (A \ to B) \ Leftrightarrow (\ lnot B \ to \ lnot A)}(От A \ до B) \ Leftrightarrow (\ lnot B \ to \ lnot A) ( «если A подразумевает B, то not-B подразумевает not-A», и наоборот), который выражает закон противопоставления.
  • ((¬ A → B) ∧ (¬ A → ¬ B)) → A {\ displaystyle ((\ lnot A \ to B) \ land (\ lnot A \ to \ lnot B)) \ to A}((\ lnot A \ to B) \ land (\ lnot A \ to \ lnot B)) \ to A ("если не-A подразумевает как B, так и его отрицание не- B, тогда not-A должно быть ложным, тогда A должно быть истинным "), что является принципом, известным как reductio ad absurdum.
  • ¬ (A ∧ B) ⇔ (¬ A ∨ ¬ B) {\ displaystyle \ lnot (A \ land B) \ Leftrightarrow (\ lnot A \ lor \ lnot B)}\ lnot (A \ land B) \ Leftrightarrow (\ lnot A \ lor \ lnot B) («если не одновременно A и B, то не-A или не-B», и наоборот), который известен как закон Де Моргана.
  • ((A → B) ∧ (B → C)) → (A → C) {\ displaystyle ((A \ to B) \ land (B \ to C)) \ to (A \ to C)}((A \ to B) \ land (B \ to C)) \ to (A \ to C) («если A подразумевает B, а B подразумевает C, то A подразумевает C»), который является принципом, известным как силлогизм.
  • ( (A ∨ B) ∧ (A → C) ∧ (B → C)) → C {\ displaystyle ((A \ lor B) \ land (A \ to C) \ land (B \ to C)) \ to C }((A \ lor B) \ land (A \ to C) \ land (B \ to C)) \ to C («если хотя бы одно из A или B истинно, и каждое подразумевает C, то C также должно быть истинным»), который является принципом, известным как доказательство по случаям.

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

  • (A ∨ B) → (A ∨ B) {\ displaystyle (A \ lor B) \ to (A \ lor B)}{\ displaystyle (A \ lor B) \ to (A \ lor B)} - тавтология, но не минимальная, потому что является воплощением C → C {\ displaystyle C \ to C}C \ к C .
Проверка тавтологий

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

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

((A ∧ B) → C) ⇔ (A → (B → C)). {\ displaystyle ((A \ land B) \ to C) \ Leftrightarrow (A \ to (B \ to C)).}((A \ земля B) \ к C) \ Leftrightarrow (A \ to (B \ to C)).

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

A {\ displaystyle A}A B {\ displaystyle B}BC {\ displaystyle C}C A ∧ B {\ displaystyle A \ land B}A \ land B (A ∧ B) → C {\ Displaystyle (A \ земля B) \ к C}(A \ land B) \ to C B → C {\ displaystyle B \ to C}B \ to C A → (B → C) {\ displaystyle A \ to (B \ to C) }A \ to (B \ to C) ((A ∧ B) → C) ⇔ (A → (B → C)) {\ displaystyle ((A \ land B) \ to C) \ Leftrightarrow (A \ to (B \ to C)) }((A \ land B) \ to C) \ Leftrightarrow (A \ to (B \ to C))
TTTTTTTT
TTFTFFFT
TFTFTTTT
TFFFTTTT
FTTFTTTT
FTFFTFTT
FFTFTTTT
FFFFTTTT

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

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

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

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

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

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

Замена

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

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

(A ∧ B) ∨ ¬ A ∨ ¬ B {\ displaystyle (A \ land B) \ lor \ lnot A \ lor \ lnot B}{\ displaystyle (A \ land Б) \ lor \ lno t A \ lor \ lnot B} .

Пусть S A будет C ∨ D {\ displaystyle C \ lor D}C \ lor D и пусть S B будет C → E {\ displaystyle C \ to E}C \ to E .

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

((C ∨ D) ∧ (C → E)) ∨ ¬ (C ∨ D) ∨ ¬ (C → E) {\ displaystyle ((C \ lor D) \ land (C \ to E)) \ lor \ lnot (C \ lor D) \ lor \ lnot (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 - количество переменных в формуле. Этот экспоненциальный рост длины вычислений делает метод таблицы истинности бесполезным для формул с тысячами пропозициональных переменных, поскольку современное вычислительное оборудование не может выполнить алгоритм за допустимый период времени.

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

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

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

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

(((∃ x R x) ∧ ¬ (∃ x S x)) → ∀ x T х) ⇔ ((∃ x R x) → ((¬ ∃ x S x) → ∀ x T x)). {\ Displaystyle (((\ существует xRx) \ земля \ lnot (\ существует xSx)) \ к \ forall xTx) \ Leftrightarrow ((\ существует xRx) \ к ((\ lnot \ существует xSx) \ к \ forall xTx)).}(((\ существует xRx) \ land \ lnot (\ exists xSx)) \ to \ forall xTx) \ Leftrightarrow ((\ exists xRx) \ to ((\ lnot \ exists xSx) \ to \ forall xTx)).

Он получается заменой A {\ displaystyle A}A на ∃ x R x {\ displaystyle \ exists xRx}\ exists xRx , B {\ displaystyle B}Bс ¬ ∃ x S x {\ displaystyle \ lnot \ exists xSx}\ lnot \ exists xSx и C {\ displaystyle C}C с ∀ Икс T Икс {\ Displaystyle \ forall xTx}\ forall xTx в пропозициональной тавтологии ((A ∧ B) → C) ⇔ (A → (B → C)) {\ displaystyle ((A \ land B) \ to C) \ Leftrightarrow (A \ to (B \ to C))}((A \ land B) \ to C) \ Leftrightarrow (A \ to (B \ to C)) .

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

(∀ x R x) → ¬ ∃ x ¬ R x {\ displaystyle (\ forall xRx) \ to \ lnot \ exists x \ lnot Rx}(\ forall xRx) \ to \ lnot \ exists x \ lnot Rx

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

В естественном языке

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

См. Также

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

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

Ссылки
Дополнительная литература
Внешние ссылки
Последняя правка сделана 2021-06-09 11:00:18
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте