Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
дискретка_1.DOC
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
6 Мб
Скачать
☆

Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій

  1. T0 – клас функцій, які зберігають константу 0, тобто таких, що f(0, …, 0) = 0.

  2. T1 – клас функцій, які зберігають константу 1, тобто таких, що f(1, …, 1) = 1.

  3. S – клас самодвоїстих функцій, тобто таких, що f* = f, де f * – двоїста до функції f функція (f*( ) = ( )).

  4. M – клас монотонних функцій, тобто таких, що для довільних наборів , , для яких << (ai << i, i  {1, …, n}), f( )  f( ).

  5. L – клас лінійних функцій, тобто функцій, для яких поліном Жегалкіна має вигляд f*( ) = c0c1x1 c2x2  …  cnxn, ciE2.

Лема про самодвоїсту функцію. Якщо 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];

б) якщо M1M2, то [M1]  [M2];

в) [M1 M­2]  [M1] [M2];

г) [] = .

Розв’язування 1б). Якщо f, f1, f2, …, fs­M1, то  = f[f1, f2, …, fs]  [M1]. Оскільки M1M2, то f, f1, f2, …, fs­, …  M2 і тоді  = f[f1, f2, …, fs, …]  [M2]. Отже, якщо   [M1], то   [M2], тобто [M1]  [M2]. Тут скористалися таким означенням.

Нехай F = {f1, …, fm}, fiPn. Замиканням [F] називається множина всіх булевих функцій, які реалізуються формулами над F: [F] = {fPn | f = funcF [F]}.

Приклад 2. Зведенням до повних систем в P2 показати, що множина Q є повною системою в P2, де:

а) Q = {x1x2};

б) Q = {x1x2x3, (x1 ~ x2)  x3};

в) Q = {xy, (1100001100111100)};

г) Q = {xy, };

д) Q = {x ~ y, x / y};

е) Q = {0, m(x, y, z), xyz}, де m(x, y, z) = xyxzyz – функція, яка називається медіаною (або функцією голосування).

Розв’язування 2а). Розглянемо систему B = { , x1x2, x1x2}, яка повна, оскільки для будь-якої булевої функції можна записати ДДНФ, яка є формулою над системою B. Тоді за теоремою зведення система B1 = { , x1x2} – повна, тому що за законами де Моргана x1x2 = . Покажемо, що функції системи B1 можна записати у вигляді формули над системою Q = {x1x2}. Маємо = x1x1, x1x2 = =  ; x1x2 =  = (x1x1)  (x2x2).

Отже, за теоремою зведення система Q – повна.

Приклад 3. Зведенням до повних систем в P2 показати, що множина S є повною системою в P2, де:

а) S = {x1 / x2};

б) S = {0, 1, x1x2, x1 + x2}, де x1 + x2 =

Розв’язування 3а). Розглянемо систему функцій S = {x1 / x2}, яка складається з єдиної функції x1 / x2 = =  .

Маємо

x1 / x1 =  = ,

(x1 / x2) / (x1 / x2) = / = =  = x1x2.

Оскільки система B = { , x1x2, x1x2} повна за попереднім прикладом, то й система S – повна.

Розв’язування 3б). Розглянемо повну систему функцій B1 = { , x1x2} – оскільки за законами де Моргана x1x2 = . Покажемо, що функції системи S можна записати у вигляді формули над системою B1. Маємо

0 = x  , 1= = , x1 + x2 = , = 1  x, Отже, система S повна.

Приклад 4. Показати, що кількість лінійних функцій f( ), які істотно залежать від k змінних із множини {x1, x2, …, xn} дорівнює 2 , де = .

Приклад 5. Показати, що функцію xy не можна отримати із функцій f1 = xyz, f2 = x  1, f3 = xy за допомогою операцій суперпозиції.

Розв’язування. Запишемо для функції xy ДКНФ: xy =  y. Використаємо формули x1x2 = x1x2x1x2, = x  1, xx = 0. Тоді xy =  y = y   y = (x  1)y  (x  1)  y = xyx  1. Отже, xyL, а нелінійну функцію xy не можна побудувати у вигляді формули над системою {f1, f2, f3}.

Приклад 6. З’ясувати, чи можна із функції f за допомогою підстановки 0, 1, x1, x2, , отримати функцію x1x2:

а) f( ) = (x1x2)  ;

б) 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( ) = x1x2x1x2  1. Оскільки fL, то із леми про нелінійну функцію випливає, що за допомогою підстановки 0, 1, x1, x2, , у функцію, можна дістати кон’юнкцію x1x2.

Приклад 7. Довести, що fL тоді і тільки тоді, коли f змінює значення на будь-якій парі сусідніх за істотною змінною наборах.

Приклад 8. Якщо 1 і 2 – лінійні булеві функції, то чи будуть лінійними функції 12, , 12?

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

а) f( ) = (x1x2  )  x3;

б) f( ) = x1x2 (x1x2);

в) f( ) = x2x3x4x1 ;

г) f( ) = ((x1x2)(x2x1)) ~ 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. З’ясувати, чи можна функцію xy реалізувати формулою над множиною функцій Ф, де:

а) Ф = L {xyxzzy};

в) Ф = (L {xyyzzx}) \ S;

б) Ф = L \ S;

г) Ф = (L {xy}) \ S.

Розв’язування 11а). Розглянемо функцію f(x, y, z) = xy xz zy  . Оскільки 1  L, то будуємо формулу f1(x, 1, z) = xxzz = xz. Функція x  1 =  L, і тому можна побудувати формулу f1(x  1, 1, z) = (x  1)  z =  z = xz. Знову функція z = yL, і тоді дістанемо формулу f1(x  1, 1, y) = xy, тобто дану функцію xy реалізуємо формулою над множиною Ф.