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


НазваТема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів
Дата конвертації10.02.2013
Розмір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Тема № математичні основи теорії алгоритмів. 4 Елементи теорії графів
Широко використовується теорія графів при рішенні різних задач на обчислювальних машинах. Вірогідно і те, що теорія графів служить...
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconЛекція 4 Елементи математичної логіки
Висловлювання та операції над ними Основними об’єктами математичної логіки є висловлювання та константи
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconОснови теорії ймовірності та математичної статистики План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconОснови теорії ймовірності та математичної статистики проф. В. П. Марценюк План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconТема 2: «Основи теорії графів»
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconУрок 8 клас
Квадратні рівняння. Вказівка розгалуження. Логічні вирази. Елементи математичної логіки
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconОснови теорії держави І права план основні теорії виникнення держави І права
Держава як класове явище І як суспільний договір (порівняння концепції Енгельса І гоббса)
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconТеорії кислот іоснов Теорії кислот іоснов
Якщо ступінь дисоціації кислот (основ) не перевищує 5%, то рН можна розраховувати із загальної концентрації кислоти (основи)
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconТеорії кислот іоснов Теорії кислот іоснов
Якщо ступінь дисоціації кислот (основ) не перевищує 5%, то рН можна розраховувати із загальної концентрації кислоти (основи)
Тема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів iconІз біографії…
Ейнштейна), передбачив (1916) вимушене випромінювання. Розвинув статистичну теорію броунівського руху, заклавши основи теорії флуктуацій,...

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка