Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
Приклад 1. За допомогою еквівалентних перетворень привести до ДНФ (диз’юнктивної нормальної форми) формулу:
а) f = (x1 x2 )(x1 x3);
б) f = (x2 ~ x1x3) ;
в) f = ((x1 x2 )(( x4) x1 ) x2x3) ( x4);
г) f = ((x1 x2x3)(x2x4 x3) x1 ) .
Розв’язування 1а). Скористаємося властивістю дистрибутивності для диз’юнкції відносно кон’юнкції: (x1 x2)(x1 x3) = x1 x2x3. Маємо
f = (x1 x2 )(x1 x3) = x1x1 x1x3 x2 x1 x2 x3 = x1 x1x3 x1x2 = x1(1 + x3 + x2 ) = x1.
Розв’язування 1б). Функція x1 ~ x2 набуває значення 1 на наборах (0, 0) та (1, 1). Якщо для неї записати ДДНФ (досконалу диз’юнктивну нормальну форму), то x1 ~ x2 = x1x2. Аналогічно x1 x2 набуває значення 1 на наборах (0, 1) , (1, 0) і відповідно ДДНФ має вигляд x1 x2 = x2 x1 . Тому, використовуючи закони де Моргана, отримаємо
f(
)
= (x2
~ x1x3)
= (
x1x2x3)
=
= ( ( ) x1x2x3) = ( x1x2x3) =
=
(
)
(
x1x2x3)
=
=
(
(
x1x2x3)(x2
x3)
=
= (x1 x2)(x2 x3)( ) x1x2x3 x3 =
= ( )(x1x3 x2) x1x2x3 x3 =
= (x2 x2 x1x3) x1x2x3 x3 = x1x2x3 x3.
Приклад 2. Розкласти за змінними x1, x2 функції
а) f( ) = (x1 / ) (( x4) x3);
б) f( ) = ( ~ x3) ( );
в) f( ) = ( x1 ) ~ ((x4 / ) x3).
Розв’язування 2а). Оскільки n = 4, m = 2, то розвинення за змінними x1, x2 має вигляд
f( ) = f(0, 0, x3, x4) x2f(0, 1, x3, x4) x1 f(1, 0, x3, x4) x1x2f(1, 1, x3, x4).
Обчислимо окремо коефіцієнти розвинення:
f(0, 0, x3, x4) = (0 / ) (( x4) x3) = 1 1 ((1 x4) x3) =
= 1 ((0 ) x3) = 1 (0 x3) = 1;
f(0, 1, x3, x4) = (0 / ) (( x4) x3) = 0 ((1 x4) x3) = 0 x3 = 1;
f(1, 0, x3, x4) = (1 / ) (( x4) x3) = x3 1 ((0 x4) x3) =
= x3 ( x3) = x3;
f(1, 1, x3, x4) = (1 / ) (( x4) x3) = 0 ((0 x4) x3) = x3.
Отже,
f( ) = x2 x1 ( x3) x1x2f( x3).
Розв’язування 2б). Оскільки n = 3, m = 2, то розвинення за змінними x1, x2 має вигляд
f( ) = f(0, 0, x3) x2f(0, 1, x3) x1 f(1, 0, x3) x1x2f(1, 1, x3).
Обчислимо окремо коефіцієнти розвинення:
f(0, 0, x3) = ( ~ x3) ( ) = (1 ~ x3) (1 ) = 1 x3 = 0 = 0;
f(0, 1, x3) = ( ~ x3) ( ) = (0 ~ x3) (1 ) = 0 x3 = 1 = ;
f(1, 0, x3) = ( ~ x3) ( ) = (1 ~ x3) (0 ) = 1 1= 0;
f(1, 1, x3) = ( ~ x3) ( ) = (0 ~ x3) (0 ) = 0 1= 0.
Отже, f( ) = x2 .
Приклад 3. Зобразити у вигляді ДДНФ і ДКНФ такі функції
а) f( ) = (x1 x1) x2x3; б) f( ) = (x2 / ) ( ); в) f( ) = (x1 x2)(x2 x1) ~ ; |
г) f( ) = x1x2 (x1 x2) x1; д) f( ) = (01101100); е) f( ) = (10001110). |
Розв’язування 3а). Побудуємо таблицю істинності функції f:
x1 |
x2 |
x3 |
p = x1 x2 |
q = x2x3 |
f = p q |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
Функція f( ) = 1 на наборах (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 0), (1, 1, 1). Тому відповідна ДДНФ функції має вигляд
f(
)
=
x3
x2x3
x1x2
x1x2x3.
Функція
f(
)
= 0
на наборах (0, 1,
0), (1,
0, 0),
(1,
0,
1).
Тому вона має таку ДКНФ f(
)
= (
)(
)(
)
=
= (x1 x3)( x2 x3)( x2 ).
Розв’язування 3г). Побудуємо таблицю істинності функції f:
x1 |
x2 |
p = x1 x2 |
q = x1x2 |
r = p x1 = p + x1 |
f
= q
r
=
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
+ rФункція f( ) = 1 на наборах (0, 0), (0, 1), (1, 0). Тому відповідна ДДНФ функції має вигляд
f( ) = x2 x1 .
Функція f( ) = 0 на наборі (1, 1). Тому вона має таку ДКНФ:
f( ) = = .
Розв’язування 3е). Побудуємо таблицю істинності функції f:
x1 |
x2 |
x3 |
f |
Функція f( ) = 1 на наборах (0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0). Тому відповідна ДДНФ функції має вигляд f(
)
=
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
x1
x1
x3
x1x2
. Функція
f(
)
= 0
на наборах (0, 0,
1),
(0,
1,
0),
(0,
1,
1),
(1, 1, 1).
Тому вона має таку ДКНФ f(
)
= (
)(
)(
)(
)
= (x1
x2
)(x1
x3)(x1
)(
).
Приклад 4. За допомогою перетворень вигляду A = Ax A , A A = A перейти від заданої ДНФ до ДДНФ:
а) D( ) = x1 x3; б) D( ) = x1 x3; |
в) D( ) = x1 x2 x3; г) D( ) = x2 x1. |
Розв’язування 4а). Використовуючи дані перетворення та 1 = x1 , маємо
D( ) = x1 x3 = x1x2 x1 x1 x3 x3 = x1x2x3 x1x2 x1 x3 x1 x1 x3 x3 = x1x2x3 x1x2 x1 x3 x1 x3.
Розв’язування 4в). Використовуючи дані перетворення, 1 = x1 , маємо
D( ) = x1 x2 x3 = x1x2 x1 x2x3 x2 x3 x1 x3 = x1x2x3 x1x2 x1 x3 x1 x2x3 x2 x3 x1 x3 =
= x1x2x3 x1x2 x1 x3 x1 x2x3 x2 x3.
Двійкові набори можна задати десятковими еквівалентами
(1,
1,
…, n)
,
а булеву функцію задають переліком десяткових еквівалентів, які відповідають конституентам одиниці, які входять в ДДНФ. При цьому використовують позначення
f(x1, x2, …, xn)|1 = V(n1, n2, …, nk),
де n1, n2, …, nk – десяткові еквіваленти двійкових наборів, на яких функція f( ) дорівнює одиниці.
Приклад 5. Знайти ДДНФ функції
f(x1, x2, x3)|1 = V(0, 1, 2 , 3, 7).
Розв’язування. Запишемо двійкові набори десяткових еквівалентів. Маємо:
0 = 0 22 + 0 21 + 0 20; 1 = 0 22 + 0 21 + 1 20; 1 = 0 22 + 1 21 + 0 20;
3 = 0 22 + 1 21 + 1 20; 7 = 1 22 + 1 21 + 1 20.
Маємо набори (0, 0 ,0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 1, 1), на яких функція f дорівнює одиниці. Тоді отримаємо ДДНФ вигляду
f( ) = x3 x2 x2x3 x1x2x3.
Приклад 6. Знайти ДДНФ функції:
а)
f(
)|1
= V(2,
7, 8, 12, 13);
б)
f(
)|1
= V(0,
3,
5,
8, 14, 31);
в)
f(
)|1
= V(0,
5, 7, 11 ,19, 20, 57, 62);
г) f( )|1 = V(2 , 4, 7, 9, 11, 13);
д) f( )|1 = V(1, 3, 7, 9, 15, 30);
е) f( )|1 = V(1, 6, 7, 11, 14).
Розв’язування 6а). Запишемо двійкові набори десяткових еквівалентів. Маємо:
2 = 0 23 + 0 22 + 1 21 + 0 20;
7 = 0 23 + 1 22 + 1 21 + 1 20;
8 = 1 23 + 0 22 + 0 21 + 0 20;
12 = 1 23 + 1 22 + 0 21 + 0 20;
13 = 1 23 + 1 22 + 0 21 + 1 20.
Маємо набори (0, 0, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 1, 0, 0), (1, 1, 0, 1), на яких функція f дорівнює одиниці. Тоді отримаємо ДДНФ вигляду
f(
)
=
x3
x2x3x4
x1x2
x1x2
x4.
Приклад 7. Знайти ДДНФ і ДКНФ булевої функції f( ), яка приймає значення 1 на наборах з номерами 3, 4, 7.
Розв’язування. Запишемо двійкові норми десятковими еквівалентами. Маємо:
3 = 0 22 + 1 21 + 1 20;
4 = 1 22 + 0 21 + 0 20;
7 = 1 22 + 1 21 + 1 20.
Маємо набори (0, 1, 1), (1, 0, 0), (1, 1, 1), на яких функція f дорівнює одиниці. Тоді отримаємо ДДНФ вигляду
f( ) = x2x3 x1 x1x2x3.
Функція f( ) дорівнює нулю на наборах (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 1), (1, 1, 0). Тоді вона має таку ДКНФ:
f(
)
=
(
)(
)(
)(
)(
)
= =
(x1
x2
x3)(x1
x2
)(x1
x3)(
x2
)(
x3).
Приклад 8. Методом невизначених коефіцієнтів знайти поліноми Жегалкіна для функцій:
а) f( ) = (x3 ) ~ x2 ; б) f( ) = (0 1 1 0 1 0 0 0); в) f( ) = (( x3) ) / x1; |
г) f( ) = (1 1 1 1 1 0 0 0); д)
f(
)
= ( е) f( ) = (1 0 1 0 1 0 1 0). |
)
x3;
Розв’язування 8б). Побудуємо таблицю істинності функції f:
x1 |
x2 |
x3 |
f |
x1 |
x2 |
x3 |
f |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Запишемо для даної функції поліноми Жегалкіна невизначеними коефіцієнтами
f( ) = ax1x2x3 bx1x2 cx1x3 dx2x3 ex1 gx2 hx3 r.
Підставляємо в праву частину останньої рівності послідовно множину всіх двійкових наборів, а в ліву – відповідні значення функції:
f(0, 0, 0) = r = 0; f(0, 0, 1) = 1 = h r = h 0 = h, h = 1;
f(0, 1, 0) = 1 = g r = g 0 = g, g = 1;
f(0, 1, 1) = 0 = d g h r = d 1 1 0 = d, d = 0;
f(1, 0, 0) = 1 = e r = e 0 = e = 1, e = 1;
f(1, 0, 1) = 0 = c e h r = c 1 1 0 = c, c = 0;
f(1, 1, 0) = 0 = b e g r = b 1 1 0 = b, b = 0;
f(1,
1, 1) = 0 = a
b
c
d
e
g
h
r
= a
0
0
0
1
1
1
0 =
,
a
= 1.
Тоді функція реалізується поліномом Жегалкіна:
f( ) = x1x2x3 x1 x2 x3.
Розв’язування 8д). Побудуємо таблицю істинності функції f:
x1 |
x2 |
x3 |
r
=
/ x2
=
|
|
f = x3 = r |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
Запишемо для даної функції поліноми Жегалкіна з невизначеними коефіцієнтами
f( ) = ax1x2x3 bx1x2 cx1x3 dx2x3 ex1 gx2 hx3 r.
Підставляємо в праву частину останньої рівності послідовно множину всіх двійкових наборів, а в ліву – відповідні значення функції:
f(0,
0, 0) = 1 = r,
r
= 1; f(0,
0, 1) = 0 = h
r
= h
1 =
,
= 0, h
= 1;
f(0,
1, 0) = 0 = g
r
= g
1 =
,
= 0, g
= 1;
f(0,
1, 1) = 0 = d
g
h
r
= d
1
1
1 =
,
= 0, d
= 1;
f(1,
0, 0) = 1 = e
r
= e
1,
= 1, e
= 0;
f(1, 0, 1) = 0 = c e h r = c 0 1 1 = c, c = 0;
f(1, 1, 0) = 1 = b e g r = b 0 1 1 = b, b = 1;
f(1, 1, 1) = 0 = a b c d e g h r = a 1 0 1 0 1 1 1 = = 0, a = 1.
Тоді функція реалізується поліномом Жегалкіна:
f( ) = x1x2x3 x1x2 x2x3 x2 x3 1.
Приклад
9.
Знайти поліном Жегалкіна за формулою
f,
побудувавши еквівалентну формулу над
множиною зв’язок {,
&}, в якій замінити
= x
1 і розкрити дужки, використовуючи
дистрибутивний закон (x1
x2)x3
= x1x2
x2x3,
а також привести подібні члени:
а) f( ) = (x1 / x2) x3; б) f( ) = (x1 x2)(x2 x3); в)
f(
)
= ((x1
x2)
|
г)
f(
)
= (x1
д) f( ) = (x1 x2) x3; е)
f(
)
= (
~ x1)
( |
)
/ x1;
)
x1x2;
x3).
Розв’язування 9а). Використаємо формули
x1
/ x2
=
=
;
x1
x2
=
=
;
x1
x2
=
x1x2
x1
x2.
Тоді
f(
)
= (x1
/ x2)
x3
= (
)
=
= x1x2
= x1x2(x3
1) = x1x2x3
x1x2.
Розв’язування 9б). Використовуючи формули
x1 x2 = x2; x2 x3 = ; = x1 1, (x1 x2)x3 = x1x3 x2x3, маємо
f( ) = (x1 x2)(x2 x3) = ( x2)( ) = = (x3 1) = x3 = x3(x2 1) (x2 1) = x2x3 x3 x2 = x2x3(x1 1) x3(x1 1) x2(x1 1) (x1 1) = x1x2x3 x2x3 x1x3 x3 x1x2 x2 x1 1.
Розв’язування 9д). Використовуючи формули
x1 x2 = x2; x1 x2 = x1x2 x1 x2, маємо
f(
)
= (x1
x2)
x3
= (
x2)
x3
=
x3
= x1
x3
= x1
x3
x1
x3
= x1x3(x2
1)
x1(x2
1)
x3
= x1x2x3
x1x3
x1x2
x1
x3.
Розв’язування 9в). Використаємо формули:
x1
x2
=
x2;
x
/ y
=
x1
x2
=
x1x2
x2
x1,
x
1 =
,
=
,
x1(x2
x3)
= x1x2
x1x3.
Маємо
f(
)
= ((x1
x2)
)
/ x1
= (
x2
)
/ x1
=
=
=
= (
)(
x3)
=
x3
x3
=
(1
x3
)
x3
=
x3
=
x3
x3
=
x3(
1)
= x1
x3
= x1x3(x2
1)
(x1
1) = x1x2x3
x1x3
x1
1.