- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
T0 – клас функцій, які зберігають константу 0, тобто таких, що f(0, …, 0) = 0.
T1 – клас функцій, які зберігають константу 1, тобто таких, що f(1, …, 1) = 1.
S – клас самодвоїстих функцій, тобто таких, що f* = f, де f * – двоїста до функції f функція (f*(
)
=
(
)).M – клас монотонних функцій, тобто таких, що для довільних наборів
,
,
для яких
<<
(ai
<< i,
i
{1, …, n}),
f(
)
f(
).L – клас лінійних функцій, тобто функцій, для яких поліном Жегалкіна має вигляд f*( ) = c0 c1x1 c2x2 … cnxn, ci E2.
Лема про самодвоїсту функцію. Якщо f S, то з неї шляхом підстановки на місця її змінних функцій x і можна отримати константу.
Лема
про нелінійну функцію.
Якщо
f
L,
то з неї шляхом підстановки на місця її
змінних функцій 0, 1, x,
,
y,
можна отримати або x
& y,
або
.
Лема про немонотонну функцію. Якщо f M, то з неї шляхом підстановки на місця її змінних функцій 0, 1, x можна отримати функцію .
Теорема Поста про функціональну повноту. Система функцій P = {f1, f2, …} повна в P2 тоді і тільки тоді, коли вона цілком не міститься в жодному з класів T0, T1, S, M, L.
Приклад 1. Довести такі властивості замикання:
а) [[M]] = [M];
б) якщо M1 M2, то [M1] [M2];
в) [M1 M2] [M1] [M2];
г) [] = .
Розв’язування 1б). Якщо f, f1, f2, …, fs M1, то = f[f1, f2, …, fs] [M1]. Оскільки M1 M2, то f, f1, f2, …, fs, … M2 і тоді = f[f1, f2, …, fs, …] [M2]. Отже, якщо [M1], то [M2], тобто [M1] [M2]. Тут скористалися таким означенням.
Нехай F = {f1, …, fm}, fi Pn. Замиканням [F] називається множина всіх булевих функцій, які реалізуються формулами над F: [F] = {f Pn | f = funcF [F]}.
Приклад 2. Зведенням до повних систем в P2 показати, що множина Q є повною системою в P2, де:
а) Q = {x1 x2};
б) Q = {x1x2 x3, (x1 ~ x2) x3};
в) Q = {x y, (1100001100111100)};
г)
Q
= {x
y,
};
д) Q = {x ~ y, x / y};
е) Q = {0, m(x, y, z), xy z}, де m(x, y, z) = xy xz yz – функція, яка називається медіаною (або функцією голосування).
Розв’язування
2а).
Розглянемо систему B
= {
,
x1
x2,
x1x2},
яка повна, оскільки для будь-якої булевої
функції можна записати ДДНФ, яка є
формулою над системою B.
Тоді за теоремою зведення система B1
= {
,
x1x2}
– повна, тому що за законами де Моргана
x1
x2
=
.
Покажемо, що функції системи B1
можна записати у вигляді формули над
системою Q
= {x1
x2}.
Маємо
= x1
x1,
x1
x2
=
=
;
x1x2
=
= (x1
x1)
(x2
x2).
Отже, за теоремою зведення система Q – повна.
Приклад 3. Зведенням до повних систем в P2 показати, що множина S є повною системою в P2, де:
а) S = {x1 / x2};
б)
S
= {0,
1, x1
x2,
x1
+
x2},
де x1
+ x2
=
Розв’язування 3а). Розглянемо систему функцій S = {x1 / x2}, яка складається з єдиної функції x1 / x2 = = .
Маємо
x1 / x1 = = ,
(x1
/ x2)
/ (x1
/ x2)
=
/
=
=
= x1
x2.
Оскільки система B = { , x1 x2, x1 x2} повна за попереднім прикладом, то й система S – повна.
Розв’язування 3б). Розглянемо повну систему функцій B1 = { , x1x2} – оскільки за законами де Моргана x1 x2 = . Покажемо, що функції системи S можна записати у вигляді формули над системою B1. Маємо
0
= x
,
1=
=
,
x1
+ x2
=
,
= 1
x,
Отже, система S
повна.
Приклад
4.
Показати, що кількість лінійних функцій
f(
),
які істотно залежать від k
змінних із множини {x1,
x2,
…, xn}
дорівнює 2
,
де
=
.
Приклад 5. Показати, що функцію x y не можна отримати із функцій f1 = x y z, f2 = x 1, f3 = x y за допомогою операцій суперпозиції.
Розв’язування. Запишемо для функції x y ДКНФ: x y = y. Використаємо формули x1 x2 = x1x2 x1 x2, = x 1, x x = 0. Тоді x y = y = y y = (x 1)y (x 1) y = xy x 1. Отже, x y L, а нелінійну функцію x y не можна побудувати у вигляді формули над системою {f1, f2, f3}.
Приклад 6. З’ясувати, чи можна із функції f за допомогою підстановки 0, 1, x1, x2, , отримати функцію x1x2:
а) f( ) = (x1 x2) ; |
б) f( ) = (1 0 0 1 1 0 0 1); |
в) f( ) = (1 1 1 0 1 0 0 0); |
г) f( ) = (0 1 1 1 1 1 1 1). |
Розв’язування 6а). Запишемо поліном Жегалкіна для даної функції: f( ) = x1x2 x1 x2 1. Оскільки f L, то із леми про нелінійну функцію випливає, що за допомогою підстановки 0, 1, x1, x2, , у функцію, можна дістати кон’юнкцію x1x2.
Приклад 7. Довести, що f L тоді і тільки тоді, коли f змінює значення на будь-якій парі сусідніх за істотною змінною наборах.
Приклад
8.
Якщо 1
і 2
– лінійні булеві функції, то чи будуть
лінійними функції 1
2,
,
1
2?
Приклад 9. Розкладаючи функцію в поліном Жегалкіна, з’ясувати, чи вона лінійна:
а) f( ) = (x1x2 ) x3;
б) f( ) = x1x2 (x1 x2);
в) f( ) = x2 x3 x4 x1 ;
г) f( ) = ((x1 x2)(x2 x1)) ~ x3;
д) f( ) = (x1 ) ~ (x3 );
е) f( ) = ( / x2) ( ).
Приклад 10. З’ясувати, чи є лінійною функція f:
а) f( ) = (1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0);
б) f( ) = (1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1).
Приклад 11. З’ясувати, чи можна функцію x y реалізувати формулою над множиною функцій Ф, де:
а) Ф = L {xy xz zy}; |
в) Ф = (L {xy yz zx}) \ S; |
б) Ф = L \ S; |
г) Ф = (L {xy}) \ S. |
Розв’язування 11а). Розглянемо функцію f(x, y, z) = xy xz zy . Оскільки 1 L, то будуємо формулу f1(x, 1, z) = x xz z = x z. Функція x 1 = L, і тому можна побудувати формулу f1(x 1, 1, z) = (x 1) z = z = x z. Знову функція z = y L, і тоді дістанемо формулу f1(x 1, 1, y) = x y, тобто дану функцію x y реалізуємо формулою над множиною Ф.
