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

Логічні висловлювання (чи́слення висло́влень, логіка висловлень, пропозиційна логіка, англ. propositional calculus) — поняття висловлювання, як і поняття множини, не означають, а дають йому описову характеристику з використанням багатьох прикладів. Зокрема, до висловлювань відносять розповідні речення, які можна охарактеризувати як істинні або хибні. Таким чином, під висловлюванням розуміють таке речення, яке є істинним або хибним. Відповідь на запитання про істинність чи хибність даного висловлювання дає та галузь науки чи людської діяльності, до якої воно належить.

Розглянемо приклади:

Київ — столиця України;
квадрат будь-якого дійсного числа невід'ємний;
x + 2y < 1;
5=9;
відкрийте книгу на десятій сторінці.

Серед наведених речень 1–4 є висловлюваннями, причому 1, 2 істинні, а 4 — хибне. Речення 5 не належить до висловлювань.

Висловлювання позначають великими латинськими буквами (з індексами або без них): A, B, C1, C2,… Ці букви називають висловлювальними змінними. У математичній логіці висловлювання вивчають тільки з погляду того, істинні вони чи хибні, не цікавлячись їх конкретним змістом.

Тому для довільного висловлювання A введемо його значення істинності |A| за таким правилом: Наприклад, якщо позначимо A висловлювання «е — раціональне число», а B — висловлювання «залізо — це метал», то матимемо |A| = 0, |B| = 1.

Усі висловлювання можна поділити на прості і складні. Просте висловлювання — це таке висловлювання, яке не утворене з інших висловлювань, а складне висловлювання утворюється з простих висловлювань. Наприклад, висловлювання «2 + 3 = 8» є простим, а висловлювання «Якщо 36 ділиться на 2 і 36 ділиться на 3, то 36 ділиться на 6» є складним.

У математичній логіці прості висловлювання розглядаються як цілі, неподільні, їх внутрішню структуру не аналізують. Навпаки, визначення істинності чи хибності складних висловлювань є одним із завдань логіки.

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

Логіка висловлювань (ЛВ) — розділ символічної логіки, що вивчає необхідні відношення між висловлюваннями, на підставі чого визначають значення істинності висловлювань; дедуктивна теорія, яка моделює процес виведення одних висловлювань з інших за принципом логічного слідування. Це історично перша формально-логічна система, побудована засобами.

У межах логіки висловлювань можуть бути побудовані морфологічні системи (формально-логічні теорії без дедуктивної частини, тобто без аксіом і правил виведення) та логічні числення (формально-логічні теорії, на синтаксичному рівні котрих задаються системи їхніх аксіом і строго визначена сукупність правил виведення). Більшість класичних формально-логічних теорій логіки висловлювань побудовано у формі логічних числень. Перше числення висловлювань отримало назву «класичне числення висловлювань» (КЧВ) — формалізація висловлювань засобами особливої мови та здійснення логічних операцій над ними з метою перетворення простих висловлювань на складні та їх перетворення на нові складні висловлювання.

Класична логіка висловлювань (КЛВ)

Класична логіка висловлювань (КЛВ) є основою сучасної символічної логіки, на базі якої створюються нові формально-логічні системи (логічні числення). Ідею логічного числення вперше сформулював німецький філософ, логік, математик Г. Лейбніц. Історично першу систему логіки висловлювань, або алгебру логіки, створив англійський логік Дж. Буль, в якій використовували алгебраїчні методи для вирішення певних логічних задач. Подальший розвиток логіки висловлювань здійснювали логіки та математики — О. де Морган, Б. Шредер, Г. Фреге, Б. Рассел.

Логіка висловлювань як формально-логічна система будується за певним алгоритмом, тобто на підставі визначених принципів і в певній послідовності. Розрізняють семантику і синтаксис логіки висловлювань.

Семантика визначає змістовний аспект неформальних відношень між висловлюваннями у термінах «висловлювання», «властивість», «відношення».

Синтаксис

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

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

Мова логіки висловлювань — система символів, котрі називаються алфавітом. Алфавіт:

Символи для позначення простих висловлювань (пропозиційні змінні) — А, В, С, … (або р, </, г, я; р{, р2, р).
Символи, що позначають істинносні значення висловлювань — «і», «*».
Символи для позначень пропозиційних зв'язок (логічні сполучники, логічні постійні):
Допоміжні (розділові, технічні) символи — (ліва дужка, права дужка).

ДНФ та КНФ

Визначення або обґрунтування семантичної властивості будь-якої довільної складної формули в логіці висловлювань може здійснюватися і на синтаксичному рівні, тобто на підставі аналізу зовнішнього вигляду (структури) самої формули. Для цього використовують розв'язувальну процедуру — зведення формули до її кон'юнктивної нормальної форми (КНФ) або диз'юнктивної нормальної форми (ДНФ).

Якщо нормальна форма є формулою, яка містить лише логічні операції кон'юнкції, диз'юнкції та заперечення, то кон'юнктивою нормальною формою називають формулу, яка є кон'юнкцією елементарних диз'юнкцій (тобто диз'юнкцій простих формул або їх заперечень), а диз'юнктивною нормальною формою називають формулу, що є диз'юнкцією елементарних кон'юнкцій (тобто кон'юнкції простих формул або їх заперечень). Наприклад, формула виду («o А, V А2) ^ А8 є КНФ, а саме — кон'юнкцією таких двох елементарних диз'юнкцій, як і А, V А2 та А,; формула виду (-„А1 Λ А^) V А, V А4 є ДНФ, а саме — диз'юнкцією таких трьох елементарних кон'юнкцій, як -“ А₁ Л А₂, А₃, А₄, а формула виду А, V А₂ Л А₃ не є ні КНФ, ні ДНФ.

Формула тотожно-істинна, якщо в кожну елементарну диз'юнкцію її КНФ одночасно входить будь-яка її проста формула разом зі своїм запереченням (таке входження ще називають регулярним). Наприклад, КНФ для формули (А → В) → (-ч В -» -і А) має вигляд (Ач В V → А) л (→ В V В V → А). Оскільки і перша елементарна диз'юнкція (А V В V -o А) містить регулярне входження А та -o А, і друга елементарна диз'юнкція ("o В V В V -"А) містить регулярне входження -«В і В, то й кон'юнкція цих двох істинних диз'юнктивних формул є істинною формулою, а отже, є істинною і та формула, для якої було знайдено саме цю КНФ.

Формула тотожно-хибна, якщо в кожну елементарну кон'юнкцію її ДНФ одночасно входить будь-яка її проста формула разом зі своїм запереченням, оскільки диз'юнкція всіх хибних підформул — хибна формула. Якщо ні КНФ, ні ДНФ конкретної складної формули не містить у своїх підформулах регулярних входжень, то таку складну формулу вважають нейтральною (або виконуваною), і її істинне значення залежить не лише від логічної структури, а й від конкретних властивостей простих висловлювань бути істинними чи хибними.

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

Рівносильні формули логіки висловлювань

Формули називаються рівносильними, якщо таблиці істинності цих формул будуть збігатися. Рівносильні формули називаються ще еквівалентними, бо в процесі кожного набору значень для своїх змінних вони набувають однакового значення істинності або значення хибності (див. таблицю істинності для формули еквівалентності А = В).

Рівносильну формулу можна отримати внаслідок заміни пропозиційних зв'язок на підставі відношення залежності між ними. Визначають, що для будь-якої формули можна назвати рівносильну для неї формулу, яка містить символи -і, V, V. Наприклад, формулу виду −1 А V-» В можна замінити формулою виду -« (А Λ В), що означає -oA /-іВ = -» (А Λ В); формулу виду А → В можна замінити формулою -« А V В, що означає А → В = -і А V В; формулу А V В можна замінити формулою -» (-«А В), що означає А V В =→(-* А Л → В).

Рівносильні формули називаються законами логіки висловлювань.

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

Закон тотожності визначає, що кожне висловлювання є логічним наслідком самого себе. Формальний вираз закону А→ А.

Закон несуперечності визначає, що висловлювання А неправильне, якщо водночас істинні його ствердження і його заперечення. Формальний вираз закону −1 (А л → А).

Закон виключеного третього визначає, що висловлювання А або істинне, або хибне за значенням істинності, але не може бути водночас істинним і хибним. Формальний вираз закону А 1 А.

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

З виникненням і подальшим розвитком символічної логіки були визначені нові закони логіки висловлювань.

Закони

Закон експортації визначає, що коли змінні А, В, С з'єднані символами кон'юнкції та імплікації, то з істинності кон'юнкції А та В випливає істинність С: (А Λ В → С) К А → (В → С), де ь- — символ дедуктивного виведення (чит.: якщо істинність кон'юнкції А Λ В → С, то, якщо істинне А, — випливає з істинності В слідує істинність С).
Закон ідемпотентності (лат. — той, що зберігає те ж саме) означає: добуток двох висловлювань А Λ А чи сума двох висловлювань А V А еквівалентна самому висловлюванню А, тобто, для кон'юнкції (А Λ А) = А (кон'юнкція двох висловлювань А й А еквівалентна А); для диз'юнкції А V А = А (диз'юнкція двох висловлювань А чи А еквівалентна А).
Закон комутативності (лат. — змінюючий) означає, що при множенні (кон'юнкції) та додаванні (диз'юнкції) результат не залежить від порядку змінних. Закон комутативності: для кон'юнкції (А Λ В) = (В Λ А) (чит.: А та В еквівалентне В та А); для диз'юнкції (А V В) = (В V А) (чит.: А або В еквівалентне, що В або А).
Закон контрапозиції (лат. — протиставлення) — закон, за яким імплікації можна протиставити її заперечення: (А → В) = (¬ В → ¬А) (чит.: якщо з висловлювання А випливає висловлювання В, то із заперечення висловлювання В випливає заперечення А).
Закон поглинання визначає, що в кон'юнктивному або диз'юнктивному висловлюванні зі змінними А, В здійснюється поглинання додаткового висловлювання. Закон поглинання: для кон'юнкції А Λ (А v В) = А (чит.: А й (А або В) еквівалентне А); для диз'юнкції А V (А V В) = А (чит.: А або (А або В) еквівалентне А).
Закон подвійного заперечення визначає, що подвійне заперечення висловлювання А (заперечення заперечення) еквівалентне його ствердженню. Зображають формулами:
- 1. -» А → А (чит.: якщо неправильно, що не А, то А);
- 2* "« -» А = А (чит.: неправильно, що не А еквівалентне ствердженню А).

Відношення логічного слідування між формулами

Між певними формулами логіки висловлювань існує відношення логічного слідування. Це означає: якщо із формули виду слідує формула виду то кожен раз, коли формула Р є істинною, то й формула Р₂ є істинною. Формальний вираз відношення логічного слідування: Р, -« Р₂. Наприклад, із формули виду А слідує формула виду А v В; із формули виду → -o А слідує формула виду А; із формули виду А v А слідує формула виду А.

На підставі встановлення відношення рівносильності та слідування здійснюють операцію доведення певних формул на істинність за правилами виведення. Операція доведення — невід'ємна частина будь-якого числення висловлювань.

Числення логіки висловлювань — система символів і правил логічного виведення із аксіом довільних формул або теорем з метою їх доведення на істинність. Розрізняють натуральне й аксіоматичне числення логіки висловлювань.

Натуральне числення логіки висловлювань відтворює логічну будову звичайних міркувань. Вперше натуральні числення розробили незалежно один від одного польський логік С. Яськовський (1906—1965) і німецький логік Генцен Герхард (1907—1945) у 30-х роках XX ст.

Розглянемо одну із систем натурального числення, яку позначимо літерою 5. Основні правила системи 5.

Правила логічного слідування

(А → В, А) -» В (правило модус поненс); (А -« В, -і В) -» -« А (правило модус толленс); (А, В) → А Λ В (правило ВК — введення кон'юнкції); (А Λ В) → А; (А Λ В) → В (правило усунення кон'юнкції);

А → (А v В); В -» (А v В) (правило ВД — введення диз'юнкції);

(А 1 В, А) -« -і В; (А 1 В, — В) -» А (правило УД — усунення диз'юнкції);

((А → В, В → А)) -« (А = В) (правило ВЕ — введення еквівалентності);

(А = В) → (А → В); (А = В) -»(В → А) (правило УЕ — усунення еквівалентності));

А → -і -і А (правило (В32) — введення подвійного заперечення);

-« -і А → А (правило У32 — усунення подвійного заперечення).

Правила побудови доведення.

Правила побудови прямого доведення. Пряме доведення формули А₁ → (А₂ … (А_я → С) будується в такий спосіб. На будь-якому кроці доведення можна визначити:

Одну із формул А₁, А₂,… А_n як припущення.
Формулу, що випливає з раніше невизначених формул за правилами логічного слідування.
Раніше доведену формулу.

Непряме доведення формули А, → (А₂ -» (А_л→ С) будується так: На будь-якому кроці доведення можна визначити:

Одну з формул А,, А₂,… А_я як припущення.
Формулу, що суперечить формулі С.
Формулу, що випливає з раніше визначених формул за одним із правил логічного слідування.
Раніше доведену формулу.

Див. також

Література

J. M. Bocheński. Formale Logik. 5. unveränderte Auflage. Alber, Freiburg (Breisgau) u. a. 1996, ISBN 3-495-44115-8, (Orbis academicus 3, 2).
Walter Bröcker. Formale, transzendentale und spekulative Logik. Klostermann, Frankfurt am Main 1962.
Paul Hoyningen-Huene. Formale Logik. Eine philosophische Einführung. Reclam, Stuttgart 1998, ISBN 3-15-009692-8.
Edmund Husserl. Formale und transzendentale Logik. Versuch einer Kritik der logischen Vernunft. 2. Auflage. Unveränderter Nachdruck der 1. Auflage 1929. Niemeyer, Tübingen 1981, ISBN 3-484-70129-3.

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.