Елементи математичної логіки, Доведені формули обчислення висловлювань та правила виведення
Наступним етапом у побудові обчислення висловлювань є виділення класу формул, що доводяться.Доказна формула– формула, одержувана з аксіом за допомогою правил виведення. Тут знову слід абстрагуватися від звичного поняття доказів.
Визначення доведених формул має той самий характер, як і визначення формули.
Спочатку визначаються вихідні формули, що доводяться (аксіоми), а потім визначаються правила виведення, які дозволяють з наявних доведених формул отримати нові формули, що доводяться.
Утворення формули, що доводиться, з вихідних доведених формул шляхом застосування правил виведення, називаєтьсявиводом формулиз аксіом.
Система аксіом обчислення висловлювань складається з таких формул.
У систему аксіом обчислення висловлювань входять 11 аксіом, які поділяються на чотири групи.
Перша група аксіом:
Друга група аксіом:
Третя група аксіом:
Четверта група аксіом:
IV1.
IV2.
IV3.
Якщо пам'ятати, що однією з інтерпретацій обчислення висловлювань є алгебра висловлювань, то легко бачити, що в даній інтерпретації перераховані вище аксіоми (як і взагалі доведені формули) є тавтологіями в алгебрі висловлювань, про що буде сказано нижче.
Існують такі правила виведення доведених формул.
1. Правило підстановки.
Якщо формулаAдоведена у вирахуванні висловлювань,хзмінна,B– довільна формула обчислення висловлювань, то формула, отримана в результаті заміни у формуліAзмінноюхусюди, де вона входить, формулоюB, є також доведеною формулою. Знову ж таки цеправило очевидно в алгебрі логіки. Якщо формула алгебри логіки є тавтологія, то заміна будь-якої змінної у формулі іншою довільною формулою також дасть тавтологію.
Операція заміни у формуліAзмінноюхформулоюBносить назвуправила підстановкиі символічно записується так:
.
Уточнимо сформульоване правило.
1.1. Якщо формулаAє змінною x, то підстановка даєB.
1.2. Якщо формулаAє зміннау, відмінна відx, то підстановка даєA.
1.3. ЯкщоA– формула, для якої підстановка вже визначена, то підстановкаBзамістьху запереченніAє заперечення підстановки, тобто
.
1.4. ЯкщоA1 таA2 – формули, для яких підстановки вже визначені, то підстановка
.
ЯкщоA– формула, що доводиться, будемо записувати це як .
Тоді правило підстановки можна записати схематично в такий спосіб:
.
І читається цей запис так: «Якщо формулаAяка стоїть над межею доведена, то формула, яка стоїть під межею, також доказується.
2. Правило укладання.
Правило укладанняформулюється так: якщо формулиAіA®Bдоведені в обчисленні висловлювань, то формулаBтакож доказується.
Схематичний запис цього правила має вигляд
.
Дамо суворе визначення формули, що доводиться.
2.1. Будь-яка аксіома є формулою, що доводиться.
2.2. Формула, отримана з доведеної формули шляхом застосування підстановки замість змінноїхдовільної формулиB, є формула, що доводиться.
2.3. ФормулаB, отримана з доведених формулAіA®Bшляхом застосуванняправила укладання, є формула, що доводиться.
2.4. Жодна інша формула обчислення висловлювань не вважається доведеною.
Процес отримання формул, що доводяться, будемо називатидоказом.
Наведемо приклади доказів.
1. Довести, що ¦A®A(рефлексивність імплікації).
Скористайтеся аксіомоюI2:
і виконаємо підстановку. Тоді отримаємо
Застосовуючи правило укладання до аксіоми до формули (1) і враховуючи аксіомуI1, отримуємо
У формулі (2) здійснимо підстановку
.
В результаті отримаємо формулу, що доводиться.
. (3)
Застосовуючи правило висновку до формули (3) з урахуванням аксіомиIV2, приходимо до формули, що доводиться (4)
Нарешті, здійснивши підстановку у формулі (4) замістьхформулиA, отримаємо
Похідні правила виведення, як і розглянуті правила підстановки та висновків, дозволяють отримувати нові формули, що доводяться. Вони виходять за допомогою правил підстановки та укладання, а тому є похідними від них.
1. Правило одночасної підстановки.
НехайA– формула, що доводиться;x1,x2, …,xn- змінні, аB1,B2, … ,Bn- будь-які формули обчислення висловлювань. Тоді результат одночасної підстановкиAзамістьx1,x2, …,xnвідповідно формулB1 ,B2, …,Bnє формулою, що доводиться.
Для доказу цього правила виберемо змінніz1,z2, …,znпопарно різні та відмінні від усіх змінних, що входять до формулиA,B1,B2, …,Bn. Тепер послідовно зробимо у формуліAnпідстановок, замінюючи спочаткух1 наz1, потімx2 наz2 і так даліі, нарешті,xnнаzn. Ці підстановки дають формули, що доводяться:
.
Далі проведемо послідовно щеnпідстановок у формулуA, замінюючи спочаткуz1 наB1, потімz2 наB2 і так далі і, нарешті,znнаBn. Ці підстановки дають формули, що доводяться.
.
Ясно, що формулаcn, що доводиться, виходить в результаті одночасної підстановки у формулуAзамість зміннихx1,x2, …,xnформулB1,B2, …,Bn.
Схематично операція одночасної підстановки записується у вигляді
.
2. Правило складного укладання.
Друге похідне правило застосовується до формул виду
і формулюється в такий спосіб.
Це твердження легко доводиться послідовним застосуванням правила укладання.
Дійсно, якщо формулиA1, іA1® (A2® (A3®(…(An)®L)…))) доведені, то за правилом укладання доведена формула
Продовжуючи ці міркування, ми нарешті доведемо, що формулаLдоведена.
Правило складного висновку схематично записується так:
.
3. Правило силогізму.
Якщо доводять формулиA®BіB®С, то доводиться формула ®С, тобто
.
Для доказу цього правила скористаємося аксіомамиI1 таI2 і зробимо наступні одночасні підстановки:
.
Отримаємо формули, що доводяться.
Крім того, за умовою доведені формули
З формул (8) та (6) за правилом висновку отримуємо
Але тоді з формул (9), (7) і (5) за правилом складного висновку маємо ¦A®С.
4. Правило контрпозиції.
Якщо доводиться формулаA®B, то доказуєтьсяформула
.
Для доказу цього правила, використавши аксіомуIV1 і зробивши одночасну підстановку
,
отримаємо формулу, що доводиться.
. (10)
Але за умовою доведена формула
З формул (2) та (1) за правилом висновку маємо
.
5. Правило зняття подвійного заперечення.
5.1. Якщо доводиться формула , то доведена формулаA®B.
5.2. Якщо доводиться формула , то доводиться формулаA®B, тобто.
.
Для доказу цього правила, скориставшись аксіомамиIV2,IV3 та виконавши підстановки
,
отримаємо формули, що доводяться.
, (12)
. (13)
Але за умовами 5.1 та 5.2 доведені формули
, (14)
. (15)
Таким чином, якщо виконано умову 5.1, то із формул (14) та (13) за правилом силогізму отримуємо
Якщо ж виконано умову 5.2, то формул (12) і (15) отримуємоA®B.