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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

КРЕМЕНЧУЦЬКИЙ ДЕРЖАВНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

ІМЕНІ МИХАЙЛА ОСТРОГРАДСЬКОГО

ФАКУЛЬТЕТ ЕЛЕКТРОНІКИ ТА КОМП’ЮТЕРНОЇ ІНЖЕНЕРІЇ

КАФЕДРА ІНФОРМАТИКИ І ВИЩОЇ МАТЕМАТИКИ

КУРСОВА РОБОТА

З ДИСЦИПЛІНИ МАТЕМАТИЧНА ЛОГІКА ТА ТЕОРІЯ АЛГОРИТМІВ

ТЕМА ПОБУДОВА ВИВОДІВ В АКСІОМАТИЧНІЙ СИСТЕМІ З ПРАВИЛОМ ВИВОДУ м.р.

ЗАВІДУВАЧ КАФЕДРИ                                         Ляшенко В.П.

КЕРІВНИК РОБОТИ                                                Кобильська О.Б.

ВИКОНАЛА                                                               Лазоренко Олексадра П.

КРЕМЕНЧУК 2009

РЕФЕРАТ

Пояснювальна записка до курсового проекту: 28 с, 6 джерел.

Об'єкт дослідження – Побудова виводів в аксіоматичній системі з правилом виводу М.Р.

Мета роботи – є побудова та вивід формул із в аксіоматичних систем. Довести їх властивість та вихідність.

Метод дослідження – Застосування різних методів побудови різницевих схем.

РЕФЕРАТ             

Пояснительная записка к курсовому проекту: 28 с., 6 источников литературы.

Объект исследования - Построение выводов в аксиоматической системе с правилом вывода М.Р.

Цель работы - есть построение и вывод формул из у аксиоматических  систем. Довести их свойство и вихиднисть.

Метод исследования - Применение разных методов построения разностных схем.

ABSTRACT
Explanatory note to the course project: 28 с. 6 sources of literature.
A research object is Construction of conclusions in the axiomatic system with an inference of M.R rule.

Purpose of work - there is a construction and conclusion of formulas from at the axiomatic systems. To lead to their property and vikhidnist'.

A research method is Application of different methods of construction of riznicevikh charts.

ЗМІСТ

Вступ……………………………………………………………………………………...5

1. Аксіоматична система та логіка висловів.……………………….............………...6

1.1. Аксіоматизація логіки.………………………………………....………………….6

1.2 Аксіоми і правила виведення числення висловів………...………........................6

1.3.Аксіоматичні системи : висновки і докази. ………………………........................7

2 Логіка предикатів…………..………………………...………....................................9

2.1 Відмітні риси логіки предикатів……………………………....…………………..9

2.2 Закони логіки висловлень і логіки предикатів………………...…......................11

2.3. Основні поняття предикатів……………………………………………………..18

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

3 Постановка задачі…………………………………………………………………...26

3.1 Розв’язання задачі………………………………………………………………....26

Висновки……………………………………………………………………………….27

Список використаної літератури……………………………….................................28

ВСТУП

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

1. Аксіоматична система та логіка висловів.

1.1. Аксіоматизація логіки.

Будь-яка математична система грунтується на безлічі аксіом, тобто виразів, що вважаються загальнозначущими і безлічі правил виводу, тобто механізмів, що дозволяють будувати нові загальнозначущі вирази. Такі вирази називають теоремами. Доказом теорем називається послідовність з аксіом, правил виводу і вже доведених теорем, що дозволяють отримати нову теорему. Важливо, що логічні правила, які використовуються для виведення нових теорем з аксіом і раніше доведених в даній системі теорем, не породжували як «теореми» помилкові вислови.

Розглянемо наочну область, що включає всі можливі вислови. Визначимо безліч аксіом, що визначають цю область. Такими питаннями займається область матлогики, звана численням висловів.

Необхідно запропонувати такі формалізми, які б визначали всі процедури і не вимагали додатково ніяких посилань на смисловий зміст. У наведених вище прикладах ми вирішували задачу виводу виходячи з того, що відомі поняття і або, якщо те і ін., які використовувалися при виводі. Так, якщо аксіома визначена як А&в, то, виходячи з сенсу цієї операції, виводилася істинність висловів А і Ст. В численні висловів операція І визначається явно у вигляді двох аксіом: (А&в)-»А, (А&в)-»В. Це дозволяє організувати вивід, не удаючись до розгляду сенсу фраз.

Силлогизми - правильні схеми міркувань, в яких висновок вірний через іменну форму міркування, а не зміст.

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

Гіпотези є переліком висловів або посилок. Висновок правильний, якщо всякий раз, коли Нь Н2... Нп істинні, то істинно і С. Правільность висновки можна перевірити, побудувавши таблицю істинності і показати, що всякий раз, коли гіпотези істинні, істинно і висновок.

1.2 Аксіоми і правила виведення числення висловів

Класичне числення висловів задається наступними аксіомами і правилами виводу:

Аксіоми:     1. А - (У - А)

2.(A - (B - C)) - ((A- B) - (A

3.A л B - A

4.A л B - B

5.A - (B - A л B)

6.A - A v B

7.B - A v B

8.(A - C) - ((B - C) -- (A v B -с)),

9.(A - B) - ((A - -b)--A),

10.A   A.

Правило виводу: A-A - B (modus ponens, MP)

1.3.Аксіоматичні системи : висновки і докази.

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

Гіпотенуза прямокутного трикутника довше за будь-яке з катетів

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

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

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

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

2 Логіка предикатів

2.1. Відмітні риси логіки предикатів.

Символічну логіку поділяють на логіку висловлень і логіку предикатів. Логіка предикатів ґрунтуєтнся на логіці висловлень.

Якщо логіка висловлень ігнорує структуру простих висловлень, вивчаючи тільки правильність зв'язків між ними, то логіка предикатів зосереджує свою увагу саме на структурі висловлень

У логіці предикатів розрізняють логіку предикатів першого ступеня (порядку) і логіку предикатів більш високая ступенів (порядків).

З часів Арістотеля (384— 322 до н. е.) у логіці існує поняття «судження». Давньогрецький філософ означав його як думку, що стверджує чи заперечує що-небудь про що-небудь.

Структурно судження складається з суб'єкта, предиката й дієслова-зв'язки. Так, у судженні «Хома Брут є київський філософ» ім'я «Хома Брут» є суб'єктом (5), вираз «київський філософ» — предикатом (Р), а дієслово «є» - І зв'язкою.

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

«Греки завдали поразки персам при Платеях»; «Перси були розбиті греками при Платеях».

Граматична відмінність між цими реченнями полягає І зміні активної форми («греки завдали») на пасивну («роя биті греками»), тобто в першому реченні суб'єктом є «греки», а в другому — «перси».

У живій мові часто буває так: те, що раніше виступало у ролі суб'єкта (підмета), відносно легко може стати предикатом (присудком), і навпаки. Але в такому разі відмінність має лінгвістичний характер, а не строго логічний. Незважаючи на це, дані речення мають одне й те саме значення істинності. У зв'язку з цим Фреге вважав, що словесний порядок, який спирається на граматичне розмежування суб'єкта й предиката, не має значення для логіки.

Необхідність переосмислити сутність іменування в логіці була зумовлена введенням Фреге понять «функція» і «аргумент». На його думку, номінативний вираз («ім'я») можна поділити не тільки на суб'єкт й предикат, а й на функцію і аргумент, що більше відповідає логіці, яка орієнтується на математику, а не на психологію чи лінгвістику. Вчений неодноразово наголошував, що поняття «функція» і «аргумент» лише маркірують структурні особливості певного виразу, не зачіпаючи його смислового змісту.

Запропонований фрегівський погляд на процес номінації (іменування) був корисним для логіки тим, що давав змогу користуватися під час логічного аналізу теоретико-множинними уявленнями (наприклад: функція як відображення однієї множини в іншій множині), в результаті чого предикат стали розглядати як пропозиційну функцію форми F(x).

Вчення про пропозиційні функції та квантори є найважливішим внеском Фреге в сучасну логіку.

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

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

Відомо, що вираз форми F(x) (де F — властивість певного індивіда х) являє собою таку елементарну пропозиційну функцію, з якої одержують елементарне (просте) висловлення, замінивши змінну позначеннями конкретних індивідів. Наприклад: F(x) -> «х зелений» -» «трава зелена».

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

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

Хоч ідея квантифікації належить Фреге, автором термінів «квантор» і «квантифікація» є американський вчений Ч. С Пірс (1839- 1914).

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

Здавалося б, з поняттям «предикат» у логіці покінчено раз і назавжди. Проте цей термін залишився: ним користуються, коли треба вказати на можливість логічного  аналізу структури висловлень. У такому випадку термін  «предикат» набув метафоричного значення. Так, у Д. Гіль-J Берта, американського математика й логіка С. Кліні (1909— 1994) цей термін вживається для позначення пропозиційної функції.