Быстрый поиск

Курсовая работа: Математична логіка

Приклад 2.1. Прикладами речень, які містять змінн "х>3", "x=y+3", "x+у=z". Ці речення н стинні, ні фальшиві доти, поки змінні не одержать значення.

У наведеному прикладі речення "х>3", або, в іншій формі, "х більше 3" складається з двох частин: першу, змінну х, називають предметом, другу - "більше 3", - яка вказує властивість предмета, називають предикатом. Часто предикатом називають все речення.

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

1) Індивідні символи або сталі - це імена об'єктів, які починаються з великої букви: Іван, Марія та сталі: Т, F або 3.

2) Предметні символи - імена змінних, які позначають малими буквами, можливо, з індексами: х,у,z,vi,wj.

3) Предикатні символи — імена, якими позначають предикати та записують великими буквами: Р, Q, R, або змістовними словами, які записують великими буквами БІЛЬШЕ, ЛЮБИТЬ тощо.

Приклад 2.2. Позначимо речення "х більше 3" через Р(х), де предикатний символ Р позначає предикат "більше 3", а х - змінна, або предметний символ. Вираз Р(х) у цілому теж називають предикатом. Щоб записати твердження "х більше 3" як предикат, можна поступити інакше - визначити предикат БІЛЬШЕ(х,у), який означає "х більше y". Тод речення "х більше 3" можна записати за допомогою предиката БІЛЬШЕ(х, 3).

Загалом, предикат, який містить n змінних: x1, x2, x3,…, xn, записують Р(х1,х2,...,хn) та називають n-місним. Змінну xiDi (i=1,2,..,n) називають предметною, множину Di - її предметною областю, а символ Р - n-місним предикатним символом. Замість терміну "предикат" іноді використовують "пропозиційна функція".

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

Атом логіки першого ступеня має вигляд Р(х1, х2,...,хn), де Р- предикатний символ, а x1,x2,…,xn - предметні або індивідні символи.

Приклад 2.3. Нехай вираз "x+у=2" задано предикатом Q(х, у). Тоді Q(1,2) - фальшиве висловлювання, а Q(2,0) - істинне. Позначимо це так: Q(1,2)=F, Q(2,0)=Т. Задамо речення "х любить y" предикатом ЛЮБИТЬ(х,у). Тоді істинне речення "Іван любить Марію" подається істинним висловлюванням ЛЮБИТЬ (Іван, Марія).

Приклад 2.4. Якщо БІЛЬШЕ(х, у) - предикат, визначений у прикладі 2.2, то БІЛЬШЕ(5,3) - істинне висловлювання, а БІЛЬШЕ (1,3) - фальшиве висловлювання.

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

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

1. Атом є формулою.

2. Якщо H та G - формули, то (¬H),(HG),(HG),(H→G) та (H~G) - формули.

3. Якщо H формула, а х - змінна у формулі H, то хH та хH - формули.

4. Формули одержують лише скінченною кількістю застосувань правил 1-3.

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

Приклад 2.5. Позначимо речення "х просте число" через P(х), "х раціональне число" - через Q(х), "х дійсне число" - через R(х) та "х менше y" - через МЕНШЕ(х, у). Розглянемо так стинні речення.

1. Кожне раціональне число є дійсним.

2. Існує число, яке є простим.

3. Для кожного числа х існує таке число у, що х < у.

Наведені речення записують такими формулами.

1. x (Q(x) → R(x)).

2. x P(x)

3. xy МЕНШЕ(x, y)

Перехід від Р(х) до х Р(х) або х Р(х) називають зв'язуванням змінної x, а змінну х — зв'язаною. Не зв'язану змінну називають вільною. У формулах х Р(х) та х Р(х) предикат Р(х) перебуває в області дії відповідного квантора.

Приклад 2.6. У формулі х Р (х, у) змінна х зв'язана, а змінна у - вільна, оскільки перед формулою відсутній квантор, який містить цю змінну.

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

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

2.2 Закони логіки предикатів.

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

Аналогічно до попереднього, формули логіки першого ступеня називають еквівалентними, якщо вони приймають однакові значення істинності при довільних значеннях вільних змінних. Зокрема, якщо формули Р та Q еквівалентні, то формула Р~Q - тавтологія. Еквівалентність формул Р та Q будемо записувати Р-Q.

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

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

1. ¬(x P(x))=x(x).

2. ¬(x P(x))=x(x).

3. x(P(x)Q(x))=x P(x)x Q(x).

4. x(P(x)Q(x))=x P(x)x Q(x).

5. x(P(x)Q)=x P(x)Q

6. x(P(x)Q)=x P(x)Q

7. x(P(x)Q)=x P(x)Q

8. x(P(x)Q)=x P(x)Q

9. ху Р(х,у)=ух Р(х,у).

10. ху Р(х, у)= ух Р(х, у).

Процедура доведення законів вимагає використання спеціальних прийомів. Проілюструємо це на прикладі доведення еквівалентності ¬(x P(х))=x(x). Нехай для деякого предикатного символу Р та предметної області D ліва частина ц еквівалентності істинна. Тоді не існує такого аD для якого Р(а) істинне. Отже Р(а) фальшиве для довільного а, а (а) - істинне, та істинна права частина еквівалентності. Якщо ліва частина еквівалентності фальшива, то снує таке аD для якого Р(а) стинне, тобто й права частина фальшива. Аналогічно доводять ¬(x P (х))=x(x).

Приклад 2.7. Розглянемо заперечення речення "Кожний студент університету вивчає математичний аналіз". Це речення записують з використанням квантора загальності як х Р(х) де Р(х) - речення "х вивчає математичний аналіз". Запереченням заданого речення є речення "Це не так, що кожний студент університету вивчає математичний аналіз", яке еквівалентне реченню "Існує такій студент університету, який не вивчає математичний аналіз". Останнє доводить заперечення початкової формули: х(х). Цей приклад ілюстру еквівалентність ¬(х Р(х))=х(х).

Приклад 2.8. Розглянемо речення "В університеті є студент, який вивчає математичний аналіз". Це речення можна записати із використанням квантора існування як х Р (х), де Р(х) речення "х вивчає математичний аналіз". Запереченням заданого речення речення "Це не так, що є студент в університеті, який вивчає математичний аналіз", яке еквівалентне реченню "Кожний студент університету не вивчає математичний аналіз". Останнє отримують квантифікацією квантором загальності заперечення заданого речення: х Р(х). Цей приклад люструє еквівалентність ¬(х Р(х))=х(х).

Доведемо закон x(Р(х)Q(х))=х Р(х)хQ(х). Нехай ліва частина стинна для деяких Р та Q, тобто для довільного аD істинне Р(а)Q(а). Тому Р(а) та Q(а) одночасно стинні для довільного а, тобто х Р(х)хQ(х) істинне. Якщо ж ліва частина фальшива, то для деякого аD фальшиве Р або Q. Це означає, що фальшиве х Р(х) або хQ(х), тобто фальшива й права частина. Аналогічно доводять еквівалентність.

У законах 9 та 10 змінні в предикатах зв'язані однаковими кванторами, що дозволяє переставляти їх без порушення еквівалентності. У випадку різних кванторів така еквівалентність виконується не завжди, тобто, загалом ху Р(х, у)≠ух Р(х, у). Наведемо приклад, який ілюструє це зауваження.

Приклад 2.9. Розглянемо двомісний предикат Р(х, у) зі змістом "х≥y" на різних предметних областях. Формула ху Р(х, у) стверджує, що в предметній області існує єдиний максимальний елемент. Ця формула істинна на предметній області, яка є будь-якою скінченною множиною цілих чисел, але фальшива, наприклад, на такій множині {1/2, 2/3, 3/4,...,n /(n+1),...}. Формула ух Р (х, у) істинна на довільній непорожній множині. Отже, цей приклад ілюструє той факт, що переставлення кванторів існування та загальності може змінити зміст формули та її істинність.

Якщо D={а1, a2, ..., аn} - скінченна предметна область змінної х у предикаті Р(х), то можна скористатись логічними еквівалентностями х Р(х)=Р(а1)Р(а2)...Р(аn) та х Р (х)=Р(а1)Р(а2)...Р(аn). У такому раз заперечення квантифікованої формули дає той самий результат, що й застосування відповідного закону де Моргана. Це випливає з того, що

¬(хP(х))=¬(P(а1)Р(а2)...P (аn))=(а1)(а2...(аn), а це, у свою чергу, еквівалентне х(х).

Аналогічно, ¬(х Р(х))=¬(Р(а1)Р(а2)...Р(аn))=(а1)(а2)...(а), що еквівалентне х(х).

2.3. Випереджена нормальна форма логіки предикатів

Формула логіки першого ступеня записана у випередженій нормальній формі, якщо вона має вигляд Q1x1Q2x2…Q n x n M, де кожне Q i xi (i=1,2,...,n) - це або xi, або хi, а формула М не містить кванторів. Вираз Q1x1Q2x2…Q n x n називають префіксом, а М - матрицею формули, записаної у випередженій нормальній формі.