А   Б  В  Г  Д  Е  Є  Ж  З  І  Ї  Й  К  Л  М  Н  О  П  Р  С  Т  У  Ф  Х  Ц  Ч  Ш  Щ  Ю  Я 


Натуральний висновок

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

Ця система (натурального виведення) є адекватною: якщо висновки в чисельнику довільного правила загальнозначимі, то висновок в знаменнику того ж правила також общезначім.

Введена в обчисленні висловлювань система натурального виведення (§ 217) узагальнюється на числення предикатів шляхом додавання правил введення і видалення кванторів спільності та існування.

Описана дедуктивна система, в якій аспекти резолюції (зокрема, уніфікація і використання функцій Сколема) з'єднані з аспектами натурального виведення. Дія системи вдало порівнюється з найкращими програмами доказів теорем числення предикатів.

Потім Правицю[3]для обчислення натуральних висновків вдалося отримати навіть сильніший результат: а саме, виявилося, що для системи редукцій Правиця всякий натуральний висновок наводиться до нормального вигляду довільній послідовністю редукцій. Що стосується повного обчислення секвенций, то Цукер навів конкретний приклад нескінченної послідовності редукцій (із запропонованого їм набору редукцій), який не веде до нормального висновку.

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

Спочатку формалізації логічних і мате-Матіч. Логічні обчислення); вирішальне просування в цьому напрямку склало обчислення натуральних висновків (див. Генцен формальна система], що імітує форму звичайних математичних.

Точніше, можна показати, що доказ переборні перетину з висновків обмеженою складності саме формалізується в интуиционистской простий теорії типів з аксіомою нескінченності. Ми проводимо доказ в стилі Жирара-Мартін - Лефа-Правиця для звичайного числення секвенцій, а не для натурального виведення або систем типу секвенціальной системи Шютте (див., наприклад, Освальд[2], Буххольц[1]), метод докази поширений на теорію з правилом об'ємності і , нарешті, наше доказ має спеціальну алгебраїчну форму. насправді будується конкретна модель для розглянутого обчислення така, що з істинності секвенції в цій моделі слід її виводимість без перетинів. Логіка моделі утворює алгебру з поповненням, так що модель є прикладом застосування алгебри з поповненням в конкретних дослідженнях з теорії інтуїционістського виведення.

Потім Правицю[3]для обчислення натуральних висновків вдалося отримати навіть сильніший результат: а саме, виявилося, що для системи редукцій Правиця всякий натуральний висновок наводиться до нормального вигляду довільній послідовністю редукцій. Що стосується повного обчислення секвенций, то Цукер навів конкретний приклад нескінченної послідовності редукцій (із запропонованого їм набору редукцій), який не веде до нормального висновку.

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

Ці логічні засоби можна застосовувати досить безпосередньо. Логічні мови служать опорою для вираження знань, які також представлені декларативно у вигляді логічних виразів. Міркування визначається як операція докази общезначимости або здійсненності логічного твердження. Міркування здійснюються обхідним шляхом, за допомогою маніпулювання дедуктивним компонентами даної логічної системи. Наприклад, такими компонентами є класичні аксіоматичні системи (§ § 213 218), системи натурального виведення (§ § 217 219) або семантика даної логічної системи. Так як процес докази повинен бути автоматизований, то це дуже часто реалізується методами пошуку, причому проводиться систематична маніпуляція з дедуктивної компонентою.