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

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




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

1. (А  А)  ((А  А)  А) аксіома А3

2. А  А теорема Т1

3. (А  А)  А наслідок 2 теореми 2 до 1,2

4. А  (А  А) аксіома А1

5. AА наслідок 1 теореми 2 до 3,4
3. Довести теорему в численні L:├─(AB)  (( AB)  B)

Застосуємо теорему 2 – теорему дедукції.

Отримуємо: AB├─( AB)  B

Ще раз застосуємо теорему дедукції і отримуємо: AB, AB├─ B.

Побудуємо виведення AB, AB├─ B.

1. AB гіпотеза 1

2. AB гіпотеза 2

3. (AB)  (BA) теорема T6

4. (AB)  (BA) теорема T6

5. BA правило MP(1,3)

6. BA правило MP(2,4)

7. (B  A)  ((B  A)  B). аксіома A3

8. (B  A)  B правило MP(6,7)

9. B правило MP(5,8)

Якщо тепер застосувати зворотну теорему дедукції, то отримуємо потрібний результат.
4. Побудувати таблиці істинності на області інтерпретації D = {1, 2} для формули Ф = xy( P(x)  Q(y)  R ).

Предикати P(x) та Q(y) на області інтерпретації D = {1, 2} приймають наступні значення:

x

P1

P2

P3

P4

1

F

F

T

T

2

F

T

F

T



y

Q1

Q2

Q3

Q4

1

F

F

T

T

2

F

T

F

T


R – замкнена формула, тобто висловлювання, яке приймає значення T та F.

Оскільки предикат P(x) приймає 4 значення, предикат Q(y) – 4 значення, формула R – 2 значення, і в формулі Ф немає вільних змінних, її таблиця істинності буде складатись з 4×4×2 = 32 рядків. Очевидно, що якщо R = T, то Ф = T, тому залишається обчислити значення формули на решті 16 інтерпретаціях формул при R = F.

Нехай R = F. Розглянемо обчислення значень формули на інтерпретації P = P1 та Q = Q2.



Нехай P = P2 та Q = Q1.



Аналогічно знаходяться решта значень формули Ф, яки наведені нижче в таблиці.

P

P1

P1

P1

P1

P2

P2

P2

P2

P3

P3

P3

P3

P4

P4

P4

P4

Q

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

Ф

T

T

T

F

F

F

F

F

F

F

F

F

F

F

F

F


5. Перевірити логічне слідування у логіці предикатів, побудувавши виведення у численні K.

Область визначення: люди. 1. Деякі студенти люблять своїх викладачів. 2. Ніхто не любить невігласів. 3. Відповідно, жоден з викладачів не є невігласом.

Всі предикати задані на області D = {люди}. Нехай P(x): x – студент, D(x): x – викладач, Q(x): x – невіглас, L(x, y): x любить y. Формалізуємо посилання:

F1: x( P(x) & y(D(y)  L(x, y))).

F2: x( P(x)  y( Q(y)  L(x, y))).

Наслідок G: y( D(y)  Q(y)).

Побудуємо формальне виведення.

1. x( P(x) & y(D(y)  L(x, y))) гіпотеза Г1

2. x( P(x)  y( Q(y)  L(x, y))) гіпотеза Г2

3. P(b) & y(D(y)  L(b, y)) правило ЕК(1)

4. P(b) правило видалення &(3)

5. y(D(y)  L(b, y)) правило видалення &(3)

6. P(b)  y( Q(y)  L(b, y)) правило УК(2)

7. y( Q(y)  L(b, y)) правило MP(4,6)

8. Q(z)  L(b, z) правило УК(7)

9. D(z)  L(b, z) правило УК(5)

10. L(b, z)  Q(z) контрпозиція (8)

11. D(z)  Q(z) правило силогізму (9, 10)

12. y( D(y)  Q(y)) правило Gen(11)
6. Визначити за допомогою метода Девіса-Патнем, чи є формула суперечливою або ні.

Ф = ((C  (C  B))  (A & (BA))).

Щоби скористатись даним методом, нам необхідно отримати множину диз’юнктів для цієї формули, а для цього нам необхідно звести формулу до КНФ.

((C  (C  B))  (A & (BA))) = ((C  (C  B))  (A & (BA))) =

= ((C  (C  B)) & (A & (BA))) = ((C  (C  B)) & (A  (BA))) =

= ((C  (C  B)) & (A  (B&A))) = ((C  B) & ((A  B) & (A A)))

= (C  B) & (A  B) & (A A).

Отже, отримали множину диз’юнктів S={C  B, A  B, A A}.

Застосуємо правило 1. Тавтологічним диз’юнктом тут є третій диз’юнкт.

Отримуємо S1={C  B, A  B}.

Застосувати правило 2 ми не можемо, тому що в множині S1 немає однолітерних диз’юнктів.

Застосуємо правило 3 до чистої літери C. Викреслюємо перший диз’юнкт. Отримуємо множину S2={A  B}.

Другий раз застосовуємо правило 3 до чистої літери А. Викреслюємо одиничний диз’юнкт і отримуємо порожню множину. Таким чином висхідна множина S несуперечлива, а відповідна й формула Ф також несуперечлива.
7. Визначити за допомогою методу резолюцій, чи є формула абсолютно істинною.

Ф = (AB)  ((AB)  B).

Через те, що метод резолюцій визначає тільки суперечливість множини диз’юнктів, то нам необхідно спочатку заперечення цієї формули, а потім перетворити її у КНФ. Якщо в процесі використання методу резолюцій ми отримуємо порожній диз’юнкт, то тоді множина диз’юнктів та перетворена формула є суперечливими, а отже висхідна формула є абсолютно істинною.

((AB)  ((AB)  B)) = ((AB)  ((AB)  B)) =

= (AB) & ((AB)  B)) = (AB) & ((AB)  B)) =

= (AB) & (AB) & B

Множина диз’юнктів S={AB, AB, B}.

Застосуємо до цієї множини метод резолюцій.

1. AB з множини S

2. AB з множини S

3. B з множини S

4. В резольвента диз’юнктів 1 и 2

5. □ резольвента диз’юнктів 3 и 4

Ми отримали порожній диз’юнкт, а це означає, що множина S суперечлива. Тому формула Ф є абсолютно істинною.
8. Перевірити логічне слідування в логіці предикатів за допомогою методу резолюцій.

Область визначення: тварини. 1. Я люблю всіх тварин, які належать мені. 2. Собаки гризуть кістки. 3. Жодну тварину я не пускаю до себе у кабінет, якщо воно мені не «служить». 4. Всі тварини у дворі належать мені. 5. Всім тваринам, яких я люблю, дозволяється входити до мене у кабінет. 6. Єдина тварина, яка «служить», - собака. 7. Відповідно, всі тварини в цьому домі гризуть кістки.

Всі предикати задані на області D = {тварини}. Нехай для xD предикат K(x) означає «x гризе кістки», G(x) – «x – собака», L(x) – «x – тварина, яку я люблю», S(x) – «х служить», B(x) – «x належить мені», P(x) – «я пускаю x до кабінету», D(x) – «тварина x знаходиться на дворі». Тоді посилання та ціль можна представити у вигляді формул логіки першого порядку. Відразу ж відмітимо, що кінцева формула, істинність якої необхідно встановити, буде мати наступний вигляд:

Ф=P1&P2&P3&P4&P5&P6G,

де P1,…, P6 – посилання, а G – ціль. Тобто з шести висхідних посилань має слідувати ціль. Через те, що метод резолюції доводить суперечливість формул, то необхідно взяти заперечення формули та привести її до КНФ. Отримуємо:

Ф = (P1&P2&P3&P4&P5&P6G) =

= ((P1&P2&P3&P4&P5&P6&G)) = (P1&P2&P3&P4&P5&P6&G).

Тобто множина диз’юнктів S={P1,P2,P3,P4,P5,P6,G}. Всі диз’юнкти цієї множини мають бути зведені до ССФ.

P1=

P2=

P3=

P4=

P5=

P6=

G=

Отримали множину

.

Застосуємо метод резолюцій.

1. L(x) з S

2. B(x) з S

3. G(x) з S

4. K(x) з S

5. S(x)P(x) з S

6. D(x) з S

7. P(x) з S

8. S(x)G(x) з S

9. D(a)K(a) з S

10. S(x) з 5 та 7

11. G(x) з 8 та 10

12. K(a) з 6 та 9, підстановка {a/x}

13. □ з 4 и 12, підстановка {a/x}

Отримали порожній диз’юнкт, що означає суперечливість множини диз’юнктів S. Значить формула Ф є абсолютно істинною.
3. Варіанти завдань

Варіант 1.

1. Визначити істинність формули логіки висловлювань за допомогою методу таблиць істинності.

(B  AC)  ((BC)  ((DC)  (BD  C)))

2. Довести теорему в численні L:

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

3. Довести теорему в численні L:

├─ (B&A)  (C  B)

4. Побудувати таблиці істинності на області інтерпретації D = {1, 2} для формули:



5. Перевірити логічне слідування у логіці предикатів, побудувавши виведення у численні K.

Область визначення: дні. 1. Я не називаю день «нещасливим», якщо Робінсон чемний зі мною. 2. Середи завжди бувають похмурими днями. 3. Якщо люди беруть із собою парасолі, день ніколи не буває сонячним. 4. Єдиний день тижня, коли Робінсон чемний зі мною – середа. 5. Будь-хто візьме із собою парасолю, якщо йде дощ. 6. Мої «щасливі» дні незмінно виявлялись сонячними. 7. Відповідно, дощові дні похмурі.

6. Визначити за допомогою метода Девіса-Патнем, чи є формула суперечливою або ні:

 (B  AC)  ((BC)  ((DC)  (BD  C)))

7. Методом резолюцій довести, що формула з пункту 2 є абсолютно істинною.

8. Методом резолюцій довести, що формула з пункту 3 є абсолютно істинною.

9. Методом резолюцій перевірити логічне слідування з умови пункту 5.
Варіант 2.

1. Визначити істинність формули логіки висловлювань за допомогою методу таблиць істинності.

(AB) & (CD)  (AC  BD)

2. Довести теорему в численні L:

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

3. Довести теорему в численні L:

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

4. Побудувати таблиці істинності на області інтерпретації D = {1, 2} для формули:



5. Перевірити логічне слідування у логіці предикатів, побудувавши виведення у численні K.

Область визначення: люди. 1. Ніхто не забуде зачесатись, якщо він йде на бал. 2. Не модна сказати, що людина виглядає чудово, якщо вона неохайна. 3. Люди, які палять опіум, втрачають контроль на собою. 4. Зачесана людина виглядає чудово. 5. Ніхто не надіне білі лайкові рукавички, якщо він не йде на бал. 6. Людина завжди неохайна, якщо вона втратила контроль над собою. 7. Відповідно, ті хто курять опіум ніколи не носять білих лайкових рукавичок.

6. Визначити за допомогою метода Девіса-Патнем, чи є формула суперечливою або ні:

 ((AB) & (CD)  (AC  BD))

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
Реферати
Автореферати
Методички
Документи
Випадковий документ

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