85764 (612568), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

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

2. Якщо H та G - формули, то (¬H),(H G),(H G),(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. x y МЕНШЕ(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={а₁, a₂, ..., а_n} - скінченна предметна область змінної х у предикаті Р(х), то можна скористатись логічними еквівалентностями х Р(х)=Р(а₁) Р(а₂) ... Р(а_n) та х Р (х)=Р(а₁) Р(а₂) ... Р(а_n). У такому разі заперечення квантифікованої формули дає той самий результат, що й застосування відповідного закону де Моргана. Це випливає з того, що

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

Аналогічно, ¬( х Р(х))=¬(Р(а₁) Р(а₂) ... Р(а_n))= (а₁) (а₂) ... (а), що еквівалентне х (х).

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

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

Приклад 2.10. Наступні формули записані у випередженій нормальній формі:

1) x y(P(x, y) Q(y));

2) x y( (x, y)→Q(y));

3) x y z(Q(x, y)→R(z)).

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

Крок 1. Виключити з формул логічні зв'язки "~" та "→" застосуванням правил Р~Q=(Р→Q) (Q→Р) та Р→Q= Q.

Крок 2. Внести знак заперечення всередину формули, для чого використати закони:

• подвійного заперечення = Р;

• де Моргана = , =

• ¬( х Р (х))= х (х) та ¬( х Р(х))= х (х).

Перейменувати зв'язані змінні, якщо це потрібно.

Крок 3. Винести квантори у префікс, для чого скористатись законами 3 - 8 з підпункту 2.2.

Література

1. Капітонова Ю. В., Кривий С. Л., Летичевський О. А., Луцький Г. М., Печурін М. К. Основи дискретної математики. - К.: Наукова думка, 2002.

2. Середа В. Ю., Математична логіка в шкільному курсі математики. – К.: Радянська школа, 1984.

3. Мендельсон 3. Введение в математическую логику. - М.: Наука, 1971.

4. Новиков П. С. Элементы математической логики. - М.: Наука, 1973.

5. Столл Р. Множества. Логика. Аксиоматические теории. — М: Просвещение, 1968.

6. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. – В: Магнолія плюс, 2005.

Характеристики

Список файлов курсовой работы