Математична логіка (стр. 7 из 8)

7.

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

8.

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

9.

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

10.

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

Процедура доведення законів вимагає використання спеціальних прийомів. Проілюструємо це на прикладі доведення еквівалентності ¬(

xP(х))= 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), а це, у свою чергу, еквівалентне х (х).