Тавтологія (логіка): відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 35:
== Перевірка тавтології ==
Проблема визначення, чи являється формула тавтологією є основоположним в логіці висловлювань. Якщо є '''''n''''' змінних, що входять в формулу, тобто '''''2n''''' різних оцінок для формули. Тому завдання визначення того, чи є формула тавтологією, є кінцевим: потрібно тільки оцінити справжнє значення формули в рамках кожного з його можливих оцінок. Один алгоритмічний метод для перевірки коли кожна оцінка викликає цю фразу, щоб бути правдою, щоб зробити таблицю істинності, яка включає всі можливі оцінки.
Розглянемо, наприклад, формулу
Рядок 123 ⟶ 122:
Оскільки кожен рядок в останньому стовпці показує T, пропозиція про яку йде мова, може бути перевірена.
Крім того, можна визначити [[Дедукція|дедуктивну]] систему (доказ системи) для логіки висловлювань, як більш простий варіант дедуктивних систем, використовуваних для логіки першого порядку (див Кліні 1967, гл 1,9) для однієї такої
▲Крім того, можна визначити дедуктивну систему (доказ системи) для логіки висловлювань, як більш простий варіант дедуктивних систем, використовуваних для логіки першого порядку (див Кліні 1967, гл 1,9) для однієї такої системі. Доказ тавтології в відповідній системі утримання може бути значно коротшою повної таблиці істинності (формули з '''''n '''''пропозіціональних змінних вимагає таблицю істинності з '''''2n''''' ліній, які швидко стають неможливим ростом '''''n'''''). Доказ системи також потрібен для вивчення [[Інтуїціонистська логіка|інтуїціонистської логіки]], в якій метод таблиці істинності не можуть бути використаними, тому що [[закон виключеного третього]] не виконується.
== Приклади тавтологій ==
| |||