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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

Історія[ред.ред. код]

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

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

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

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

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

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

Під час 1930-х була формалізація семантики логіки висловлювань з точки зору завдань істини. Термін тавтологія стала застосовуватися в тих висловлювань формули, які істинні незалежно від істинності чи хибності своїх пропозіціональних змінних. Деякі ранні книги за логікою (наприклад, символічної логіки по CI Льюїса та Ленгфорд, 1932) використовують термін для будь-якої пропозиції (в будь-якої формальної логіки), що є загальнообов'язкової. Це поширене в презентацій після цього (такі як Стівен Кліні 1967 і Херберт Ендертон 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). Доказ системи також потрібні для вивчення інтуїціонистської логіки, в якій метод таблиць істинності не може бути використаний, тому що закон виключеного третього не виконується.

Приклади тавтологій[ред.ред. код]

 Тавтології обчислення висловлювань (і алгебри висловлювань)[ред.ред. код]

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

Приклад тавтології в літературі[ред.ред. код]

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

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

 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 x Rx) \land \lnot (\exists x Sx)) \to \forall x Tx) \Leftrightarrow ((\exists x Rx) \to ((\lnot \exists x Sx) \to \forall x Tx)). Його отримують шляхом заміни A з  \exists x Rx, B, з  \lnot \exists x Sx та C з \forall x Tx в висловлювань тавтології ((A \land B) \to C) \Leftrightarrow (A \to (B \to C)).

Не всі логічні терміни дії є тавтології в логіці першого порядку. Наприклад, фраза

(\forall x Rx) \to \lnot \exists x \lnot Rx

Правда, в який-небудь інтерпретації першого порядку, але це відповідає висловлювань вироку  A \to B який не є тавтологією логіки висловлювань.

Література[ред.ред. код]

  • Колмогоров А. Н., Драглин А. Г. (2006). Математическая логика. ISBN 5-484-00520-5. 
  • Игошин В. І. Математична логіка і теорія алгоритмів. — Academia, 2008.
  • Карпов Ю. Г. Теорія автоматів. — П., 2003.- С. 49, 60. 
  • Мендельсон Е. Введення в математичну логіку. — М. Наука, 1971.

Див. також[ред.ред. код]