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

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

в 1800, Іммануїл Кант писав у своїй книзі «Логіка»: «Ідентичність понять в аналітичних суджень може бути явною (explicita) або НЕ явною (implicita). У першому випадку аналітичні судження є тавтологією.»

Тут, аналітична пропозиція відноситься до аналітичної істини, та заява природною мовою, що є істиною.

В 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)}$. Тут оцінку необхідно призначити кожному з А і В або Т або F. Але незалежно від того, як це призначення зроблено, загальна формула не вийде такою, якщо перше з'єднання ${\displaystyle (A\land B)}$ не задовольняє певну оцінку.

Для з'ясування того, чи є дана формула тавтологією, в алгебрі висловлювань є простий спосіб — побудова таблиці істинності. В обчисленні висловлювань, тавтологіями є аксіоми (точніше — схеми аксіом), а також всі формули, які можна отримувати з відомих тавтологій за допомогою заданих правил виведення (найчастіше це Modus ponens і правило підстанови). Перевірка, чи є дана формула в численні висловів тавтологією, більш складна, а також залежить від системи аксіом і доступних правил виводу.

Проблема визначення того, чи є довільна формула в логіці предикатів тавтологією, алгоритмічно нерозв'язна.

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

A	B	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))}$
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	T	T
T	F	F	F	T	T	T	T
F	T	T	F	T	T	T	T
F	T	F	F	T	F	T	T
F	F	T	F	T	T	T	T
F	F	F	F	T	T	T	T

Оскільки кожен рядок в останньому стовпці показує T, пропозиція про яку йде мова, може бути перевірена. Крім того, можна визначити дедуктивну систему (доказ системи) для логіки висловлювань, як більш простий варіант дедуктивних систем, використовуваних для логіки першого порядку (див. Кліні 1967, гл. 1, 9) для однієї такої системи. Доказ тавтології в відповідній системі утримання може бути значно коротшою повної таблиці істинності (формули з n пропозиційних змінних вимагає таблицю істинності з 2n ліній, які швидко стають неможливим ростом n). Доказ системи також потрібен для вивчення інтуїціоністської логіки, в якій метод таблиці істинності не можуть бути використаними, тому що закон виключеного третього не виконується.

Існує загальний порядок, правило підстановки, що дозволяє додатковій тавтології бути побудованою з даної тавтології (Кліні 1967). Припустимо, що S є тавтологією і для кожного з висловлювань змінної А в S фіксовану, вирок SA вибраний. Тоді вирок, який є заміною кожної змінної A в S з відповідним вироком SA також є тавтологією.

Наприклад, нехай S буде ${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$ , тавтологія. Нехай SA буде ${\displaystyle C\lor D}$ і нехай SB буде ${\displaystyle C\to E}$. З правила підстановки випливає, що пропозиції ${\displaystyle ((C\lor D)\land (C\to E))\lor (\lnot (C\lor D))\lor (\lnot (C\to E))}$ є тавтологією.

Принципове визначення тавтології в контексті логіки висловлювань може бути продовженим, однак, тільки в пропозиції логіки першого порядку (див Enderton (2002, стор. 114) і Кліні (1967)). Ці пропозиції можуть містити квантори, на відміну від пропозицій логіки висловлювань. В контексті логіки першого порядку, розходження між логічними законами пропозицій і тавтологіями, які власне є підмножиною логічних термінів дії першого порядку, зберігається. В контексті логіки висловлювань, ці два терміни збігаються.

Тавтологія в логіці першого порядку є вирок, який може бути отриманий шляхом прийняття тавтологією логіки висловлювань і рівномірно заміняти кожну пропозиційну змінну по формулі першого порядку (одна формула в пропозиційній змінній). Тому ${\displaystyle A\lor \lnot A}$ є тавтологією логіки висловлювань, а${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$ тавтологією в логіці першого порядку. Точно так же, на мові першого порядку з одномісними символами відносин R, S, T, наступна пропозиція є тавтологією: ${\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,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}$ який не є тавтологією логіки висловлювань.

• Колмогоров А. Н., Драглин А. Г. (2006). Математическая логика. ISBN 5-484-00520-5.

• Игошин В. І. Математична логіка і теорія алгоритмів. — Academia, 2008.

• Карпов Ю. Г. Теорія автоматів. — П., 2003.- С. 49, 60. 

• Мендельсон Е. Введення в математичну логіку. — М. Наука, 1971.

• Протиріччя,
• Логічна хиба.

• Тавтологія // Універсальний словник-енциклопедія. — 4-те вид. — К. : Тека, 2006.