L_3_U

Зміст лекції.
1. Поняття предикату.
2. Квантори.
3. Формули логіки предикатів.
4. Интерпретація. Модель.
5. Правила для кванторів.
6. Числення предикатів.

Поняття «предикат» узагальнює поняття «висловлювання». Неформально кажучи, предикат - це висловлювання, в яке можна підставляти аргументи. Якщо аргумент один - то предикат виражає властивість аргументу, якщо більше - то відношення між аргументами.
Предика́т (лат. praedicatum — заявлене, згадане, сказане) — це те, що стверджується про суб'єкт. Суб'єктом висловлювання називається те, про що робиться твердження.
Приклад предикатів. Візьмемо вислови: “Сократ – людина” , “Платон – людина “. Обидва ці висловлювання виражають властивість “бути людиною “. Таким чином, ми можемо розглядати предикат “бути людиною “ і говорити, що він виконується для Сократа і Платона.

Предикат – розповідне речення, що містить предметні змінні, визначені на відповідних множинах. При заміні змінних конкретними значеннями (елементами) цих множин предикат звертається у висловлювання, тобто приймає значення "істинно" або "хибне".
Фрідріх Людвіг Готлоб Фреге
Бертран Артур Уільям Рассел
Альфред
Норт Уайтхед
Логіка предикатів, як і логіка висловлювань, може бути побудована у вигляді алгебри логіки предикатів і числення предикатів. Тут, як і у випадку логіки висловлювань, для знайомства з основними поняттями логіки предикатів скористаємося мовою алгебри, а не числень.
предикат Р(х1,х2,...,хn) являє собою функцію типу Р: М1 x М2 x ... x Мn → B, де множини М1, М2, ..., Мn називаються предметними областями предикату; х1, х2,..., хn – предметними змінними предикату; В - двійкова (бінарна) множина: В = {І, Х} або {1,0}. Якщо предикатні змінні приймають значення на одній множині, то Р: Мn→В.

Визначення і приклади.
Предикатом називається розповідне речення про елементи деякої заданої множини M, яке (речення) стає висловлюванням, якщо всі змінні в ньому замінити фіксованими елементами з M; висловлювання теж будемо вважати предикатом – нуль-місним предикатом. Часто замість "предикат від n-змінних" кажуть "n - місний предикат".
Приклад: Нехай x, y, z - цілочисельні змінні. 1) x> 10; 2) x + y = 7; 3) x2 + y2 = z2 - предикати. За кількістю вільних змінних, що входять в предикат, розрізняють предикати одномісні, двомісні, тримісні і т.д. (відповідають приклади 1) -3)).
Поняття предикату узагальнює поняття висловлення, а теорія предикатів є більш витонченим інструментом порівняно з алгеброю висловлень для вивчення закономірностей побудови умовиводів в процесі міркування. У цій теорії розглядається внутрішня структура простих висловлень: у висловленнях виділяють підмет і присудок (предикат), і якщо на місце підмета потім ставити інший підмет, то вийде інше висловлення.

Існують такі види логічних міркувань, які не можуть бути обґрунтовані в рамках обчислення висловлювань. Ось приклади таких міркувань:
A) Будь який друг Мартіна є друг Джона. Пітер не є друг
Джона. Отже, Пітер не є друг Мартіна.
B) Всі люди безсмертні. Сократ-людина. Отже, Сократ безсмертний.
Коректність цих умовиводів залежить не тільки на істінностно - функціональних відношень які входять у них між пропозиціями, але і на внутрішній структурі самих пропозицій, а також і на розумінні таких виразів, як «все», «будь який» і т. Д.
Кожний ромб є паралелограм.
Чотирикутник ABCD - ромб.
Отже, чотирикутник ABCD - паралелограм.
Позначимо ці пропозиції буквами X, Y, Z.
Правильність наведеного умовиводу не викликає сумніву. Але як відомо з логіки висловлювань, Z логічно випливає з X і Y тоді і тільки тоді, коли X ∧Y → Z є тотожно істинною формулою. Але ця формула - НЕ тавтологія. Отже, на базі алгебри висловлювань Z не випливає з X і Y.
Тобто X, Y ├ Z

Квантори
Квантор - логічна операція, яка дає кількісну характеристику предметної області, до якої відноситься вираз, одержуване в результаті використання квантора. Квантор - це загальна назва для логічних операцій, які по предикату P (x) будують висловлювання, що характеризує область істинності предиката P (x).
Квантори загальності ∀ та існування ∃ використовуються для визначення області дії змінних. Так, якщо x - змінна, то запис ∀ x читається "для будь-якого x", "для кожного x" і т.п., а запис ∃x - "існує x", "хоча б для одного x" і т.п .
Входження змінної в формулу безпосередньо після знака квантора або в область дії квантора, після якого стоїть ця змінна, називається зв'язаним. Всі інші входження змінних називаються вільними.

Квантором загальності називають символ ∀, під дією якого предикат P (x), визначений на множині М, приймає значення істинності для всіх x∈М і позначається ∀хР (х).
Квантором існування називається символ ∃, під дією якого предикат, визначений на множині М, приймає значення істинності для деяких x∈М і позначається ∃хР (х).
Приклад. Висловлювання «Всі студенти здають іспити» і «Деякі студенти здають іспити на відмінно» представити логікою предикатів.
Рішення.
Введемо предикати - Р (х) - «х - здає іспит».
Q (x) - «х здає іспит на відмінно».
х∈М - множина студентів.
Тоді, шукані подання мають вигляд - ∀хР (х) і ∃хQ (х).

Приклад 1. Задано предикат: «х любить у» - позначимо його Р (х, у).
∀х∃уР(х,у) –
всяка людина когось любить.
∃у∀хР(х,у) –
існує така людина, що його всі люблять. ∀х∀уР(х,у) –
всі люди люблять всіх людей.
∃х∃уР(х,у) –
існує людина, якого хтось любить
∃х∀уР(х,у) –
існує людина, яка любить усіх людей
∀у∃хР(х,у) -
кожну людину хтось любить.

Логіка предикатів
На сукупності всіх предикатів, заданих на множині М, додаються знайомі по логіці висловлень операції кон’юнкція, диз'юнкція, заперечення, імплікація і эквіваленція. Ці операції вводяться досить очевидним чином. Наведемо як приклад визначення кон’юнкції предикатів.
Визначення 2.3.2 Предикат W(x1,…,xn)називається кон’юнкцією предикатів U(x1,…,xn)і V(x1,…,xn),заданих на множині М, якщо для будь-яких а1,…,аn з М висловлення W(а1,…,аn) є кон’юнкцією висловлень U(а1,…,аn) і V(а1,…,аn).
Легко за аналогією привести визначення й інших згаданих вище операцій.

На предикати можна дивитися і більш формально, причому з двох точок зору.
По-перше, предикат можна представити відношенням у такий спосіб. Нехай предикат P(x1,…,xn)заданий на множині M. Розглянемо прямий ступінь цієї множини Mn=MxMx…xM підмножина Dp множини Mn, обумовлена рівністю:
Dp={(a1,…,an)∈Mn : висловлення P(a1,…,an) істинно}.
Відношення Dp можна назвати областю істинності предиката P. У багатьох випадках предикат P можна ототожнити з відношенням Dp. При цьому, правда виникають деякі труднощі при визначенні операцій над відношеннями, аналогічними операціям над предикатами.
По-друге, предикат P(x1,…,xn),заданий на M, можна ототожнити з функцією fp:Mn→{0,1}.

Означення. Множиною (областю) істинності предиката Р(x1,…,xn) , заданого на множині М ⊂
(М1×М2×…Мn), називається сукупність всіх наборів (а1, а2, …аn) ∈М, для кожного з яких |Р(а1, а2, …аn)|=1.
Цю множину позначимо Мр.
Наприклад. Предикат Р(x, y):”x+y=5”, заданий на множині М = {1, 2, 3, 4, 5}, має Мр ={(1, 4), (2, 3), (3, 2), (4, 1)}.
Предикат Р(x):”sinx=1/2”, заданий на множині R, має
Мр ={(-1)n π/6 + πn, n∈Z}.

Теорема. Предикат Р(x1,…,xn), заданий на множині М ⊂ (М1×М2×…Мn), буде:
1) тотожно істинним ⇔ Мр = М;
2) тотожно хибним ⇔ Мр = ∅;
3) виконуваним ⇔ Мр ≠ ∅ ;
4) спростовним ⇔ Мр ≠ М.
Означення. Предикат Q(x1,…,xn), заданий на множині М ⊂ (М1×М2×…Мn), називається логічним наслідком предиката
Р(x1,…,xn),заданого на тій же множині, якщо Мр ⊂ МQ

Визначення. Інтерпретацією на непорожній множині М називається функція, задана на сигнатурі F∪R, що
1) константі ставить у відповідність елемент із М;
2) символові n-місНОї функції ставить у відповідність деяку n-місНу функцію, визначену на множині М;
3) символові n-місного предиката ставить у відповідність n-місний предикат, заданий на М.
У результаті будь-яка формула F одержує у відповідність предикат, місність якого дорівнює числу вільних зміних в формулі F.

 Приклад. Нехай сигнатура складається із символу одномісного предиката P і двомісного предиката D, M={2,3,6,9,12,15} і
F=(P(x)^(∀ y)(P(y) ^(D(x,y))
Поставимо у відповідність (проінтерпретуємо) P(x) предикат «x – просте число», D(x,y) – предикат «x менше або дорівнює y». Тоді формула F одержить у відповідність предикат «x=2». На цій же множині можна розглянути й іншу інтерпретацію: P(x) ставиться у відповідність «x – непарне число», D(x,y) – предикат «x поділяє y». У такому випадку, формула F одержує у відповідність предикат «x=3».

Одним з основних типів задач цієї теми є задачі, пов'язані з використанням виразних можливостей мови логіки предикатів. Як приклад, розглянемо задачу перекладу на мову логіки предикатів наступного міркування.
«Кожний другокурсник знайомий з ким-небудь зі спортсменів. Ніякий другокурсник не знаком ні з одним аматором підлідного лову. Отже, ніхто зі спортсменів не є аматором підлідного лову».
Для зручності посилань це міркування умовимося називати міркуванням про другокурсників. Виберемо наступну сигнатуру:
Д(х): «х – другокурсник», С(х): «х – спортсмен»,
ПЛ(х): «х – аматор підлідного лову», З(x,y): «х знайомий з y».

Тоді міркування запишемо у вигляді наступної послідовності формул.
Н1=(∀ x)[Д(х)→ (∃y)(C(y)^З(x,y))],
H2=(∀ x)(∀ y)[Д(x) ^ПЛ(y ) → ¬З(x,y)],
H3=(∀ x)(C(x )→¬ПЛ(x))

Визначення Формули F(x1,…,xn) і G(x1,…,xn) називаються рівносильними, якщо для будь-якої інтерпретації з областю М висловлення F(a1,…,an) і G(a1,…,an) при будь-яких a1,…,an з М одночасно істинні або одночасно хибні.
Визначення Формула F(x1,…,xn) називається тотожно істиною, якщо для будь-якої інтерпретації φ з областю М висловлення
( φ F)(a1,…,an) при будь-яких a1,…,an з М є істинним.
Аналогічно вводиться означення тотожно хибної формули.

Логіка першого порядку (числення предикатів)
Логіка першого порядку (числення предикатів) - формальне числення, яка допускає висловлювання щодо змінних, фіксованих функцій і предикатів. Розширює логіку висловлювань. В свою чергу є окремим випадком логіки вищого порядку.
Мова логіки першого порядку будується на основі сигнатури, що з множини функціональних символів fin і множини предикатних символів Pin. З кожним функціональним і предикатним символом пов'язана арність, тобто число можливих аргументів. Допускаються як функціональні, так і предикатні символи арності 0. Перші іноді виділяють в окрему множину констант a1, a2, ..., an. Крім того, використовуються такі додаткові символи 1) Символи змінних (зазвичай x, y, z, ... x1, x2, x3, .... Тощо. Д.). 2) Пропозіціональние зв'язки: ¬, ∨, ∧, →, ↔. 3) Квантори: загальності ∀ та існування ∃. 4) Службові символи: дужки і кома.
Перераховані символи разом з символами з f і P утворюють Алфавіт логіки першого порядку.

Більш складні конструкції визначаються індуктивно:
Терм є символ змінної або предметної константи, або має вигляд fin (t1, ...,, tn) де f - функціональний символ арності n, а ti -Терм.
Атом має вигляд Pin (t1, ..., tn), де P - предикатний символ n арності, а tn - терми.
Формула - це або атом, або одна з наступних конструкцій : ¬F, F1∨F2, F1∧F2, F1→F2, F1↔F2, ∃xF(x), ∀xF(x), де F, F1, F2 — формули, а x — змінна.
Змінна називається зв'язаною у формулі F, якщо F має вигляд ∃xG або ∀xG , або представима в одній з форм ¬F, F1∨F2, F1∧F2, F1→F2, F1↔F2, причому x вже звязана в F, F1 та F2 . Якщо x не зв'язана в F, її називають вільною у F. Формулу без вільних змінних називають замкнутої формулою, або пропозицією. Теорією першого порядку називають будь-яку множину пропозицій.

Аксіоматика і доведення формул
Система логічних аксіом логіки першого порядку складається з аксіом числення висловів доповненої двома новими аксіомами:
∀xA→A [x / t], A ​​[x / t] →∃xA,
де, A [x / t] - формула, отримана в результаті підстановки терма t замість кожної вільної змінної x, що зустрічається у формулі A.
Правила виводу 2:Modus ponens: A, A→B ⊢B.
Правило узагальнення : A ⊢ ∀x A.

Використання
Будучи формалізованим аналогом звичайної логіки, логіка першого порядку дає можливість строго міркувати про істинність і хибність тверджень і про їх взаємозв'язок, зокрема, про логічне слідуванні одного твердження з іншого, або, наприклад, про їх еквівалентності. Розглянемо класичний приклад формалізації тверджень природної мови в логіці першого порядку.
Візьмемо міркування «Кожна людина смертна. Конфуцій - людина. Отже, Конфуцій смертний ». Позначимо «x є людина» через ЛЮДИНА (x) і «x смертний» через Смертний (x). Тоді твердження «кожна людина смертна» може бути представлено формулою: ∀ x (ЛЮДИНА (x) → Смертний (x)) твердження «Конфуцій - людина» формулою ЛЮДИНА (Конфуцій), і «Конфуцій смертний» формулою Смертний (Конфуцій). Твердження в цілому тепер може бути записано формулою
(∀x (ЛЮДИНА (x) → Смертний (x)) ЛЮДИНА (Конфуцій)) → Смертний (Конфуцій)

Рівносильні формули логіки предикатів.
Визначення 1.
Дві формули логіки предикатів А і В називаються рівносильними на області М, якщо вони приймають однакові логічні значення при всіх значеннях вхідних у них змінних, віднесених до області М.
Визначення 2.
Дві формули логіки предикатів А і В називаються рівносильними, якщо вони рівносильні на будь якій області.

Ясно, що всі рівносильности алгебри висловлювань будуть вірними, якщо в них замість змінних висловлювань підставити формули логіки предикатів. Але, крім того, мають місце рівносильності самої логіки предикатів. Розглянемо основні з цих рівносильностей.
Нехай А (х) і В (х) - змінні предикати, а С - змінне висловлювання (або формула, яка не містить х). Тоді мають місце рівносильності:

Рівносильність 1 означає той простий факт, що, якщо не для всіх х істинно А (х), то існує х, при якому буде істиною.
Рівносильність 2 означає той простий факт, що, якщо не існує х, при якому істинно А (х), то для всіх х буде істиною.
Рівносильності 3 і 4 виходять з рівносильних 1 і 2, відповідно, якщо від обох їх частин взяти заперечення і скористатися законом подвійного заперечення.

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