логіка висловлювань

1. Алфавіт мови логіки висловлювань [ правити | правити код ]
2. Пропозіціональние змінні [ правити | правити код ]
3. Пропозіціональние формули [ правити | правити код ]
4. Угоди про дужках [ правити | правити код ]
5. Формалізація і інтерпретація [ правити | правити код ]
6. Аксіоми і правила виводу формальної системи логіки висловлювань [ правити | правити код ]
7. Таблиці істинності основних операцій [ правити | правити код ]
8. Тотожно істинні формули (тавтології) [ правити | правити код ]

Логіка висловлювань, або пропозіціональная логіка ( лат. propositio - «висловлювання» [1] ), Або числення висловів [2] - це розділ символічної логіки , Що вивчає складні висловлювання , Утворені з простих, і їх взаємини. На відміну від логіки предикатів , Пропозіціональная логіка не розглядає внутрішню структуру простих висловлювань, вона лише враховує, за допомогою яких союзів і в якому порядку прості висловлювання сочленяются в складні [3] .

Незважаючи на свою важливість і широку сферу застосування, логіка висловлювань є найпростішою логікою і має дуже обмежені кошти для дослідження суджень [2] .

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

Алфавіт мови логіки висловлювань [ правити | правити код ]

Вихідні символи, або алфавіт мови логіки висловлювань, розділені на наступні три категорії [1] [5] :

• пропозіціональние літери (пропозіціональние змінні):

p, q, r, s, t, p 1, q 1, r 1, s 1, t 1,. . . {\ Displaystyle p, q, r, s, t, p_ {1}, q_ {1}, r_ {1}, s_ {1}, t_ {1}, ...}

• логічні знаки (логічні союзи):

Пропозіціональние змінні [ правити | правити код ]

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

Пропозіціональние формули [ правити | правити код ]

Роль структурних утворень, аналогічних елементарним і складним висловлюванням, грають в цій мові формули. Пропозіціональная формула - слово мови логіки висловлювань [6] , Тобто кінцева послідовність знаків алфавіту, побудована за викладеними нижче правилами і утворює закінчений вираз мови логіки висловлювань [1] . Великі латинські літери A {\ displaystyle A} , B {\ displaystyle B} та інші, які вживаються у визначенні формули, належать не мови логіки висловлювань, а його метамови, тобто мови, який використовується для опису самої мови логіки висловлювань. Містять метабукви вираження ¬ A {\ displaystyle \ neg A} , (A → B) {\ displaystyle (A \ to B)} і інші - не пропозіціональние формули, а схеми формул. Наприклад, вираз (A ∧ B) {\ displaystyle (A \ wedge B)} є схема, під яку підходять формули (p ∧ q) {\ displaystyle (p \ wedge q)} , (P ∧ (r ∨ s)) {\ displaystyle (p \ wedge (r \ vee s))} та інші [1] .

індуктивне визначення формули логіки висловлювань: [4] [1]

1. пропозіціональная змінна є формула;
2. якщо A {\ displaystyle A} - довільна формула, то ¬ A {\ displaystyle \ neg A} - теж формула;
3. якщо A {\ displaystyle A} і B {\ displaystyle B} - довільні формули, то (A → B) {\ displaystyle (A \ to B)} , (A ∧ B) {\ displaystyle (A \ wedge B)} , (A ↔ B) {\ displaystyle (A \ leftrightarrow B)} , (A ∨ B) {\ displaystyle (A \ vee B)} і (A ∨ ˙ B) {\ displaystyle (A ~ {\ dot {\ lor}} ~ B ~)} - теж формули.

Інших формул в мові логіки висловлювань немає.

Щодо будь-якій послідовності знаків алфавіту мови логіки висловлювань можна вирішити, є вона формулою чи ні. Якщо ця послідовність може бути побудована відповідно до пп. 1-3 визначення формули, то вона формула, якщо ні, то не формула [1] .

Угоди про дужках [ правити | правити код ]

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

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

Наприклад: запис A ∨ B ∧ ¬ C {\ displaystyle A \ vee B \ wedge \ neg C} означає формулу (A ∨ (B ∧ (¬ C))) {\ displaystyle (A \ vee (B \ wedge (\ neg C)))} , А її довжина дорівнює 12.

Формалізація і інтерпретація [ правити | правити код ]

Як і будь-який інший формалізований мову , Мова логіки висловлювань можна розглядати як безліч всіх слів, побудованих з використанням алфавіту цієї мови [7] . Мова логіки висловлювань можна розглядати як безліч всіляких пропозіціональних формул [4] . Пропозиції природної мови можуть бути переведені на символічну мову логіки висловлювань, де вони будуть представляти із себе формули логіки висловлювань. Процес перекладу висловлювання в формулу мови логіки висловлювань називається формалізацією. Зворотний процес підстановки замість пропозиційних змінних конкретних висловлювань називається інтерпретацією [8] .

Аксіоми і правила виводу формальної системи логіки висловлювань [ правити | правити код ]

Одним з можливих варіантів ( гильбертовськой ) Аксиоматизации логіки висловлювань є наступна система аксіом:

A 1: A → (B → A) {\ displaystyle A_ {1}: A \ rightarrow (B \ rightarrow A)} ;

A 2: (A → (B → C)) → ((A → B) → (A → C)) {\ displaystyle A_ {2} :( A \ rightarrow (B \ rightarrow C)) \ rightarrow ((A \ rightarrow B) \ rightarrow (A \ rightarrow C))} ;

A 3: A ∧ B → A {\ displaystyle A_ {3}: A \ wedge B \ rightarrow A} ;

A 4: A ∧ B → B {\ displaystyle A_ {4}: A \ wedge B \ rightarrow B} ;

A 5: A → (B → (A ∧ B)) {\ displaystyle A_ {5}: A \ rightarrow (B \ rightarrow (A \ wedge B))} ;

A 6: A → (A ∨ B) {\ displaystyle A_ {6}: A \ rightarrow (A \ vee B)} ;

A 7: B → (A ∨ B) {\ displaystyle A_ {7}: B \ rightarrow (A \ vee B)} ;

A 8: (A → C) → ((B → C) → ((A ∨ B) → C)) {\ displaystyle A_ {8} :( A \ rightarrow C) \ rightarrow ((B \ rightarrow C) \ rightarrow ((A \ vee B) \ rightarrow C))} ;

A 9: ¬ A → (A → B) {\ displaystyle A_ {9}: \ neg A \ rightarrow (A \ rightarrow B)} ;

A 10: (A → B) → ((A → ¬ B) → ¬ A) {\ displaystyle A_ {10} :( A \ rightarrow B) \ rightarrow ((A \ rightarrow \ neg B) \ rightarrow \ neg A )} ;

A 11: A ∨ ¬ A {\ displaystyle A_ {11}: A \ vee \ neg A} .

разом з єдиним правилом:

A (A → B) B {\ displaystyle {\ frac {A \ quad (A \ rightarrow B)} {B}}} ( Modus ponens )

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

Таблиці істинності основних операцій [ правити | правити код ]

Основним завданням логіки висловлювань є встановлення истинностного значення формули, якщо дані істинності значення входять до неї змінних. Істінностное значення формули в такому випадку визначається індуктивно (з кроками, які використовувалися при побудові формули) з використанням таблиць істинності зв'язок [9] .

Нехай B {\ displaystyle \ mathbb {B}} - безліч всіх істиннісних значень {0, 1} {\ displaystyle \ {0,1 \}} , А V a r s {\ displaystyle Vars} - безліч пропозіціональних змінних. Тоді інтерпретацію (або модель) мови логіки висловлювань можна представити у вигляді відображення

M: V a r s → B {\ displaystyle M \ colon Vars \ to \ mathbb {B}} ,

яке кожну пропозіціональному змінну p {\ displaystyle p} зіставляє з істінностним значенням M (p) {\ displaystyle M (p)} [9] .

Оцінка заперечення ¬ p {\ displaystyle \ neg p} задається таблицею:

Значення двомісних логічних зв'язок → {\ displaystyle \ rightarrow} (Імплікація), ∨ {\ displaystyle \ vee} (Диз'юнкція) і ∧ {\ displaystyle \ wedge} (Сполучення) визначаються так:

Тотожно істинні формули (тавтології) [ правити | правити код ]

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

¬ (p ∨ q) ↔ (¬ p ∧ ¬ q) {\ displaystyle \ neg (p \ vee q) \ leftrightarrow (\ neg p \ wedge \ neg q)} ; ¬ (p ∧ q) ↔ (¬ p ∨ ¬ q) {\ displaystyle \ neg (p \ wedge q) \ leftrightarrow (\ neg p \ vee \ neg q)} ; (P → q) ↔ (¬ q → ¬ p) {\ displaystyle (p \ rightarrow q) \ leftrightarrow (\ neg q \ rightarrow \ neg p)} ;

• закони поглинання:

p ∨ (p ∧ q) ↔ p {\ displaystyle p \ vee (p \ wedge q) \ leftrightarrow p} ; p ∧ (p ∨ q) ↔ p {\ displaystyle p \ wedge (p \ vee q) \ leftrightarrow p} ; p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r) {\ displaystyle p \ wedge (q \ vee r) \ leftrightarrow (p \ wedge q) \ vee (p \ wedge r)} ; p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r) {\ displaystyle p \ vee (q \ wedge r) \ leftrightarrow (p \ vee q) \ wedge (p \ vee r)} .

1. ↑ 1 2 3 4 5 6 7 Чупахін, Бродський, 1977 , С. 203-205.
2. ↑ 1 2 Кондаков, 1971 , Стаття «Обчислення висловлювань».
3. ↑ 1 2 НФЕ 2010 .
4. ↑ 1 2 3 Герасимов, 2011 , С. 13.
5. ↑ Войшвилло, Дегтярьов, 2001. , С. 91-94.
6. ↑ Едельман, 1975 , С. 130.
7. ↑ Едельман, 1975 , С. 128.
8. ↑ Игошин, 2008 , С. 32.
9. ↑ 1 2 Герасимов, 2011 , С. 17-19.
10. ↑ Герасимов, 2011 , С. 19.

• Кондаков Н. І. Логічний словник / Горський Д. П .. - М.: Наука, 1971. - 656 с.
• Едельман С. Л. Математична логіка. - М.: Вища школа, 1975. - 176 с.
• Чупахін І. Я., Бродський І. Н. Формальна логіка. - Ленінград: Видавництво Ленінградського університету, 1977. - 357 с.
• Войшвилло Е. К. , Дегтярьов М. Г. Логіка. - М.: ВЛАДОС-ПРЕСС, 2001. - 528 с. - ISBN 5-305-00001-7 .
• Игошин В. І. Математична логіка і теорія алгоритмів. - 2-е изд., Стереотип .. - М.: Видавничий центр «Академія», 2008. - 448 с. - ISBN 978-5-7695-4593-1 .
• Логіка висловлювань // Нова філософська енциклопедія. - М., 2010. - Т. 2. - С. 415-418.
• Герасимов А. С. Курс математичної логіки і теорії обчислюваності . - СПб. : Видавництво «ЛЕМА», 2011. - 284 с. - ISBN 978-5-98709-292-7 .