Перейти до вмісту

Елементарна математика/Математична логіка

Матеріал з Вікіпідручника

Математична логіка

[ред.]

Пропозиції (висловлювання)

[ред.]

Навіть при поверхневому розгляді тверджень видно, що про них є сенс говорити, що вони істинні чи хибні. Наприклад, висловлювання "серед натуральних чисел немає найбiльшого" ми сприймаємо як істинне; висловлювання "число 1 є простим числом" ми сприймаємо як хибне тощо. Таким чином, при разглядi математичних тверджень й роздумів можна повністю обмежитися лише такими пропозиціями, про які можна сказати, що вони істинні чи хибні. Слова "пропозиція" та "висловлювання" будемо вважати синонімами. З цієї точки зору математичну теорему або аксіому можна розглядати як пропозицію, а доказ теореми - як послідовність пропозицій, пов'язаних між собою певним чином. Однак тут необхідно зробити зауваження. По-перше, у математичних текстах зустрічаються твердженя, що не є пропозиціями у вказаному сенсі. Наприклад, відносно пропозицій "позначмо прості числа " та "розгляньмо числа " немає сенсу говорити, що вони істинні або хибні. По-друге, пропозиції як речення, що є істинними чи хибними, зустрічаються не лише у математиці. Наприклад, висловлювання "маса Землі надзвичайно велика" може бути як істинним, так й хибним, в залежності від деякої іншої маси, з якою порівнюють масу Землі. Пропозиція "людина - це тварина" є істинною у біологічному сенсі, однак може бути хибною, якщо її використовують при розгляді соціальних та етичних питань. Необхідно особливо зауважити, що ми зосереджуємося на формі пропозиції безвідносно до її змісту - ми не з'ясовуємо істинність чи хибність тверджень, які входять до даної пропозиції, нас цікавить лише зв'язок цих тверджень, за якого дана складна пропозиція може бути істинною чи хибною. Розгляньмо ряд тверджень:

  • "Тарас має прізвище Фоменко",
  • "Богдан і Тарас - брати",
  • "Богдан має прізвище Фоменко".

Цей логічний роздум є безвідносним щодо з'ясування чи істинним є твердження "Тарас має прізвище Фоменко" саме по собі, чи хибним. Аксіоми (грец. axiōma; кор. axio (достойність), укр. гідність, гідне) відіграють подібну роль первинних тверджень, які приймаються в якості ядерних (тобто елементарних) - таких, які не піддаються сумніву. Сумніву ж можуть піддаюватися твердження, зроблені безвідносно до аксіом чи їх множин (систем аксіом). У математиці усі твердження робляться з огляду на прийняті системи аксіом. Відокремлюючи форму від змісту, ми констатуємо їх незалежність одна від одної. Таке абстрагування породжує універсальність форм, коли одна форма може виражати множину змістів. Тобто ми можемо "підігнати" той чи інший зміст під відповідну форму міркування. І, скажімо, можемо стверджувати:

  • "Матерія має фізичні властивості",
  • "Об'єкти Всесвіту складаються з матерії",
  • "Усі об'єкти Всесвіту мають фізичні властивості".

За формою це міркування та міркування стосовно приналежності Богдана до сімейства Фоменків є однаковими. Форма такого міркування називається силогізмом, який складається з двох тверджень й висновку на їх основі.

Для позначення висловлювань будемо використовувати великі латинські літери: Єдиною суттєвою для нас характеристикою пропозиції є її істинність або хибність. Цю характеристику назвемо значенням істинності даного висловлювання. Будемо вважати, що значення істинності висловлювання дорівнює якщо висловлювання істинне, та дорівнює якщо воно хибне. Значення істинності довільного висловлювання будемо позначати Таким чином, якщо - висловлювання "", а - висловлювання "", то

Визначити декотру логічну операцію над сукупністю висловлювань - значить вказати значення істинності висловлювання, яке є результатом даної операції, за усіх можливих значень істинності початкових висловлювань Задавати ці значення зручно за допомогою таблиці, яку називають таблицею істинності розглядуваної операції. У розмовній та літературній мові слова і вирази "та", "або", "якщо..., то..." розуміються по-різному, тоді як логічні операції повинні бути визначені так, щоб усі їх розуміли однаково.

Представлення математичного знання
[ред.]

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

Визначенням називається пропозиція, у якій розкривається зміст нового поняття, тобто вказуються істотні ознаки цього поняття. Зазвичай визначення полягає у вказанні:

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

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

Аксіоматична теорія побується з перелічення об'єктів, які вивчаються даною теорією, та деяких відношень (зв'язків, співвідношень) між ними. Такі об'єкти та відношення називаються основними (невизначеними, вихідними, початковими) поняттями даної теорії. Кожне поняття, яке не було визначене у списку основних понять, повинне бути точно визнечене (математика від грецького μάθημα означає дослівно "точне знання"). Іноді замість поняття точності говорять про суворість, таким чином, поняття повинне бути точно (суворо) визначеним.

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

Зміст основних понять аксіоматичної теорії можна пояснити за допомогою множин:

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

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

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

Логічні операції
[ред.]

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

1 0
0 1

Таке висловлювання позначається (читається "не ") і називається запереченням висловлювання Таким чином, висловлювання істинне лише тоді, коли висловлювання є хибним.


Кон'юнкція - це логічна операція, яка будь-яким двом висловлюванням ставить у відповідність складене висловлювання значення істинності якого визначеється значеннями істинності висловлювань та за наступним правилом:

1 1 1
1 0 0
0 1 0
0 0 0

Таке висловлювання позначається (читається " та ") і називається кон'юнкцією висловлювань та Як видно, висловлювання та у цьому визначенні є рівноправними і називаються кон'юнктивними членами висловлювання Таким чином, висловлювнання та істинне лише тоді, коли істинні обидва висловлювання та Для позначення кон'юнкції використовується також символ

Диз'юнкція - логічна операція, що ставить висловлюванням та у відповідність складене висловлювання значення істинності якого визначається значеннями істинності висловлювань та за наступним правилом:

1 1 1
1 0 1
0 1 1
0 0 0

Таке висловлювання позначається (читається " або ") та називається диз'юнкцією висловлювань та При цьому висловлювання та є рівноправними і називаються диз'юнктивними членами висловлювання Таким чином, висловлювання істинне, зокрема, коли істинні обидва висловлювання та Іноді розглядається також логічна операція "виключне або" (позначається ), яка визначається тим, що істинне лише тоді, коли У зв'язку із цим диз'юнкцію можна назвати операцією "невиключного або".

Кон'юнкцію і диз'юнкцію називають також "логічним множенням" та "логічним додаванням" відповідно.


Імплікація - це логічна операція , яка будь-яким двом висловлюванням та ставить у відповідність складне висловлювання значення якого визначається значеннями істинності висловлювань та за наступним правилом:

1 1 1
1 0 0
0 1 1
0 0 1

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


Еквіваленція - логічна операція, яка двом висловлюванням та ставить у відповідність складне висловлювання значення істинності якого визначається значеннями істинності висловлювань та за наступним правилом:

1 1 1
1 0 0
0 1 0
0 0 1

Таке висловлювання позначається (читається " лише тоді, коли ") і називається еквіваленцією та При цьому висловлювання та повністю рівноправні, їх називають членами еквіваленції Таким чином, висловлювання істинне лише тоді, коли обидва та висловлювання мають однакове значення істинності. Еквіваленція позначається також


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

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

Рівносильність висловлювань має властивості, повністю аналогічні властивостям еквівалентності чи рівності чисел:

  • властивість рефлексивності: будь-яке висловлювання є рівносильним самому собі,
  • властивість симетричності: для будь-яких висловлювань та з слідує
  • властивість транзитивності: для будь-яких трьох з того, що та слідує

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

Для економії дужок домовляються про "пріорітети дій", вважаючи За такої домовленості вираз варто розглядати як а вираз - як але не як

Запис означає, що є необхідною ознакою чи необхідною умовою у свою чергу, - достатня умова або достатня ознака Вираз можна перефразовувати як:

  • необхідно й достатньо для
  • лише тоді, коли
  • лише якщо
  • рівносильно

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

Булеві функції
[ред.]

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

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

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

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

Цю таблицю можна зіставити з таблицями істинності для логічних операцій. Таким чином,

Булеві функції називаються основними. Іноді основними булевими функціями вважають також функції та

Характеристична функція
[ред.]

Нехай - деяка підмножина довільної множини . Функцію , де означену таким чином:

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

Булева алгебра
[ред.]

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

  • (асоціативність);
  • (комутативність);
  • (дистрибутивність);
  • (абсорбція);
  • (додатковість);
  • та для усіх .

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

У математичному товаристві можна виділити дві головні школи: школу інтуїціонізму та школу конструктивізму. У 1930 році Аренд Гейтинг запропонував аксіоматичну систему пропозиційної логіки, яка, як стверджувалося, породжує в якості теорем у точності висловлювання, загальнозначущі у відповідності до інтуїціоністської концепції істини.

Система аксіом:

  • ;
  • ;
  • ;
  • ;
  • ;

де - довільні пропозиції. До цієї системи умов додається також правило відокремлення, за яким з пропозицій та можна вивести пропозицію Це правило називають середньовічним терміном modus ponendo ponens. Васне, modus ponens є назвою першої форми гіпотетичного силогізму. Наприклад, розгляньмо пропозицію "Якщо атмосферний тиск знижується, то буде погана погода". У цьому гіпотетичному силогізмі висловлювання "атмосферний тиск знижується" можна позначити змінною висловлювання "буде погана погода" - змінною Тоді форма modus ponens символічно може бути виражена за допомогою наступної формули: Застосовується й наступний запис форми modus ponens: Відтак правило modus ponens застосовується до пари теорем, одна з яких має структуру імплікації, а друга представляє собою антецедент цієї імплікації й полягає у "відокремленні" консеквента імплікації як нової теореми.

До тавтологій, які не є теоремами цієї системи, відносяться формули:

  • ;
  • ;
  • ;
  • ;
  • ;

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

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

Представники ж конструктивного напрямку у математиці називають інтуїціоністську логіку конструктивною логікою. Конструктивна логіка є напрямком у математичній логіці, в рамках якого дослідження обмежуються конструктивними об'єктами. Конструктивний об'єкт є поняттям математичної логіки, об'єм якого містить такі предмети (абстрактні й конкретні), яким притаманна відносна стійкість, яка дозволяє розрізняти й ототожнювати їх, що дає можливість конструктивно оперувати із ними. Дослідження у конструктивній логіці здійснюютьсяв рамках абстракції потенційної здійснюваності, за якого існування математичного об'єкта вважається доведеним тоді, коли вказується спосіб потенційно здійснюваної подубови об'єкта. Візаві А.Гейтинга у цьому сенсі є Лейтзен Брауер.

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

Логіка предикатів

[ред.]