Решение Пример 6

Пример 6.

Выполнить булевы операции над логическими фун­кциями трех переменных f₁ и f₂, используя изоморфизм буле­вых алгебр логических функций и двоичных векторов, если:

1. f₁ и f₂ определены таблицами истинности в табл. 4.11 (см. § 4.4, упражнение 3);

2. f₁ и f₂ определены своими СДНФ:

Изоморфизм булевых алгебр логических функций (P₂ (m), &,Ú, ù) и двоичных векторов

(В_п; &, Ú, ù) позволяет переходить от операций над функциями к операциям над двоичными векторами и обратно при выполнении условия (4.28): 2 ^m = n. Поэтому функциям трех переменных (m = 3) соответствуют вектора длины n = 8. Установим взаимно од­нозначное соответствие Г: Р ₂ (3) ® В₈ и выполним необхо­димые операции, используя изоморфизм булевых алгебр.

1) Зафиксировав последовательность рассмотрения всех возможных наборов значений переменных, например, как это указано в табл. 4.14, ус­тановим взаимно одно­значное соответствие

x1 x2 x3 Х2Х3	f1	f2	f1 & f2	f1 Ú f2
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Г: Р ₂ (3) ® В₈ следую­щим образом: для функции f, пред­ставленной таблицей ис­тинности, в соответству­ющем ей векторе a = (a ₁,a₂,…, a_n) i -я ком­понента

a _i = 1, если для f i - й набор значений пе­ременных является единичным, т.е. функция на этом наборе принимает значение f_i = 1, и a _i = 0 - в противном случае.

Тогда:

Г(f₁) = (0 0 0 1 1 0 1 1) = a,

Г(f₂) = (0 0 1 1 0 1 1 1) = b.

Выполним операции (&, Ú, ù) над функциями f₁ и f₂, ис­пользуя изоморфизм булевых алгебр Г: Р ₂ (3) ® В₈:

а) Г(f₁ & f₂)= a & b = (0 0 0 1 1 0 1 1) & (0 0 1 1 0 1 1 1)= =(000 1 00 1 1).

Но вектору (000 1 00 1 1) соответствует функция

(f₁ & f₂): Г^-1 ((0 0 0 1 0 0 1 1)) = f₁ & f₂, таблица истинности которой представлена в табл. 4.14.

б) Г(f₁ Ú f₂) = a Ú b = (0 0 0 1 1 0 1 1) Ú (0 0 1 1 0 1 1 1) =

= (00111111).

Но Г^-1 ((0 0 1 1 1 1 1 1)) = f₁ Ú f₂ (см. табл. 4.14).

в) Г(f₁) = == (1 1 1 0 0 1 0 0).

Г^-1 ((1 1 1 0 0 1 0 0)) =(см. табл. 4.14).

2) Определим последовательность всех возможных эле­ментарных конъюнкций всех переменных

и установим взаимно однознач­ное соответствие

Г: Р ₂ (3) ® В₈ следующим образом:

для функции f, представленной СДНФ, в соответствую­щем ей векторе a = (a ₁,a₂,…, a_n) i -я компонента a _i = 1, если в СДНФ f имеется i -я конъюнкция, и a _i = 0 - в противном случае.

Тогда:

Г(f₁) = = (0 0 011 0 11) =a,

Г(f₂) ==

= (0 0 1 1 0 1 1 l) = b.

Выполним операции (&, Ú, ù) над функциями f₁ и f₂, используя изоморфизм булевых алгебр Г: Р₂ (3)® В₈:

а) Г(f₁ & f₂) = a & b = (0 0 0 1 1 0 1 1) & (0 0 1 1 0 1 1 1) = =(0 0 0 1 0 0 1 1).

Но вектору (0 0 0 1 0 0 1 1) соответствует функция, СДНФ которой

Г^-1 ((0 0 0 1 0 0 1 1)) = .

Таким образом, f₁ & f₂ =.

б) Г (f₁ Ú f₂) = a Ú b = (0 0 0 1 1 0 1 1) Ú (0 0 1 10 1 1 1) =

= (0 0 1 1 1 1 1 1).

Но ((0 0 1 1 1 1 1 1)) =

=

Таким образом

в) (1 1 1 00 1 00).

Ho Г^-1((1 1 1 0 0 1 0 0)) .

Таким образом,

Дата добавления: 2014-01-14