На головну

Несуперечливість і повнота аксіоматичної теорії числення висловів

  1.  I. Визначте, яке з цих висловлювань несе психологічну інформацію.
  2.  II. Базові поняття теорії ймовірностей
  3.  II. Перевірка правильності визначення оподатковуваних оборотів, обчислення податків і зборів.
  4.  II. еволюційні теорії
  5.  Quot; Гіпотези і теорії.
  6.  V. Повнота і дух
  7.  А (додаткова). Кілька слів про методологію науки. Принцип актуалізму, "Бритва Оккама" і презумпції. Перевірка теорії: верифікації та фальсифікації.

Немає нічого простішого створення аксіоматичних теорій! Як сказав один відомий математик: "Аксіоматизації те саме крадіжки!".

Визначивши свою мову, придумавши свої аксіоми і правила виводу, ви отримуєте

свою аксіоматичну теорію.

Наприклад, в якості мови візьмемо будь-які послідовності символів @, єдиною аксіомою оголосимо один символ @, а правило виведення буде

@ ?? @@.

Тоді в даній теорії буде виведена будь-яка послідовність з одного або більше символів @.

Одне погано, толку в таких теоріях зазвичай ніякого немає ...

А ось розглянута раніше аксіоматична теорія обчислення висловлювань має ряд важливих (цікавих, чудових) властивостей. Формули цієї теорії можна інтерпретувати як формули алгебри висловлювань, записані з використанням (функціонально повного набору!) Операцій: O і ® (заперечення і імплікації).

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

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

Доведемо несуперечливість цієї теорії.

Прямий перевіркою доводиться, що всі аксіоми, одержувані з схем аксіом, є тавтологія. Наприклад, для першої схеми аксіом:

А ® (В ® А)

А В Ф

А з тавтологію за допомогою m.p. ( A , A ® B ?? B ) Можна отримати тільки тавтології. А оскільки будь-яка отримана в цій теорії формула Ф є тавтологія,

то її заперечення OФ було б протиріччям, яке не виводиться.

Повнота і несуперечність дуже важливі властивості. На жаль, більшість складніших аксіоматичних теорій не може похвалитися повнотою (відкритий Геделем принцип неповноти). У них можуть існувати формули, для яких неможливо довести як виводимість, так і невиводимість ...

Що ж стосується несуперечності, то це дуже жорстка вимога.

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

 




 алгебра висловлювань |  Форми подання висловлювань |  перетворення висловлювань |  Перетворення СДНФ в СКНФ і навпаки. |  Мінімізація висловлювань методом Квайна |  Мінімізація за допомогою карт Вейча |  функціональна повнота |  логіка предикатів |  Основні равносильности для предикатів |  отримання диз'юнктів |

© um.co.ua - учбові матеріали та реферати