9.4 Контрольні запитання та завдання

1. Запишіть структуру алгебри Жегалкіна.

2. Назвіть основні закони алгебри Жегалкіна.

3. Запишіть тотожності, які дозволяють виразити основні операції булевої алгебри в алгебрі Жегалкіна.

4. Дайте визначення поняття "поліном Жегалкіна".

5. Які булеві функції називаються лінійними?

6. Скільки різноманітних поліномів Жегалкіна можливо побудувати для довільної булевої функції?

7. Сформулюйте правило побудови поліному Жегалкіна.

9.5 Приклади аудиторних і домашніх задач

1. Запишіть у вигляді поліному Жегалкіна такі функції:

a) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .

2. Доведіть, що функція заперечення лінійна.

3. Чи є лінійною функції:

а) y= ₁x₂x₃;

б) у=(х₁х₂ _{1 2})х₃;

в) y=(x₁х₂)х₃;

г) у=(х₁~х₂)х₃ ?

10 Практичне заняття № 8. Функціональна повнота наборів булевих функцій

10.1 Мета заняття

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

10.2 Методичні рекомендації до самостійної роботи студентів

Під час підготовки до практичного заняття крім конспекту лекцій рекомендується використовувати [1, c. 145-155; 2, c. 145-155; 3, c. 55-61; 9, c. 56-59; 12, c. 55-62; 17, c. 23-63].

При вивченні й повторенні матеріалу слід звернути увагу на такі питання:

• функціональна повнота набору булевих функцій;

• методи визначення повноти набору булевих функцій;

• лінійна булева функція;

• самодвоїста булева функція;

• монотонна булева функція;

• булева функція, яка зберігає 0;

• булева функція, яка зберігає 1;

• теорема Поста про функціональну повноту набору булевих функцій;

• використання теореми Поста.

10.3 Приклади розв’язання типових завдань

1. З’ясуйте, чи зберігає 0 і 1 функція імплікації f(x,y)=x y.

Побудуємо таблицю істинності імплікації (табл. 10.1).

Таблиця 10.1

x	y
0	0	1
0	1	1
1	0	0
1	1	1

На наборі значень аргументів (0,0) функція приймає значення 1, тобто f(0,0)=1. Отже, функція імплікації не зберігає 0.

На наборі (1,1) функція приймає значення 1, тобто f(1,1)=1. Отже, функція імплікації зберігає 1.

2. З’ясувати, чи є самодвоїстою функція диз’юнкції.

Знайдемо функцію, двоїсту до функції диз’юнкції:

.

Умова самодвоїстості не виконується вказаною функцією, тобто f^*(x,y)f(x,y), отже, функція диз’юнкції несамодвоїста.

3. Дослідити на монотонність функції f(x,y)=xy, g(x,y)=xy.

Для функції f(x,y) запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на цих наборах і порівняємо їх:

(0,0)(0,1), f(0,0)=0, f(0,1)=0, f(0,0)f(0,1).

(0,0)(1,0), f(0,0)=0, f(1,0)=0, f(0,0)f(1,0).

(0,0)(1,1), f(0,0)=0, f(1,1)=1, f(0,0)f(1,1).

(0,1)(1,1), f(0,1)=0, f(1,1)=1, f(0,1)f(1,1).

(1,0)(1,1), f(1,0)=0, f(1,1)=1, f(1,0)f(1,1).

Висновок: функція f(x,y)=xy є монотонною.

Аналогічно проводимо дослідження функції g(x,y).

(0,0)(0,1), g(0,0)=0 g(0,1)=1, g(0,0)g (0,1).

(0,0)(1,0), g(0,0)=0 g(1,0)=1, g(0,0)g(1,0).

(0,0)(1,1), g(0,0)=0 g(1,1)=0, g(0,0)g(1,1).

(0,1)(1,1), g(0,1)=1 g(1,1)=0, g(0,1)g(1,1).

Висновок: функція g(x,y)=xy не є монотонною.

4. Використовуючи теорему Поста, довести повноту системи функцій xy, .

Заданий набір булевих функцій містить:

1) нелінійну функцію – кон’юнкцію, оскільки f(x,y)=xy;

2) немонотонну – заперечення, оскільки з того, що 1≥0, не випливає, що f(1)≥f(0);

3) функція заперечення не зберігає ні 0, ні 1, оскільки f(0)=1, f(1)=0;

4) функція кон’юнкції несамодвоїста, оскільки .

Отже, заданий набір булевих функцій є повним.