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


Пропозіціональная формула

Пропозіціональная формула, яка є аксіомою, тотожно істинна.

Пропозіціональная формула А називається виведеної в обчисленні висловлювань, або теоремою числення висловів, якщо існує висновок, в якому остання формула дорівнює А. Такий висновок називають висновком формули А. У принципі можна було б і не вимагати, щоб формула А була останньою - все подальші формули можна просто викреслити.
 Пропозіціональная формула, загальнозначуща на 5ЛА, наз.

Будь-яку пропозіціональному формулу неважко перетворити в таку форму. У нашому випадку це робиться в такий спосіб.

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

Додавання недовідної пропозіціональной формули в якості схеми аксіом до переліку постулатів обчислення висловлювань порушує просту несуперечність останнього.

Для будь-якої пропозіціональной формули А можна побудувати класично еквівалентну їй І. В, що містить ті ж змінні, що і А.

Якщо А - пропозіціональная формула, то - iA - пропозіціональная формула.

Тоді для деяких пропозіціональних формул А і В розглянутого типу, які мають ступені g, формула D є А & Е або D є А V В.

Безліч ML всіх ФІНІТНОГО загальнозначущих пропозіціональних формул замкнуто щодо ниноді-мости в інтуїціонистська логіка п містить неї формули, виведені в цьому обчисленні. Тим самим ML є проміжною (або суперннтупцноіістской, з уперконструктівной) логікою, паз. Ця логіка містить формули, що не виводяться в інтуїціонистська логіка (така, напр. Логіка Медведєва має властивість диз'юнктивне: якщо формула виду A v Н ФІНІТНОГО общезначима, то принаймні одна з формул /1 пли Н ФІНІТНОГО общезначима. Келі пропозіціональная формула не містить будь-якого пз логічний. V, ID, то вона ФІНІТНОГО общезначима тоді п тільки тоді, коли виведена в інтуїціонистська логіка. Все ФІНІТНОГО загальнозначущі формули виведені н класичні.

Відповідність між F-залежностями і пропозіціональнимі формулами встановлюється безпосередньо.

Для того, щоб дві пропозіціональние формули Е і F були еквівалентні, необхідно, щоб вони були тотожно рівні; інакше кажучи, якщо - Е - F, то Е і F тотожно рівні.

По теоремі 10 ця пропозіціональная формула отримує значення f для деякого безлічі значень пропозіціональних букв, які вона містить.

Довести інтерполяційну теорему: якщо пропозіціональная формула Л D В - тавтологія, і формули - (А і В не є тавтологія, то існує пропозіціональная формула С, що містить тільки ті змінні, які входять як в А, так і в Б, така, що формули A D С і С D Б суть тавтології.

Покажіть, що вказане зіставлення пропозіціональних формул F - і MV-залежностям можна розширити на вкладені MV - залежно так, щоб збереглася еквівалентність відношення слідування.

Очевидно, що якщо в пропозіціональному формулу замість всіх пропозіціональних змінних підставити якісь формули мови першого порядку, то вийде формула мови першого порядку.

Теорема 6 була сформульована в термінах пропозіціональних формул. Але, в силу правила підстановки (теорема 3 § 25), вона може бути застосовна і до формул в інших сенсах, аби при цьому А, В, Сд виходили з пропозіціональних формул одночасної підстановкою формул замість пропозіціональних букв.

Цим доведено несуперечливість числення висловів в термінах пропозіціональних формул. Якщо А і - i A - доказові формули обчислення з іншим поняттям формули, то, в силу зворотного правила підстановки (теорема 4 § 25), є доказові пропозіціональние формули А і - i А. Таким чином, несуперечливість поширюється і на випадки формул в інших сенсах.

Програма, керована зразками, для автоматичного доведення теорем. Залишається ще одне питання: як перетворити задану пропозіціональному формулу в кон'юнктівную нормальну форму.

якщо при деякому застосуванні правила виведення посилки є тотожно істинними пропозіціональнимі формулами, то і висновок є тотожно істинною пропозіціональной формулою.

Якщо А, В, Сд і Св - пропозіціональние формули, пов'язані один з одним, як в попередньому визначенні заміни, то А-В ь - СА-СВ.

Якщо А - пропозіціональная формула, то - iA - пропозіціональная формула.

Булева функція і задає її формула. Будь-яка булева функція п аргументів може бути записана у вигляді пропозіціональной формули.

У § 3 глави 2 було введено поняття тавтології як пропозіціональной формули, яка перетворюється в істинне висловлення при будь-підстановці в неї конкретних висловлювань замість пропозіціональних змінних. Поширимо поняття тавтології на формули мови першого порядку.

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

Чи існує спосіб для з'ясування в кінцеве число кроків тотожною істинності довільної пропозіціональной формули. Як випливає видозмінити визначення пропозіціональной формули, щоб всі такі формули можна було б записувати словами кінцевого алфавіту.

Припустимо, що методами § § 52 і 56 побудована геделевская нумерація для пропозіціональних формул з цифрами. Нехай Н (а) а - геделевскій номер формули, що належить FJ; тоді предикат Н рекурсівен.

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

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

Якщо при деякому застосуванні правила виведення посилки є тотожно істинними пропозіціональнимі формулами, то і висновок є тотожно істинною пропозіціональной формулою.

Для того щоб показати, що ДНФ-тавтології Р - зводиться до D3 припустимо, що А - пропозіціональная формула в диз'юнктивній нормальній формі. Таким чином, ми зменшили число кон'юнкція в BI, і цей процес можна повторювати до тих пір, поки в кінці кінців - не знайдемо формули, яка має не більше трьох атомів в кожній кон'юнкції. Ясно, що весь процес обмежений за часом деяким поліномом від довжини А.

Покажіть, що всі правила виведення для F-залежностей переходять в коректні логічні правила виводу, якщо F-залежності інтерпретуються як пропозіціональние формули.

Пропозиціонального числення, і з ч і з ледачий висловлювання і, - логічне числення, в к-ром виведеними об'єктами є пропозіціональние формули.

Як кажуть, ми маємо тут одинадцять схем аксіом; з кожної схеми можна отримати різні конкретні аксіоми, замінюючи входять до неї букви на пропозіціональние формули.

Довести інтерполяційну теорему: якщо пропозіціональная формула Л D В - тавтологія, і формули - (А і В не є тавтологія, то існує пропозіціональная формула С, що містить тільки ті змінні, які входять як в А, так і в Б, така, що формули A D С і С D Б суть тавтології.

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

Покажіть, що всі правила виведення для одних MV-залежностей і для F-залежностей спільно з MV-залежностями переходять в коректні логічні правила, коли F - і MV-залежності інтерпретуються як пропозіціональние формули.

Покажіть, що всі правила виведення для одних MV-залежностей і для F-завіснмостей спільно з MV-залежностями переходять в коректні логічні правила, коли F - і MV-залежності інтерпретуються як пропозіціональние формули.

Один спосіб реалізації цієї процедури полягає в формуванні так званої загальної розгортки F над універсумом з р елементів з подальшим пред'явленням її на вхід процедури, яка розпізнає здійсненність пропозіціональних формул.

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

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

Пропозіціональная формула називається тавтологією, якщо вона перетворюється в істинне висловлення при будь-підстановці конкретних висловлювань замість змінних; кожна тавтологія є схемою справжніх висловлювань і в цьому сенсі висловлює певний логічний закон. Наведемо приклади логічних законів: (Р V - Р) - закон виключеного третього; (- I - iP Р) - закон подвійного заперечення; - I (P & - iP) - закон суперечності; (((Р D Q) D Р) D Р) - закон Пірса.

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

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

Чи існує спосіб для з'ясування в кінцеве число кроків тотожною істинності довільної пропозіціональной формули. Як випливає видозмінити визначення пропозіціональной формули, щоб всі такі формули можна було б записувати словами кінцевого алфавіту.

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