Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції), Детальна інформація

a a a

b r b r b r a r

r = a(b r = a(b r = a(b r = (a

Розглянемо реалізацію бульових функцій у вигляді комбінаційних схем. Найпростішими з них є логічні елементи, відповідні бульовим функціям: кон'юнкції (, диз'юнкції (, додавання за модулем 2 ( та заперечення (. Вони позначаються й зображаються таким чином:

Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон'юнкція, диз'юнкція та додавання за модулем 2.

З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:

a1 b1

a2 b2

.

.

.

an bm

Тут bj=fj(a1, a2, …, an), j=1, 2, …, m..

Приклади.

1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, (}:

x(y = x((y((x(y.

x

y

Звідси відповідна схема має вигляд:

2. Побудуємо схему з І- та (-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, 1}:

x(y = x(y(x(y.

Звідси відповідна схема має вигляд:

x

y

3. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує так званий "однорозрядний напівсуматор"[****] з двома симетричними входами x, y і двома виходами: s = x(y, d = x(y. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору {(, (, (}: s = x((y((x(y. Тоді схема має вигляд:

x s

d

y

Список літератури

Виленкин Н.Я. Популярная комбинаторика.–М.: Наука, 2000.