Пошук навчальних матеріалів по назві і опису в нашій базі:

Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань”




462.31 Kb.
НазваМетодичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань”
Сторінка1/4
Дата конвертації09.10.2012
Розмір462.31 Kb.
ТипМетодичні вказівки
Зміст
Просте висловлювання
Проблема розв
T5: ├─(ab)  (ba)
Одномісним предикатом
Ав, ba├─ ab
Чиста літера
Визначити істинність формули
Визначити за допомогою методу резолюцій, чи є формула абсолютно істинною
Список літератури
  1   2   3   4



Методичні вказівки
до виконання курсової роботи з кредитного модуля

Теорія алгоритмів та математичні основи представлення знань”

для студентів заочної форми навчання

спеціальності

„Інформаційні управляючі системи та технології”

1. ТЕОРЕТИЧНІ ВІДОМОСТІ

Логіка – наука про правильні міркування, про прийоми та методи пізнання за допомогою міркувань. Слово «логіка» походе з давньогрецького «логос»: «поняття», «розум», «міркування». Логіка як наука про правильні міркування була закладена у Стародавній Греції Аристотелем та на протязі багатьох століть розвивалась як частина філософії. Тільки в кінці 19-го – початку 20-го сторіччя з появою булевої алгебри почався бурхливий розвиток математичної (формальної) логіки. На сьогоднішній день розрізняють традиційну логіку та формальну, математичну логіку.
1.1. Логіка висловлювань

Логіка, вивчаючи правильні міркування, оперує поняттями істинності та хибності. Правильні міркування або висловлювання вважаються істинними, неправильні – хибними.

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

Логічні висловлювання Істина (True) та Хибність (False) позначаються відповідно T та F. Кожне просте висловлювання позначають символами латинського алфавіту, які називаються пропозиційними символами: A, B, C

Приклади простих висловлювань: «Київ – столиця України», «Всі люди смертні», «2+2=5».

Складні висловлювання отримуються з простих за допомогою операцій (логічних зв’язок): конюнкції (& або ; логічне «і»), дизюнкції (; логічне «або»), заперечення (; логічне «ні»), імплікації (; логічна операція «якщо, то») та еквівалентності (). Всі ці операції, окрім заперечення, є бінарними, а заперечення – унарне. Значення даних операцій можна задати за допомогою таблиць істинності.

A

B

A

A&B

AB

AB

AB

F

F

T

F

F

T

T

F

T

T

F

T

T

F

T

F

F

F

T

F

F

T

T

F

T

T

T

T

Складне висловлювання (формула) називається абсолютно істинною (тавтологією), якщо вона у всіх рядках таблиці істинності приймає істинне значення (T). Запис ╞A означає: «формула А – тавтологія».

Якщо у всіх рядках таблиці буде значення хибність (F), то формула є протиріччям. В інших випадках формула називається ні істинною, ні хибною. Дві формули називаються еквівалентними, якщо їх таблиці істинності співпадають.

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

Якщо А та В – формули, то говорять, що В логічно слідує з А, якщо на всіх інтерпретаціях (рядках таблиці істинності), де А приймає істинне значення, В також приймає істинне значення. Це позначається як А╞В.

Теорема 1. Логічне слідування А╞В виконується тоді й тільки тоді, коли формула AB – тавтологія.
2. Числення висловлювань

Формальні теорії будуються за наступними правилами. Задається злічена множина символів, які називаються алфавітом теорії. З цієї множини символів будуються скінчені послідовності, які називаються словами або виразами даної теорії. З множини виразів виділяють правильно побудовані вирази – формули. З множини формул виділяють підмножину аксіом. Між формулами теорії визначають відношення – правила виведення теорії. Правила виведення дозволяють з множини аксіом виводити теореми. Таким чином, формальна теорія є аксіоматичною теорією.

Доведенням теореми називають послідовність формул A1,…,An, кожна з яких або є аксіомою, або отримана з попередніх за правилами виведення даної теорії. Кожна формула у переліку є теоремою даної теорії. Іншими словами, теорема – це формула, яка виводиться з множини аксіом за правилами виведення, які визначені в даній теорії. Запис ├─A позначає, що формула виводиться в певній теорії.

Виведенням формули А з множини гіпотез Г називається послідовність формул A1,…,An, кожна з яких є або аксіомою, або гіпотезою з множини Г, або отримана з попередніх за правилами виведення. Формула An називається такою, що виводиться з множини гіпотез Г.
Числення висловлювань L задається наступною системою:

1. Мова числення L.

1.1 Символи числення L.

а) пропозиційні літери: A, B, C,…;

б) символи зв’язків  (заперечення),  (імплікація);

в) службові символи: (, ).

1.2 Довільна послідовність символів мови числення L називається виразом мови числення L.

1.3 Формули мови числення L:

а) довільна пропозиційна літера є формулою;

б) якщо A, B – це формули мови L, то AB, A, BA, B – також формули мови L;

в) інших формул в численні L не існує.

2. Аксіоми числення L.

Якими б не були A, B, C наступні формули є аксіомами.

А1: A  (B  A)

A2: (A  (B  C))  ((A  B)  (A  C))

A3: (B  A)  ((B  A)  B).

3. Правила виведення числення L.

Числення L має одне єдине правило виведення Modus Ponens (MP): якщо мають місце формули A  B та А, то тоді має місце формула В.
Наведені вище аксіоми числення L треба розглядати як схеми аксіом. Це означає, що при підставленні у аксіому А1 замість пропозиційних літер А та В довільних формул, отримана формула також буде аксіомою А1. Наприклад, якщо А = ЕС, В = С, то отримуємо формулу (ЕС)  (С  (ЕС)), яка також буде аксіомою А1.

Інші логічні зв’язки (кон’юнкція та диз’юнкція) можуть бути виражені через заперечення та імплікацію за допомогою наступних перетворень: A&B = (AB); AB = AB.

Важливим результатом є теорема дедукції Ербрана.

Теорема 2. Нехай Г – множина формул, А та В – деякі формули. Якщо Г, А├─ В, то Г├─АВ. Зокрема, якщо А├─ В, то ├─АВ. Вірно й обернене твердження: якщо Г├─АВ, то Г, А├─ В або якщо ├─АВ, то А├─ В.

Наслідок 1. Правило силогізму: AB, BC├─ AC.

Наслідок 2. Правило видалення середнього посилання: A(BC), B├─AC.

Наслідок 3. Правило видалення крайнього посилання: (AB)C├─BC.

Якщо раніше певна теорема А вже була доведена в численні L, то в подальшому нею можна користуватись як аксіомою. Це справедливо в силу того, що завжди можна замінити дану теорему А в деякому виведенні її власним виведення і при цьому не порушити правила побудови виведень у численні L. Такими теоремами є:

T1: ├─AA

T2: ├─AA

T3: ├─AA

T4: ├─A(AB)

T5: ├─(AB)  (BA)

T6: ├─(BA)  (AB)

T7: ├─A(B(AB))
1.3. Логіка першого порядку

Існують такі логічні схеми міркувань, які не можуть бути обґрунтовані у логіці висловлювань. Наприклад, умовивід: «Всі люди смертні (А). Сократ – людина (В). Відповідно, Сократ смертний (С)». Зрозуміло, що С слідує з А та В, але логічне слідування А, В╞ С не доводиться у логіці висловлювань. Для цього вводиться поняття предикату.

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

Над предикатами визначені логічні операції: кон’юнкції, диз’юнкції, заперечення, імплікації, еквівалентності, а також операції квантифікації:  - квантор загальності,  - квантор існування.

Якщо P(x) означає деяку властивість на множині М, то формула xP(x) означає висловлювання: “для будь-якого предмету mM виконується властивість P(x)” або “всі x маються властивість P(x)”. Формула xP(x) набуває значення “істина”, коли властивість Р виконується для всіх об’єктів з М, та набуває значення “хибність” у протилежному випадку, тобто коли існує хоча б один об’єкт з множини М, для якого ця властивість не виконується.

Формула xP(x) означає: “існує принаймні один предмет x, який має властивість P» або «деякі x мають властивість Р”. Значення формули xP(x) є істинним, коли властивість Р виконується хоча б для одного об’єкту з множини М, та хибним, коли не існує жодного об’єкта, для якого ця властивість виконувалась би.

Розглянемо наступний приклад. Задане речення: “Сума двох додатних чисел – додатне число”. Спочатку перепишемо це речення так: “Два довільні додатні числа дають у сумі додатне число”. Уведемо змінні x та y і отримаємо речення: “Будь-які додатні числа x та y утворюють суму х+у, яка є додатнім числом”. Запишемо його формулою xy(((x>0)  (y>0))  (x+y>0)). Тут предметна область кожної змінної – усі дійсні числа.

Квантори пов’язані між собою за принципом двоїстості законами де Моргана:

хР(х) = х(Р(х)),

хР(х) = х(Р(х)).

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

(1) Кожна предметна змінна є термом. (2) Кожна предметна константа є термом. (3) Якщо f – функціональний символ та t1,…,tn – терми, то f(t1,…,tn) є термом. (4) Інших термів не існує.

Визначення формули у логіці першого порядку.

(1) P(t1,…,tn), де Р – предикатний символи, t1,…,tn – терми, є атомарною формулою. (2) Якщо А та В – формули та x – предметна змінна, то формулами є: A, AB, AB, AB, A~B, xA, xA. (3) Інших формул немає.

Формула, на яку розповсюджується дія квантора, називається областю дії квантора. Змінна, за якою “навішується” квантор та яка попадає в його область дії, називається звязаною змінною. Змінна, яка лежить за межами області дії квантора, називається вільною змінною. Формула, що не містить вільних змінних, називається замкненою. Замкнуті формули є висловлюваннями.

Наприклад, розглянемо формулу x( P(x)  yQ(x,y) ) та її підформули. У підформулу yQ(x,y) змінна х входить вільно, а обидва входження змінної y зв’язані (квантором загальності). Таким чином, ця підформула не є замкненою. З іншого боку, теж саме входження змінної х у підформулу Q(x,y) є зв’язаним входженням у формулі x( P(x)  yQ(x,y) ). В цій формулі всі входження всіх змінних зв’язані, тому ця формула замкнена.

У формулах логіки першого порядку можна робити заміну змінних (в загальному випадку – термів) при виконанні певних умов, які полягають в тому, щоб жодне вільне входження змінної не стало зв’язаним в наслідок заміни.

Кажуть, що терм y є вільним для змінної x в формулі A(x), якщо жодне вільне входження x в A(x) не знаходиться в області дії жодного квантора по z, де z – змінна, яка входить в терм y.

Будь-який терм, який не містить змінних, є вільним для довільної змінної у будь-який формулі. Будь-який терм є вільним для x в формулі A(x), якщо A(x) не містить вільних входжень x. Терм y є вільним для довільної змінної в формулі A, якщо жодна змінна терму y не є зв’язаною змінною в формулі A.

Наприклад, терм y є вільним для змінної x в формулі P(x), але той самий терм y не є вільним для змінної x в формулі yP(x). Терм f(x,z) є вільним для змінної x в формулі yP(x,y)Q(x), але той самий терм f(x,z) не є вільним для змінної x в формулі zyP(x,y)Q(x).
1.4. Інтерпретації формул логіки першого порядку

Формули мають зміст тільки тоді, коли є яка-небудь інтерпретація символів, які входять до її складу.

Інтерпретацією називається система I, яка складається з непорожньої множини D, яка називається областю інтерпретації, а також відповідності, яка ставить кожному n-місному предикату Pi деяке відношення на області Dn, кожній предметній константі ai – деякий елемент з області D, кожній функціональній літері fi – деяку n-місну операцію з області D (тобто функцію DnD).

Коли задана область інтерпретації всі предметні змінні пробігають всі значення з області D, а логічні зв’язки мають звичайний логічний зміст.

Наприклад, нехай задана формула xyP(f(x,y), t). Предикат P(v, u) – двомісний, змінні x,y – зв’язані, t – вільна змінна. Задамо наступну інтерпретацію: область інтерпретації D – множина дійсних чисел R, t = 1, f(x,y) = x2 + y2, предикат P(u, t): u = t. Тоді формула набуває вигляд: xy(x2 + y2 = 1). Вона істинна, тому що існують такі x та y, які задовольняють рівнянню кола x2 + y2 = 1.

Якщо покласти f(x,y) = x2 + y2, t = r2, то формула xy(x2 + y2 = r2) – одномісний предикат, область істинності якого – множина дійсних чисел, які задовольняють рівнянню кола x2 + y2 = r2 з радіусом r.

Інтерпретація називається моделлю для даної множини формул Г, якщо кожна формула з Г істинна в даній інтерпретації.

Формула називається виконуваною, якщо існує хоча б одна інтерпретація, на якій формула істинна. Формула називається загальнозначущою, якщо вона істинна на будь-якій інтерпретації для будь-яких значень змінних. Формула, яка є хибною на будь-якій інтерпретації при будь-яких значеннях змінних, називається
  1   2   3   4

Схожі:

Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” icon1 Вимоги до виконання курсової роботи 4 2 Завдання для курсової роботи 7
Дані методичні вказівки призначені для організації виконання курсової роботи студентів спеціальності 000008 «Енергетичний менеджмент»...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки до виконання курсової роботи з дисципліни "Податкова система" для студентів напряму 0501 "Економіка і підприємництво"
Методичні вказівки до виконання курсової роботи з дисципліни "Податкова система" / Укладачі: Т. О. Кірсанова, І. М. Кобушко, М. Ю....
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconТип модуля: обов'язковий Семестр: VI обсяг модуля
Методичні вказівки до виконання курсової роботи для студентів всіх форм навчання та екстернів базових напрямів 050501, 050502, 050504,...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки до виконання курсової роботи з дисципліни „ регіональний менеджмент для студентів спеціальності 0306 «Менеджмент І адміністрування»
Методичні вказівки до виконання курсової роботи з дисципліни „Регіональний менеджмент” // Укладачі: А. Ю. Жулавський, О. О. Павленко,...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки до виконання курсової роботи Цілі та завдання курсової роботи
Прошу розмістити на сайті дну у розділі «Методичні матеріали для самостійної роботи студентів» наступні матеріали
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки щодо виконання та оформлення курсової роботи з дисципліни «Обчислювальна математика»
Методичні вказівки з виконання та оформлення курсової роботи з дисципліни «Обчислювальна математика» для студентів геологічного факультету...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconРозрахунок та оптимізація характеристик систем електрозв'язку завдання на виконання курсової роботи з дисципліни
Телекомунікації” 0924 передбачене виконання курсової роботи з дисципліни “Теорія електричного зв'язку”. Мета кр закріплення знань...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки щодо виконання курсової роботи з курсу „технології програмування розробив: Томашевський В. В
Важливим етапом вивчення дисципліни „ Технології програмування ” є написання курсової роботи. Задачами курсової роботи є
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки до виконання та оформлення курсової роботи для студентів всіх форм навчання
Методичні вказівки до виконання та оформлення курсової роботи для студентів усіх форм навчання з дисципліни “Програмування”/Укладачі:...
Методичні вказівки до виконання курсової роботи з кредитного модуля „Теорія алгоритмів та математичні основи представлення знань” iconМетодичні вказівки до виконання курсової роботи "Визначення впливу вражаючих факторів нс "
Мармазинський О. А., Савіна О. Ю., Штейн П. В. Методичні вказівки до виконання курсової роботи: “Визначення впливу вражаючих факторів...
Додайте кнопку на своєму сайті:
ua.convdocs.org


База даних захищена авторським правом ©ua.convdocs.org 2014
звернутися до адміністрації
ua.convdocs.org
Реферати
Автореферати
Методички
Документи
Випадковий документ

опубликовать
Головна сторінка