пропозіціональная логіка
ЛОГІКА ВИСЛОВЛЮВАНЬ, пропозіціональная логіка - розділ символічної логіки, що вивчає
складні висловлювання, освічені з простих, і їх взаємини. На відміну від логіки предикатів, прості висловлювання при цьому виступають як цілі освіти, і їх внутрішня структура не розглядається, а враховується лише те, за допомогою яких союзів і в якому порядку прості висловлювання сочленяются в складні. Під висловом розуміється то, що виражається розповідним пропозицією.
У природній мові існує багато способів утворення складних висловлювань з простих. Ми виберемо п'ять загальновідомих граматичних зв'язок (спілок): «не», «і», «або», «якщо. то »і« якщо і тільки якщо ». Процес символізації природної мови засобами Л. в. полягає в наступному. Елементарні висловлювання заміщуються пропозіціональнимі змінними р, q, r. з індексами або без них; зазначені вище граматичні зв'язки називаються пропозіціональнимі (логічними) зв'язками і відповідно отримали наступні позначення і назви: - • (заперечення), л або (Сполучення), v (диз'юнкція), г> (імплікація) і = (еквіваленція); і, нарешті, використовуються дужки (,), для того щоб можна було по-різному групувати висловлювання і цим визначати порядок виконання операцій. Заперечення є одномісній зв'язкою, а інші чотири - двомісні зв'язки. Виявом мови Л. в. будемо називати будь-яку послідовність зазначених вище символів. Деякі з цих виразів є правильно побудованими. Такі вирази називаються формулами, визначення яких задається наступними Правилами, де букви А, В. використовуються як метапеременние: 1) будь-яка пропозіціональная змінна є формула; 2) якщо А і В - формули, то -та, А л В, AVB, AZDB, A = B теж формули; 3) ніякі ін. Вирази не є формулами. Таким чином, правила задають ефективний спосіб розпізнавання, чи є вираз Л. в. формулою.
Тепер зробимо два основних допущення, на яких ґрунтується семантика класичної Л. в. I. Кожне просте висловлювання є або тільки істинним, або тільки хибним (принцип двозначності). «Істина» і «брехня» називаються істиннісними значеннями висловлювання і позначаються відповідно І і Л, або 1 і 0. II. Істінностное значення складного висловлювання визначається тільки істиннісними значеннями складових його простих висловлювань (принцип екстенсіональності). Це означає, що пропозіціональние зв'язки є знаками істиннісних функцій. Виникає питання: які істінностние функції відповідають нашим зв'язкам?
Зручним способом завдання істиннісних функцій є табличний, де зліва вказуються всі можливі приписування значень аргументів (пропозіціональним змінним), а праворуч - значення самої функції.
Наведемо цей спосіб словесно. Якщо висловлювання р істинно, то висловлювання -<р ложно; и наоборот: если ->р істинно, тор помилково. Висказиваніер л q істинно тоді і тільки тоді (т.т.т.), коли істинні обидва висловлювання р і q. Висловлення р v q помилково т.т.т. коли помилкові обидва висловлювання р і q. Висловлення р z> q помилково, якщо р істинне, a q помилково; В інших випадках висловлювання р з q істинно. Висловлення р = q істинно т.т.т. коли обидва висловлювання р і q приймають однакові значення.
Кожна формула визначає деяку істиннісну функцію, яка графічно може бути представлена істінностной таблицею. При цьому формула може бути такою, що на кожному рядку вона приймає тільки значення, рівне І, або тільки значення, рівне Л. В першому випадку вона називається тавтологією (тотожне істинним висловлюванням), а в другому - протиріччям (тотожне хибним висловлюванням). У формальній логіці тавтології грають важливу роль. Вони служать для запису її законів (див. Логічний закон), тому що тавтології є завжди істинними висловлюваннями тільки в силу своєї символічної форми, незалежно від змісту входять до них вихідних висловлювань. Легко встановити, що формули Аз А, А v -> А, -А л -iA) є тавтологія. Закони, що виражаються цими формулами називаються відповідно законом тотожності, законом виключеного третього і законом несуперечливий.
Звернемо увагу на виключно важливе властивість істиннісних таблиць: вони дають нам ефективну процедуру для вирішення питання про те, чи є дана пропозіціональная формула тавтологією. Зазначена процедура називається роздільною процедурою, і це означає, що розвивається тут Л. в. є вирішуваною логікою (див. Дозволи проблема). Наведемо деякі загальні факти про тавтологіях, настільки загальні, що вони називаються правилами Л. в.
1. Правило відділення (modus ponens). Якщо А і A Z) У тавтології, то В тавтологія.
2. Правило підстановки. Якщо А (р) є тавтологія, то А (В) теж тавтологія, де В заміщає кожне входження р, тобто підстановка в тавтологію призводить до тавтології. Вже звідси випливає, що є безліч тавтологію.
Відзначимо деякі еквівалентності, що вказують на взаімовиразімость одних зв'язок через інші: А л В H -. (-, Av-iB), AvBH -, (-, AAnB), ADB = -.AvB, (A = B) = (АЕВ) л (ЗЕА). Назвемо систему пропозіціональних зв'язок М повної, якщо будь-яка істиннісне функція представима деякою формулою, в яку входять тільки зв'язки з системи М, тобто за допомогою такої сіетеми можна висловити все істінностние функції. Тоді системи зв'язок - i, л, v, - л, - i, v і ->, з є повними. Це означає, що ми можемо будувати Л. в. взявши в якості вихідної будь-яку із зазначених систем зв'язок. Виявляється, повної може бути система, що складається тільки з однієї зв'язки |, яка називається «штрих Шеффера»: висловлювання pq істинно, коли невірно, що р і q обидва істинні. Достатність зв'язки | випливає з тавтологію -A = А | А, AvB = (AA) (BB).
Поряд з поняттям тавтології фундаментальним для Л. в. є поняття логічного слідування. Запис А | = В позначає, що В логічно випливає з А, а р = А позначає, що А є тавтологія.
Якщо визначено поняття тавтології і визначено семантичне поняття логічного слідування, то кажуть, що дано семантичне уявлення Л. в. а сама Л. в. часто ототожнюється з безліччю тавтологію або з самим ставленням логічного слідування. Однак таке уявлення ставить наступну серйозну проблему: як оглянути всі тавтології, яких безліч? Для вирішення цієї проблеми переходять до синтаксичному поданням Л. в.
Формальний (символічний) мову Л. в. і поняття формули залишаються колишніми, і тепер з усім тим натовпом тавтологію вибирається деякий їх кінцеве підмножина, елементи якого називаються аксіомами. Напр. 1. р з (q з р), 2. (р з (
Логічне числення, заданий за допомогою деякого безлічі аксіом і деякого безлічі правил виведення, називається гильбертовськой обчисленням. Доказовими формулами (або теоремами) розглянутого обчислення називаються будь-які формули, які можуть бути отримані з аксіом числення в результаті застосування (можливо, багаторазового) зазначених правил. Запис | - А служить скороченням затвердження «А є теорема». Якщо формула А виводиться з деякого безлічі Г вихідних формул (посилок), то тоді запис приймає вигляд Г-А (див. Висновок логічний).
Виходячи з синтаксичного представлення Л. в. остання часто ототожнюється з безліччю теорем або з відношенням виводимості. Незважаючи на відмінність семантичного і синтаксичного підходів до побудови Л. в. обидва підходи до побудови Л. в. по суті, еквівалентні і, як кажуть, є адекватними. Це означає, що поняття логічного слідування і поняття виведення рівнозначні. Розглянемо наступну примітну теорему, яка іноді називається теоремою адекватності: для будь-якої формули А, -А т.т.т. коли | = А.
Доказ в одну сторону, а саме: для всіх А, якщо | -А, то р А, носить назву теореми про коректність. Це мінімальна умова, яку ми вимагаємо від логічного обчислення і яке полягає в тому, що представлена нами семантика коректна для обраної аксиоматизации. Звідси випливає, що С2 є несуперечливим обчисленням. Має місце і зворотне твердження: кожна тавтологія доказова, тобто для будь-якої формули А, якщо | = А, то - А. Доказ цієї теореми носить назву теореми про повноту числення висловів щодо запропонованої семантики. По суті тут стверджується, що логічних засобів, тобто аксіом і правил виведення, обчислення висловлювань С2 цілком достатньо для доказу всіх тавтологію.
Перша аксіоматизація класичної логіки С2 була зроблена Г. Фреге в 1879. Проте в термінах сучасного символічного мови аксіоматизація С2 з'явилася в «Principia Mathematica» А. Уайтхеда і Б. Рассела в 1910-1913. Перша публікація докази повноти належить Е. Посту (1921), який виходив з системи Уайтхеда і Рассела і використовував двозначні істінностние таблиці (наведені вище) для доведення теореми адекватності.
Тепер ми можемо дати характеристику того, що називається класичної Л. в. а) С. заснована на принципі двозначності (Двозначності принцип). Ь) С2 є максимальною в тому сенсі, що вона не має несуперечливих розширень: всяке додавання до неї в якості аксіоми будь-якої формули, що не доведеною в ній, робить її суперечливою, з) З має найбільш просту семантику.
За допомогою модифікації, винятком або додаванням ін. Аксіом отримують різні некласичні логіки висловлювань.
Див. Алгебра логіки, Логіка, Символічна логіка.
А.С. Карпенко