Математика в Internet

ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.ЗАДАЧІ ДЛЯ САМОСТІЙНОГО РОЗВ'ЯЗУВАННЯ

1. Вказати на істинні та фіктивні змінні булевих функцій:

а) ;

б) ;

в) ;

г) ;

д) .

2. Визначити, чи являються формули тавтологіями:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

3. Чи еквівалентні формули:

а) та ;

б) та ;

в) та ;

г) та ;

4. Побудувати функції, що реалізуються формулами. Записати логічний вираз у ДДНФ та ДКНФ.

а)

б)

в) ;

г) .

5. Максимально спростити вираз, скориставшись законами логіки Буля:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

6. Знайти мінімальні ДНФ булевих функйій методом Куайна; методом Куайна-Вейча;методом Мак-Клаксі:

а) на наборах ;

б) на наборах ;

в) на наборах ;

г) на наборах ;

д) на наборах ;

е) на наборах ;

ж) на наборах ;

з) на наборах ;

7. Чи буде повною система функцій:

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

8. Наведені нижче клаузи довести відповідними методами (аксіоматичним, натупального числення та резолюції):

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .

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

а) тому хто лисий, волосся фарбувати не має сенсу. Ні одна жаба не має волосся;

б) розумні люди ходять на руках. Нерозумні люди ходять на руках;

в) всі кози люблять капусту. Василь любить капусту;

г) ні одному ішаку не можна відмовити в розумі. Розумна істота не втрапить в халепу;

д) ні один професор не являється дурнем. Дурні люди тщеславні;

е) сіль солона. Море солоне. Люди люблять море. Ні один будинок не побудований із солі. Деякі будинки дуже гарні;

ж) пісок сипучий. Діти люблять бавитись в піску. Побудований будинок з піску недовговічний;

з) якщо пан Івашко – щасливий, то пані Івашко – нещаслива, якщо пан Івашко нещасливий, то пані Івашко щаслива;

і) якщо Джон піде на танці, то Макс не піде на танці, або Джон не піде на танці, то Макс прекрасно проведе вечір;

к) необхідна і достатня умова для щастя шейха складається в тому, щоб мати золото, вино, жінок і слухати легкі мелодії;

л) якщо додатне, то– від’ємне;

м) для того, щоб х було непарним, досить щоб воно було простим.

10. Скласти клаузи для приведених нижче легенд та за методом резолюцій перевірити логічний наслідок.

а) якщо Іван – комуніст, то Іван – атеїст. Наслідок: Іван – комуніст;

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

г) дещо, що несе в собі риси чогось доброго, добре само по собі. Дещо, що несе в собі риси поганого, погане саме по собі. Війна несе в собі риси миру і страждань. Мир це добре, страждання – погано. Наслідок: деякі речі як хороші, так і погані;

д) перукарі стрижуть всіх тих, хто не стрижеться сам, і не стрижуть тих, хто стрижеться сам. Чи існують перукарі ?

е) кожний, хто їде в тролейбусі, купує білет. Наслідок: якщо не існує білетів, то ніхто нікуди не їде.

11. Чи буде сумісна множина приведених нижче тверджень ? Впевнитися в цьому, склавши клаузи та перевірити їх кон’юнкції на сумісність:

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

б) або свідок був заляканим, або, якщо Джон покінчив життя самогубством, то записка була знайдена. Якщо свідок був заляканим, то Джон не покінчив життя самогубством. Якщо записка була знайдена, то Джон покінчив життя самогубством;

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

12. Нижче приведені легенди. Записати калузу, що вміщує 4-6 букв, яка відповідає тексту та підтексту легенди, для чого сформулювати необхідні посилки та два наслідки: один істинний, другий хибний. З допомогою таблиці істинності знайти МНФ, мінімальне та трансверстальне покриття:

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

б) всі автори літературних опусів, що пізнали природу людини, розумні люди. Ні одного автора не можна вважати істинним поетом, якщо він не може хвилювати серця людей. Шекспір написав “Гамлета”. Ні один автор, який не пізнав природу людини, не може хвилювати серця людей. Тільки істинний поет міг написати “Гамлета”. Шекспір розумна людина;

в) ні один чоловік, який дарує жінці плаття, не може бути недобрим. Акуратний чоловік повертається додому до вечері. Жінці нелегко слідкувати за одежею чоловіка, якщо повернувшись він кидає одежу де попало. Хороший чоловік завжди дарує своїй жінці плаття. Ні один чоловік не може не бути не добрим, якщо жінка не слідкує за його одежею. Неакуратний чоловік розкидає одяг. Хороший чоловік завжди повертається додому на вечерю;

г) я не називаю день нещасливим, якщо начальник не викликає мене. Четверги завжди бувають похмурими. Якщо люди беруть зонти, то день не буває сонячним. Єдиний день неділі, коли начальник мене викликає – четвер. Кожний візьме зонт, якщо йде дощ. Мої нещасливі дні завжди сонячні. Дощові дні похмурі;

д) “Ти мене поважаєш?” – “Так”. – “Тоді дай мені грошей”. – “Якщо я дам гроші, то перестану тебе поважати”. – “Ти мене поважаєш за гроші?” – “Ні, як актора”. – “Ну, тоді тим паче дай мені гроші”. – “Я даю лише тим, у кого вони є. Ти ж їх не віддаєш”. – “Позич під проценти”. – “Добре”;

е) “Цей костюм не вдягай, ти в ньому як бомж”. – “Але це плаття я теж не вдягну, бо воно на мені, як на вішалці”. – “Вдягни шкіряний піджак та спідницю”. – “Піджак весь у красці”. – “Це не біда, покрий краску сумкою”. – “Ні, я одягну сарафан, якщо ти не заперечуєш”. – “Заперечую, вдягай костюм”;

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

з) сьогодні я попаду на першу пару, якщо не затримається автобус. Автобус не запізнився, але в мене не було грошей на білет. Поїду “зайцем”. В салоні з’явився контролер. Контролер мене затримав, але потім відпустив. На першу пару я запізнився;

і) з твердження “два плюс два дорівнює три” слідує, що Ваня і Папа римський одне лице. Якщо від обох частин рівності відняти по одиниці, то буде справедлива рівність “три дорівнює двом”. Якщо знову відняти по одиниці, то буде справедлива рівність “два дорівнює одиниці”. Один це Ваня, два – Ваня і Папа римський. Оскільки вірно, що “один дорівнює двом”, Ваня – Папа римський;

к) якщо хмари – це гори в небі та гори – це хмари на землі, то гроза – це вулкан на небі і вулкан це гроза на землі. Вулкан викидає попіл, а гроза воду, які допомагають підняти врожайність. Врожай це благо. Все благо – від Бога. Отже, попіл, вода, вулкан, грози, хмари – все від Бога;

л) існує дві теорії виникнення людства на землі – теорія еволюції Дарвіна і теорія створення людини Богом. Якщо справедлива перша теорія, то людина виникла в результаті перетворення живих організмів. Як довели вчені, такі перетворення відбувалися. По теорії створення людини Богом вона була виліплена із глини, а життя вдихнув Господь. Глини завжди багато, а про дихання Бога сумніватися не приходиться, про це написано у Біблії. Отже – обидві теорії правильні;

м) сліпий та глухий пішли на прогулянку. “Дивися, спереду поле з помідорами, отже, ми поїмо”. – сказав глухий. “Але”. – сказав сліпий. “Послухай, десь гримить грім, напевно піде дощ” – сказав сліпий. “Ага” – сказав глухий. Вони набрали помідорів та відкрили парасольки. Все це бачив і чув німий. “Я їм не товариш” – сказав німий;

н) щоб зварити грибний суп, треба: гриби, морква, цибуля, картопля, пшоно. Моркви та пшона в нашому магазині не було. Все інше я купив. Проте, супу уже не зварити. Добре, куплю м’ясо і приготую котлети, відварю картоплю – друге уже є. На перше відварю грибний бульйон;

о) щоб назбирати грибів, треба зранку поїхати до лісу. Поїхати можна або електричкою, або автомобілем. Автомобілем швидше. Петро поїхав на автомобілі. По дорозі він зламався, Петро його відремонтував, але їхати в ліс було запізно. Грибів Петро не назбирав; п) щоб успішно здати екзамен, треба або вивчити весь матеріал, або підготувати шпаргалки, або вивчити і написати шпаргалки. Студент написав шпаргалки, проте забув їх удома. Екзамен не був зданий;

р) щоб приготувати каву, необхідно купити каву, цукор та мати нагріту воду. Петя купив каву, цукор, але була відсутня вода. Коли Петя приніс воду, згорів кип’ятильник. Петя приготував каву з холодної води;

с) якщо Джон не зустрічав вечором Сміта, то або Сміт був вбивцею, або Джон бреше. Якщо Сміт не вбивця, то Джон його не зустрічав вечором, і вбивство було після опівночі. Якщо вбивство було після опівночі, то або Сміт – вбивця, або Джон бреше. Отже, Сміт був вбивцею;

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

у) “Хочеш молока?” – “Молоко я не п’ю після риби, а рибу я не їм після борщу. Борщ я сьогодні не їв, але з’їв трохи гречаного супу. Після нього з’їв кусок риби. Якщо я їм гречаний суп, то в цей день не буду відмовлятися від молока, але при умові, що я не пив компоту. Отже, давай сюди молоко”;

ф) касир Іванова сказала, що вона бачила водія Петрова в кімнаті відпочинку. Ця кімната по її словам знаходиться поруч з приміщенням складу. Стріляли в складу. Водій заявив, що він пострілів не чув. Отже, якщо касир сказала правду, то водій обманює, не можуть касир й водій одночасно говорити правду;

х) мотоцикл я спочатку не побачив, так як його закривав бензовоз, а “Волга” вивернула із-за рогу, коли “Жигулі” були біля світлофору. Іномарка проскочила на “червоне світло” і стала, як мені здається причиною всієї аварії. Із-за неї “Волга” різко загальмувала і мотоцикліст впав на асфальт. “Жигулі”, щоб не задавити мотоцикліста, повернули на тротуар, а бензовоз в цей час врізався в “Волгу”. Якби не було мотоциклу, то такої ситуації не було б. Хоча винен і водій “Волги”, тому що він їхав дуже швидко.

13. Побудувати таблиці істинності на області інтерпретації

а);

б);

в);

г);

д);

е).

14. Довести еквівалентність формул:

а) та ;

б) та ;

в) та ;

г) та ;

д) та ;

е) та .

15. Встановити істинність логічного виразу шляхом конкретизації:

а);

б);

в);

г);

д);

е);

ж).

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

1);

2)

;

3);


4)
;

5);
.

17. Задана ПРОЛОГ-програма “Родинні зв’язки”. Необхідно виконати трасування програми окремо для двох цілей, вводячи предикати і правила. Так як може існувати декілька значень зміннихта, що задовольняють одній цілі, при трасуванні допустимо обмежитися одним істинним значенням х або у (приклад взятий з [1]). Окрім того, в зв’язку з великою кількістю повторних викликів, дозволяється вказувати лише перший і останній рядки викликів, які повторюються, наприклад:



81 В: чоловік (Фелікс) – 85,

82 П: чоловік (Фелікс) – 1,



99 П: чоловік (Фелікс) – 18,

100 У: чоловік (Фелікс) – 19.

ПРОЛОГ-програма “Родинні зв’язки”:

чоловік() – – чоловік,

жінка() – – жінка, дочкадочка,

батько– батько, син син,

мати – мама, батьки батько або мати,

сестра – сестра, братбрат.

Клаузи:

1) чоловік(Микола). 2) чоловік(Іван).

3) чоловік(Степан). 4) чоловік(Сергій).

5) чоловік(Павло). 6) чоловік(Ігор).

7) чоловік(Анатолій). 8) чоловік(Йосип).

9) чоловік(Роман). 10) чоловік(Кирило).

11) чоловік(Дмитро). 12) чоловік(Максим).

13) чоловік(Євген). 14) чоловік(Петро).

15) чоловік(Юхим). 16) чоловік(Юрій).

17) чоловік(Вадим). 18) чоловік(Олег).

19) чоловік(Фелікс). 20) жінка(Марія).

21) жінка(Ольга). 22) жінка(Тетяна).

23) жінка(Жанна). 24) жінка(Ірина).

25) жінка(Аліса). 26) жінка(Катерина).

27) жінка(Олена). 28) жінка(Вікторія).

29) жінка(Поліна). 30) жінка(Луїза).

31) жінка(Наталія). 32) жінка(Барбара).

33) жінка(Бела). 34) жінка(Ганна).

35) батько(Микола,Іван). 36) батько(Степан,Марія).

37) батько(Іван,Ольга). 38) батько(Іван,Сергій).

39) батько(Іван,Тетяна). 40) батько(Сергій,Вікторія).

41) батько(Павло,Роман). 42) батько(Сергій,Дмитро).

43) батько(Йосип,Ірина). 44) батько(Юхим,Анатолій).

45) батько(Юхим,Поліна). 46) батько(Юрій,Вадим).

47) батько(Петро,Юхим). 48) батько(Петро,Юрій).

49) батько(Петро,Ганна). 50) батько(Максим,Петро).

51) батько(Дмитро,Наталка). 52) батько(Фелікс,Олег).

53) батько(Олег,Євген). 54) мати(Аліса,Петро).

55) мати(Катерина,Олена). 56) мати(Олена,Юхим).

57) мати(Олена,Юрій). 58) мати(Олена,Ганна).

59) мати(Марія,Ольга). 60) мати(Ганна,Вікторія).

61) мати(Луїза,Євген). 62) мати(Тетяна,Поліна).

63) мати(Марія,Сергій). 64) мати(Ганна,Олег).

65) мати(Тетяна,Анатолій). 66) мати(Ганна,Дмитро).

67) мати(Вікторія,Бела). 68) мати(Марія,Тетяна).

69) мати(Ольга,Жанна). 70) мати(Ольга,Павло).

71) мати(Жанна,Ірина). 72) мати(Ірина,Ігор).

73) мати(Ірина,Кирило). 74) мати(Барбара,Роман).

75) род.батько . 76) род. мати .

77) синбатьки, чоловік.

78) дочкарод., жінка.

79) братрод., род., чоловік;.

80) сестрарод., род., жінка;.

Цілі:

1. Тесть(Фелікс,), племінник(Павло,).

2. Тьотя(Ганна,), внук(,Аліса).

3. Двоюрідний брат(Вадим,), внучка(,Сергій).

4. Дядько(Юхим,), свекруха(Марія,).

5. Невістка(,Максим), внук(,Ганна).

6. Племінниця(Жанна,), внук(Роман,).

7. Теща(Олена,), внучка(Бела,).

8. Теща(Марія,), свекор(,Олена).

9. Внук(Євген,), дядя(Юрій,).

10. Тітка(Тетяна,), двоюрідний брат(Дмитро,).

11. Зять(Петро,), тьотя(Ольга,).

12. Свекор(Петро,), внучка(Поліна,).

13. Свекруха(,Луїза), дядя(Сергій,).

14. Тесть(,Сергій), двоюрідний брат(Вадим,).

15. Теща(,Сергій), двоюрідний брат(,Вікторія).

16. Троюрідна сестра(,Бела), зять(Сергій,).

17. Племінник(Вадим,), внучка (Ірин,).

18. Невістка(Ганна,), двоюрідний брат(Вікторія,).

19. Невістка(Олена,), племінниця(Вікторія,).

20. Двоюрідна сестра(Жанна,), свекор(Іван,).

21. Троюрідна сестра(Наталія,), племінник(, Юхим).

22. Тесть (Петро,), троюрідний брат(Роман,).

23. Племінниця(,Сергій), зять(Юхим,).

24. Внучка(,Марія), двоюрідна сестра(Бела,).

25. Двоюрідна сестра(,Поліна), зять(,Петро).

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




ЗМІСТ