ЗАДАЧІ ТА ВПРАВИ ДО РОЗДІЛІВ

Задачі і вправи до розділу «ПОНЯТТЯ ТА ОПЕРАЦІЇ З НИМИ»

Методи завдання множин

Визначення: Інтуїтивне поняття множини. Нехай Р(х) означає деяку властивість, тоді Р(а) буде означати ту саму властивість, а й з заміною х на а.

Інтуїтивний принцип абстракції, або аксіома згортання. Всяка властивість Р(х) визначає деяку множину А за допомогою такої умови: елементами множини А є ті і лише ті предмети а, які мають властивість Р.

2. Чи є властивостями множин наступні вирази:

а) для всіх х, у ху = ух; Ь) існує таке х, що 2x < 0

Операції над множинами

Приклади вирішення задач до розділу «Операції над множинами (поняттями)»

1. Чи є множина А = {а, Ь, с} підмножиною множини В = {a, b, с, d, е}?

Розв’язок. Множина А = {а, Ь, с} є власною підмножиною множини В = {а, Ь, с, d, е}.

2. Чи є множина студентів юридичного факультету підмножиною множини всіх студентів університету?

Розв’язок. Множина студентів юридичного факультету - підмножина множини всіх студентів університету.

3. Чи є множина парних натуральних чисел власною підмножиною множини всіх натуральних чисел?

Розв’язок. Множина парних натуральних чисел є власною підмножиною множини всіх натуральних чисел.

4. Чи є множина натуральних чисел підмножиною множини всіх цілих чисел, а множина цілих чисел - підмножиною множини всіх раціональних чисел?

Розв’язок. Множина натуральних чисел є підмножиною множини всіх цілих чисел, а множина цілих чисел - підмножиною множини всіх раціональних чисел.

Визначення: Нехай U - деяка множина. Тоді B(U) - множина всіх підмножин множини U. У цьому випадку множину U називають універсальною, а множину B(U) - множиною-степенем або булеаном 7. Яке нове утворення матимемо при об’єднанні А - множини прямих, які проходять через точку а деякої площини, В - множини прямих, які проходять через точку C цієї ж площини.

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

Задачі і вправи до розділу «Алгебра множин (числення понять)»

Задачі і вправи до розділу

«ПОНЯТТЯ, ОПЕРАЦІЇ НАД МНОЖИНАМИ»

Основні визначення та приклади вирішення задач до РОЗДІЛУ

«Тотожна істинність формул дедуктивних умовиводів»

Основні визначення

Застосування союзу і при побудові висловлень зветься кон’юнкцією.

Форма запису таблиці істинності кон’юнкції:

Якщо істині висловлення, які складають, кон’юнкцію, то кон’юнкція істина, і навпаки, якщо кон’юнкція істина, то істина кожна її складова.

складова.

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

Форма запису таблиці істинності імплікації:

Коли обидві посилки вірні, то висновок вірний. Якщо одна з посилок зрадлива, то і весь алгоритм зрадливий.

Диз’юнкція завжди є комунікативною. Вона характерна спілкою або.

Фоцма запису таблиці істинності диз’юнкції:

Диз’юнкція істина тоді, коли один з її членів є істинним.

Закон, що характеризує еквівалентність Форма таблиці істинності еквівалентності:

Закони де-Моргана

3. [Не (р або q)] тоді і лише тоді, коли [(не р) і (не q)].

4. [Не (q і не р)] тоді і лише тоді, коли [(не р або не q)].

Обидва закони мають численні застосування, у першу чергу при підстановках.

Визначення. Літерою називається атом або заперечення атома. Диз’юнктом називається диз’юнкція літер. Одиничним диз’юнктом називається однолітерний диз’юнкт. Якщо диз’юнкт не має жодної літери, то він називається пустим диз’юнктом і позначається 0. Літери L і називаються контрарними.

Правило тавтології (ДП1). Викреслити всі тавтологічні диз’юнкти із S. Множина диз’юнктів S∣, що залишились, суперечна тоді і лише тоді, коли S суперечна.

Правило чистих літер (ДПЗ). Літера L деякого диз’юнкта з S називається чистою в S тоді і лише тоді, коли літера не з’являється ні в якому диз’юнкті з S.

Правило розщеплення (ДП4). Якщо множину S можна подати у

Задачі і вправи до розділу

«Тотожна істинність формул дедуктивних умовиводів»

219

15.

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

a) Я піду до дому (H) або залишусь тут і послухаю музику (S). Я не піду до дому. Значить, я залишусь тут і послухаю музику.

b) Якщо Джон ляже спати сьогодні пізно (S), він буде вранці не в формі (D). Якщо він ляже спати не пізно, то йому буде здаватися, що не варто жити (L). Значить, або Джон завтра буде не в формі, або йому здаватиметься, що йому не варто жити.

c) Заробітна плата зросте на (W), якщо буде інфляція (J). Якщо буде інфляція, то збільшиться вартість життя (C). Заробітна плата зросте. Значить збільшиться вартість життя.

d) Якщо 2 - просте число (P), то це найменше просте число (L). Якщо 2 - найменше просте число, то 1 не є простим числом (N). Число 1 не є простим числом. Значить, 2 - просте число.

e) Джон або перевтомився (E), або хворий (S). Якщо він перевтомився, то він дратується (C). Він не дратується. Значить він хворий.

1) Якщо я поїду автобусом (В), а автобус запізниться (L), то я пропущу важливе побачення (M). Якщо я пропущу важливе побачення я почну засмучуватись (D), то мені не слід їхати до дому (H). Якщо я не отримаю цієї роботи (І), то я почну засмучуватись і мені треба поїхати до дому. Значить, якщо я поїду автобусом і автобус запізниться, то я отримаю цю роботу.

g) Якщо 6 - складне число (S), то 12 - складне число (W). Якщо 12 - складне число, то існує росте число, то існує просте число, більше, ніж 12 (P). Якщо існує просте число, більше, ніж 12, то існує складне число більше 12 (C). Якщо 6 ділиться на 2 (D), то 6 - складне число. Число 12 складне. Отже, 6 - складне число.

h) Якщо завтра буде холодно (C), я одягну тепле пальто (H), якщо рукав буде полагоджений (S). Завтра буде холодно, а рукав не буде полагоджений, значить, я не одягну тепле пальто.

17. Нехай Р(х) означає “х - просте число”, Е(х) - “х - парне число”, О(х) - “непарне число”, D(x, у) - “у ділиться на х”. Перекладіть такі формулилогіки предикатів першого порядку:

18. Нижче наведено п’ять речень українською мовою, за якими йде стільки ж речень символічної мови предикатів першого порядку. Знайдіть відповідні пари речень, так що кожний член пари був перекладом члена, який йому відповідає.

Застосування логічної побудови контактних схем в СИМВОЛІЧНІЙ ЛОГІЦІ ВИСЛОВЛЮВАНЬ

Приклади вирішення задач

1. Побудувати контактну схему висловлення, яка складається з трьох змінних, має таблицю істинності 11101000. Її основні кон’юнкції надані в таблиці 1.

Таблиця 1

Схема задовольняє такій умові: вона проводить струм тоді і лише тоді, коли замкнуті, принаймні, два з трьох контактів.

2. Використовуючи таблицю 1, побудувати схему з трьома незалежними контактами, яка проводить струм якщо замкнуті лише два контакти.

Розв’язок. Формула, що відповідає даній схемі приймає значення істина тоді і лише тоді, коли це значення приймають дві з трьох змінних, р, q, r. Це відповідає другому третьому і п’ятому рядкам

При рішенні такого роду задач приймемо метод синтезу (побудови) контактної схеми по їх характеристиках.

3. Визначити умови роботи заданої схеми. Знайти, при яких положеннях контактів (рис.

Задачі та вправи

1. Використовуючи основні послідовно сполучені схеми, побудуйте мережі відповідним формулам:

2. Накреслити схему, що відповідає формулі

3. Побудувати мережу, що відповідає формулі

4. Побудуйте формулу схеми, яка зображення на рис. 5.

5. Побудуйте схеми, які відповідають формулі:

6. Побудуйте схему, що відповідала б таблиці з набором значень 10110100.

7. Машина - екзаменатор дає сигнал «залік» (запалюється лампочка) тоді і лише тоді, коли студент відповідає правильно хоча б на два з трьох питань квитка. При запровадженні в машину правильної відповіді замикається контакт у ланцюзі сигнальної лампочки. Побудуйте схему й опишіть її за допомогою правил логіки висловлень.

8. Складіть формулу, що відповідає приведеній на рис. 6 схемі:

г

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

10. Побудуйте й опишіть за допомогою правил логіки висловлень схему «електрифікованої версії» гри з моментами: «По встановленому сигналу кожен гравець замикає або розмикає перемикач, яким він управляє. Якщо обидва роблять те саме, то виграє гравець А; якщо ж вони роблять протилежне те виграє гравець В». У схему введіть джерело току і лампочку. Побудуйте таку схему, щоб у випадку, коли виграє А, запалювалося світло.

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

12. Складіть схему з трьома незалежними контактами, котра замкнута тоді і лише тоді, коли: а) замкнуті не більш чим два контакти; Ь) замкнутий лише один контакт; с) розімкнутий лише один контакт.

13. Потрібно, щоб у кімнаті можна було включити і виключити світло

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

14. Комітет, який складається з трьох чоловік, включно й голову, приймає рішення більшістю голосів, однак рішення не може бути прийняте, якщо за нього не проголосував голова. Голосування “за” проводиться натиском кнопки, яка замикає контакт. У випадку прийняття рішення замигається лампочка. Побудуйте схему, яка відповідає наведеним умовам.

15. Доведіть, що з’єднання S кінцевої кількості функціональних елементів φι,... φ_m є схемою тоді і лише тоді, коли:

a) серед елементів фі є один і лише один елемент з вільним виходом не з’єднаним ні з яким із входів елементів φ_j∙ (на кожному з виходів реалізується власна функція алгебри логіки);

b) ВХІД КОЖНОГО 3 елементів фі може бути з’єднаний не більш чим з одним із виходів елементів Φj.

c) в S немає зворотних зв’язків.

16. Визначити умови роботи схеми, яка задана формулою:

Знайти, при яких положеннях контактів струм буде проходити або не проходити.

17. Чи отримаємо повну систему, якщо приєднаємо до елемента ф, який реалізує функцію Шеффера ху елементи, котрі реалізують константи.

18. Побудувати таблицю істинності формули:

г). Визначити умови, при яких ланцюг буде проводити струм.

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

Елементи теорії графів в системі числення понять.

Основні визначення, задачі та вправи

Основні визначення

E ⊂ V*-²∖ Всякий граф є мультиграфом, але не всякий мультиграф буде графом. Якщ(- мультиграф, то E може мати кілька ребер, що

з’єднують одні і ті ж вершини u і V. Такі ребра називаються кратними ребрами.

Два ребра називаються суміжними, якщо вони мають спільний кінець.

Вершина u і ребро е називаються інцидентними, якщо u є кінцем ребра е, і неінцидентними в протилежному випадку.

Степенем n(u) вершини u графа G називається число інцидентних їй ребер. Вершина степені 0 називається ізольованою, а вершина степені 1 - висячою, або кінцевою. Ребро, інцидентне кінцевій вершині, також називається кінцевим.

Якщо G = (V, Е) - скінчений граф порядку п, то йому відповідає квадратна матриця A(G) розмірності п * п, яка називаєтьяс матрицею

суміжності

Приклад визначення ребер і вершин графа за допомогою матриці суміжності

Всяка квадратна матриця, елементи якої Oil, буде матрицею суміжності орієнтованого графа. Ранги матриць суміжностей ізоморфних графів рівні між собою.

називаєтьяс матрицею інцидентності, вона задовольняє таким умовам

Задачі і вправи

Необхідно:

a) задати граф геометричним способом;

b) знайти матрицю суміжності;

c) визначити степені вершин графа.

2. Задано неорієнтований граф (рис. 8).

Необхідно:

a) знайти матрицю суміжності

b) визначити степені вершин графа;

3. Орієнтований граф G = (V,E,O) заданий аналітичним способом.

Необхідно:

a) задати граф геометричним способом;

b) знайти матрицю інцидентності;

c) визначити полу-степені вершин графа.

4. Задано орієнтований граф (рис. 9).

Необхідно:

a) знайти матрицю інцидентності;

b) визначити полу-степені вершин графа.

5. Знайти найкоротший шлях у графі G (рис. 10) між вершинами x_i і x_i0.

6. Знайти остовне дерево найменшої ваги для графа з задачі №5.

7. Вирішити задачу комівояжера, якщо задана матриця відстаней

8. Знайти максимальну течію у мережі (рис. 11).

9. Нехай V - множина додатних цілих чисел від 1 до 20 і а|Ь - відношення подільності, тобто а|Ь означає, що число а є дільником числа Ь. Намалюйте граф відношення а|Ь для множини V.

10. Побудуйте матриці суміжності та інцидентності для платонових графів.

11. Нехай G - регулярний граф порядку п і степеня d. Покажіть, що

12. 1 раф називається критичним, якщо вилучення будь-якої його вершини приводить до графа з меншим хроматичним числом. Доведіть, що:

a) K_n є критичним для всіх п > 1;

b) C_n критичний тоді, і лише тоді, коли п непарне;

c) якщо п непарне, то з’єднання C_n і C_n є критичним графом, хроматичне число якого дорівнює 6.

13. Знайдіть Ейлерів ланцюг для графа, зображеного на рис. 12.

14. Побудуйте граф, множина вершин котрого відповідає множині курсів навчання, котрі вам необхідно пройти для отримання ступеня бакалавра. При цому, дугу от вершини х до вершини у включайте в граф лише в тому випадку, якщо курс х попередній від курсу у. Інтерпретуйте наступні елементи побудови графа:

а) путь, Ь) ланцюг, с) цикл,сІ) контур,

d) зв’язану компоненту.

15. Степінь входження d (x) вершини х визначається як число дуг, які заходять у вершину х. Степінь сходу d⁺(x) вершини х визначається як число дуг, які починаються у вершині х. Степінь d(x) вершини х визначається як сума степеней входження та сходу для даної вершини. Покажіть, що в будь-якому графі G кількість вершин з непарним степенем парно. Покажіть, що для будь-якого графа G = (X, А) має місце співвідношення

16. Нехай T - дерево, яке покриває для графа G. Покажіть, що в G для будь-яких двох вершин існує єдиний ланцюг, який складається лише із ребер дерева Т.

17. Чи можливо, щоб розтин і цикл вміщували в точності загальну дугу? Якщо неможливо, то чому?