Логіка - Карамишева Н.В. - Рівносильні формули логіки предикатів

Після квантифікації, тобто використання квантора загальності або існування до вільної змінної одномісного або /і-місного предиката, можна отримати різні формули. Наприклад, V* VyP(x, у); /у VxP(x, у); Зх VyP(x, у); /х ЗхР(х, у); Зх 3yP(xt у).

Формули, які містять однакові квантори, називають рівносильними, або еквівалентними. Вони мають такий вид:

Vx VyP(x, у) = VxP(xf у) (формули виду Vx УуР(х, у) і виду /у УхР(х, у) істинні тоді й лише тоді, коли Р(х, у) - тотожно істинний предикат);

Зх 3yP(xt у) = Зу ЗхР(х, у) (формули виду Зх 3yP(xt у) і виду Зу 3xP(xt у) істинні лише тоді, коли Р(х, у) є тотожно-істинним предикатом).

Заперечення висловлювань з кванторами

Заперечення в символічній логіці - логічна операція, виражена за допомогою сполучника "неправильно, що". Наприклад, запереченням висловлювання "Усі студенти вивчають математику" буде висловлювання "Неправильно, що всі студенти вивчають математику".

Заперечення висловлювання з кванторами загальності формально виражається: -" VxP(x), з квантором існування так: - 3xF(x).

Заперечне висловлювання з квантором загальності -" VxP(x) має те саме значення істинності, що й висловлювання з квантором існування, зі запереченням висловлювання Зх -* F(x), а заперечення висловлювання з квантором існування -" 3xF(x) має те саме значення істинності, що й висловлювання з квантором загальності зі запереченням висловлювання Vx -" Р(х).

На підставі визначення взаємозалежності кванторів загальності й існування зі запереченнями встановлюють рівносильність (еквівалентність) таких формул: VxP(x) = Зх -" Р(х); -> 3xF(x) = Vx - F(x).

Відношення слідування в логіці предикатів

Між формулами F і Q логіки предикатів існує відношення логічного слідування (F -> Q) тоді й лише тоді, коли в процесі визначення значень вільних змінних, що входять до структури формули "якщо F - істинне, то Q - істинне", між формулами виду Fr F2,... Fn і формулою виду Q існує відношення логічного слідування тоді й тільки тоді, коли при визначенні значень вільних змінних усіх формул і якщо Fx, F2,... Fn істинні, то Q - істинне.

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

Законом логіки предикатів називають формулу (формальний вираз), що за будь-якого підставлення значень вільних змінних набуває значення "істина". Така формула - загальнозначуща (тотожно-істинна): Vx(P(x) V v - Р(х)).

Закони логіки предикатів можна вивести із законів логіки висловлювань через підстановку замість пропозиційних змінних предикатів. Візьмемо, наприклад, перший закон контра-позиції логіки висловлювань (А -> В) -> (-> В -" -" А). Замість змінної А підставляємо предикат Р(х), а замість змінної В - предикат Q(x). Отримуємо формулу ((Р(х) ->Q(x)) ->((-" Q(x) -" -> -і Р (х))9 яка є загальнозначущою формулою, тобто законом логіки предикатів.

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

У логіці предикатів аналітична таблиця - скінченна чи безмежна послідовність n-рядків, кожен з яких є скінченне число стовпчиків (рядків формул), котрі будують із попередніх за правилами редукції. Стовпчик, що входить у рядок з номером аналітичної таблиці, називають замкненим, якщо він містить формулу виду F та її заперечення. Аналітична таблиця називається замкненою, якщо всі її стовпчики замкнені.

Правила побудови аналітичної таблиці:

де F(t) - результат заміни всіх вільних змінних х у F на будь-який замкнений терм t.

де Р(Л) - результат заміни всіх вільних входжень х у Р на предметну константу к, яка ще не була в таблиці.

де Р(£) - результат заміни всіх вільних входжень х у Р на предметну константу яка не була в таблиці.

де F(t) - результат заміни всіх вільних входжень х у F на будь-який замкнений терм і.

Числення предикатів (система виведення формул виду Q із формул виду F за принципом логічного слідування) - це система символів і правил логічного виведення з аксіом довільних формул з метою їх доведення на істинність; здійснення логічних операцій над одномісними та багатомісними предикатами. Розрізняють два види числення предикатів: натуральне й аксіоматичне.

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

1. Правило усунення імплікації (УІ) (правило модус понненс):

(чит.: із двох формул виду Р, Р -> ф можна отримати формулу виду (5).

2. Правило введення квантора загальності (ВУ):

(чит.: якщо х не є вільною в Р, то з формули виду Р -* ф(я) можна вивести формулу виду Р -ьУуЖу))-

3. Правило усунення квантора загальності (УУ):

(чит.: із формули виду VF(x) -> Q(y) можна вивести формулу виду F(x) -" Q(y)).

4. Правило введення квантора існування (ВЗ):

(чит.: якщо х не є вільною в Q, то з формули виду F(x) -" Q можна вивести формулу виду 3yF(y) -► Q)"

5. Правило усунення квантора існування (УЗ):

(чит.: із формули виду 3F(x) -> Q можна вивести формулу виду F(x) -> Q).

Аксіоматичне числення логіки предикатів означає побудову системи доведення теорем на підставі аксіом за правилами виведення.

Аксіоми логіки предикатів (ЛП) доповнюють аксіоми логіки висловлювань (ЛВ) (див. 4.2.1), тобто до них додають нові аксіоми:

На підставі аксіом виводять (доводять) формули, які є теоремами на підставі таких правил введення кванторів загальності V й існування 3:

Формалізація простих атрибутивних (категоричних) висловлювань та простого категоричного силогізму в логіці предикатів (ЛП).

Атрибутивні (категоричні) висловлювання та простий категоричний силогізм, які досліджують у традиційній логіці (див. 3.4.2; 3.4.3), формалізуються мовою логіки предикатів.

І. Формалізація чотирьох видів простих атрибутивних (категоричних) висловлювань мовою ЛП.

1. Загальностверджувальне висловлювання (А), формальний вираз якого в традиційній логіці "всі 5 є Р" - висловлювання, в якому стверджується притаманність властивості Р усім предметам певного класу, У логіці предикатів 5 і Р визначають як пропозиційні змінні, замість котрих можна підставити аргументи і надати висловлюванню значення істинності або хибності. Наприклад: "Усі трикутники є геометричними фігурами" (/), "Усі власні імена пишуть з великої літери" (і); "Усі птахи літають" (х), а саме висловлювання - як висловлювання, що виражає одномісний предикат.

Формальний вираз загальностверджувального висловлювання мовою логіки предикатів: Ух(Р(х) ->(?(*))" Дв V - символ, що позначає квантор загальності, Р, (? - властивість, х про-позиційна змінна (чит.: для всіх х, якщо притаманна властивість Р, то х притаманна властивість <?).

2. Загальнозаперечне висловлювання (Е), формальний вираз якого в традиційній логіці "жодне 5 не є Р" - висловлювання, в якому заперечується властивість Р у всіх предметів певного класу: "Жодна собака не є кішкою" (/), "Жодна жива істота не може жити довго без їжі" (і); "Жодний студент не вчиться на відмінно" (х).

Формальний вираз загальнозаперечного висловлювання мовою логіки предикатів: Ух(Р(х) -> - Я(х)) (чит.: для всіх х, якщо х притаманна властивість Р, то х не притаманна властивість в).

3. Частковостверджувальне висловлювання (/), формальний вираз якого в традиційній логіці "декотрі 5 є Р" - висловлювання, в якому властивість Р приписується певним предметам певного класу (підкласу класу А). Наприклад: "Декотрі люди є спортсменами" (і); "Декотрі люди є довгожителями" (і).

Формальний вираз частковостверджувального висловлювання мовою логіки предикатів Зх(Р(х) а Я(х)) (чит.: існує такий предмет х, якому притаманна властивість Р і притаманна властивість (і), де 3 - символ, що позначає квантор існування.

4. Частковозаперечне висловлювання (О), формальний вираз якого в традиційній логіці "декотрі 5 не є Р" - висловлювання, в якому певна властивість Р заперечується у певній кількості предметів певного класу (підкласу класу А): "Деякі логічні теорії не є двозначними за значенням істинності" (і); "Деякі люди не грають в шахи" (і).

Формальний вираз частковозаперечного висловлювання мовою логіки предикатів ЗхР(х) Л -"Я{х)) (чит.: існує такий предмет х, якому притаманна властивість Р і не притаманна властивість О).

За допомогою правил перетворення кванторів, усі види атрибутивних (категоричних) висловлювань можна зобразити так:

1. Загальностверджувальне висловлювання (А):

II. Формалізація простого категоричного силогізму мовою логіки предикатів. Першу формалізацію простого категоричного силогізму здійснив Я. Лукасевич.

Формалізація простого категоричного силогізму означає його формальне зображення мовою логіки предикатів з метою точнішого виведення висновку із засновків. Подаємо виведення висновку із засновків за правилами першої фігури та правильного модусу AAA (модус Barbara). У традиційній логіці він має вигляд:

Мовою логіки предикатів:

(Vx(M(x) -> Р(х)) а Vx(Q(x) -" М(х))) -> Vx(Q(x)) -*Р(х)) (чит.: якщо правильно, що для кожного х із М(х) випливає Р(х), і якщо правильно, що для кожного х із Q(x) випливає М(х), то для кожного х правильно, що з Q(x) випливає Р(х).Формалізація висловлювань мовою логіки предикатів та інтерпретація формул логіки предикатів.

Формалізація висловлювань із певним змістом означає їх перетворення на мову логіки предикатів, а інтерпретація логіки предикатів - встановлення сфери дії кванторних виразів виду УхР(х), ЗхР(х), УхР(х, у), УхР{х, у, г)у у контексті міркувань про певну множину предметів, яким притаманна властивість Р і встановлення певного виду відношень між предметами, що належать до цієї множини.

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

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

Послідовність здійснення названих логічних операцій:

I. Визначають предметну сферу міркувань, у межах якої формалізують висловлювання й інтерпретують кванторні формули.

II. Задають точнішу сферу міркувань - клас (множина) М, у межах якої кванторна формула визначає властивості та відношення.

Наприклад:

- у математиці: множина усіх натуральних чисел (арифметика); множина усіх множин (теорія множин); множина усіх геометричних фігур (геометрія) і под.;

- у логіці: множина усіх логічних законів; множина усіх висловлювань; множина усіх формально-логічних систем тощо;

- у соціальному світі: множина усіх людей; множина усіх політиків, усіх юристів, усіх науковців, усіх студентів та ін.;

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

III. У точно визначеній множині М суто абстрактно задають властивості, притаманні предметам, що належать до певної множини та відношення (бінарні, тернарні та ін.) між предметами, які належать до цієї множини М.

IV. Надають значення істинності висловлювань, що виражають властивості або відношення.

Покажемо операції формалізації висловлювань мовою логіки предикатів й інтерпретації формул логіки предикатів. У символічній логіці - множина усіх логічних законів.

1. Кожна тотожно-істинна формула є логічним законом у межах певної формальної системи. Це означає, що кожній тотожно-істинній формулі притаманна властивість "бути логічним законом". Для формалізації цього висловлювання визначаємо: слово "кожний", що природною мовою виражає квантор загальності (V), "логічний закон" - одномісний предикат Р(х), "тотожно-істинна формула" (одномісний предикат Я(х) "певна формальна система" (сфера дії квантора загальності (чит.: кожна формула, що має властивість "бути тотожно-істинною формулою", має властивість "бути логічним законом" у межах певної формальної системи). Формула: Ух(Р(х) -> С?(дг)£)).

2. Створюємо формулу логіки предикатів: Зх(Р(х) л -і (?(*). Інтерпретуємо її в сфері символічної логіки. "Існує вираз х, який має властивість "бути формулою" і не має властивості "бути законом символічної логіки".

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

1. Створюємо висловлювання, в якому загальною сферою дії квантора із предметними змінними х, у, г, су буде сфера наукового знання, а саме - гіпотеза й теорія. "У кожній науці є гіпотези, які після їх перевірки на істинність не стають теоріями".

"У кожній (квантор загальності V) науці (одномісний предикат Р(х)) є (квантор існування 3) гіпотези (одномісний предикат Жу)> які після їх перевірки на істинність (Єг) не стають (заперечення слідування) теоріями (одномісний предикат Н(д)". Формула: УхР(х) -> ((ЗуЯ(у) -> (вг -> -" #(?))).

2. Будуємо висловлювання, в якому загальною сферою дії квантора існування всіх предметних змінних х, у, г, с, д буде множина людей, серед яких є підмножина студентів, котрим притаманні певні властивості: "Існують люди, які є студентами, і серед них є такі, що вчаться на відмінно і займаються науковою роботою".

"Існують (3) люди (Р(х)), які є (3) студентами ((?(*/)) і серед них є (3) такі {Щг)), що вчаться на відмінно (У(с)) і займаються науковою роботою (#д)). Формула: ЗхР(х) -> (((Зу()(у) -> -> ((Згй(г) -> (У(с) Л На))).

На підставі логічного аналізу певного висловлювання та визначення його структури можна здійснити символічний запис цього висловлювання мовою традиційної логіки та мовою класичної символічної логіки (логіки висловлювань і логіки предикатів). Наприклад:

І. "Усі люди, що працюють, платять податки".

1. Мовою традиційної логіки: "Усі (квантор загальності виражений природною мовою) люди, що працюють (суб'єкта), платять податки (властивість Р)" (у цьому висловлюванні зв'язка "є" виражена неявно, але вона мислиться). Усі 5 є Р.

2. Мовою логіки висловлювань. У логіці висловлювань абстрагуються від суб'єктно-предикатної структури висловлювання, і це висловлювання визначають як просте. Позначається символом А.

3. Мовою логіки предикатів (береться до уваги внутрішня структура висловлювання): "Усі (квантор загальності виражений штучною мовою V) люди, що працюють (підмножина індивідів, що належать до множини людей, яким притаманна властивість працювати Р(х) оплачують податки (властивість "платити податки" <?(дг) (чит.: для усіх індивідів, котрим притаманна властивість "працювати", притаманна властивість "платити податки"). Формула: УхР(х) -> Я(х)).

II. "Деякі мови є важкими для вивчення".

1. Мовою традиційної логіки: "Деякі (квантор існування "деякі" виражено природною мовою) мови (S) є (зв'язка) важкими для вивчення (предикат Р)". Деякі S є Р.

2. Мовою логіки висловлювання. Просте висловлювання А.

3. Мовою логіки предикатів: "Деякі (квантор існування виражено штучною мовою 3) мови (Р(х)) є (3) важкими для вивчення (Q(x)". ЗхР(х) -" Q(x).

Цьому прикладу може відповідати і складніший символічний запис відповідно до точнішого виразу. Існують (3) мови (Р(х)), яким притаманна властивість "бути знаковою системою" (Q(y)) і властивість "бути важкими для вивчення" (Н(г)). Формула: ЗхР(х) -> ((Q(y) (H(z)).