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

Размещено на http://www.allbest.ru/

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

1.1 Предикати та операції над ними

Нехай M - непорожня підмножина декартового добутку деяких множин (n?1).

n-місним предикатом, заданим на множині М, називається речення, що містить n змінних , яке перетворюється на висловлення при підстановці замість цих змінних відповідних конкретних значень, для яких.

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

В подальшому викладі будемо використовувати наступні позначення: - предикат; - предметні змінні; елементи множин, що їх пробігають предметні змінні - предметні константи; - значення істинності предиката для відповідного набору елементів.

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

Приклад 1. Речення « х ділиться на 2 без остачі» є одномісним предикатом на множині натуральних чисел. Позначимо його . Тоді при підстановці замість х конкретних натуральних чисел будемо отримувати конкретні висловлення, які будуть або істині, або хибні. Так «4 ділиться на 2 без остачі» - істинне висловлення, і тому , а «3 ділиться на 2 без остачі» - хибне висловлення і .

Приклад 2. Речення «» є тримісним предикатом на множині цілих чисел. Позначимо його . Тоді , а .

Предикат , заданий на множині , називається:

тотожно істинним, якщо для будь-якого набору предметних констант він перетворюється в істинне висловлення, тобто ;

тотожньо хибним, якщо для будь-якого набору предметних констант він перетворюється в хибне висловлення, тобто ;

виконуваним, якщо існує такий набір предметних констант , для якого значення істинності ;

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

Приклад 3. На множині дійсних чисел предикат «» є тотожно істинним, а отже і виконуваним предикатом. На цій же множині предикат «» є виконуваним і спростовним предикатом одночасно. На множині натуральних чисел предикат «» є тотожньо хибним, а отже і спростовним.

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

Приклад 4. Розглянемо предикат «» на множині дійсних чисел. Множиною істинності цього предиката буде множина всіх невід'ємних дійсних чисел. Множиною істинності предиката «», заданого на множині дійсних чисел, буде порожня множина, оскільки квадрат будь-якого дійсного числа завжди більший за нуль або дорівнює йому. Множиною істинності предиката «», заданого на множині натуральних чисел буде множина .

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

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

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

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

Оскільки, в результаті однієї з операцій над предикатами P i Q утвориться новий предикат, то можна говорити про його множину істинності.

Очевидно постає запитання, а чи можна якось пов'язати множину істинності результату з множинами істинності вихідних предикатів? Відповідь на це питання дає наступна теорема.

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

, якщо ;

, якщо ;

, якщо ;

, ;

, якщо .

предикат диз'юнкція квантор

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

Приклад 5. Розглянемо два одномісні предикати задані на множині натуральних чисел. Предикат означає «х ділиться на 2», предикат - «х ділиться на 3». Множинами істинності цих предикатів очевидно будуть множини і . Нехай результат однієї з логічних операцій, виконаних над предикатами і . Тоді множина істинності предикату буде мати наступний вигляд, в залежності від операції:

, якщо ;

, якщо ;

, якщо ;

, якщо ;

, якщо .

В логіці предикатів використовують ще так звані операції зв'язування квантором (операції квантифікації).

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

По іншому це можна записати так

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

Інакше кажучи,

Приклад 6. Розглянемо двомісний предикат «», заданий на множині натуральних чисел, та зв'яжемо квантором загальності змінну х. Отримаємо одномісний предикат «», який буде тотожно істинним для будь-якого значення y.

Відмітимо, що якщо є n-місний предикат, то його змінні можна по черзі зв'язувати одним із кванторів. Якщо зв'язати кванторами всі змінні деякого предиката, то отримаємо висловлення.

Приклад 7. Як приклад розглянемо предикат «», заданий на множині дійсних чисел. Зв'яжемо всі його змінні кванторами так «» і одержимо істинне висловлення. Дійсно, для будь-яких двох дійсних чисел x і y можна вказати таке дійсне число z, що (для цього достатньо покласти ).

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

Область дії квантора - це предикат, до якого відноситься цей квантор.

Входження предметної змінної x в даний предикат називається зв'язаним, якщо x є змінною квантора або знаходиться в області дії квантора за цією змінною.

В протилежному випадку входження предметної змінної називається вільним.

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

Приклад 8. Розглянемо предикат «». Областю дії квантора існування буде предикат «», областю дії квантора загальності буде предикат «», змінна y є зв'язаною змінною, а змінна x - частково зв'язаною, оскільки має одне вільне та одне зв'язане входження.

Вправи.

3.1 Визначити, які з наступних речень будуть предикатами та вказати їх місність

4 і 6 діляться на 3 без остачі;

х - парне число;

х і у чотирикутники;

f(x) - диференційовна функція;

кожен день неділі - середа;

сьогодні четвер і буде хороша погода;

у будь-якому трикутнику можна провести три висоти.

3.2. Вказати приклади тотожно істинних, тотожно хибних, виконуваних та спростовних предикатів, заданих на множині:

цілих чисел;

простих чисел;

{-1,0,1}.

3.3. Для кожного з наступних висловлень знайти предикати, які перетворюються в дане висловлення при заміні предметних змінних їх деякими значеннями з області задання предиката:

6>2+3;

гори Карпати знаходяться в Україні;

через точку А(1;0) можна провести пряму, паралельну до прямої b.

3.4. Визначити які з входжень змінних у формулу є вільними, а які зв'язаними:

;

;

;

.

3.5. Визначити множини істинності наступних предикатів:

P(x)= «», М - множина дійсних чисел;

P(x)= «х парне і просте число», М - множина натуральних чисел;

P(x)= «х взаємно просте з 5», М - множина цілих чисел;

P(x)= «x>х+1», М - множина від'ємних чисел.

3.6. Визначити множини істинності наступних предикатів, заданих на множині М, та зобразити їх на площині:

,

де P(x,y) = «», R(x,y) = «», М -множина дійсних чисел;

,

де Q(x,y) = «», М - множина цілих чисел;

, де P(x,y) = «», R(x,y) = «», М - множина дійсних чисел;

, де P(x,y) = «», R(x,y) = «», М - множина дійсних чисел;

, де P(x,y)= «», R(x,y)= «», М - множина дійсних чисел;

, де P(x,y)= «», R(x,y)= «», М - множина дійсних чисел;

, де P(x,y)= «», R(x,y)= «», М - множина дійсних чисел.

3.7. Нехай на множині людей задано предикати P(x,y) = « х батько у», Q(x,y)= «х мати у», R(x,y) = «х син у» та S(x,y) = «х дочка у». Виразити через них наступні предикати:

«х брат у»;

«х тітка у»;

«х бабуся у з боку матері»;

«х і у - двоюрідні сестри»;

«х і у - внуки z»;

3.8. Вказати всі можливі варіанти зв'язування обох змінних предиката R(x,y), та для кожного утвореного предиката вказати інтерпретації на яких він буде тотожньо істинним висловленням:

R(x,y) = «»,

R(x,y) = «».

3.9. Предикати P(x,y), R(x,y) та Q(x) за дано на множині таблицями значень:

Побудувати таблиці значень предикатів:

;

;

;

;

.

3.10. Для предикатів P(x,y) та Q(x), заданих на множині , скласти таблиці значень так, щоб предикат R(x,y) був:

тотожно істинним, якщо ;

тотожно хибним, якщо ;

виконуваним, якщо .

3.11. Студент вирішив кожну прослухану лекцію повторювати дома. В кінці семестру виявилось що він не виконав свого рішення. Запишіть цей факт мовою логіки предикатів.

3.12. Випадок в магазині. Юнак вирішив купити туфлі в подарунок брату але забув розмір його ноги. Тоді продавець сказав йому: «В нашому магазині для будь-якої ноги знайдуться туфлі підходящого розміру». На що юнак відповів: «Тоді дайте мені туфлі, що підходять до будь-якої ноги». Чи правильно юнак зрозумів продавця?

3.13. На множині натуральних чисел з нулем вибрано такі атомарні предикати:

Виразити через них такі предикати:

;

- просте число;

;

- НСД чисел та .

Формули логіки предикатів. Інтерпретація формул. Виконувані та логічно загальнозначущі формули

Алфавітом логіки предикатів є наступні категорії символів:

предметні змінні;

предметні константи;

функціональні символи (і - порядковий номер, n - кількість аргументів);

предикатні символи (і - порядковий номер, n - кількість аргументів;

знаки логічних операцій: ;

знаки пунктуації «(», «)».

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

Формулами логіки предикатів є:

будь-які елементарні формули;

формули, отримані наступним чином , де і - формули логіки предикатів;

якщо формула логіки предикатів, а вільна змінна цієї формули, то слова і також є формулами логіки предикатів.

всі інші слова, крім тих, які утворюються за правилами 1)-3), не є формулами логіки предикатів.

Приклад 1. Перевірити, чи утворюють наступні слова формули логіки предикатів: «», «».

Слово не є формулою логіки предикатів, оскільки є формулою згідно пунктів 1)-3), але в цій формулі змінна є частково вільною, а тому навішування квантора існування не відповідає пункту 3) і, згідно 4), слово не утворює формулу логіки предикатів.

Слово утворює формулу логіки предикатів. Дійсно, слова і є формулами згідно пункту 1). А слова , і є формулами логіки предикатів згідно пункту 2). Отже формула є формулою логіки предикатів.

Формула, яка не має вільних входжень предметних змінних, називається замкнутою. В протилежному випадку формула є відкритою.

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

Приклад 2. Побудувати деяку інтерпретацію для формули .

Наша формула містить тримісний предикат, один функціональний символ, дві вільні та одну зв'язану змінну. За область інтерпретації оберемо множину всіх дійсних чисел. Функціональному символу поставимо у відповідність унарну операцію піднесення до квадрата . Предикатний символ позначимо тримісним предикатом «». В цій інтерпретації ми отримали формулу , яка буде виконуватись на тих наборах дійсних чисел, для яких і .

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

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

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

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

Приклад 3. Формула логіки предикатів

є загальнозначущою, оскільки одержана підстановкою

,

застосованою до формули алгебри висловлень , що є законом контрапозиції.

Приклад 4. Чи буде формула логіки предикатів виконуваною? ЛЗЗ?

Знайдемо умови, які повинні задовольняти предикати в інтерпретації. Припустимо, що існує інтерпретація на множині М: . Тобто і існують інтерпретації предикатних символів і - і - такі, що:

.

Це рівносильно системі умов:

Останню систему можна переписати так:

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

Наприклад, нехай =«» і =«» на множині . Одержимо формулу , яка набуває істинних значень на всіх цілих числах . Таким чином - виконувана.

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

.

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

Приклад 5. Довести, що формула логіки предикатів є ЛЗЗ.

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

Остання рівність рівносильна системі

Використовуючи означення операцій квантування та імплікації прийдемо до рівносильної системи

яка містить суперечність. Отже наше припущення про спростовність формули є невірним. А тому вона є логічно загальнозначущою.

ВПРАВИ.

3.14. Перевірити чи утворюють наступні слова формули логіки предикатів:

;

;

;

.

3.15. Записати наведені нижче математичні твердження за допомогою формул логіки предикатів:

існують такі дійсні числа x, y, z, що ;

будь-який опуклий чотирикутник має площу;

якщо кожна з двох прямих паралельна третій, то вони паралельні між собою;

для довільного дійсного числа х:;

існують три точки, що не належать одній прямій.

3.16. Побудувати інтерпретації для наступних формул:

;

;

;

.

3.17. Записати деяку інтерпретацію формули над множиною і записати таблицю значень отриманого предиката:

;

;

.

3.18. Навести приклад формули F логіки предикатів, для якої виконується наступна умова:

F є тотожно істиною на всіх скінченних множинах і виконуваною на всіх нескінченних;

F є виконуваною на деякій нескінченній множині і тотожно хибною на всіх скінченних множинах;

F виконувана на скінченних множинах з парною кількістю елементів і тотожно хибна на всіх інших скінченних множинах.

3.19. Перевірити, чи буде формула логіки предикатів логічно загальнозначущою:

;

;

;

;

;

.

3.20. Перевірити, чи буде виконуваною формула логіки предикатів:

;

;

;

;

;

;

;

.

1.2 Відношення рівносильності в логіці предикатів. Зведена та пренексна нормальні форми

В логіці предикатів, як і в алгебрі висловлень, введемо поняття логічного наслідку та задамо відношення рівносильності на множині формул логіки предикатів.

Формула називається логічним наслідком множини формул , якщо вона виконується на всіх наборах елементів з області довільної інтерпретації, на яких виконується кожна формула . Позначення: .

Якщо множина складається лише з однієї формули , то кажуть що формула є логічним наслідком формули .

Дві формули логіки предикатів називаються рівносильними, якщо перша є логічним наслідком другої і навпаки. Позначення: .

Теорема 3.3.1. Якщо і - формули логіки предикатів, то:

формула є логічним наслідком формули тоді і тільки тоді, коли - загальнозначуща формула;

якщо формула є логічним наслідком формули , і формула в даній інтерпретації істинна, то і формула є істинною в даній інтерпретації;

формули і рівносильні тоді і тільки тоді, коли - загальнозначуща формула.

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

Теорема 3.3.2. Мають місце наступні рівносильності формул логіки предикатів:

(перейменування зв'язаних змінних);

(закони де Моргана для кванторів);

, ;

, ;

, ;

Рівносильності 3)-5) мають назву пронесення кванторів через кон'юнкцію та диз'юнкцію.

, ;

, .

Рівносильності 6)-7) мають назву пронесення кванторів через імплікацію. Відмітимо наступне: рівносильності 4)-7) виконуються при умові, що не містить вільних входжень змінної x.

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

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

В логіці предикатів має місце наступна теорема.

Теорема 3.3.3. Для кожної формули логіки предикатів існує зведена форма.

Приклад 1. Знайти ЗФ для формули .

Виконаємо наступні рівносильні перетворення:

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

Теорема 3.3.4. Для кожної формули логіки предикатів існує пренексна нормальна форма.

Приклад 2. Знайти ПНФ для формули .

В попередньому прикладі ми знайшли ЗФ для даної формули. Застосуємо до неї закон пронесення квантора існування і отримаємо формулу , яка ще не утворює ПНФ. У підформулі , згідно рівносильності (1) виконаємо перейменування зв'язаної предметної змінної в нову предметну змінну . Отримаємо нову формулу . Тепер, згідно рівносильності (5), отримаємо . Неважко переконатися, що це і є ПНФ для формули .

ВПРАВИ.

3.21. Перевірити, чи правильно стоїть знак |= у співвідношеннях;

;

;

;

.

3.22. Використовуючи поняття логічного наслідку, перевірити, чи будуть логічними такі міркування:

Ніхто не може розв'язати задачу не знаючи алгоритму розв'язку. Студент не розв'язав задачу. Отже студент не знає алгоритму розв'язку.

Будь-яка людина смертна. Вовк смертний. Отже вовк - людина.

Кожен студент за весь термін навчання пропускає хоч одну пару. Викладачі не поважають студентів, які пропускають пари. Отже викладачі не поважають всіх студентів.

Не всі алгебраїчні числа є раціональними. Всі раціональні числа - дійсні. Отже, деякі алгебраїчні числа не належать до дійсних чисел.

Кожна нескінченна множина має зчисленну підмножину. Множина всіх ірраціональних чисел нескінченна. Кожна множина має потужність не меншу, ніж будь-яка її підмножина. Отже потужність множини ірраціональних чисел не менша ніж зчисленна.

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

Кожний математик мислить логічно. Той, хто мислить логічно, не робить логічних помилок. Іван робить логічні помилки. Отже, Іван - не математик.

3.23. Перевірити, чи існують наступні рівносильності:

;

;

;

.

3.24. Побудувати зведені та пренексні форми для наступних формул логіки предикатів:

;

;

;

;

;

.

3.25. Розв'язати наступні рівняння, системи рівнянь та нерівності, попередньо записавши відповідні їм формули:

;

;

;

;

.

1.3 Застосування логіки предикатів

1.3.1 Застосування символіки логіки предикатів в математичних формулюваннях

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

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

Також, при вивченні математичних дисциплін дуже часто зустрічаються вирази «існує натуральне число», «для будь -якого дійсного числа», «існує єдиний елемент х» і т. д. . Тому в математиці використовуються так звані обмежені квантори. Це по суті скорочені записи тих чи інших формул логіки предикатів, а точніше - їх інтерпретацій. Наприклад, формули і з використанням обмежених кванторів загальності та існування запишуться наступним чином:

і .

В подальшому будемо використовувати дещо зручнішу форму запису, а саме:

і .

Тобто, для формули з нашого прикладу в тій інтерпретації ми мали б записати наступний вираз без використання обмежених кванторів:

.

Також, при записі математичних понять використовують так званий квантор існування та єдиності , який читається: «існує єдиний елемент х, такий, що…». Наприклад, запис в розгорнутому вигляді є формулою

.

1.3.2 Використання елементів математичної логіки для аналізу структури математичних теорем

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

A: «Всі S суть P» - загальностверджувальне судження;

E: «Будь-яке S не є P» - загальнозаперечувальне судження;

I: «Деякі S суть P» - частковостверджувальне судження;

O: «Деякі S не є P» - частковозаперечувальне судження.

В термінах логіки предикатів судження відповідних типів записуються наступним чином.

A: . Тобто судження типу А розуміють так: для будь-якого елемента х , якщо він має властивість S(x), то він має і властивість P(x). Прикладом такого судження може бути наступне: якщо функція диференційована, то вона неперервна.

E: . На мові логіки предикатів це означає наступне: для будь-якого елемента х , якщо він має властивість S(x), то він не має властивості P(x). Прикладом може бути судження: Якщо многокутник є трикутником, то він не може бути ромбом.

I: . В межах логіки предикатів судження типу І потрібно розуміти так: існує елемент х, який має властивість S(x) і одночасно має властивість P(x). Приклад: існують такі функції є неперервними і не диференційованими одночасно.

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

В математичній теорії особливий інтерес становлять судження типу А, які можна записати наступним чином, використовуючи обмежені квантори:

,

де S(x) і P(x) - деякі предикати, задані на множині М, які описують ті чи інші властивості елементів цієї множини. Така конструкція теореми відповідає в математиці конструкції «якщо…, то…» або «нехай…, тоді…». В наведеному формулюванні чітко виділяють умову теореми S(x) та висновок теореми P(x).

Теорема вважається вірною, якщо множина істинності предиката S(x) непорожня і є підмножиною множини істинності предиката P(x). При цьому S(x) називають достатньою умовою для P(x), а P(x) - необхідною умовою для S(x).

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

твердження

називається оберненим для даної теореми, твердження

протилежною теоремою до теореми , а твердження

протилежним до оберненої теореми .

Розглянемо спочатку поняття оберненої теореми. Отже теорема - пряма, а теорема - обернена до неї. Тоді для них можуть бути справедливими чотири випадки.

Обидві теореми вірні. Прикладом може бути твердження «Якщо у чотирикутника протилежні сторони взаємно паралельні, то такий чотирикутник паралелограм», і обернена їй «Якщо чотирикутник є паралелограмом, то його протилежні сторони - паралельні».

Пряма теорема вірна, а обернена - ні. Це можна побачити на такому прикладі: пряма теорема «Якщо функція інтегрована за Ріманом, то вона інтегрована і за Лебегом» є вірною, а обернена - «Якщо функція інтегрована за Лебегом, то вона інтегрована і за Ріманом» - невірна.

Пряма теорема невірна, а обернена вірна. Для цього випадку можна взяти в попередньому прикладі обернену теорему за пряму, а пряму - за обернену.

Обидві теореми невірні. Як приклад розглянемо твердження «Якщо число ділиться на 2, то воно ділиться і на 3» - пряма теорема, яка є не вірною, і обернена - «Якщо число ділиться на 3, то воно ділиться і на 2» - також є невірною.

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

,

і формулювання обох теорем читають «для кожного елемента має місце тоді і тільки тоді, коли має місце P(x)». Прикладом такого твердження може бути наступне: натуральне число ділиться на 6 тоді і тільки тоді, коли воно одночасно ділиться і на 2, і на 3.

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

,

.

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

ВПРАВИ.

3.26. Записати наступні означення за допомогою мови логіки предикатів:

границі функції;

збіжного ряду;

перпендикулярних прямих;

неперервної функції;

колінеарних векторів;

суми векторів в координатах;

паралелограма;

рівностороннього трикутника;

складеного числа;

НСД двох чисел.

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

Якщо діагоналі чотирикутника перетинаються і в точці перетину діляться пополам, то цей чотирикутник паралелограм.

Якщо функція неперервна в кожній точці відрізка, то вона неперервна і на всьому відрізку.

Для того, щоб ряд був збіжний необхідно щоб його загальний доданок прямував до нуля.

Якщо функція неперервна на відрізку і приймає на кінцях цього відрізка значення різних знаків, то на цьому відрізку міститься принаймі один корінь рівняння f(x)=0.

Якщо дві прямі паралельні деякій третій прямій, то вони паралельні між собою.

3.28. Виділити умову та висновок теореми та сформулювати теореми за допомогою зв'язки «якщо…,то…»:

Для подільності добутку двох натуральних чисел на деяке число достатньо подільності на це число одного із співмножників.

Рівність трикутників є достатньою умовою їх рівно великості.

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

На 3 діляться ті числа, у яких сума цифр ділиться на 3.

Для того, щоб послідовність була збіжною, необхідно, щоб вона була обмеженою.

Размещено на Allbest.ru

...