загрузка...
загрузка...
На головну

Для прикладів з п. 6 побудувати доказ, використовуючи метод зворотного дедукції.

  1. A) Складіть пропозиції, використовуючи наведені словосполучення.
  2. Case-метод Баркера
  3. I. 2. 1. Марксистсько-ленінська філософія - методологічна основа наукової психології
  4. I. 2.4. Принципи та методи дослідження сучасної психології
  5. I. Методичні рекомендації
  6. I. Методичні рекомендації
  7. I. Методичні рекомендації

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

1) якщо піти на першу пару, то треба встати рано, а якщо грати в преферанс, то лягти доведеться пізно;

2) якщо лягти пізно і рано встати, то спати доведеться мало;

3) мало спати не можна.

Висновок: треба чи не грати в преферанс, або не йти на першу пару.

Введемо наступні позначення для висловлювань:

g - Встати рано;

d - Грати в преферанс;

с - Йти на першу пару;

s - Лягти пізно спати;

e - Мало спати.

Використовуючи введені позначення, перейдемо від тверджень до наступного набору гіпотез: , ,  . Слідство набуде вигляду .

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

.

Заперечення слідства матиме вигляд .

 1. 2. 3. 4. 5. c 6. d 7. g (1-5) 8. s (2-6) 9. (3-7) 10. e (8-9) 11. Порожній диз'юнкт (4-10) 1.

9. Записати формально наступне міркування на природній мові в термінах логіки висловлювань і довести його справедливість, використовуючи метод резолюцій:

а) Посилки: Якщо йде дощ, то жарко. Якщо світить сонце, то жарко. Йде дощ.

Висновок: не спекотна і не світить сонце.

б) Посилки: Іспит зданий вчасно або сесія продовжена. Якщо сесія продовжена, то чи не здана курсова робота або не зараховано лабораторні роботи. Курсова робота здана. Іспит вчасно не зданий.

Висновок: Невірно, що якщо курсова робота здана, то лабораторні роботи зараховані.

в) Посилки: Якщо має місце грошова емісія, то зростає курс долара. Якщо емісії немає і інфляція не зростає, то курс долара не росте. Інфляція не росте.

Висновок: Має місце емісія і росте курс долара чи ні емісії і курс долара не росте.

г) Посилки: Заробітна плата зросте тільки, якщо буде інфляція. Якщо буде інфляція, то збільшиться вартість життя. Заробітна плата зросте.

Висновок: Вартість життя збільшиться.

д) Посилки: Якщо 2 - просте число, то це найменше просте число. Якщо 2 - найменше просте число, то 1 цієї статті не є просте число. Число 1 цієї статті не є просте число.

Висновок: 2 - просте число.

е) Посилки: Джон або перевтомився, або він хворий. Якщо він перевтомився, то він дратується. Він не рветься до гніву.

Висновок: Джон хворий.

ж) Посилки: Якщо завтра буде холодно, то я одягну тепле пальто, якщо рукав буде полагоджений. Завтра буде холодно, а рука не буде полагоджений.

Висновок: Я не одягну тепле пальто.

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

Висновок: Результат перегонів не визначений змовою.

і) Або Вася і Петя одного віку, або Вася старше Петі. Якщо Вася і Петя одного віку, то Федя і Петя не одного віку. Якщо Вася старше Петі, то Петя старше Семена.

Висновок: Або Федя і Петя не одного віку, або Петя старше Семена.

к) Посилки: Якщо буде йти сніг, то машину буде важко вести. Якщо буде важко вести машину, то я спізнюся, якщо не виїду раніше. Йде сніг.

Висновок: Я повинен виїхати раніше.

л) Посилки: Якщо підозрюваний скоїв крадіжку, то вона або була ретельно підготовлена, або він мав співучасника. Якби крадіжка була підготовлена ??ретельно, то, якби був співучасник, то вкрадено було б набагато більше. Вкрадено мало.

Висновок: Підозрюваний невинний.

м) Посилки: У бюджеті виникне дефіцит, якщо не підвищити податки. Якщо в бюджеті є дефіцит, то державні витрати на соціальні потреби скорочуються.

Висновок: Якщо підвищити податки, то державні витрати на соціальні потреби не скорочуються.

н) Посилки: Намічена атака вдасться, тільки якщо захопити противника зненацька, або ж якщо його позиції погано захищені. Захопити його зненацька можна тільки тоді, коли він безтурботний. Він не буде безтурботний, якщо його позиції погано захищені.

Висновок: Атака не вдасться.

7.3. ЛОГІКА предикатів

1. Нехай задані предикати: - x - Парне число і - x - число, кратне трьом. Предикати визначені на множині N - Натуральних чисел. Визначити області істинності предикатних виразів:

а)

б)

в)

г) .

2. Нехай Р (х) позначає «х - просте число", Е (х) - «х - парне число", О (х) - «х - Непарне число »і D (x, y) - «у ділиться на х». Перекласти на російську мову такі предикатні вирази:

1) Р(7);

2) Е(2)& Р(2);

3)

4)

5)

6)

7)

8)

Нехай предикати визначені на множині N - Натуральних чисел:

- - n ділиться на 3;

- - n ділиться на 2;

- - n ділиться на 4;

- - n ділиться на 6;

- - n ділиться на 12.

Визначити, які з предикатних виразів справжні, а які - неправильні:

а) ;

б) ;

в) ;

г) .

4. Знайти заперечення наступних формул:

а) ;

б) .

Приклад. Довести тотожну істинність заданого предикатного виразу

Приклад. Довести тотожну хибність заданого предикатного виразу

Визначити, які з наведених формул є тотожно істинними, а які - тотожно хибними:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

4. Привести до нормальної формі такі вирази:

а) ;

б) ;

в) .

5. Уявити затвердження, сформульовані на природній мові у вигляді предикатних виразів:

1) всі судді - юристи (J (x) позначає «х - Суддя »; L (x) позначає «х - Юрист);

2) деякі юристи - шахраї (S (x) позначає «х - Шахрай »);

3) жоден суддя не є шахраєм;

4) деякі судді - люди похилого віку, але бадьорі (O (x) позначає «х - Старий »; V (x) позначає «х - Бадьорий »);

5) суддя Сидоров не старий і не бадьорий (константу «Сидоров» позначає символ «j»);

6) не всі юристи - судді;

7) деякі юристи, які є політиками, - члени державної Думи (P (x) позначає «х - Політик »; C (x) позначає «х - Член державної Думи »);

8) жоден член державної думи не бадьорить;

9) всі старі члени державної думи - юристи;

10) деякі жінки одночасно є юристами і членами державної думи (W (x) позначає «х - Жінка »);

11) жодна жінка не є одночасно політиком і домогосподаркою (Н (х) позначає «х - Домашня господарка");

12) деякі жінки-юристи є домашніми господарками;

13) всі жінки-юристи захоплюються яким-небудь суддею (А (х, у) позначає «х - захоплюється y);

14) деякі юристи захоплюються тільки суддями;

15) деякі юристи захоплюються жінками;

16) деякі шахраї не захоплювати жодним юристом;

17) суддя Сидоров не захоплювати жодним шахраєм;

18) існують як юристи, так і шахраї, які захоплюються суддею Сидоровим;

19) тільки судді захоплюються суддями;

20) всі судді захоплюються тільки суддями.

Приклад. Довести за допомогою методу резолюцій справедливість наступних міркувань.

1. Деякі керівники з повагою ставляться до всіх програмістам.

2. Жоден керівник не поважає нероб.

Отже, жоден програміст не є ледарем.

Введемо наступні предикати:

C (x) - «x - керівник»;

P (x) - «x - програміст »;

B (x) - «x - нероба»;

U (x, y) - «x поважає y».

Тоді посилки, записані у вигляді предикатних виразів, будуть виглядати так:

1) ;

2) .

Висновок прийме наступний вигляд:

.

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

:

 1)    
 2)    
 3)    
 4)    
 5)    
 6) (1 - 3) S = {a / x}
 7) (2 - 4) S = {b / y}
 8) (6 - 7) S = {a / x, b / y}
 9) порожній диз'юнкт (5 - 8)  

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

1) Усі мексиканці носять сомбреро. Жодна мавпа не носить сомбреро. Отже, жодна мавпа не є мексиканцем.

2) Кожен член демократичної партії голосує за президента і не любить комуністів. Деякі демократи є підприємцями. Отже, існують підприємці, які не люблять комуністів.

3) Всі батьки - чоловіки. Якщо у дітей один батько, то вони єдинокровні. Брат - це єдинокровний чоловік. Джон - батько Боба. Джон - батько Сіда. Сід - батько Ліз. Отже, Сід і Боб - брати.

4) Жодна людина не є чотириногим. Всі жінки - люди. Отже, жодна жінка не є чотириногою.

5) Деякі республіканці люблять всіх демократів. Жоден республіканець не любить жодного соціаліста. Отже, жоден демократ не є соціалістом.

6) Жоден торговець наркотиками не є наркоманом. Деякі наркомани залучаються до відповідальності. Отже, не всі залучаються до відповідальності є торговцями наркотиками.

7) Всі раціональні числа є дійсними числами. Деякі раціональні числа - цілі числа. Отже, деякі дійсні числа - цілі числа.

8) Всі першокурсники спілкуються з усіма другокурсниками. Жоден першокурсник не спілкується ні з одним студентом останнього курсу. Отже, жоден другокурсник не є студентом останнього курсу.

9) Деяким подобається група «Queen». Деякі не люблять нікого, кому подобається група «Queen». Отже, деяких люблять не всі.

10) Кожен батько має дитину. Якщо той з батьків - жінка, то це - мати. Ліз - жінка. Анна - батько Ліз. Отже, Анна - мати.

11) Якщо батько - чоловік, то це батько. Якщо дитина - чоловік, то це син. Іван - чоловік. Сидор - чоловік. Іван - батько Сидора. Отже, Іван - батько і Сидор - син.

12) Якщо дві людини є родичами третього, то перший - родич другого. Кожен - чийсь родич. Значить, якщо Іван - родич Петра, а Петро - родич Сидора, то Іван - родич Сидора.

13) Митники повертають всіх, хто в'їхав в країну без паспорта. Люди на машинах в'їхали в країну і були повернуті тільки іншими людьми на машинах. Жодна людина на машині не мав паспорта. Отже, деякі митники були на машинах.

7. Використовуючи метод резолюцій для предикатних виразів для заданої множини гіпотез Н = {h1, h2 , ..., Hn} і затвердження S , Довести справедливість виразу Н | - S :

 1) h1 = "X (K (x) &" y (R (y) ®U (x, y))), h2 = "X (K (x) ®" y (B (y) ® (X, y))), S = "y (R (y) ® (Y));
 2) h1 = "X (T (x) ® (X)), h2 = $ X (N (x) & O (x)), S = $ x (N (x) & (X));
 3) h1 = "X (C (x) ®W (x) & R (x)), h2 = $ X (C (x) & O (x)), S = $ x (P (x) & R (x));
 4) ;
 5) h1 = "X (P (x) ®Q (x)), h2 = "X (Q (x) ®R (x)), S = "x (P (x) ®R (x));
 6) h1 = "X" y (F (x, y) ®M (x)), h2 = "X" y "w (F (x, y) & F (x, w) ®E (y, w)), h3 = "X" y (E (x, y) & M (x) ®B (x, y)), h4 = F (Y, H), h5 = F (Y, D), h6 = F (D, L), S = B (z, H);
 7) h1 = "Z (H (z) ® (Z)), h2 = "Y (W (y) ®H (z)), S = "x (W (x) ® (X));
 8) h1 = "X" y (P (x) & V (y) ®W (x, y)), h2 = "X" y (P (x) & E (y) ® (X, y)), S = "x (V (x) ® (X));
 9) h1 = "X" y (R (x, y) & M (x) ®O (x)), h2 = "X" y (R (x, y) & M (y) ®C (y)), h3 = M (D), h4 = M (B), h5 = R (D, B), S = O (D) & C (B));
 10) h1 = "X (M (x) ®W (x)), h2 = "X (N (x) ® (X)), S = "x (N (x) ® (X));
 11) h1 = "X (D (x) ® (X, K)), h2 = $ X (D (x) & P (x)), S = $ x (P (x) & (X, K));
 12) h1 = $ X (H (x) & U (x, Q)), h2 = $ X "y (H (x) & H (y) & U (x, Q) ® (X, y)), S = $ x $ y (H (x) & H (y) & L (x, y));
 13) h1 = "Z (H (z) & R (z) ® (Z)), h2 = "Y (W (y) ®H (z)), h3 = R (A), h4 = W (x), S = "x ( (X) & (X)).

7.4. ТЕОРІЯ АЛГОРИТМІВ

Приклад.Нехай на стрічці записані два натуральних числа в унарна коді (унарний код - це уявлення числа у вигляді відповідної послідовності одиниць. Наприклад, 4 = 1111 = 14). Числа розділені символом «+». Потрібно реалізувати операцію складання таким чином, щоб після її реалізації на стрічці були збережені вихідні дані і записаний результат виконання операції. Керуючий пристрій після завершення роботи повинно знаходитися на першому символі поточного запису на стрічці.

Початковий стан МТ, наприклад, для чисел 2 і 4 має мати вигляд:

А заключне:

В основі алгоритму буде лежати наступна ідея, записавши символ «=», після вихідних даних, за ним слід скопіювати всі одиниці з першого і другого числа, після чого повернути керуючий пристрій в першу позицію записи на стрічці. Опишемо МТ у вигляді системи команд:

 

безлічі A и Q визначені так:

8. Побудувати машину Тьюринга, що реалізує задану функцію. Опис машини повинно бути представлено у вигляді системи команд, графа переходів або таблиці. Вважати, що вихідні дані записані на стрічці, на ній же вони повинні бути збережені після виконання всіх дій. Результати записуються на стрічці після вихідних даних і відокремлюються від них символом «=»:

а) Нехай на стрічці записана послідовність нулів і одиниць. Реалізувати машину, яка буде підраховувати число одиниць у вихідній послідовності і записувати результат рахунку;

б) Реалізувати функцію, яка в вираженні в бінарній формі запису буде підраховувати кількість комбінацій виду 010. Наприклад, 1101101010101 = 11;

в) Реалізувати функцію, яка в вираженні в бінарній формі запису буде підраховувати кількість комбінацій виду 101. Наприклад, +01101110001011010 = 111;

г) Реалізувати функцію, яка в вираженні в бінарній формі запису буде робити заміну комбінації 01 на 1, а 10 на 0. Вважати, що такі комбінації в вихідному виразі є взаємно перетинаються або відокремлені один від одного символами. Наприклад, 01111001110001 = 111011001;

д) ;

е) ;

ж)

з)

і)

к) Реалізувати функцію, яка в вираженні в унітарній формі запису буде кожну третю одиницю замінювати на нуль. Наприклад, 1111111 = 1101101;

л)  . Символ «[]» означає виділення цілої частини від результату ділення. Вважати, що x> y;

м) ;

н) ;

о)  . Вважати, що x> y;

п) .

7.5. ЕЛЕМЕНТИ ТЕОРІЇ НЕЧІТКИХ МНОЖИН

1. Нехай задано безліч студентів С= {Іванов, Петров, Сидоров, Федоров}. Визначити на ньому такі нечіткі множини: S - Працьовитих студентів, P - Лінивих студентів та U - Студентів, які успішно склали сесію. Знайти результати наступних операцій над множинами:

2. Нехай задано два безлічі E = {a, d, f, r} и Y = {10,20,15,55}, На яких визначені нечіткі множини E и T, Відповідно визначити відношення між E и T, Якщо ці безлічі задані наступним чином:

E = , T = .

3. Нехай задано безліч студентів С={Іванов, Петров, Сидоров} і безліч курсових проектів K = {k1, k2, k3, k4}. Визначити на безлічі студентів нечітка множина S - Сильних студентів, а на K - безліч P - Складних курсових проектів. Визначити нечітке відношення, яке буде відповідати твердженням: «Якщо студент сильний, то він буде захищати складний курсовий проект».

4. Нехай задано безліч курсових проектів K = {k1, k2, k3, k4}, на якому визначено нечітка множина P - Непростих курсових проектів і задано безліч D = {d1, d2, d3, d4, d5} - Дипломних проектів, на якому визначено нечітка множина H - Хороших дипломних проектів. Визначити нечітке відношення, яке буде відповідати твердженням: «Якщо курсової проект непростий, то з нього можна зробити хороший дипломний проект».

5. Нехай задані два нечітких відносини U и B:

;

.

Визначити їх згортку .

6. Використовуючи результати прикладів 3 і 4 побудувати згортку нечітких відносин, яка буде відповідати твердженням: «Якщо студент сильний, то у нього вийде хороший дипломний проект».



1   2
загрузка...
© um.co.ua - учбові матеріали та реферати