ЛОГІКА ВИСЛОВЛЮВАНЬ, пропозіціональная логіка - розділ логіки символічної , Що вивчає складні висловлювання, освічені з простих, і їх взаємини. При цьому на відміну від логіки предикатів внутрішня структура простих висловлювань не розглядається, а враховується лише, за допомогою яких союзів і в якому порядку прості висловлювання сочленяются в складні. Під висловом розуміється то, що виражається розповідним пропозицією. Тому логіку висловлювань деякі автори називають також «логікою пропозицій».

У природній мові існує багато способів утворення складних висловлювань з простих. Зазвичай вибирають п'ять загальновідомих граматичних зв'язок (спілок): «не», «і», «або», «якщо ..., то» і «якщо ..., і тільки якщо». процес символізації мови логіки висловлювань полягає в наступному. Елементарні висловлювання замінюються пропозіціональнимі змінними p, q, r, ... з індексами або без них; зазначеним вище граматичним зв'язкам ставляться у відповідність (з близьким змістом) логічні зв'язки , Які отримують відповідно наступні позначення і назви: (Заперечення), ∧ або & (сполучення), ∨ (диз'юнкція), ⊃ (імплікація) і ≡ (еквіваленція); і, нарешті, використовуються дужки (,) для того, щоб можна було по-різному групувати висловлювання і цим визначати порядок виконання операцій. Заперечення називається одномісним зв'язкою, а інші чотири - двомісними зв'язками. Виявом мови логіки висловлювань називають будь-яку послідовність зазначених вище символів. Деякі з цих виразів оголошуються правильно побудованими. Їх називають формулами. Формули визначаються наступними правилами, де букви А, В ... представляють довільні висловлювання: (1) будь-яка пропозіціональная змінна є формула; (2) якщо А і В - формули, то А), (А ∧ В), (Α ∨ В), (А ⊃ В), (Α ≡ В) теж формули; (3) ніякі інші сполуки символів не є формулами. Прикладами формул є p, q, (P ∨ q). Зовнішні дужки при записі формул зазвичай опускають, а зв'язки (за визначенням) розрізняють по «силі зв'язування». Напр., Знак заперечення пов'язує сильніше, ніж двомісні зв'язки. Т.ч., правила задають ефективний спосіб розпізнавання, чи є вираз логіки висловлювань формулою.

Потім роблять два основних допущення, на яких грунтується семантика логіки висловлювань: (I) Кожне просте висловлювання є або тільки істинним, або тільки хибним (принцип двозначності). «Істина» і «брехня» називаються істиннісними значеннями висловлювання і позначаються відповідно І і Л, або 1 і 0. (II) істинності значення складного висловлювання визначається тільки істиннісними значеннями складових його простих висловлювань. Це означає, що логічні зв'язки (їх називають також пропозіціональние зв'язки) є істиннісними функціями.

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

p

p

І

Л

Л

І

p

q

p∧q

p∨q

p⊃q

p≡q

І

І

І

І

І

І

І

Л

Л

І

Л

Л

Л

Л

Л

І

І

Л

Л

Л

Л

Л

І

І

Наведені вище таблиці називаються істиннісними таблицями, а обумовлені ними пропозіціональние зв'язки - класичними зв'язками. Легко визначити, скільки є різних класичних зв'язок. Число різних рядків в таблиці довжини m одно 2m і на кожній з них значення функції можна задати двома способами: І чи Л. Тому число функцій двозначної логіки, що залежать від m аргументів, становить 2 певною мірою 2m. Звідси, напр., Число одномісних зв'язок дорівнює 4, а число двомісних зв'язок дорівнює 16.

Кожна формула задає деяку істиннісну функцію, яка графічно може бути представлена ​​істінностной таблицею, що містить 2m рядків, якщо у формулі є m різних пропозіціональних змінних. При цьому формула може бути такою, що на кожному рядку вона приймає тільки одне значення, рівне І, або тільки одне значення, рівне Л. В першому випадку вона називається тавтологією (тотожне істинним висловлюванням), а в другому - протиріччям (тотожне хибним висловлюванням) . У формальній логіці тавтології грають важливу роль. Вони служать для запису її законів ( закон логічний ), Так як тавтології є завжди істинними висловлюваннями тільки в силу своєї символічної форми, незалежно від змісту входять до них вихідних висловлювань. Легко встановити, що формули виду А ⊃ A, A ∨ A, (А ∧ А) є тавтологія. Закони, що виражаються цими формулами, називаються відповідно законом тотожності, законом виключеного третього і законом несуперечливий.

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

1. Правило висновку (modus ponens). Якщо А і A⊃В тавтології, то В тавтологія.

2. Правило підстановки. Якщо А (р) є тавтологія і В - формула, то А (В) теж тавтологія, де В заміщає кожне входження змінної p у формулі А, тобто підстановка в тавтологію призводить до тавтології. Вже звідси випливає, що є безліч тавтологію.

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

З останнього правила випливає, що можна перетворювати формули, отримуючи інші, їм еквівалентні, на більш прості (містять менше пропозіціональних зв'язок і змінних). Можна тепер будь-яку формулу привести до якогось канонічного вигляду і цим вирішувати певного роду завдання. Більш того, деякі еквіваленціі виражають основні властивості пропозиційних зв'язок. Напр., Еквіваленціі (А∧В) ≡ (В∧А) і (Α∨В) ≡ (Α∨В) висловлюють комутативними закон кон'юнкції і відповідно диз'юнкції. Всі ці питання (і інші) вивчає алгебра логіки , Основи якої закладені в роботах Дж.Буля (1847, 1854) і А. де Моргана (1847).

Відзначимо деякі еквіваленціі, що вказують на взаімовиразімость одних зв'язок через інші: А∧В ≡ ( Α∨ Β), А∨В ≡ ( А∧ В), А ⊃ В ≡ А∨В, (А ≡ В) ≡ (А ⊃ В) ∧ (В ⊃ А). Система пропозіціональних зв'язок M називається повною, якщо будь-яка формула еквівалентна деякій формулою, в яку входять тільки зв'язки з системи М, тобто за допомогою такої системи можна виразити все істінностние функції. Так, системи зв'язок { , ∧, ∨), { , ∧}, { , ∨} і { , ⊃} є повними. Це означає, що ми можемо будувати логіку висловлювань на основі будь-якої із зазначених систем зв'язок. Виявляється, повної може бути система, що складається тільки з однієї зв'язки |, яка називається «штрих Шеффера»: висловлювання ρ | q істинно тоді і тільки тоді, коли невірно, що p і q обидва істинні. Достатність зв'язки | випливає з тавтологію А ≡ А | ​​А, A∨В ≡ (A | A) | (B | B).

Поряд з поняттям тавтології фундаментальним для логіки висловлювань є поняття логічного слідування (див. дотримання логічне ), Оскільки одним із головних завдань логіки є встановлювати, що з чого випливає, і тим самим вказувати, які висловлювання є теоремами при заданих умовах. Будь-яку теорему можна записати у вигляді імплікації і таким чином виділити її умова і висновок. Кажуть, В логічно випливає з А чи є логічним наслідком з А, і пишуть А | = В, якщо в таблицях істинності для А і В формула В має значення І у всіх тих рядках, де А має значення І. Звідси випливає, що А | = В тоді і тільки тоді, коли А ⊃ В є тавтологія. Якщо формула А тавтологія, то іноді пишуть | = А. Наведене визначення логічного слідування без праці розширюється на деяку систему формул (систему посилок) А1, ..., Аn, яка позначається за допомогою Г, і тоді пишуть Г | = В. Прикладом логічного слідування (виведення) з посилок є вже згадане правило modus ponens. Виводимість В з висловлювань А і А ⊃ В випливає з того, що формула (А∧ (Α ⊃ В)) ⊃ В є тавтологією. Відзначимо також, що в силу таблиць істинності для зв'язки імплікації отримуємо, що тотожне справжня формула логічно випливає з будь-якої системи формул. А з того, що є роздільна процедура для тавтологію, отримуємо, що проблема виводимості довільної формули В із заданої системи посилок також можна вирішити.

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

Формальний (символічний) мову логіки висловлювань і поняття формули залишаються колишніми. Але тепер з усім тим натовпом тавтологію вибирають деякий їх кінцеве (і, взагалі кажучи, визначаються неоднозначно) підмножина, елементи якого називаються аксіомами . Напр .: l. p ⊃ (q ⊃ p). 2. (p ⊃ (q ⊃ r)) ⊃ ((р ⊃ q) ⊃ (p ⊃ r)), 3. p ⊃ (p∨q), 4. q ⊃ (p∨q), 5. (p ⊃ r) ⊃ ((q ⊃ r) ⊃ ((p∨q) ⊃ r)), 6. (p∧q) ⊃ p, 7. (p∧q) ⊃ q, 8. (p ⊃ q) ⊃ ((p ⊃ r) ⊃ (p ⊃ (q∧r))), 9. (p ⊃ q) ⊃ (q ⊃ p), 10. p ⊃ ( p ⊃ q), 11. p∨ p.

Т.ч., на відміну від табличного визначення логічних зв'язок , ∧, ∨, ⊃ задається аксіоматично. Потім за допомогою вже відомих правил, але чисто формально здійснюється висновок - перехід від висловлювання або системи висловлювань до вислову: з А і А⊃В слід В (правило укладення); з А (p) слід А (В) (підстановка). Так, задану логіку висловлювань позначимо за допомогою С2 і назвемо класичної.

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

Логічне числення, заданий за допомогою деякого безлічі аксіом і деякого безлічі правил виведення, називається обчисленням гильбертовськой типу. Висновком в ньому називається всяка послідовність А1, ..., Аn формул така, що для будь-якого i формула Аi, є або аксіома, або безпосередній наслідок будь-яких попередніх формул по одному з правил виведення. Формула А називається теоремою, якщо існує висновок, в якому останній формулою є А; такий висновок називається висновком формули А.Запісь | - А служить скороченням затвердження «А є теорема». Якщо формула А виводиться з деякого безлічі Г вихідних формул, то тоді запис приймає вигляд Г | - А (докладніше див. висновок логічний ).

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

Доказ в одну сторону, а саме: для всіх А, якщо | -Α, то | = А носить назву теореми про коректність. Це мінімальна умова, яку ми вимагаємо від логічного обчислення і яке полягає в тому, що представлена ​​нами семантика коректна для обраної аксиоматизации. Для доведення теореми потрібно перевірити, по-перше, що всі аксіоми (1) - (11) є тавтологія, що легко встановлюється безпосередньою перевіркою за допомогою істиннісних таблиць, і, по-друге, що правила виведення обрані таким чином, що вони зберігають тавтологічні. Тому все формули послідовності, що утворює доказ будь-якої теореми обчислення С2, в тому числі і сама доказова теорема, є тавтологія. З цієї теореми випливає найважливіша властивість нашого числення висловів С2: в С2 формули А і А одночасно недоказові, тобто числення висловів С2 несуперечливо. Їли б це було не так, то (з використанням аксіоми (10) і подвійним застосуванням modus ponens) в С2 була б доказова будь-яка формула В. В силу цього суперечлива логіка висловлювань ніякої цінності не представляє. У ній істина і брехня невиразні і тому будь-яка теорема одночасно істинна і помилкова.

Має місце і зворотне твердження про те, кожна тавтологія доказова, т. E для всіх А, якщо | = А, то | - А.Доказательство цієї теореми не настільки тривіально і носить назву теореми про повноту числення висловів щодо запропонованої семантики. По суті тут стверджується, що логічних засобів, тобто аксіом і правил виведення, обчислення висловлювань С2 цілком достатньо для доказу всіх тавтологію. Т.ч., поставлена ​​мета досягнута: використовуючи мінімальні кошти, можна оглянути все безліч тавтологію.

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

Перша аксіоматизація класичної логіки С2 була зроблена Г.Фреге (1879). Однак в термінах сучасного символічного мови аксіоматизація С2 з'явилася в «Prinсіріа Mathematica» А. Уайтхеда і Б. Рассела (1910-13). В обох роботах питання про повноту просто не виникало. Їх метою було показати, що вся логіка, а в дійсності вся математика може бути розвинена всередині їх системи. Перша публікація докази повноти належить Е.Посту (1921), який виходив з системи Уайтхеда і Рассела. Ще раніше це було зроблено П.Бернайсом. В обох випадках використовувалися двозначні істінностние таблиці (наведені вище) для доведення теореми адекватності. В цьому випадку говорять ще, що ці таблиці є характеристичними для С2.

Тепер можна перейти до характеризації того, що називається класичною логікою висловлювань: (а) С2 заснована на принципі двозначності (бівалентності). Останнім часом велике розвиток отримали так звані «бівалентні семантики», не тільки для С2; (B) двозначні істінностние таблиці є характеристичними. У цьому сенсі класична логіка висловлювань є мінімальною; (С) класична логіка висловлювань є максимальною в тому сенсі, що вона не має розширень: всяке додавання до неї в якості аксіоми до.-л. формули, що не виводиться в ній, робить її суперечливою; нарешті, (d) класична логіка висловлювань має найбільш просту семантику, яку можна тільки винайти. Все це говорить про класичній логіці висловлювань як унікальне явище серед усієї множини логік (див. некласичні логіки ).

Якщо в наведеною аксиоматизации С2 відкинути останню аксіому ( виключеного третього закон ), То отримаємо аксіоматизації пропозіціональной интуиционистской логіки . Виявляється, вона має континуум розширень (В.Л.Янков, 1968) і ніякі конечнозначние істінностние таблиці не є для неї характеристичними (К.Гёдель, 1932). Є логіки, які мають тільки одне розширення, тобто саму С2.

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

Варто відзначіті Широке! Застосування алгебраїчніх методів для вирішенню різніх завдання логіки вісловлювань. Це становится можливий самперед з Тлумачення логіки вісловлювань як деякої структури (в СЕНСІ алгебраїчної «теорії структур»). Так, дистрибутивная структура з ДОПОВНЕННЯ (алгебри Буля) відповідає класічній логіці вісловлювань (див. алгебра логіки ), А імплікатівной структура, де імплікація є деяким аналогом поділу, якщо кон'юнкція трактується як множення (псевдобулеви алгебри або алгебри гейтинг), відповідає интуиционистской логіці висловлювань. Зауважимо, що в основі додатків булевої алгебри до логіки лежить інтерпретація елементів булевої алгебри як висловлювань.

На закінчення звернемо увагу на застосування класичної логіки висловлювань для аналізу і синтезу релейно-контактних схем (К.Шеннон, 1938 і В.І.Шестаков, 1941). В автоматичному управлінні і при експлуатації обчислювальних машин доводиться мати справу з релейно-контактними схемами, що містять сотні і тисячі реле, напівпровідників і магнітних елементів. Опис і конструювання таких схем дуже непроста справа. Виявилося, що на допомогу може прийти логіка висловлювань. Кожній схемі ставиться у відповідність певна її формула в мові { , ∧, ∨) і кожна формула реалізується за допомогою деякої схеми. Вивчаючи відповідну формулу, можна виявити можливості заданої схеми і спростити її (рішення подібного роду задач називається аналізом схеми). З'являється можливість побудувати схему, заздалегідь описавши за допомогою формули ті функції, які схема повинна виконувати (синтезування схеми). Залишається тільки додати, що саме класична логіка висловлювань лежить в основі проектування мікросхем для сучасної цифрової електронної техніки, в тому числі і для комп'ютерів, хоча останнім часом ведуться подібні роботи, засновані на інших логіках - багатозначних, нечітких, паранепротиворечивая.

література:

1. Кліні С.К. Введення в математику. М., 1957;

2. Черч А. Введення в математичну логіку, т. I. М., 1960;

3. Новиков П.С. Елементи математичної логіки. М., 1973;

4. Мендельсон Е. Введення в математичну логіку. М., 1984;

5. Карпенко AC Класифікація пропозіціональних логік. - В кн .: Логічні дослідження, вип. 4. М., 1997;

6. Яглом І.М. Булева структура і її моделі. М., 1980;

7. Янков В.А. Побудова послідовності сильно незалежних суперінтуіціоністскіх пропозіціональних обчислень. - В кн .: Доповіді Академії наук СРСР, 1968, т. 181, № 1;

8. Логіка висловлювань (Яновська С.А.). - В кн .: Філософська енциклопедія, т. 3. М., 1964;

9. Epstein RL The semantic foundations of logic, vol. 1: Propositional logic. Dordrecht, 1990;

10. From Frege to Gödel: A source book in mathematical logic 1879-1931, Harvard University Press, 1967, p. 264-283.

А.С.Карпенко