КОНЪЮНКТОР

Конъюнктор - логический элемент «И», преобразует входные сигналы и выдает результат логического умножения.

А&

F=A В &B

А	В	F=A&
		B
0	0	0
0	1	0
1	0	0
1	1	1

93

ДИЗЪЮНКТОР

Дизъюнктор - логический элемент «ИЛИ», преобразует входные сигналы и выдает результат логического сложения.

А1

				F=A
В				B

А	В	F=A B
0	0	0
0	1	1
1	0	1
1	1	1

94

ИНВЕРТОР

Инвертор - логический элемент «НЕ». Преобразует входной сигнал и выдает результат логического отрицания.

А	F =
	Ā

АFĀ=

0	1
1	0

95

ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

Функция	Логический элемент
Инверсия: F(x)= x	Схема НЕ
	(инвертор):
Дизъюнкция:	Схема ИЛИ
F(x,y)=x V y	(дизъюнктор):
Конъюнкция:	Схема И
F(x,y)=x & y	(конъюнктор):
Инверсия	Схема ИЛИ—НЕ
дизъюнкции	(элемент Пирса):
(стрелка Пирса):
F(x,y)=x y= (x V y)
конъюнкции:	(элемент Шеффера)
(штрих Шеффера)			96
F(x,y)=x y = (x &

	ЛОГИЧЕСКАЯ СХЕМА
	A &	A &	A & B v
А	& B	B	B
				С=С(А
В
				,В)
Формула		С=С(А, A & v B
функции:
	Логические элементы компьютера (для
		В)=	B
А	&	А 1 справки):		Ā
	A&	A B	А
В	B	В
Конъюнк		Дизъюнк		Инверто
тор		тор		97
				р

По логической схеме можно воссоздать логическую формулу функции = логическая схема определяет логическую формулу функцииВместе.с тем, справедливо: формула булевой функции определяет ее логическую схему.

Формула С=С(А, A & v B

функции: В)= B Логическая схема:

A & B	A &	A & B
	B	v B

С=С(А

,В)

98

КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ

Элементарной конъюнкциейФУНКЦИЙ называется конъюнкция нескольких переменных и/или их инверсий, причем среди переменных могут быть одинаковые.

Примеры: ¬X&X X&¬Z

¬ X&Y& ¬Z

Дизъюнктивной нормальной формой (ДНФ)

функции F называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций (логическую сумму логических произведений).

ДНФ не содержит:

скобок и общих для нескольких аргументов99

отрицаний.

КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

Совершенной дизъюнктивной нормальной формой (СДНФ) функции F (x1, x2, … , xn)

называется ДНФ, равная 1 на тех же наборах, что и функция F, и обладающая четырьмя свойствами совершенства.

Четыре «свойства совершенства» ДНФ
формулы функции:
1. Каждое логическое слагаемое формулы
содержит все аргументы функции.
2. Все логические слагаемые формулы
различны.
3. Ни одно логическое слагаемое формулы
не содержит одновременно аргумент
функции и его инверсию.
4. Ни одно логическое слагаемое формулы
не содержит один аргумент более одного	100
раза.

СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СДНФ) логической функции

ТЕОРЕМА:

Пусть F (x1, x2, … , xn) – булева функция, не равная тождественно нулю, тогда существует СДНФ, выражающая функцию F (x1, x2, … , x ).

СДНФn функции F (x1, x2, … , xn) можно получить

- с помощью равносильных преобразований,

- с помощью таблицы истинности. 101

ПОЛУЧЕНИЕ СДНФ ФУНКЦИИ С ПОМОЩЬЮ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ

Для формулы функции получить ДНФ. Затем помощью равносильных преобразований добиться выполнения свойств совершенства для нее.

Основные приемы:
1)	Пусть В есть слагаемое в ДНФ функции,
не содержащее x1, тогда:
В	B&(x1 V x1)	B & x1 V B & x1
2)	Если в ДНФ встретится два одинаковых
слагаемых
B V B, то оставить одно: В B V B
3)	Если в некоторое
слагаемое В переменная x1 входит			x1102
дважды, то лишнюю надо отбросить: x1
& x1