Составители:
Рубрика:
14
рах переменных в строках 1, 3, 5, а следовательно и будет искомой совершенной дизьюнк-
тивной нормальной формой (СДНФ):
()()()ABC ABC ABC
∧
∧
∨
∧
∧
∨∧∧
5.30. Для того, чтобы записать формулу в приведенном виде, следует, пользуясь фор-
мулой
A
B
A
B
→=∨, исключить операцию импликации, а затем “опустить” операцию
отрицания на простые переменные:
CBACBACBACBA =∨∧=∨∨=∨→ )(.
6.30.
Способ 1. (Метод неопределенных коэффициентов).
Составляем таблицу истинности для функции
x
1
↔
x
2
x
1
x
2
x
1
↔
x
2
0 0 1
0 1 0
1 0 0
1 1 1
Записываем полином Жегалкина с неизвестными коэффициентами a
0
, a
1
, a
2
, a
12
для функции
от двух переменных:
x
1
↔
x
2
= a
0
⊕ a
1
x
1
⊕ a
2
x
2
⊕ a
12
x
1
x
2
.
Подставляя в это разложение значения
x
1
и x
2
из таблицы, определяем неизвестные коэффи-
циенты:
Подставляя
x
1
=0, x
2
=0, получаем: 1= a
0
;
x
1
=0, x
2
=1 — 0=1⊕ a
2
⇒ a
2
=1;
x
1
=1, x
2
=0 — 0=1⊕ a
1
⇒ a
1
=1;
x
1
=1, x
2
=1— 1=1⊕ a
12
⇒ a
12
=0.
Полином Жегалкина имеет вид:
x
1
~x
2
= 1⊕ x
1
⊕ x
2
.
Способ 2. (Эквивалентные преобразования).
Сначала запишем СДНФ
21
2121
21
1),(),(
/\
σσ
σσσσ
xx
f =
эквивалентности:
=
∨=↔
212121
xxxxxx {т.к.
x
y
x
y
x
y∨
=
⊕
⊕
} =
=
⊕
⊕
=
xx xx xx xx
12 12 1212
{по-
скольку
xx xx
1212
0
=
} =
⊕
=
xx xx
12 12
{далее,
x
x
=
⊕
1 , поэтому }
2121
)1)(1( xxxx ⊕⊕⊕=
=⊕ ⊕
⊕
⊕
=
⊕
⊕
11
1 2 12 12 1 2
x x xx xx x x
7.30. Сначала преобразуем исходную формулу:
312131213121
)()( xxxxxxxxxxxx ∨=∨∨=→→
=
∨xx x
12 3
()
;
fx x x x x x(, , ) ( )
123 12 3
=∨
. =∨∨=∨= )()(),,(
321321321
xxxxxxxxxf
321
xxx ∨ . Пусть
рах переменных в строках 1, 3, 5, а следовательно и будет искомой совершенной дизьюнк-
тивной нормальной формой (СДНФ): ( A ∧ B ∧ C ) ∨ ( A ∧ B ∧ C ) ∨ ( A ∧ B ∧ C )
5.30. Для того, чтобы записать формулу в приведенном виде, следует, пользуясь фор-
мулой A → B = A ∨ B , исключить операцию импликации, а затем “опустить” операцию
отрицания на простые переменные: A → B ∨ C = A ∨ ( B ∨ C ) = A ∧ B ∨ C = AB C .
6.30. Способ 1. (Метод неопределенных коэффициентов).
Составляем таблицу истинности для функции x1 ↔ x2
x1 x2 x1 ↔ x2
0 0 1
0 1 0
1 0 0
1 1 1
Записываем полином Жегалкина с неизвестными коэффициентами a0, a1, a2, a12 для функции
от двух переменных: x1 ↔ x2 = a0⊕ a1 x1⊕ a2 x2⊕ a12 x1 x2.
Подставляя в это разложение значения x1 и x2 из таблицы, определяем неизвестные коэффи-
циенты:
Подставляя x1=0, x2=0, получаем: 1= a0;
x1=0, x2=1 — 0=1⊕ a2 ⇒ a2=1;
x1=1, x2=0 — 0=1⊕ a1 ⇒ a1=1;
x1=1, x2=1— 1=1⊕ a12 ⇒ a12=0.
Полином Жегалкина имеет вид: x1~x2 = 1⊕ x1 ⊕ x2.
Способ 2. (Эквивалентные преобразования).
Сначала запишем СДНФ \ /σ x1σ 1 x2σ 2 эквивалентности:
(σ 1 ,σ 2 ) f( 1 ,σ 2 ) =1
x1 ↔ x2 = x1 x2 ∨ x1 x2 = {т.к. x ∨ y = x ⊕ y ⊕ xy } = = x1 x 2 ⊕ x1 x 2 ⊕ x1 x 2 x1 x 2 = {по-
скольку x1 x 2 x1 x 2 = 0 } = x1 x 2 ⊕ x1 x 2 = {далее, x = 1 ⊕ x , поэтому }
= (1 ⊕ x1 )(1 ⊕ x2 ) ⊕ x1 x2 = 1 ⊕ x1 ⊕ x 2 ⊕ x1 x 2 ⊕ x1 x 2 = 1 ⊕ x1 ⊕ x 2
7.30. Сначала преобразуем исходную формулу:
( x1 → x 2 ) → x1 x3 = ( x1 ∨ x 2 ) ∨ x1 x3 = x1 x 2 ∨ x1 x3 = x1 ( x 2 ∨ x 3 ) ;
f ( x1 , x 2 , x 3 ) = x1 ( x 2 ∨ x 3 ) . f ( x1 , x2 , x3 ) = x1 ( x2 ∨ x3 ) = x1 ∨ ( x2 ∨ x3 ) = x1 ∨ x2 x3 . Пусть
14
