Побудова виводiи в аксiоматичнiй системi З правилом виводу М.Р.

Числення предикатів.

Логіка висловів дозволяє формалізувати лише малу частину безлічі міркувань. Вислови, що описують деякі властивості об'єктів, або стосунки між об'єктами виходять за рамки логіки висловів. Наприклад, ми не зможемо судити про логічну правильність такого простого міркування: «Кожне натуральне число є коренем деякого квадратного рівняння. Число 5 -натуральноє. Отже, 5 є коренем деякого квадратного рівняння».

Логіка предикатів починається з аналізу будови висловів, які виражають той факт, що об'єкти володіють деякими властивостями, або знаходяться між собою в деяких стосунках. Поняття «властивості» і поняття «стосунки» розглядаються як окремий випадок загального поняття «предиката». Об'єкти, про які мовиться у вислові, називаються термами або наочними константами.

Наочні константи, подібно до констант в математиці, визначають значення, які можуть бути приписані у висловах наочним змінним. При цьому кожною змінною відповідає своя безліч наочних констант. Наприклад, якщо мова йде про студентській групі, то змінній ПРІЗВИЩЕ відповідає безліч констант - конкретних прізвищ студентів групи, зміною ОЦЕНКА - безліч констант { отл., хор., удовл., неуд.}, змінній ВУЗ - безліч імен Вузів. Над змінними і константами визначаються функції так само, як і в математиці, тобто як однозначне відображення декартове твори Х1хх2х ...Хгп =>У, де XI і У - імена наочних змінних.

Приклад предиката: ПРІЗВИЩЕ = «Петров». Тут ПРІЗВИЩЕ - змінна, «Петров» - константа.

Числення висловлень, що розглядалось у попереднiх роздiлах, як алгебра висловлень i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак воно є занадто бiдним для опису та аналiзу найпростiших логiчних мiркувань науки i практики.

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

Для того, щоб побудувати систему правил, яка дозволяла б проводити логiчнi мiркування для виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, пропонується формальна теорiя, що дiстала назву числення предикатiв.

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

Наприклад, в iстинному висловленнi «5 є просте число» пiдмет «5» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.

У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.

Наприклад, замiнюючи у наведеному вище висловленнi 5 на 2, 4, 8 або 14, матимемо вiдповiдно такi висловлення: «2 є просте число», «4 є просте число», «8 є просте число», «14 є просте число», з яких друге є iстинним, а решта - хибними висловленнями.

Таким чином, можна розглянути вираз «x є просте число», який не є висловленням, а є так званою пропозицiйною (висловлювальною) формою. Тобто формою (або формуляром), пiсля пiдстановки в яку замiсть параметра (змiнної) x об’єктiв (значень) з певної множини M, дiстаємо висловлення.

Аналогiчно можна трактувати, наприклад, пропозицiйнi форми «a є українцем», «b i c є однокурсники», «c важче d», або «точка x лежить мiж точками y i z». У першi двi з них можна пiдставляти замiсть параметрiв a, b i c прiзвища конкретних людей. У третю замiсть c i d назви будь-яких об’єктiв (предметiв), якi мають вагу. Для четвертої множиною M значень змiнних x, y i z є множина точок певної прямої.

Перша з цих пропозицiйних форм задає, як i в наведенiй ранiше формi, певну властивiсть для об’єкта a. Iншi три форми описують деякi вiдношення мiж вiдповiдними об’єктами.

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

Предикат називається «-местним ( «= 1,2 ... ), якщо відповідна функція є функція від «-аргументов. Вислів - не що інше, як предикат без аргументу, або предикат з нульовим числом місць.

Приклади.

1.              Бінарні предикати: х,у,2є До, Р(х,у)= (х>у), Я(х, у)= (х = у2),
(2(х, у)= «х ділить у»;

2.              Тримісні: Р(х,у,2)= «число х є НОД (найбільший загальний

дільник) чисел у і 2», Я(х,у,2)= (2 = х + у).

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

Отже, такi фундаментальнi математичнi поняття як вiдповiднiсть (зокрема, функцiя), вiдношення, висловлення можна загального поняття предиката.

2.4. Числення предикатів. Аксіом і правила виводу методом М.Р.

Числення предикатів.

Логіка висловів дозволяє формалізувати лише малу частину безлічі міркувань. Вислови, що описують деякі властивості об'єктів, або стосунки між об'єктами виходять за рамки логіки висловів. Наприклад, ми не зможемо судити про логічну правильність такого простого міркування: «Кожне натуральне число є коренем деякого квадратного рівняння. Число 5 -натуральне Отже, 5 є коренем деякого квадратного рівняння».

Логіка предикатів починається з аналізу будови висловів, які виражають той факт, що об'єкти володіють деякими властивостями, або знаходяться між собою в деяких стосунках. Поняття «властивості» і поняття «стосунки» розглядаються як окремий випадок загального поняття «предиката». Об'єкти, про які мовиться у вислові, називаються термами або наочними константами.

Наочні константи, подібно до констант в математиці, визначають значення, які можуть бути приписані у висловах наочним змінним. При цьому кожною змінною відповідає своя безліч наочних констант. Наприклад, якщо мова йде про студентській групі, то змінній ПРІЗВИЩЕ відповідає безліч констант - конкретних прізвищ студентів групи, зміною ОЦЕНКА - безліч констант { отл., хор., удовл., неуд.}, змінній ВУЗ - безліч імен Вузів. Над змінними і константами визначаються функції так само, як і в математиці, тобто як однозначне відображення декартове твори Х1хх2х ...Хгп =>У, де XI і У - імена наочних змінних.

Приклад предиката: ПРІЗВИЩЕ = «Петров». Тут ПРІЗВИЩЕ - змінна, «Петров» - константа.

Числення висловлень, що розглядалось у попереднiх роздiлах, як алгебра висловлень i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак воно є занадто бiдним для опису та аналiзу найпростiших логiчних мiркувань науки i практики.

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

Для того, щоб побудувати систему правил, яка дозволяла б проводити логiчнi мiркування для виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, пропонується формальна теорiя, що дiстала назву числення предикатiв.

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

Наприклад, в iстинному висловленнi «5 є просте число» пiдмет «5» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.

У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.

Наприклад, замiнюючи у наведеному вище висловленнi 5 на 2, 4, 8 або 14, матимемо вiдповiдно такi висловлення: «2 є просте число», «4 є просте число», «8 є просте число», «14 є просте число», з яких друге є iстинним, а решта - хибними висловленнями.

Таким чином, можна розглянути вираз «x є просте число», який не є висловленням, а є так званою пропозицiйною (висловлювальною) формою. Тобто формою (або формуляром), пiсля пiдстановки в яку замiсть параметра (змiнної) x об’єктiв (значень) з певної множини M, дiстаємо висловлення.

Аналогiчно можна трактувати, наприклад, пропозицiйнi форми «a є українцем», «b i c є однокурсники», «c важче d», або «точка x лежить мiж точками y i z». У першi двi з них можна пiдставляти замiсть параметрiв a, b i c прiзвища конкретних людей. У третю замiсть c i d назви будь-яких об’єктiв (предметiв), якi мають вагу. Для четвертої множиною M значень змiнних x, y i z є множина точок певної прямої.

Перша з цих пропозицiйних форм задає, як i в наведенiй ранiше формi, певну властивiсть для об’єкта a. Iншi три форми описують деякi вiдношення мiж вiдповiдними об’єктами.

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

Предикат називається «-местним ( «= 1,2 ... ), якщо відповідна функція є функція від «-аргументов. Вислів - не що інше, як предикат без аргументу, або предикат з нульовим числом місць.

Приклади.

1.              Бінарні предикати: х,у,2є До, Р(х,у)= (х>у), Я(х, у)= (х = у2),
(2(х, у)= «х ділить у»;

2.              Тримісні: Р(х,у,2)= «число х є НОД (найбільший загальний

дільник) чисел у і 2», Я(х,у,2)= (2 = х + у).

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

Отже, такi фундаментальнi математичнi поняття як вiдповiднiсть (зокрема, функцiя), вiдношення, висловлення можна загального поняття предиката.

            Числення предикатів. Аксіом і правила виводу  методом М.Р

Числення предикатів сигнатури   задається наступними схемами аксіом і правилами виводу.

Аксіоми:             

A1. аксіоми числення висловів, A2. VXA[a/x] - A[a/t], A3. A[a/t] - 3xa[a/x].

Схему аксіом A1 акуратніше ми розуміємо таким чином. Якщо A(Pi...,Pn) - аксіома числення висловів, то формула A[Pi/ci..., Pn/cn] є аксіома числення предикатів для будь-яких формул Ci..., Cn сигнатури Е.

У аксіомах A2 і A3 A - будь-яка формула сигнатури Е і t - будь-який терм (змінна x не входить в A).

Правила виводу:

R1. A-aя - В (modus ponens)

R2.       A - B

A - //xb[a/x]

R3.       B - A

3xb[a/x] - A

У правилах R2 і R3 змінна а не входить в A (і x не входить у В). Правила R2 і R3 називаються правилами Бернайса.

Визначення. Виводом в численні предикатів називається кінцева послідовність формул, кожна з яких або є аксіомою, або виходить з попередніх формул по одному з правил виведення R1 - R3.

Приклад.

//xa[a/x] - A              (A2)

yxa[a/x] - VYA[a/y]   (r2)

Визначення. Формула A називається такою, що виводиться в численні предикатів або теоремою числення предикатів (позначення Ь A), якщо існує вивід, в якому остання формула є A.

Приклад.   Ь //xa[a/x] - //ya[a/y] для будь-якої формули A. 4.2   Виводимість в теорії

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

Визначення. Виводом в теорії T називається кінцева послідовність формул, кожна з яких або належить безлічі T, або є логічною аксіомою виду A1 - A3, або виходить з попередніх формул по одному з правил виведення R1 - R3.

3 Розрахункова частина

3.1 Постановка задачі

1.      Довести, що наступні формули є теоремами в формалізованому численні предикатів.

1)

2)

3.2 Розвязання задачі

1)

Якщо всі значення Х істинні, то і всі значення У істинні

1. –гіпотеза наслідок з 4 –аксіоми

  2.Вирази рівносильні:

Маємо що вираз рівний самому собі,початкова рівність істинна

3. Використовуючи закон заміни зв’язної змінної, змінюємо змінну У в виразі 3. на Х маємо: (Маємо істинний вираз).

Введення нового означення зв’язної змінної не змінює значення формули логіки

Предикат якщо використовується наступна умова: Жодна вільна змінна в любій частині формули не повинна після перейменування виявиться зв’язною.