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

Об'єктна мова та метамова

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

Пропозіціональние формули будуть визначені як кінцеві послідовності символів, взятих з певного алфавіту. Можна розвинути теорію кінцевих послідовностей на строго аксіоматичної основі, але ми не будемо тут робити це. У доказах метатеорій ми будемо вільні використовувати будь-які добре відомі властивості натуральних чисел які нам можуть знадобитися, не стверджуючи їх на основі аксіом арифметики (з частини 1 ).

пропозіціональние формули

Пропозіціональная сигнатура - це безліч символів, званих атомами. Символи ¬ (заперечення), & (сполучення), видання (диз'юнкція) і Й (імплікація) називаються пропозіціональнимі зв'язками; ¬ - унарна зв'язка, а інші - бінарні.

Візьмемо непорожню пропозіціональному сигнатуру s, яка не містить ні пропозіціональних зв'язок, ні дужки (,). Алфавіт пропозіціональной логіки складається з атомів сигнатури s, пропозіціональних зв'язок і дужок. Під рядком ми розуміємо кінцеву послідовність (рядок) символів в цьому алфавіті.

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

Визначення 7. Безліч X рядків замкнуто щодо правил побудови (для логіки висловлювань), якщо

• кожен атом належить X,
• для будь-якого рядка F, якщо F належить X, то ¬F теж належить,
• для будь-яких рядків F, G і будь-який бінарної зв'язки Д, якщо F і G належать X, то також належить (F Д G).

2.1 Вкажіть два приклади безлічі рядків: одне замкнуте, інше не замкнутий щодо правил побудови.

Визначення 8 (Формула). Рядок F називається пропозіціональной формулою, якщо F належить всім множинам, які замкнуті щодо правил побудови.

2.2 Безліч формул замкнуто щодо правил побудови.

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

У двох наступних завданнях ми припускаємо, що розглянута сигнатура - це {p, q}.

2.3 Чи є формулою ¬ (p & q)?

2.4 Чи є формулою (p)?

Наступні два розділи обґрунтовують коректність понять, що вводяться нижче.

Доказ властивостей формул по індукції

семантика

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

Визначення 10 (Інтерпретація). Символи л, і ( `` брехня '', `` істина '') називаються істіностнимі значеннями. Інтерпретація пропозіціональной сигнатури s є функція з s в {л, і}.

Якщо s конечна, тоді інтерпретація може бути визначена таблицею її значень, наприклад:

Семантика логіки висловлювань, яку ми збираємося ввести, визначає які істіностние значення призначені формулою F інтерпретацією I.

Перш за все нам треба зв'язати функцію з кожної пропозіціональной зв'язкою - функцію з {л, і} в {л, і} з унарною зв'язкою ¬ і функцію з {л, і} ґ {л, і} в {л, і} з кожної бінарної зв'язкою. Функції визначаються наступними таблицями:

*

Для будь-якої формули F і будь-якій інтерпретації I істіностное значення FI, призначений формулою F інтерпретацією I, визначається як значення суперпозиції відповідних булевих функцій, а саме, в такий спосіб:

• FI = I (F) якщо F - атом,
• (¬F) I = ¬ (FI),
• (F Д G) I = Д (FI, GI) для кожної бінарної зв'язки Д.

Зауважимо, що це визначення рекурсивно: (¬F) I визначається через FI і (F Д G) I - через FI і GI.

Якщо FI = і, ми говоримо, що формула F істинна при інтерпретації I (символічно I | = F).

2.10 Знайдіть формулу F таку, що ( 3 ) - єдина інтерпретація, при якій F істинна.

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

л л л л і й і л л і й л

2.11 Для будь-яких формул F 1, ..., Fn (n и 1) і будь-якій інтерпретації I

1 & ··· & Fn) I = і тоді і тільки тоді, коли FI 1 = ··· = FIn = і.

2.12 Сформулюйте і доведіть подібний факт для диз'юнкції F 1 Комерсант ··· видання Fn.

У двох наступних завданнях ми припускаємо, що розглянута сигнатура конечна: s = {p 1, ..., pn}.

2.13 Для будь-якої інтерпретації I існує формула F така, що I - єдина інтерпретація, при якій F істинна.

2.14 Для будь-якої функції a з інтерпретацій в істінстние значення існує формула F така, що для всіх інтерпретацій I: FI = a (I).

Іншими словами, будь-яка таблиця істинності може бути представлена ​​пропозіціональной формулою. У цьому сенсі безліч пропозіціональних зв'язок, яке ми ввели `` повно ''.

нормальні форми

Визначення 11 (Еквівалентність). Формула F еквівалентна формулі G, якщо FI = GI для будь-якої інтерпретації I.

У завданнях 2.16 , 2.18 і 2.20 ми вводимо кілька `` нормальних форм '' таких, що будь-яка пропозіціональная формула може бути еквівалентно трансформована в будь-яку з цих форм.

2.15 Покажіть, що для атомів p і q

• кожна з формул p & q, p

Й q еквівалентна формулі, яка не містить зв'язок, крім видання та ¬,

Ред q, p Й q еквівалентна формулі, яка не містить зв'язок, крім & і ¬,

Ред q еквівалентна формулі, яка не містить зв'язок, крім Й і ¬.

2.16 Будь-яка формула еквівалентна

• формулою, яка не містить зв'язок, крім

Ред і ¬,

Й і ¬.

У поєднанні з результатом завдання 2.14 цей факт показує, що множини {видання, ¬}, {&, ¬} і {Й, ¬} - `` повні '' безлічі зв'язок - вони достатні для вираження будь-якої таблиці істинності. З іншого боку, безліч {видання, &, Й} НЕ `` повне '':

2.17 Припускаючи, що p - атом, покажіть що будь-яка формула, еквівалентна ¬p, містить принаймні одне заперечення. см. Вказівки

Літерал - це атом або заперечення атома. Елементарна кон'юнкція - це формула виду L 1 & ··· & Ln (n и 1), де L 1, ..., Ln - літерали. Будемо говорити, що формула знаходиться в диз'юнктивній нормальній формі, якщо вона має вигляд C 1 Комерсант ··· видання Cm (m и 1), де C 1, ..., Cm - елементарні кон'юнкції.

2.18 Будь-яка формула еквівалентна деякій формулі в диз'юнктивній нормальній формі.

Елементарна диз'юнкція - це формула виду L 1 Комерсант ··· видання Ln (n и 1), де L 1, ..., Ln - літерали. Будемо розмовляти. що формула знаходиться в кон'юнктивній нормальній формі, якщо вона має вигляд D 1 & ··· & Dm (m и 1), де D 1, ..., Dm - елементарні диз'юнкції.

2.19 Нехай F - формула в диз'юнктивній нормальній формі. Покажіть, що ¬F еквівалентно деякої формулою в кон'юнктивній нормальній формі.

2.20 Будь-яка формула еквівалентна деякій формулі в кон'юнктивній нормальній формі.

здійснимість

Визначення 12 (Здійснимість). Якщо існує інтерпретація, при якій формула F істинна, ми говоримо, що F здійсненна.

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

2.21 Нехай G - безліч літералів. Покажемо, що G здійснимо тоді і тільки тоді, коли не існує атома A, для якого і A і ¬A належать G.

Для будь-якого атома A літерали A, ¬A називаються додатковими друг до друга. Так, твердження останнього завдання може бути виражене в такий спосіб: безліч літералів здійснимо тоді і тільки тоді, коли воно не містить додаткових пар.

логічне слідування

Ми зараз визначимо в контексті логіки висловлювань, коли формула F `` слід '' з безлічі формул G. Ідея проходження центральна в логіці: в будь-який формальний аксіоматичної теорії `` теорема '' - це формула, яка випливає з аксіом.

Визначення 13 (Логічне слідування). Формула F (логічно) випливає з безлічі формул G (або безліч формул G тягне формулу F, символічно, G | = F), якщо для кожної інтерпретації, при якій всі формули G істинні, формула F також істинна. *

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

2.22 Припускаючи, що p і q - атоми, визначте

• чи слід q з (безлічі що складається з) p і p

Й q,

Й q.

2.23 G тягне F тоді і тільки тоді, коли G І {¬F} нездійсненна.

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

Поняття тавтології `` двояко '' поняттю здійсненним формули: F - тавтологія тоді і тільки тоді, коли ¬F нездійсненна. Визначення еквівалентних формул, дане вище, може бути переформулювати наступним чином: F еквівалентна G, якщо F є G - тавтологія.

2.24 Визначити, які з наступних формул є тавтологія: (p Й q) видання (q Й p), ((p Й q) Й p) Й p, ((p є q) є r) є (p є (q є r)).

2.25 Для будь-яких формул F, G 1, ..., Gn (n и 1): F випливає з {G 1, ..., Gn} тоді і тільки тоді, коли (G 1 & ··· & Gn) Й F - тавтологія.

пропозіціональний висновок

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

Про коректності, повноти і можливості розв'язання

Висновки в логіці висловлювань - наш основний об'єкт вивчення до кінця даної частини.

Висновок будуються з конструкцій, які називаються `` секвенціями ''.

Визначення 15 (Секвенция). Секвенция - це вираз виду G | - F ( `` F при посилках G '') або G | - ^ ( `` посилки G суперечливі ''), де F - формула і G - кінцеве безліч формул. *

Ми визначимо, які секвенції розглядаються `` початковими '', і опишемо кілька `` правил виведення '' для породження нових секвенций з секвенций, породжених раніше. Початкові секвенції називаються аксіомами.

Визначення 16 (Аксіоми). Аксіоми в обчисленні висловлювань мають вигляд

{F}

| - F.

Ми визначимо 12 правил виведення, і зручно вводити їх поступово.

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

Визначення 17 (Дерево докази). Дерево докази визначимо рекурсивно:

1. Деревом докази є пусте дерево докази, що складається тільки з кореня - аксіоми.
2. Нехай T 1, ..., Tk - дерева докази з корінням R 1, ..., Rk. Тоді (де S - деяка секвенция) - дерево докази, якщо S може бути отримана з R 1, ..., Rk за допомогою одного з правил виведення. Коренем такого дерева є S.

Визначення 18 (доказова секвенция). Якщо існує дерево докази з коренем R, то R називають доказовою секвенцій. Якщо цей корінь має вигляд G | - F, то говорять про виведення формули F з G.

У відповідність з дедуктивним визначенням проходження кажуть, що F випливає з G, якщо існує висновок F з підмножини G.

Правила для кон'юнкції і імплікації

G | - F & G (У &) G | - F
G І {F} | - G (В Й) G | - F Й G

У кожному з цих п'яти правил виведення, одне або два вирази над горизонтальною лінією представляють `` посилки '', до яких правило може бути застосовано, і вираз під рискою представляє `` висновок '' яке виводиться за цим правилом. Правила У & і В Й - `` правила введення '' кон'юнкції і імплікації; У & і У Й - `` правила видалення ''. Підставляючи конкретні формули замість метапеременних F і G і конкретні кінцеві безлічі формул замість метапеременной G деякий правило виведення, ми отримуємо приклад цього правила. наприклад,

є приклад правила введення кон'юнкції.

Приклад простого висновку. . Виведемо формулу q з посилки p & q. Цей висновок виходить за один крок за допомогою другого правила видалення кон'юнкції.

| - q (У &) {p & q} | - q

2.26 Знайдіть висновок q & p з p & q.

см. Рішення

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

2.27 (p & p) Й p.

2.28 (p & p) є p.

Правило введення посилки

Ми побудували кілька прикладів простих висновків. Однак, використовуючи тільки правила для кон'юнкції і імплікації, ми не зможемо побудувати висновок формули p & q з безлічі посилок {p, q}. Дійсно, формулу {p, q} | - p & q ми можемо отримати за допомогою правила (В &) з формулу {p, q} | - p і формулу {p, q} | - q. Однак `` очевидні '' формули {p, q} | - p і {p, q} | - q ми не зможемо вивести. У нас немає правила, що дозволяє виводити формулу з деякого безлічі посилок, якщо вона виводиться з більш вузького безлічі. Це правило виведення назвемо правилом введення посилки.

G | - F (ВП) G І {G} | - F

Приклад виведення. Ми наводимо висновок p Й ((p Й q) Й (p & q)) з порожньої безлічі посилок:

{P}

| - p (ВП) {p, p Й q} | - p {p} | - p (ВП) {p, p Й q} | - p {p Й q} | - p Й q (ВП ) {p, p Й q} | - p Й q (У Й) {p, p Й q} | - q (В &) {p, p Й q} | - p & q (В Й) {p} | - (p Й q) Й (p & q) (В Й) Ж | - p Й ((p Й q) Й (p & q))

2.29 Знайдіть висновок p Й r з p Й q і q Й r.

2.30 Знайдіть висновок r з p & q і p Й (q Й r).

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

2.31 p Й (q Й p).

2.32 p Й ((p & q) є q).

2.33 ((p & q) Й r) є (p Й (q Й r)).

Коректність правил виведення

Визначення 19 (Істинність секвенций). Секвенция G | - F тотожно істинна, якщо G тягне F. *

Визначення 20 (Коректність правил виводу). Правило виводу коректно, якщо для кожного прикладу цього правила посилки якого є тотожно істинними, його висновок також тотожно істинне.

2.34 Правило введення посилки коректно.

2.35 Обидва правила видалення кон'юнкції коректні.

2.36 Правило введення кон'юнкції коректно.

2.37 Правило видалення імплікації коректно.

2.38 Правило введення імплікації коректно.

Правила для заперечення і правила протиріччя

Наступні чотири правила виведення - правила введення і видалення заперечення `` правило відомості до протиріччя '' і `` правило протиріччя ''.

G І {F} | - ^ (В¬) G | - ¬F G І {¬F} | - ^ (У¬) G | - F

Виведіть секвенції:

2.39 {¬¬p} | - p.

см. Рішення 2.40 {p} | - ¬¬p.

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

2.41 ¬ (p & ¬p).

2.42 (p & ¬p) Й q.

Визначення 21 (Істинність секвенций). Секвенция G | - ^ тотожно істинна, якщо G нездійсненна.

2.43 Правило видалення заперечення коректно.

2.44 Правило введення заперечення коректно.

2.45 Правило протиріччя коректно.

Правила для диз'юнкції

Решта три правила виводу - правила введення і видалення диз'юнкції:

G | - F (В ред) G | - F видання G G | - F видання G G І F | - C G І G | - C (У ред) G | - C

Тут F і G - формули, і C - або формула, або ^.

Тепер опис системи виведення для логіки висловлювань завершено. *

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

Про те, як будувати дерево докази.

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

2.46 (p видання q) Й (q видання p).

2.47 (p видання p) є p.

2.48 ¬p Й ((p видання q) є q).

2.49 (p & (q видання r)) є ((p & q) видання (p & r)).

2.50 ¬¬p є p.

2.51 ¬ (p видання q) є (¬p & ¬q).

2.52 Обидва правила введення диз'юнкції коректні.

2.53 Правило видалення диз'юнкції коректно.

Коректність і повнота логіки висловлювань

Теорема коректності. Якщо існує висновок F з G, тоді G логічно тягне F.

Теорема повноти. Для будь-якої формули F і будь-якого безлічі формул G, якщо G тягне F, тоді існує висновок F з підмножини G.

Повнота логіки висловлювань (для іншого безлічі правил виведення) була встановлена ​​Еміл Постом в 1921 році.