Дискретна математика

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

Для цього остаточно визначимося з виділеними елементами. Очевидно, що замість виділеного елемента 0 (роль якого в алгебрі Кантора відіграє порожня множина ) варто перевірити абсолютно хибне висловлювання F (так ми назвемо заперечення абсолютно істинного висловлювання), а замість виділеного елемента 1 (роль якого в алгебрі Кантора відіграє універсальна множина U) є природним використати абсолютно істинне висловлювання Т.

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

3) асоціативність:

131

7)властивість подвійного заперечення:

А=(А );

8)правило де Моргана:

( А В ) =А В, ( А В ) =А В.

Тепер ми можемо сказати, що побудували алгебраїчну систему, яка належить до булевих алгебр, носієм якої є множина висловлювань, а операціями - логічні кон`юнкція, диз`юнкція, заперечення, носій містить виділені елементи, відносно яких та логічних зв`язок виконуються всі властивості булевої алгебри. Ця базова алгебраїчна система називається булевою алгеброю висловлювань або алгеброю висловлювань. Таким чином, на алгебру висловлювань ми можемо поширити всі відомі результати, що стосуються булевих алгебр. Наприклад, відоме в булевих алгебрах правило поглинання x (x y) = x може бути використане в алгебрі висловлювань у вигляді A (A B) = A для того ж спрощення складних висловлювань.

Для поглиблення уявлень про тотожність висловлювань буде корисно пов`язати її з еквівалентністю.

Справедлива наступна Теорема 6.6. А = В тоді і тільки тоді, коли висловлювання А ~ В асолютно істинне.

Доведення.

Пряма теорема.

Нехай А = В. Тоді, за означенням тотожності, А і В мають однакові таблиці істинності. Звідси, за означенням зв`язки еквівалентність, висловлювання А ~ В буде істинним на всіх наборах значень істиності висловлювань А та В, тобто абсолютно істинним.

Обернена теорема доводиться аналогічно.

Теорема доведена.

При алгебраїчних перетвореннях можна використовувати також властивості відношення тотожності як відношення еквівалентності:

а) рефлексивність: А = А; б) симетричність: якщо А = В, то В = А;

в) транзитивність: якщо А = В і В = С, то А = С.

Отже, ми сформували алгебраїчну систему для висловлювань і тепер можемо використовувати алгебраїчний метод для вирішення проблем логіки.

112.Елемент рні кон'юнкція т диз'юнкція

Крім контрарних пар зручні особливості мають форми, які називаються елементарними кон`юнкціями і диз`юнкціями.

Означення. Елементарною диз`юнкцією (кон`юнкцією) будемо називати складне висловлювання, що має такий вигляд A1 A2 ... An (A1 A2 ... An), де Ai, i = 1,2, ... ,n є простим висловлюванням або його запереченням.

Якщо треба аналізувати висловлювання, яке не є висловлюванням зазначеного вище вигляду, то використовуючи алгебраїчні перетворення ми можемо здійснити спробу привести його до вигляду елементарної диз`юнкції або кон`юнкції. Елементарні диз`юнкція та кон`юнкція дуже зручні для встановлення абсолютної істинності (хибності) складних висловлювань. Критерії абсолютної істинності (хибності) встановлюють наступні

Теорема 6.7. Елементарна диз`юнкція абсолютно істинна тоді і тільки тоді, коли вона містить щонайменше пару висловлювань, з яких одне є запереченням іншого.

Доведення.

Прям теорем .

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

Обернен теорем .

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

132

висловлюванням без заперечення значення F, а простим висловлюванням із запереченням - значення T. За властивостями зв`язок заперечення і диз`юнкції, елементарна диз`юнкція набуде значення F, що протирічить умові. Звідси випливає, що для того, щоб елементарна диз`юнкція була істинною, необхідна наявність в ній пари висловлювань, з яких одне є запереченням іншого.

Теорема доведена.

Теорема 6.8. Елементарна кон`юнкція абсолютно хибна тоді і тільки тоді, коли вона містить щонайменше пару висловлювань, з яких одне є запереченням іншого.

Доведення.

Прям теорем .

Нехай елементарна кон`юнкція містить таку пару Ai,Ai. Якщо вони не стоять поруч, то ми можемо поставити їх поруч, скориставшись властивістю комутативності. Тепер, виходячи з властивостей заперечення та кон`юнкції алгебри висловлювань, за кілька кроків алгебраїчних перетворень отримаємо бажаний результат, тобто те, що елементарна кон`юнкція набуде значення F.

Обернен теорем .

Нехай елементарна кон`юнкція абсолютно хибна. Покажемо, що вона містить зазначену в умові теореми пару. Доведення поведемо від супротивного. Нехай це не так. Присвоїмо простим висловлюванням без заперечення значення T, а простим висловлюванням із заперечення - значення F. За властивостями зв`язок заперечення і кон`юнкції, елементарна кон`юнкція набуде значення T, що протирічить умові теореми. Виходячи з цього, робимо висновок, що для того, щоб елементарна кон`юнкція була абсолютно хибною необхідна наявність в ній зазначеної пари.

Теорема доведена.

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

113.Диз'юнктивн і кон'юктивн норм льні форми

Нормальні форми широко використовуються всюди в дискретній математиці і зокрема в математичній логіці.

Означення. Диз`юнктивною нормальною формою (ДНФ) будемо називати диз`юнкцію

Критерії встановлення абсолютної істинності та абсолютної хибності за допомогою ДНФ і КНФ формулюється у вигляді наступних

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

Доведення.

Прям теорем .

Нехай умова виконується. Тоді, на підставі властивостей елементарної кон`юнкції (теорема 6.8.), кожна із елементарних кон`юнкцій, що входять до складу ДНФ, набуде значення F. Тоді, очевидно, і вся ДНФ набуде значення F згідно з означенням диз`юнкції.

Обернен теорем .

Нехай ДНФ абсолютно хибна. Покажемо, що повинна виконуватись умова теореми. Доведення поведемо від супротивного. Нехай умова теореми не виконується. Використовуючи прийом, який ми застосовували в доведенняі теорем 6.7 і 6.8, можемо побудувати такий набір значень істинності простих висловлювань, при якому ДНФ набуде значення T, що буде суперечити умові.

Теорема доведена.

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

Доведення.

Прям теорем .

Нехай умова виконується. Тоді, на підставі властивостей елементарної диз`юнкції, кожна із елементарних диз`юнкцій, що входять до складу КНФ, набуде значення T. Тоді, очевидно, і вся КНФ набуде значення T згідно з означенням кон`юнкції.

133

Обернен теорем .

Нехай КНФ абсолютно істинна. Покажемо, що повинна виконуватися умова теореми. Доведення поведемо від супротивного. Нехай умова не виконується. Використовуючи прийом, який ми застосовували при доведенні теорем 6.7 і 6.8, можемо побудувати такий набір значень істинності простих висловлювань, при якому КНФ набуде значення F, що буде суперечити умові теореми.

Теорема доведена.

Таким чином, якщо нам необхідно встановити абсолютну істинність (хибність) складного висловлювання, то ми повинні:

1.Алгебраїчними перетвореннями звести складне висловлювання до КНФ (ДНФ).

2.Використовуючи критерій із теореми 6.10 (6.9), встановити абсолютну істинність (хибність) вихідного складного висловлювання або їх відсутність.

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

114.Двоїстість висловлюв нь т їх вл стивості

Для того, щоб реалізувати згаданий вище підхід на практиці введемо необхідні означення. Означення. Нехай складне висловлювання A утворене з простих висловлювань A1, ... ,An та їх

заперечень лише за допомогою зв‘язок та . Висловлювання A’ будемо називати двоїстим висловлюванню A, якщо воно отримане з висловлювання A заміною зв`язок і на, відповідно, і та T і F, якщо вони зустрічаються у висловлюванні A на, відповідно, F і T.

Справедлива наступна

Теорема 6.12 (принцип двоїстості). Нехай A і B - складні висловлювання, A’ і B’ - відповідні їм двоїсті висловлювання. Тоді справедливі такі твердження:

а) якщо висловлювання A абсолютно істинне, то висловлювання A’ абсолютно істинне;

б) якщо висловлювання A абсолютно істинне, то висловлювання A’ абсолютно істинне;

в) якщо висловлювання A ~ B абсолютно істинне, то висловлювання A’ ~ B’ абсолютно істинне; г) якщо висловлювання A B абсолютно істинне, то висловлювання B’ A’ абсолютно

істинне.

Доведення твердження а).

Якщо висловлювання A абсолютно істинне, то його згідно теорем 6.10 та 6.11 можна подати у вигляді КНФ, яка містить в кожній елементарній диз‘юнкції контрарну пару або висловлювання T. Але тоді перехід від висловлювання А до двоїстого йому висловлювання А’ очевидно дозволить отримати висловлювання А’, що знаходиться в ДНФ, кожна елементарна кон` юнкція якої містить контрарну пару або висловлювання F. Виходячи з теореми 6.9, робимо висновок про те, що висловлювання А’

абсолютно хибне. Тоді А’ є абсолютно істинним висловлюванням, що й потрібно було довести.

Доведення твердження б).

Якщо висловлювання А абсолютно істинне, то висловлювання А можна подати у вигляді ДНФ, кожна елементарна кон`юнкція якої містить контрарну пару або висловлювання F. Тоді висловлювання А’, двоїсте висловлюванню А, буде мати вигляд КНФ, кожна диз‘юнкція якої містить контрарну пару або висловлювання T. Виходячи з теореми 6.10, робимо висновок, що висловлювання А’ абсолютно істинне, що й потрібно було довести.

Доведення твердження в).

Як видно із таблиць істинності, висловлювання А В та А` В` набувають однакових значень істинності при однакових А і В, тому якщо А В абсолютно істинне, то А` В` також абсолютно істинне.

Доведення твердження г).

Як видно із таблиць істинності, висловлювання А В та В` А` набувають однакових значень істинності при однакових А та В, тому якщо А В абсолютно істинне, то В` А` також абсолютно істинне.

Теорема доведена.

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

115.Озн чення числення висловлюв нь

1. Мов числення L.

1.1 Символи числення L:

а) пропозиційні літери: А, В, С, ... (інколи вони будуть з індексами);

б) символи зв`язок: ,; в) службові символи: ( , ) .

1.2Довільна послідовність символів мови числення L називається виразом мови числення L.

1.3Формули мови числення L:

а) довільна пропозиційна літера є формулою;

134

116.Дедуктивні вл стивості числення L

Слід звернути увагу на те, що вивід - надзвичайно проста конструкція. Операції, які треба виконувати при його побудові чітко визначені. Але все це ніяк не гарантує нас від одноманітного, нудного і можливо дуже довгого перебору аксіом та застосувань правила виведення МР.

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

Будемо використовувати для формулювання результатів про дедуктивні властивості числення L термін ―метареорема‖ для того, щоб не вносити плутанину між цими результатами та власне теоремами числення L.

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

Справедливі наступні

Метатеорема 6.1. Якщо | А і , то | А.

Доведення. Виходячи з того, що | А, робимо висновок про те, що існує послідовність A1, A2, ... , An , в якій An є формулою A і кожна формула Ai, i=1, ..., n є або формулою із , або аксіомою, або отримана за правилом виведення із попередніх формул послідовності. Але кожна формула із є формулою із , тому ми можемо стверджувати, що кожна формула A1, A2, ... , An належить , є аксіомою або отримана за правилом виведення із попередніх формул. Тобто | А.

Метатеорема доведена.

Метатеорема 6.2. | А тоді і тільки тоді, коли знайдеться скінченна підмножина така, що | А.

Доведення.

Пряма метатеорема.

Нехай | А. Покажемо, що існує скінченна підмножина така, що | А. Візьмемо всі формули із , що були використані для виведення A, і сформуємо з них окрему множину . Очевидно, щоскінченна і . Але тоді ми можемо записати | А.

Обернена метатеорема.

Нехай | А і . Покажемо, що | А. Висновок про це базується на метатеоремі 6.1.

Метатеорема доведена.

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

Метатеорема 6.3. Якщо | А і для кожної формули B відомо, що | B, то | А.

Доведення. Якщо | А, то існує вивід А1, ... , Аn, в якому Аn співпадає з А. Замінимо тоді всі формули цього виводу, які входять в нього на основі того, що вони належать до , виводами із множини формул .

Очевидно, що ми отримаємо послідовність, в якій кожна формула належить до , є аксіомою або отримана за правилом МР з попередніх. За означенням це вивід формули А із множини , тобто | А.

Метатеорема доведена.

Цікаву властивість виводу демонструє наступна

Метатеорема 6.4. Позначимо через S( ) все теореми, які можна вивести з множини формул . Тоді

S(S( )) = S( ).

Доведення. Згідно з означенням виводу формули із множини формул S(S( )) S( ). Залишається показати, що S( ) S(S( )).

Доведемо від супротивного. Нехай множина формул S(S(Г)) включає в себе множину S(Г) як власну підмножину. Це означає, що вона містить якусь підмножину формул, які не входять до S(Г). Візьмемо з цієї підмножини довільну формулу А. Якщо вона належить до множини S(S(Г)), то вона виводиться із множини формул Г і S(Г) і не виводиться із множини Г. Але множина S(Г) виводиться із множини Г. Тому перетворимо вивід формули А таким чином: кожну формулу виводу, яка належить до множини Г, залишимо, а ті формули, які належать до множини S(Г) і не належать множині Г, замінимо у виводі послідовністю формул (виводом формули із множини Г). Отримаємо послідовність формул, яка містить або формули із множини Г, або ті формули, які отримані за допомогою аксіом та правил виводу із попередніх. А це значить, що ми вивели формулу А із множини Г. Тому припущення невірне.

Метатеорема доведена.

В математиці основним прийомом доведення теорем вигляду ―Якщо А, то В‖ є виведення В як теореми з А. Саме так найчастіше побудоване доведення теорем в багатьох розділах математики. Справедливість результатів, отриманих завдяки цьому прийому, встановлює наступна

136

117.Теорем дедукції

Метатеорема 6.5. (Теорема дедукції Ербрана ). Нехай - множина формул, A і B - деякі формули. Якщо , A | B, то | A B. Зокрема, якщо A | B, то | A B.

Доведення. Ідея доведення - індукцією за довжиною виводу.

Крок 1. Вивід містить єдину формулу А1, причому А1 співпадає з B. Тоді можливі такі випадки на підставі яких А1 попадає в цей вивід:

а) формула А1 - аксіома. Будуємо послідовність:

Метатеорема доведена.

Частіше використовується не сама теорема дедукції, а такі її наслідки:

Наслідок 1 метатеореми 6.5. A B, B C A C.

Доведення. Нехай A B, B C, A - гіпотези. Двічі застосовуючи правило виводення, отримаємо С, тобто A B, B С, А С. Згідно теореми дедукції A B, B C A C.

Наслідок 1 доведений.

Наслідок 2 метатеореми 6.5. A (B C), B | A C.

Доведення. Нехай A (B C), A, B - гіпотези. Двічі застосовуючи правило виводення, отримаємо С, тобто A (B C), В, А С. Згідно теореми дедукції A (B C), B | A C.

137

Наслідок 2 доведений.

Теорема дедукції має важливе практичне значення, тому що дозволяє спростити процедуру побудови потрібного виводу. Наприклад, застосовуючи теорему дедукції, вивід формули A А можна було б значно скоротити. Дійсно, нехай А - гіпотеза. Тоді А | А, а за теоремою дедукції | A А.

118.Вл стивості виводу з гіпотез ми

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

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

Гіпотез - довільна формула, яка може набувати довільного значення істинності. Гіпотезу у загальному випадку вивести неможливо. Гіпотези можна використовувати у виводі, відзначаючи проте, цей факт стосовно здобутої теореми. Таким чином, результати Г | A та | A суттєво відрізняються. Перший з них підтвержує існування виводу для А, в якому, крім аксіом, використані формули з множини гіпотез Г. Другий же підкреслює, що вивід A може бути побудований без використання гіпотез. Згідно метатеореми 6.1 результат Г | A не обов‘язково вимагає присутності у виводі A гіпотез із множини Г, але поява гіпотез у виводі формули А можлива. Але якщо у виводі формули А були використані гіпотези з множини Г, то ми не можемо писати | A, а тільки Г | A.

В цьому пл ні використ ння суперечливих гіпотез при виведенні формули з пункту в) мет теореми 6.6 може зд тися неприйнятним. Дійсно, н явність суперечливих гіпотез дозволяє вивести будь-яку формулу B, в тому числі і не бсолютно істинну. Але використ ння в виведенні суперечливих гіпотез ми м ніфестуємо з писом А, А В. І тільки теорем дедукції дозволяє внести суперечливі гіпотези до формули, що виведен . А вже отрим ний т ким чином результ т А (А В) є бсолютно істинною

формулою.

Покажемо, що вивід формули з пункту в) метатеореми 1.6 можна отримати лише з однією гіпотезою:

Таким чином, виведена формула А В, але з використанням гіпотези А. Тому ми не маємо права записати | А В, а маємо право і повинні записати А | А В. Отже, за теоремою дедукції А (А В).

Легко перевірити, що ні А, ні А В не є абсолютно істинними формулами. Але це не повинно нас бентежити, тому що ми пам‘ятаємо, що одержали висновок А В тільки за умови А. Це ще раз підкреслює ідею наслідування теоремами властивостей аксіом і гіпотез. Включили до виводу гіпотезу А, яка не є абсолютно істинною формулою, і одержали формулу А В, яка також не є абсолютно істинною.

Але гідно пильної уваги те, що, застосувавши теорему дедукції Ербрана, дістанемо з А | А В - абсолютно істинну формулу А (А В), що є теоремою числення L.

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

1)А А – гіпотеза;

2)А А - теорема.

Таким чином, можна записати (А А) | (А А), звідки за теоремою дедукції здобудемо (А

А) (А А). У цьому прикладі гіпотеза не бере участі конструктивно (тобто в одержанні наслідків за правилом виведення) у формуванні останньої формули виводу. Тому може виникнути враження, що

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

бо замість А А за означенням виводу може бути підставлена або аксіома, або теорема, або сама гіпотеза, але ніяк не довільна формула.

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

138

Інколи, наприклад після багатьох невдалих спроб виведення, для формули важливо встановити те, за яких умов (гіпотез) її можна вивести. Аналіз гіпотез дозволив би припинити чи продовжувати спроби. Тому важливі універсальні способи формування гіпотез для довільної формули.

Наведемо один такий важливий спосіб формування гіпотез для довільної формули A. Слід відзначити, що довільну формулу для числення висловлювань можна побудувати в з допомогою багатокрокової

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

Дійсно, означення формул числення L працює як генератор формул: спочатку вводиться підмножина формул шляхом включення до множини формул пропозиційних літер; потім формули можна отримати із

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

формули зв‘язкою або застосовуємо до утвореної формули зв‘язку і кожна формула може бути утворена тільки таким чином.

Нехай формула A задана таблицею:

Тут A1, A2, ... , An - пропозиційні літери, які входять до складу формули A. Позначимо множину гіпотез, що формуються на основі i-го рядка таблиці, як i . Включимо у i , для всіх j = 1, ..., n, Aj, якщо Aj

в рядку i має значення T, абоAj, якщо Aj набуває значення F в рядку i. Справедлива наступна

Метатеорема 6.7. Нехай формула A задана таблицею істинності і множина i , i = 1, ..., 2n, визначена за приведеним вище означенням. Тоді, якщо в рядку i формула A набуває значення T, то i | A, а якщо в

рядку i формула A набуває значення F, то i | A.

Доведення. Ідея доведення - індукцєю за кількістю зв‘язок у формулі A.

Крок 1. Покажемо, що метатеорема виконується для числа зв‘язок 0 (нуль). Тобто формула складається лише із однієї пропозиційної літери: A має вигляд A. Тоді таблиця має вигляд:

тому що формула А має вигляд А.

Крок 2. Індуктивне припущення: нехай метатеорема виконується для числа зв‘язок r. Крок 3. Покажемо, що метатеорема виконується для числа зв‘язок r+1.

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

а) формула A отримана як заперечення деякої формули B, тобто A має виглядB.

Утакому випадку для формули B виконується індуктивне припущення. Відзначимо, що в формулах A

іB однакова кількість пропозиційних літер, тобто в таблицях істинності обох формул буде однакова кількість рядків та стовпців, відповідно.

Нехай формула A в i-тому рядку таблиці істинності набуває значення T. Тоді в цьому ж рядку

формула B набуває значення F. Тоді, за індуктивним припущенням, виконується i | B. АлеформулаB

це і є формула A, тобто i | A. Якщо в i-тому рядку таблиці істинності формула A набуває значення F, то в цьому ж рядку формула B набуває значення T. Тоді, за індуктивним припущенням, виконується i | B. За метатеоремою 6.6 (пунт б) | B B і за правилом MP з двох останніх формул отримуємо i | B. Але

B - формула A. Таким чином, отримуємо i | A;

б) формула A отримана за допомогою зв‘язки з формул В і С, тобто має вигляд B C. Тоді для формул B і C виконується індуктивне припущення.

139