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

Предикат математики

В математичній логіці предикат зазвичай розуміється як функція P: X → {правда, брехня}, звана предикатом X. Однак предикати мають багато різних застосувань і інтерпретацій в математиці і логіці, і їх точне визначення, зміст та використання будуть варіюватися від теорії до теорії. Так, наприклад, якщо теорія визначає поняття відношення, то предикат є просто характеристичної функцією, інакше відомої як індикаторна функція відносини. Однак не всі теорії мають відношення або засновані на теорії множин, тому потрібно бути обережним з правильним визначенням і семантичної інтерпретацією предиката.

Правда чи брехня

Якщо вам все ще незрозуміло, що таке предикат в математиці, то варто зупинитися на цьому докладніше. Неформально предикат – це твердження, яке може бути істинним або хибним залежно від значень змінних. Його можна розглядати як оператора або функцію, яка повертає значення, яке є істинним або хибним. Наприклад, предикати іноді використовуються для вказівки набору елементів: при розмові про наборах іноді буває незручно або неможливо описати набір, перераховуючи всі його елементи. Таким чином, предикат P (x) буде істинним або хибним, в залежності від того, належить чи x безлічі.

Властивості об’єктів

Предикати в математичній логіці також широко використовуються, щоб говорити про властивості об’єктів, визначаючи набір всіх об’єктів, що мають спільну властивість. Так, наприклад, коли P є предикатом X, іноді можна сказати, що P є властивістю X. Аналогічно, позначення P (x) використовується для позначення пропозиції або затвердження P щодо об’єкта змінної Х. Безліч, певне P (x), записується як {x | P (x)} є множиною об’єктів, для яких P істинно.

Наприклад, {x | x – натуральне число, менше 4} – множина {1,2,3}.

Якщо t – елемент множини {x | P (x)}, то твердження P (t) істинно.

Тут P (x) називається предикатом, а x – заповнювачем пропозиції. Іноді P (x) також називається пропозиційну функцію, так як кожен вибір з Х створює пропозицію.

Простим видом предиката (П) є логічне вираження, і в цьому випадку входи у вираз самі є значеннями, об’єднаними з використанням булевих операцій. Булеве вираз з безліччю істинності предиката є більш складним явищем.

Формальне визначення

• Точна семантична інтерпретація атомної формули і атомного пропозиції буде варіюватися від теорії до теорії.
• У пропозиційну логіку атомні формули називаються пропозициональными змінними. У певному сенсі це предикати з нульовими значеннями.
• У логіці першого порядку атомна формула складається з предикатного символу, що застосовується до відповідного числа членів.
• В теорії множин предикати розуміються як характерні функції або задають функції індикатора, тобто функції від заданого елемента до значення істини.
• Метод побудови видів суджень використовує предикати для їх визначення.
• У автоэпистемической логіці, яка відкидає закон виключеного третього, предикати можуть бути істинними, хибними або просто невідомими, тобто даний набір фактів може бути недостатнім для визначення істинності або хибності предиката.
• У нечіткій логіці предикатів є характерними функціями розподілу ймовірностей. Тобто строга істинна / помилкова оцінка предиката замінюється величиною, інтерпретується як ступінь правди.

Предикат у граматиці

Існує два конкуруючих поняття предиката в теоріях граматики. Конкуренція між цими двома концепціями породила плутанину щодо використання терміна «предикат» у теоріях граматики. Так що таке предикат? У цій статті розглядаються обидва ці поняття.

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

Друге поняття було отримано з роботи в обчисленні предикатів (логіка предикатів, логіка першого порядку) і є помітним в сучасних теоріях синтаксису і граматики. У цьому підході предикат пропозиції в основному відповідає головному дієслова і будь-яким допоміжним засобам, які супроводжують головний дієслово. В той же час його аргументи (наприклад, фрази іменники) знаходяться за межами предиката.

В традиційній граматиці

Поняття П у традиційній граматиці натхненне пропозиційну логікою давнину (на відміну від більш сучасної логіки предикатів). Предикат розглядається як властивість, що суб’єкт має. Отже, предикат є вираженням, яке може бути істинним. Таким чином, вираз «рухається» вірно для всього, що рухається. Це дає відповідь на питання, що таке предикат.

Таке класичне розуміння предикатів було прийнято більш або менш безпосередньо в латинській і грецькій граматиках, і звідти воно потрапило в граматику англійської і російської мов, де застосовується безпосередньо до аналізу структури пропозиції. Це розуміння П також використовується в англомовних словниках.

Суб’єкт і предикат

Предикат є однією з двох основних частин пропозиції (інший суб’єкт, який предикат модифікує). Він повинен містити дієслово, дієслово вимагає або дозволяє іншим елементам заповнювати предикат.

Предикат надає інформацію про предмет: чим він є, що робить суб’єкт, або що таке об’єкт. Зв’язок між суб’єктом і його предикатом іноді називається мовою предикатів. Його номінал – це существительная фраза. Наприклад, у фразі “Джордж III – король Англії”, король Англії є предикативних номіналом. Суб’єкт і предикативне номінал повинні бути з’єднані сполучною дієсловом, також званим копулой. Суб’єкт і предикативне прикметник також повинні бути пов’язані зв’язкою.

У синтаксисі

Синтаксичний П вказує синтаксичну обґрунтованість застосування твори у формальній граматиці і аналогічний семантичним предикату, що визначає семантичну дійсність застосування твори. У своїй первісній реалізації синтаксичні предикати мали форму «(α)?» і могли з’являтися тільки на лівому краю твори. Необхідним синтаксичним умовою α може бути будь-який дійсний контекстно-вільний фрагмент граматики.

Більш формально синтаксичний предикат представляє собою форму виробничого перетину, використовуваного в специфікаціях парсера або у формальних граматиках. У цьому сенсі термін має значення математичної функції індикатора. Якщо p1 та p2 є виробничими правилами, мову, згенерований як p1, так і p2, є їх заданими перетином.

Мудруємо граматики виразів (PEGs), винайдені Брайаном Фордом, розширюють ці прості П, дозволяючи їм з’являтися де завгодно в межах виробництва нарівні з “не предикатами”. Більш того, Форд винайшов процедуру аналізу для обробки цих граматик у лінійному часі.

Цей підхід реалізується в ANTLR версії 3, яка використовує детерміновані кінцеві автомати для перегляду. Це може вимагати тестування предиката для вибору між синтаксичними переходами (так званий «перед-LL (*)» синтаксичний аналіз).

У сучасних теоріях синтаксису

Більшість сучасних теорій синтаксису і граматики беруть свій початок у теорії обчислення предикатів, пов’язаних з Готлобом Фреге. Це розуміння бачить предикати як відносини або функції, що стоять над аргументами. Вони служать для призначення властивості одного аргументу, або для зв’язку двох або більше аргументів один з одним. Пропозиції складаються з предикатів та їх аргументів (і доповнень) і є, таким чином, структурами предикатного аргументу. Згідно з ними, цей П розглядається як зв’язування його аргументів з більшою структурою.

Предикати поміщаються зліва за межами дужок, тоді як їхні аргументи містяться всередині дужок. Один визнає валентність предикатів, у відповідності з яким він може бути доступний (не показаний), моновалентний, двухвалентный або тривалентний. Ці типи уявлень аналогічні формальним семантичним аналізом, де мова йде про належному обліку фактів кванторов і логічних операторів. Однак у відношенні основної структури пропозиції ці уявлення припускають насамперед, що дієслова є предикатами, а фрази іменників, з якими вони з’являються, є їх аргументами. При такому розумінні пропозиції бінарний поділ речення на предмет NP і предикат VP навряд чи можливо. Замість цього дієслово є предикатом, а іменники – його аргументами.

В логіці

Логіка першого порядку, також відома як числення предикатів першого порядку і логіка предикатів, являє собою набір формальних систем, що використовуються у математиці, філософії, лінгвістики та інформатики. Логіка першого порядку використовує квантовані змінні над об’єктами і дозволяє використовувати речень, що містять змінні. Це відрізняє його від логіки висловлювань, яка не використовує квантори або відносини.

Логіка першого порядку

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

Використовуються прикметники відрізняють логіки першого порядку від логіки вищих порядків, в якій є П, мають визначають предикати або функції в якості аргументів, або в яких можна один або обидва квантора предикатів або квантори функцій. В теоріях першого порядку предикати часто пов’язані з множинами. В інтерпретованих теоріях більш високого порядку їх можна інтерпретувати як множини. Щось схоже використовується і у визначенні предиката в програмуванні. Це не дивно, адже математика стала свого роду сировиною для цієї науки.

Теоретична частина

Існує багато дедуктивних систем для видів суджень і логіки першого порядку, які є як звуковими (всі доказові твердження вірні у всіх моделях), так і повними (твердження, які вірні для всіх моделей, є доказуемыми). Хоча відношення логічного наслідку розв’язується лише наполовину, в автоматизованій теореми, доведеної у логіці першого порядку, досягнутий значний прогрес. Логіка першого порядку також задовольняє кільком металогическим теорем, які роблять її придатною для аналізу в теорії доказів, такий як теорема Левенхайма-Сколема і теорема про компактності.

Логіка першого порядку є стандартом для формалізації математики в аксіомах і вивчається в основи математики. Арифметика Пеано і теорія множин Цермело-Френкеля є аксиоматизациями теорії чисел і теорії множин, відповідно, є частиною логіки першого порядку. Однак теорія першого порядку не має можливості однозначно описувати структуру з нескінченною областю, наприклад натуральні числа. Системи аксіом, які повністю описують ці дві структури (тобто системи категоріальною аксіоми), можуть бути отримані в більш сильних формах логіки, таких як логіка другого порядку.

Основи логіки першого порядку були розроблені незалежно Готлобом Фреге і Чарльзом Сандерсом Пірсом.