Тавтологія (логіка): відмінності між версіями

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

В логіці, '''тавтологія''' (від грецького слова ταυτολογία) є {{Нп5|Правильно побудована формула|формула||Well-formed formula}}, правдива у всіх можливих {{Нп5|Інтерпретація (логіка)|інтерпретаціях||Interpretation (logic)}}. Філософ [[Людвіг Вітґенштайн]] вперше застосував цей термін для скорочень в [[Числення висловлень|логіці висловлень]] в [[1921]] (він використовувався раніше для позначення [[Тавтологія (риторика)|тавтологій в риториці]], і продовжує використовуватися в цьому альтернативному сенсі). Формула {{Нп5|Здійсненність|здійсненна||Satisfiability}}, якщо вона вірна хоча б в одній інтерпретації, і, тоді, тавтологія є формула для якої заперечення нездійсненне. НездійсненніНездійсненне твердження, черезутворене як заперечення та твердження, відоміформально якє [[протиріччя]]м. A формули які не є ні тавтологією, ні суперечністюпротиріччям, є логічно не протирічними. Такa формула може бути істинною або хибною на підставі значень, приписаних його пропозиційним змінним. Подвійний турнікет позначення <math>\vDash S</math> використовується для вказівки, що S є тавтологія. Тавтологію іноді позначають як «Vpq», а суперечність як «Opq». Символ трійник <math>\top</math> іноді використовується для позначення довільної тавтології, а дуальний символ <math>\bot</math> (константа, ''брехня'') представляє довільне [[протиріччя]].

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

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

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

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

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

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

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

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

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

Тавтологія в логіці першого порядку є [[вирок]], який може бути отриманий шляхом прийняття тавтологією [[Логіка висловлювань|логіки]] висловлювань і рівномірно замінюючи кожну пропозіціональніпропозиціональні змінні по формулі першого порядку (одна формула в пропозициональній змінній). Тому <math>A \lor \lnot A </math> є тавтологією логіки висловлювань, а<math> (\forall x ( x = x)) \lor (\lnot \forall x (x = x))</math> тавтологією в логіці першого порядку. Точно так же, на мові першого порядку з одномісними символами відносин R, S, T, наступна пропозиція є тавтологією: <math>(((\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)).</math> Її отримують шляхом заміни <math>A</math> з <math> \exists x Rx, B</math>, з <math> \lnot \exists x Sx</math> та <math>C</math> з <math>\forall x Tx</math> в висловлювання тавтології <math>((A \land B) \to C) \Leftrightarrow (A \to (B \to C)).</math>