МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний авіаційний університет Контрольна робота З Дискретної математики Студент[ім’я автора приховано] Спеціальності 6.050.101 № (залікової книжки)090271 [ім’я автора приховано]а 2011 р. Машина Тюрінга Завдання №1 Скласти програму для машини Тюрінга, яка б додавала двійку до натурального числа. Прокоментувати написану програму. S (n) =n+2; n ϵ N Q ={q0,q1,q2……} – множина станів. Число n на стрічці записується в десятинній системі числення. Стан q1 заміняє останню цифру числа n: Якщо ця цифра менше 8-ми, цифрою на дві одиниці більше та переходить в стан зупинки; Якщо ця цифра дорівнює 8-ми, то її заміняє на нуль и переходить вліво в стан q2. Стан q2 додає до слідуючого розряду одиницю. Якщо ж остання цифра числа дорівнює 9-ти, то він її замінить на 1 та переходить вліво в стан q2. Розв’язок S (n) =n+2; n ϵ N (X = {0,1,2,…..,9},Q= { q0,q1,q2,q3}, q0, #,P), де P має такий вигляд: Складемо алгоритм, за яким потім побудуємо приклади, що відповідають умові завдання: цей алгоритм показує що ми з кожним разом рухаємося вправо, лише прочитуючи клітинку та залишаючи значення в клітинці незмінним. цей алгоритм показує що ми з кожним разом читаємо число що знаходиться в клітинці, додаємо як дано в умові до нього двійку та рухаємося на одну клітинку вліво.
читання пустої клітинки та рух вліво на одну клітинку Машина читає число в клітинці заміняє його на одиницю, за умови що число від 1 до 8 , якщо воно рівне 9-ти то заміняє на нуль, при цьому кожний раз рухається на одну клітинку вліво Отже наведемо приклади машин Тюрінга для таких чисел: 569 та 1088.При чому машина повинна виконувати умову завдання, тобто S (n) =n+2; n ϵ N Число 569
Число 1088
Числення висловлювань Завдання №2
Завдання №3 Спростити вираз (1→¬a) \/ (0→b) /\(1→c) Спростимо вираз за допомогою закону:

Завдання №4 Виписати всі комбінації логічних значень змінних, для яких буде хибною формула ((x \/ y) /\ ((y \/ z) /\ (z \/ x)))→ ((x/\y) /\z) Формула
побудована з трьох простих формул (x,y і z). Отже, існує вісім можливих комбінацій логічних значень для (x,y і z) .
Знайдемо ж такі логічні значення змінних, для яких формула і буде хибною. Для цього перевіримо всі 8-ім можливих комбінацій значень формул (x,y і z) при різних значеннях нульарних операцій, тобто значень нуля та одиниці. Отже… Перевіривши складену таблицю, ми бачимо що формула є хибною для таких комбінацій змінних формул (x,y і z): № 5 – коли формули мають такі значення: x=1; y=0; z=1; № 6 – коли формули мають такі значення: x=1; y=1; z=0; № 7 – коли формули мають такі значення: x=0; y=1; z=1; Теорія графів Завдання №5 Ребро (1,2) (1,4) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) (4,6) (5,6)  Довжина 3 7 2 3 4 6 2 1 1 2   Побудувати дерево найменшої довжини на графі і підрахувати суму довжин ребер дерева – довжина ребра; - Вершина графа Побудова дерева найменшої довжини ,за допомогою алгоритму Краскала Початкова фаза - ліс складається з кореня (вершини ребра) та пустої множини (мал. 1) Обираємо ребро найм. довжини – це ребро (4,6),довжина котрого =1(мал. 2) Обираємо наступне ребро найм. довжини – це ребро (4,5) (мал. 2)
Додаємо ребро (3,5) (мал. 3)
Додаємо ребро (3,2) (мал. 4)
Додаємо ребро (1,2). Дерево побудовано. Всі 6-ть вершин використані при побудові. (Мал. 5)
Сума довжин ребер = 1+1+2+2+3=9 Завдання №6 Правильно пофарбувати чотирма фарбами вершини графа Ребро (1,2) (1,4) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) (4,6) (5,6) (1,6) (2,6)   Завдання №7 1- ий спосіб
2- ий спосіб
1) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 2) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 3) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 4) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( Враховуючи транспозиції елементів (фарб) отримаємо 8 різних правильних розфарбовувань даного графа. (, (, (, ( – фарби.