Навигация
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 nx nM, де кожне Q ixi (i=1,2,...,n) - це або xi, або хi, а формула М не містить кванторів. Вираз Q1x1Q2x2…Q nx n називають префіксом, а М - матрицею формули, записаної у випередженій нормальній формі.
Приклад 2.10. Наступні формули записані у випередженій нормальній формі:
1) xy(P(x, y)Q(y));
2) xy((x, y)→Q(y));
3) xyz(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.
Похожие работы
... його функцій і структури, тобто ролі і значення в пізнанні і практичній діяльності, і в той же час з погляду складових його елементів, а також зв'язків і відносин між ними. Це і є власний, специфічний предмет логіки. Тому вона визначається як наука про форми і закони правильного мислення, що веде до істини. Що ж таке логічна культура? Це культура мислення, що виявляється в культурі письмового й ...
... (логіці, етиці і політиці) означає не що інше, як повернення до традиціоналістсько-авторитарного типу цивілізації, на що і претендував тоталітаризм XX в. 3. Загальне і відмінності формальної і діалектичної логіки В четвертій книзі “Метафізики" Арістотель ставив питання: який принцип є таким самоочевидним, що його можна покласти в основу істинної філософії. Таким самоочевидним принципом Арі ...
... , сполучників, префіксів і префіксальних словоформ, розділових знаків, а також за розподілом довжини речення). Крім статистичних методів, у мовознавстві застосовують методи теорії інформації, математичної логіки, теорії ймовірностей і теорії множин. 3. Застосування математичних теорій. Дані теорії інформації використовуються для найекономнішої передачі інформації засобами мови. Кожна ...
... і продукції. Виробничі потужності ТОВ «Брусилівський маслозавод» дозволяють виробляти близько 150 т масла, 30 т глазурованих сирків за рік, переробляючи приблизно 1000 кг молока за день. Основні споживачі продукції ТОВ «Брусилівський маслозавод» - населення Брусилівсьекого району та районів, що знаходяться поруч з Брусилівським, Житомирської області. . Отже, ТОВ «Брусилівський маслозавод» – ...
0 комментариев