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

У Вікіпедії є статті про інші значення цього терміна: Тавтологія.

Тавтологією в логіці називається тотожно істинне висловлювання, інваріантне щодо значень своїх компонент. Якщо формула A — тавтологія, то вона позначається ⊨A. У кожному логічному обчисленні є своя підмножина тавтологій.

В логіці, тавтологія (від грецького слова ταυτολογία) є формула^[en], правдива у всіх можливих інтерпретаціях. Філософ Людвіг Вітґенштайн вперше застосував цей термін для скорочень в логіці висловлень в 1921 (він використовувався раніше для позначення тавтологій в риториці, і продовжує використовуватися в цьому альтернативному сенсі). Формула здійсненна^[en], якщо вона вірна хоча б в одній інтерпретації, і, тоді, тавтологія є формула для якої заперечення нездійсненне. Нездійсненне твердження, утворене як заперечення твердження, формально є протиріччям. A формули які не є ні тавтологією, ні протиріччям, є логічно не протирічними. Такa формула може бути істинною або хибною на підставі значень, приписаних його пропозиційним змінним. Подвійний турнікет позначення $\vDash S$ використовується для вказівки, що S є тавтологія. Тавтологію іноді позначають як «Vpq», а суперечність як «Opq». Символ трійник $\top$ іноді використовується для позначення довільної тавтології, а дуальний символ $\bot$ (константа, хибність) представляє довільне протиріччя.

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

Визначення «Тавтологія» може бути поширене на вислови в логіці предикатів, які можуть містити квантори, на відміну від висловів логіки висловлювань. В логіці висловлювань, немає жодної різниці між тавтологією і логічно дійсною формулою. В контексті логіки предиката, багато авторів визначають, що тавтологія є пропозиція, яка може бути отримана шляхом прийняття тавтології з логіки висловлювань та рівномірною заміною кожної пропозиціональної змінної першого порядку в формулі (одна формула за висловлювань змінної). Множина таких формул є власною підмножиною множини логічно допустимих пропозицій з логіки предикатів, які є твердженнями, які істинні в кожній моделі.

ІсторіяРедагувати

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

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

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

В 1884, Готтлоб Фреге запропонував в своїй основоположній арифметиці, що аналітична правда точна, якщо вона може бути отримана за допомогою логіки. Але він стверджував, що існує відмінність між аналітичними істинами (ґрунтуючись лише на значеннях їх точки зору) та тавтологією (заяви, позбавлені змісту).

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

«Все, що є пропозицією логіки має бути в якомусь сенсі або іншому, як тавтологія. Воно повинне бути чимось, що має деяку особливу якість, яку не знають, як визначити, що належить до логічних суджень, але не для інших.»

Під час 1930-х була формалізація семантики логіки висловлювань з точки зору завдань істини. Термін тавтологія стала застосовуватися в тих висловлювань, формулах, які істинні незалежно від істинності чи хибності своїх пропозиціональних змінних. Деякі ранні книги про логіку (наприклад, символічної логіки по працям Льюїса та Ленгфорд, 1932) використовують термін для будь-якої пропозиції (в будь-якій формальній логіці), що є загальнообов'язковим. Це поширене в презентаціях (такі як Стівен Кліні 1967 і Херберт Ендертон^[en] 2002), для використання тавтології, щоб звернутися до логічної дії пропозиціональної формули, але для підтримки розходження між тавтологією та логічною дією в контексті першого порядку.

КласифікаціяРедагувати

Логіка висловлювань починається з пропозиціональних змінних, атомних одиниць, які представляють конкретні пропозиції. Формула складається з пропозиціональних змінних, пов'язаних логічними зв'язками, так, що істина може в цілому однозначно виводиться з істинності чи хибності кожної змінної. Оцінка є функцією, яка присвоює кожній пропозиціональній змінні або T (істина) або F (хибність). Так, наприклад, за допомогою пропозиціональних змінних A і B, двійкові зв'язки $\lor$ і $\land$ , що представляють диз'юнкцію і кон'юнкцію відповідно, і унарний сполучник $\lnot$ , що представляє заперечення, наступна формула може бути :: $(A\land B)\lor (\lnot A)\lor (\lnot B)$ . Тут оцінку необхідно призначити кожному з А і В або Т або F. Але незалежно від того, як це призначення зроблено, загальна формула не вийде такою, якщо перше з'єднання $(A\land B)$ не задовольняє певну оцінку.

Побудова тавтологіїРедагувати

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

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

Перевірка тавтологіїРедагувати

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

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	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). Доказ системи також потрібен для вивчення інтуїціонистської логіки, в якій метод таблиці істинності не можуть бути використаними, тому що закон виключеного третього не виконується.

Приклади тавтологійРедагувати

Тавтології обчислення висловлювань (і алгебри висловлювань)Редагувати

$A\rightarrow A$ («З A слідує A»)
$(A)\lor (\lnot A)$ («A або не-A», Закон виключеного третього)
$\neg (P\land \neg P)$ .
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\rightarrow (B\rightarrow A)$ (істина слідує з будь-чого)
$A\leftrightarrow \neg \neg A$ (Закон подвійного заперечення)
$(A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)$ (правило ланцюгового укладення)
$(A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)$ (дистрибутивність диз'юнкції щодо кон'юнкції)
$\neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)$ (закон де Моргана)
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ (Контрапозиція)
Якщо $\vDash F(X_{1},...,X_{n})$ и $H_{1},...,H_{n}$ — формули, то $\vDash F(H_{1},...,H_{n})$ (правило підстановки)

Тавтології обчислення предикатів (і алгебри предикатів)Редагувати

Якщо $F(X_{1},...,X_{n})$ — тавтологія в обчисленні висловлювань та $P_{1},...,P_{n}$ — предикати, то $F(P_{1},...,P_{n})$ — тавтологія в численні предикатів
$\neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)$

$\neg (\exists x)P(x)\leftrightarrow (\forall x)\neg P(x)$ (закон де Моргана)
$(\forall x)(P(x)\wedge Q(x))\leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$
$(\exists x)(P(x)\vee Q(x))\leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)$
$Q\leftrightarrow (\exists x)Q$
$Q\leftrightarrow (\forall x)Q$
$(\forall x)P(x)\rightarrow P(y)$
$P(y)\rightarrow (\exists x)P(x)$
$(\forall x)(\forall y)P(x,y)\leftrightarrow (\forall y)(\forall x)P(x,y)$
$(\exists x)(\exists y)P(x,y)\leftrightarrow (\exists y)(\exists x)P(x,y)$
$(\exists x)(\forall y)P(x,y)\rightarrow (\forall y)(\exists x)P(x,y)$

Приклад тавтології в літературіРедагувати

Розглянемо відомий з пісні вислів: «У хокей грають справжні чоловіки, (отже) боягуз не грає в хокей».

Формалізуємо його:

$X$ — грає в хокей

$M$ — справжній чоловік

$\lnot X$ — не грає в хокей

$\lnot M$ — не справжній чоловік (боягуз)

Отримуємо формулу:

$(X\rightarrow M)\rightarrow (\lnot M\rightarrow \lnot X)$

яка є логічною тавтологією.

Заміна $A\lor \lnot A$ Редагувати

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

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

Тавтології проти термінів дії в логіці першого порядкуРедагувати

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

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