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

курсовая работа

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

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

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

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

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

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

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

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

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)...(а), що еквівалентне х(х).

Делись добром ;)