Задачі до теми „Істотні та фіктивні змінні”
Приклад 1. Перерахувати істотні змінні таких функцій:
а) f( ) = (x1 (x1 x2))x3 x3;
б)
f(
)
= (x1
x2)
x2;
в) f( ) = (x1 x2 x3 x3)x4;
г) f( ) = ( x2 x3)( x3)( x2 x3)( ).
Розв’язання 1а). Якщо побудувати таблицю істинності функції f( ), то дістанемо f( ) 1, і тому всі змінні x1, x2, x3 – фіктивні змінні даної функції. Функція не має істотних змінних.
r = x1 (x1 x2) = (x1 x2) = ( x1 ) x2 = 1 x2 = 1;
q = rx3 = 1 x3 = x3;
f( ) = q x3 = x3 x3 = x3 = 1.
Розв’язання 1б). Побудуємо таблицю істинності функції f( ). Маємо
x1 |
x2 |
r = x1 x2 |
f
= r
x2
=
|
0 |
0 |
0 |
1 = 1 + 0 |
0 |
1 |
1 |
1 = 0 + 1 |
1 |
0 |
1 |
0 = 0 + 0 |
1 |
1 |
1 |
1 = 0 + 1 |
+ x2Оскільки f(1, x2) f(0, x2) і f(x1, 1) f(x1, 0), то змінні x1, x2 – істотні.
Приклад 2. Показати, що змінна x1 – фіктивна змінна функції f(виразити f формулою, в яку x1 не входить явно):
а) f( ) = (x1 x2)(x1 x2);
б) f( ) = (((x3 x2) x1)(x2 x1)x3 ) x3;
в) f( ) = ((x1 x2)(x1 ) ( x2 ))x2.
Розв’язання 2а). Використаємо співвідношення
x1
x2
=
x2
x1
,
x1
x2
=
=
.
Тоді, застосувавши закони де Моргана і дистрибутивність кон’юнкції відносно диз’юнкції, маємо
f( ) = (x1 x2)(x1 x2) = ( x2 x1 )( ) = ( x2 x1 ) =
= x2 x1 = 0 0 = 0.
Отже, змінна x1 – фіктивна для функції f.
Розв’язання 2б). Використаємо співвідношення
x3 x1 = x1, x1 x3 = x3 x1 .
Маємо
r = ((x3 x2) x1) = x2 x1;
q = ((x2 x1)x3 ) = ( x1) x3 = x3 x1 x3 = 0 0 = 0;
= rq = ( x2 x1)0 = 0;
f = x3 = 0 x3 = x3 0 = x3.
Отже, змінна x1 – фіктивна змінна для функції f.
Розв’язання 2в). Використовуючи співвідношення
x y = + y, маємо
f( ) = ((x1 x2)(x1 ) ( x2 ))x2 = ((x1x1 + x1 + x1x2 + x2 ) (x1 + x2 ))x2 = ((x1(1 + + x2) + x2 ) (x1 + x2 ))x2 = 1 x2 = x2.
Отже, змінна x1 – фіктивна для функції f.
Приклад 3. Вказати фіктивні змінні функції f:
а) f( ) = (11110000);
б) f( ) = (00110011);
в) f( ) = (00111100);
г) f( ) = (0011110011000011).
Розв’язання 3а). Побудуємо таблицю істинності функції:
x1 |
x |
x3 |
f |
Оскільки f(0, 0, 0) = 1, f(1, 0, 0) = 0, то існує пара наборів (1, 2, 3), де 1 = 0 і 1 = 1, на яких функція набуває різних значень при 2 = 3 = 0. Тоді x1 – істотна змінна функції f( ). У даній таблиці викреслимо всі рядки, для яких x2 = 1, тобто це будуть набори вигляду (1, 1, 3), а також стовпчик x2. |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
2
Отримаємо функцію g(x1, x3), яка має таку таблицю істинності.
x1 |
x3 |
g(x2, x3) |
Якщо порівняти значення функції g(x1, x3) = f(x1, 0, x3) на кожному наборі (1, 0, 3) з її значенням на наборі (1, 1, 3), то f(x1, 0, x3) = f(x1, 1, x3), тобто змінна x2 – фіктивна змінна функції f( ). |
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
Якщо в останній таблиці викреслити всі рядки вигляду (x1, 1) і стовпчик x1, то отримаємо функцію h(x1) = g(x1, 0) із таблицею істинності:
x1 |
h(x1) |
Знову порівнюємо значення функції h(x1) = g(x1, 0) на кожному наборі (1, 0) із значенням функції g(x1, x2) на наборі (1, 1), який викреслено. Отже, g(x1, 1) = g(x1, 0), тобто x3 – фіктивна змінна функції f( ). |
0 |
1 |
|
1 |
1 |
Розв’язання 3б). Побудуємо таблицю істинності функції:
x 1 |
x2 |
x3 |
f |
Оскільки f(0, 0, 0) = 0, f(0, 1, 0) = 1, то існує пара наборів (1, 2, 3), де 2 = 0 і 2 = 1, на яких функція набуває різних значень при 1 = 3 = 0. Тоді x2 – істотна змінна функції f( ). У даній таблиці викреслимо всі рядки, для яких x1 = 1, тобто це будуть набори вигляду (1, 2, 3), а також стовпчик x1. |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
Отримаємо функцію g(x2, x3), яка має таку таблицю істинності.
x2 |
x3 |
g(x2, x3) |
Якщо порівняти значення функції g(x2, x3) = f(0, x2, x3) на кожному наборі (0, 2, 3) з її значенням на наборі (1, 2, 3), то f(0, x2, x3) = f(1, x2, x3), тобто змінна x1 – фіктивна змінна функції f( ). |
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
Якщо в останній таблиці викреслити всі рядки (x2, 1) і стовпчик x3, то отримаємо функцію h(x2) = g(x2, 0) із таблицею істинності
x2 |
h(x2) |
Знову порівнюємо значення функції h(x2) = g(x2, 0) на кожному наборі (2, 0) із значенням функції g(x2, x3) на наборі (2, 1), який викреслено. Отже, g(x2, 1) = g(x2, 0), тобто x3 – фіктивна змінна функції f( ). |
0 |
1 |
|
1 |
1 |
Приклад 4. З’ясувати, для яких n (n 2) залежать істотно від своїх змінних такі функції:
а)
f(
)
= (x1
x2)
(x2
x3)
…
(xn
– 1
xn)
(xn
x1);
б) f( ) = (x1 x2)(x2 x3) (x2 x3)(x3 x2) … (xn x1)(x1 xn).