Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів icon

Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів




НазваТема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів
Дата30.09.2012
Розмір445 b.
ТипЗакон


Тема № 2. МАТЕМАТИЧНІ ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ. 2.3 Елементи математичної логіки, теорії предикатів.


Історична ремарка

  • Логіка – наука про закони мислення. Загальні принципи логічних міркувань розвинув Платон ( 427-347р. до н.е.).

  • Математична логіка - наука про правильні математичні міркування, про математичне мислення. Уперше правила міркувань систематизував грецький філософ Аристотель ( 384-322 р. до н.е.) – виклав закони логічного виведення, запропонував першу формально-аксіоматичну систему логіки -силогістику.

  • Лише наприкінці XVII століття німецький математик Гольфрід Вільгельм Лейбніц (1646 -1716) запропонував математизувати формальні міркування Аристотеля, уводячи символьне позначення для основних понять і використовуючи особливі правила, близькі до обчислень. По-суті, розвинув ідею створення універсального логічного числення.

  • Подальші успіхи логіки пов'язані з іменами філософів, логіків, математиків 19 та 20 ст.

  • Однак як наука математична логіка склалася лише в середині ХIX століття, коли англієць Джордж Буль (1815-1864 р.) увів логічні зв'язування і числення висловлень. Логіко-математичні мови і теорія їх смислу розвинуті в роботах Фрідріха Людвіга Готлоба Фреге (1848-1925), який ввів поняття предикату та кванторів.

  •  До найвизначніших досягнень математичної логіки треба віднести розробку та дослідження формальних моделей алгоритму та алгоритмічно обчислюваної функції.



Системи математичних логік

  • системи математичних логік: класична, конструктивна, модальна, нечітка, комбінаторна й ін.

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

  • Основна ідея математичної логіки – формалізація знань і міркувань. Відомо, що найбільш легко формалізовані знання – математичні. Таким чином, математична логіка, по суті, – наука про математику, або метаматематика.



Побудова формальної теорії

  • Загальновідомо, що формальна теорія ( синонім – числення) визначена, якщо:

  • Задано алфавіт (множина символів, що використовуються для побудови формул).

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

  • Виділено множину формул, називаних аксіомами. Це – стартові моменти у висновках.

  • Задано множину правил висновку, що дозволяють з деякої формули (або множини формул) одержувати нову формулу.



Логіка висловлень і логіка предикатів

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

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



Проблема вирішення

  • Алгебра і числення висловлень представляють досить докладно розроблені розділи дискретної математики .

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

  • Спосіб 1. Складання таблиць істинності.

  • Спосіб 2. Застосування методу міркувань від супротивного.

  • Спосіб 3. Приведення формул до нормальних форм.

  • На жаль проблема вирішення в логіці предикатів у загальному випадку не розв'язана. Вона може бути вирішена, якщо обмежитися формулами, що містять тільки одномісні предикати.



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

  • Поняття ``предикат'' узагальненне поняття в логіці. Неформально говорячи, предикат – це висловлення, у яке можна підставляти аргументи. Якщо аргумент один – то предикат виражає властивість аргументу, якщо більше – те відношення між аргументами.

  • Приклад предикатів. Візьмемо висловлення: ``Сократ - людина'', ``Платон - людина''. Обоє ці висловлення виражають властивість ``бути людиною''. Таким чином, ми можемо розглядати предикат ``бути людиною'' і говорити, що він виконується для Сократа і Платона.

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



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

  • Визначення 2.3.1

  • Нехай М – не порожня множина. Тоді n- місним предикатом, заданим на М, називається математичний вираз, що містить n змінних і звертається у висловлення при заміні цих змінних елементами множини М.

  • Будемо вважати, що висловлення – нульмісний предикат, тобто предикат, у якому немає змінних для підстановки.

  • Приклади тримісних предикатів, заданих на множині натуральних чисел: число z лежить між «x і y», «x плюс y дорівнює z», «|x-y| z».



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

  • На сукупності всіх предикатів, заданих на множині М, додаються знайомі по логіці висловлень операції кон’юнкція, диз'юнкція, заперечення, імплікація і эквіваленція. Ці операції вводяться досить очевидним чином. Наведемо як приклад визначення кон’юнкції предикатів.

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

  • Легко за аналогією привести визначення й інших згаданих вище операцій.



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

  • У логіку предикатів вводяться і дві нові операції. Називаються вони квантором загальності і квантором існування. Ці операції розглянемо спочатку на прикладах. Нехай дане вираження «існує х такий, що x+y=10».

  • Якщо позначити предикат «x+y=10» через S(x,y) (а це предикат двомісний), то P(y) можна записати так: «існує х такий, що S(x,y)». У цьому випадку говорять, що предикат P(y) отриманий із предиката S(x,y) навішенням квантора існування на x і пишуть P(y) = (x)S(x,y).



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

  • Визначення 2.3.3 Нехай P(x1,…,xn)–предикат, заданий на множині M, y – змінна. Тоді вираз «для всякого y виконується P(x1,…,xn)»–предикат, отриманий з P навішенням квантора загальності на змінну y, а вираз «існує y такий, що виконується P(x1,…,xn)»–предикат, отриманий з P навішенням квантора існування на змінну y і пишуть .



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

  • На предикати можна дивитися і більш формально, причому з двох точок зору.

  • По-перше, предикат можна представити відношенням у такий спосіб. Нехай предикат 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}.



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

  • Числення предикатів, тобто формальна теорія предикатів будується за класичною схемою побудови формальних (математичних) теорій.

  • 1. Алфавіт числення предикатів, тобто множина вихідних символів складається з предметних змінних x1,x2,..., предметних констант a1,a2,..., предикатних букв P11, P21,...,Pkj,... і функціональних букв f11,f21,...,fkj,..., а також знаків логічних операцій , , , , кванторів , і розділових знаків ( , ) .

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



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

  • 2. Поняття формули означають у два етапи.

  • Спочатку означають поняття терму.

  • а). Предметні змінні і предметні константи є термами.

  • б). Якщо fn - функціональна буква, а t1,t2,...,tn - терми, то fn(t1,t2,...,tn) - терм.

  • в). Інших термів, крім утворених за правилами а) і б), немає.

  • Потім, формулюють визначення формули.

  • а). Якщо Pn предикатна буква, а t1,t2,...,tn - терми, то Pn(t1,t2,...,tn) - формула, що називається елементарної. Усі входження предметних змінних у формулу Pn(t1,t2,...,tn) називають вільними.

  • б). Якщо F1, F2 - формули, то вираження (F1), (F1F2), (F1F2), (F1F2) теж є формулами. Усі входження змінних, вільні в F1 і F2, є вільними і у всіх чотирьох видах формул.

  • в). Якщо F(x) - формула, що містить вільні входження змінної x, то x(x) і x(x) - формули.

  • У цих формулах усі входження змінної x називають зв'язаними. Входження здачі змінних у F залишаються вільними.

  • г). Інших формул, чим побудованих за правилами а), б) і в), немає.



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

  • Визначення 2.3. 4 Інтерпретацією на непорожній множині М називається функція, задана на сигнатурі 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))



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

  • Визначення 2.3.5 Формули F(x1,…,xn)і G(x1,…,xn)називаються рівносильними, якщо для будь-якої інтерпретації з областю М висловлення F(a1,…,an)і

  • G(a1,…,an)при будь-яких a1,…,an з М одночасно істинні або одночасно хибні.

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

  • Аналогічно вводиться означення тотожно хибної формули.



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

  • Ясно, що всі рівносильності алгебри висловлень будуть вірні, якщо в них замість змінних висловлень підставити формули логіки предикатів. Але крім того, мають місце рівносильності самої логіки предикатів. Наприклад, закони пронесення кванторів через кон'юнкцію і диз'юнкцію: (існують і інші рівносильності)



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

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

  • Визначення 2.3.7 Говорять, що формула логіки предикатів має приведену нормальну форму, якщо вона містить тільки операції кон'юнкції, диз'юнкції і кванторні операції, а операція заперечення віднесена до елементарних формул.

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



  • Плато́н (др.-греч. Πλάτων) (428 или 427 до н. э., Афины348 или 347 до н. э., там же) — древнегреческий философ, ученик Сократа, учитель Аристотеля. Настоящее имя — Аристокл (др.-греч. Αριστοκλής). Платон — прозвище, означающее «широкий, широкоплечий». По свидетельству Олимпиодора, Платон был не только философом , но и олимпийским чемпионом . Дважды он выигрывал соревнования по панкратиону — смесь бокса и борьбы . Понимать, что справедливо, чувствовать, что прекрасно, желать, что хорошо, — вот цель разумной жизни.

  • Политика — это искусство жить вместе.









  • Фридрих Людвиг Готлоб Фреге (Friedrich Ludwig Gottlob Frege, 8 ноября 1848, Висмар — 26 июля 1925, Бад Клайнен) — немецкий логик, математик и философ. Представитель школы аналитической философии.

  • Сформулировал идею логицизма, то есть направление в основаниях математики и философии математики, основным тезисом которого является утверждение о «сводимости математики к логике».



Схожі:

Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconФормат опису модуля
Основи математичної логіки. Основи теорії нечітких множин. Відношення та їх властивості. Види відношень. Основи комбінаторики та...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconНазва модуля: Вища математика Ч. 3 Код модуля
Звичайні диференціальні рівняння та рівняння математичної фізики. Елементи теорії функцій комплексної змінної та операційного числення....
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconНазва модуля: Вища математика Ч. 3 Код модуля
Звичайні диференціальні рівняння та рівняння математичної фізики. Елементи теорії функцій комплексної змінної та операційного числення....
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconТема Модальна логіка предикатів (6 год.) Тема 5
Розглядаються засадничі поняття семантики можливих світів. Аналізуються світоглядні засади та базові властивості основних систем...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconМатематичні основи інформатики
Основи теорії чисел: прості числа, ділення із залишком, найбільший спільний дільник, взаємно прості числа. Основи алгебри: многочлени...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconОсновна література Любчак В. О., Назаренко л д. „Основи математичної теорії систем”
Любчак В. О., Назаренко л д. „Основи математичної теорії систем”, Вид-во СумДу, 2008-320с
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconІ. А. Елементи теорії ймовірностей та математичної статистики. Навчальний посібник. Київ: «Слово», 2006 -272с. Опрацювати та закон
Д., Рибалка В.І., Рудоміно-Дусятська І. А. Елементи теорії ймовірностей та математичної статистики. Навчальний посібник. – Київ:...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconІ. А. Елементи теорії ймовірностей та математичної статистики. Навчальний посібник. Київ: «Слово», 2006 -272с. Опрацювати та закон
Д., Рибалка В.І., Рудоміно-Дусятська І. А. Елементи теорії ймовірностей та математичної статистики. Навчальний посібник. – Київ:...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconЗавдання для самостійної роботи з „Теорії ймовірностей І математичної статистики” Модуль Елементи математичної статистики
Провести довільний експеримент, результатом якого є вибірка з не менше 30 значень деякої випадкової величини (неперервної)
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconФізичні основи теорії відносності
Особливу увагу звернуто на принцип відносності в електродинаміці. Показано, що незвичні ефекти теорії відносності логічно витікають...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи