ГЛАВА 4. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

4.1. Логические основы построения и работы компьютеров

Все цифровые ЭВМ построены на элементах, которые выполняют те или иные логические операции. Одни элементы обеспечивают переработку двоичных символов, представляющих информацию, другие – коммутацию каналов, по которым информация передается, третьи – управление и др. Электрические сигналы, действующие на входах и выходах перечисленных элементов, имеют, как правило, два различных уровня, следовательно, они могут быть представлены двоичными символами, например 1 и 0. Условимся обозначать свершение какого-либо события, например высокого напряжения в определенной точке схемы цифрового автомата, символом 1. Этот символ называется логической единицей (не одно и тоже, что и двоичная 1). Отсутствие события обозначается символом 0 и называется логическим нулем.

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

импульс или его отсутствие;

высокий или низкий потенциал;

высокий потенциал или его отсутствие.

При импульсном способе отображения код единицы идентифицируется наличием электрического импульса, соответственно, код нуля – его отсутствием. Импульс характеризуется амплитудой и длительностью. Длительность импульса должна быть меньше временного такта компьютера. Форма и амплитуда сигнала во внимание не принимаются. Из вышесказанного вытекает, что для анализа и синтеза схем в цифровых автоматах, например компьютерах, может быть использован аппарат алгебры логики, также оперирующий двумя понятиями – истина или ложь.

Таким образом, каждому сигналу на входе или выходе двоичного элемента ставиться в соответствие логическая переменная, которая может принимать одно из двух значений: состояние логической единицы (событие истинно) и состояние логического нуля (событие ложно).

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

Функция f(x1, x2,…xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: 0 или 1.

Алгебра логики является алгеброй состояний, а не алгеброй чисел, поэтому эту алгебру называют также алгеброй высказываний.

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

Высказывания бывают простыми и сложными. Простые отдельные высказывания – это логические переменные, их принято обозначать буквами латинского алфавита. Например, если простое высказывание х истинно, то х=1, если же ложно, то х=0.

Высказывания с различным содержанием обозначаются разными буквами и считаются различными. Два высказывания называются эквивалентными, если истинности их одинаковые. Эквивалентность высказываний обозначается знаком равенства или тождества. Например, запись х=у означает, что высказывания х и у либо истинны, либо ложны одновременно.

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

51

Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х1, х2, …хn где xi равно нулю или единице (i=1, 2,…n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 – нулевой набор; 0, 0, 0, 1 – первый набор; 0, 0, 1, 0 – второй набор; 1, 0, 1, 0 – десятый набор и т.д.

Таким образом, логическая функция (функция алгебры логики) это функция y=f(x1, x2,…xn), которая принимает значение 0 или 1 на наборе логических переменных x1, x2,…xn.

Каждой логической функции данного набора аргументов, также принято приписывать номер: 0, 1, 2,.......

Любую булеву функцию можно задать с помощью таблицы, в которой всем возможным наборам значений двоичных переменных сопоставлены соответствующие им значения функции. Такая таблица называется таблицей истинности, поскольку она определяет истинность или ложность сложного высказывания в зависимости от истинности или ложности составляющих высказываний. Для функций одной переменной может существовать всего четыре различные булевы функции F1, F2,F3 и F4, представленные в таблице 4.1.

Таблица 4.1

Таблица истинности для функций одной переменной

x	F1	F2	F3	F4
0	0	0	1	1
1	0	1	0	1

Из таблицы следует, что функции F1 и F4 не зависят от аргумента и являются соответственно константами 0 и 1, а функция F2 повторяет значение аргумента, т.е. F2=x. Функция F3 называется отрицанием или инверсией переменной x.

Как бы ни была сложна логическая связь между логической функцией и ее аргументами, эту связь всегда можно представить в виде простейших логических операций. К числу таких операций относятся:

-отрицание (операция «НЕ»);

-логическое сложение (операция «ИЛИ»).

-логическое умножение (операция «И»). Рассмотрим эти операции подробнее.

Отрицанием называется такая логическая связь между входной логической переменной

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

С помощью логико-математической символики логическая функция «НЕ» переменной

узаписывается как y x (читается – «у есть не х»). Если, например, х – утверждение о

наличии сигнала в точке схемы ЦА, то у соответствует утверждению – сигнал отсутствует.

Таблица 4.2

	Операция «НЕ»
Х		у
0		1
1		0

Функция f(x), принимающая значение, обратное значению x, – логическое отрицание (инверсия), или функция «НЕ» (NOT), может обозначаться одним из следующих способов:

f(x) = x = x.

Обратим внимание на следующие функции:

52

Логическим сложением нескольких переменных называется такая функция, которая ложна только тогда, когда одновременно ложны и все слагаемые переменные. Таблица истинности операции логического сложения приведена ниже, см. табл. 4.3.

Таблица 4.3

		Операция «ИЛИ»
х1	х2		У
0	0		0
0	1		1
1	0		1
1	1		1

Логическое сложение также называется – дизъюнкцией и обозначается следующим образом:

у(x1, x2) = x1 + x2 = x1 x2 = x1 ! x2.

Например, выражение у=х1 x2 читается следующим образом: «у есть х1 илиx2». Логическим умножением нескольких переменных называется такая функция, которая

истинна только тогда, когда одновременно истинны все умножаемые переменные. Таблица истинности операции логического умножения приведена ниже, см. табл. 4.4

Таблица 4.4

		Операция «И»
х1	х2		у
0	0		0
0	1		0
1	0		0
1	1		1

Логическое умножение также называется – конъюнкцией и обозначается следующим образом:

у(x1, x2) = x1 x2 = x1 x2 = x1 & x2.

Например, выражение у=х1 x2 читается следующим образом: «у есть х1 и x2». Функция «НЕ-И» (штрих Шеффера NAND) – это функция, которая ложна тогда, когда

все переменные истинны. Условное обозначение этой функции:

у(x1, x2) = x1/x2.

Это читается следующим образом: «функция у ложна, т.е. равна 0, когда оба аргумента х1 и х2 одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда или оба аргумента одновременно ложны, или же хотя бы один из них ложен».

Функция «НЕ-ИЛИ» (стрелка Пирса или NOR) – это функция, которая истинна только тогда, когда все переменные ложны. Условное обозначение этой функции:

у(x1, x2) = x1 x2 = x1 O x2.

Это читается следующим образом: «функция у ложна, т.е. равна 0, когда хотя бы один из ее аргументов х1 или х2 истинен, или же оба, одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда оба аргумента одновременно ложны».

Функция «ЕСЛИ-ТО» (IF-THEN импликация) это функция, которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 – следствием. Ее условное обозначение

у(x1, x2) = x1 x2.

Функция исключающее «ИЛИ» (XOR) - это функция у(x1, x2), которая обозначается знаком . Эта операция реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком :

53

у(x1, x2) = x1 x2 = x1 x2.

Из всех приведенных выше определений ясно, что в алгебре логики все знаки действий:или &, или +, , и т.д., в отличие от обыкновенной алгебры, являются знаками

логических связок, т.е. логических действий, а не знаками арифметических действий.

В таблице 4.5 приведены примеры всех элементарных логических функций от двух переменных x1 и x2.

Таблица 4.5 Перечень элементарных логических функций от двух переменных

	№ функции		Значения			Пример написания
		х1	х2	у
f0	константа ноль	0	0	0	f0
f1	конъюнкция	0	0	0	x1 x2
f2	запрет x2	0	0	1	x1 x2
f3	переменная x1	0	0	1	x1 x2 x1 x2 = x1
f4	запрет x1	0	1	0	x1 x2
f5	переменная x2	0	1	0	x1 x2 x1 x2 = x2
f6	сложение по модулю 2	0	1	1	x1 x2
f7	дизъюнкция	0	1	1	x1 x2
f8	функция Пирса	1	0	0	x1 x2
f9	равнозначность	1	0	0	x1 x2
f10	инверсия x2	1	0	1	x1 x2 x1 x2 =x2
f11	импликация	1	0	1	x2 x1
f12	инверсия x1	1	1	0	x1 x2 x1 x2 =x1
f13	импликация	1	0	0	x1	x2
f14	функция Шеффера	1	1	0	x1	│ x2
f15	константа единица	1	1	1	f1

Введем еще три специфических понятия алгебры логики.

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

Логическая переменная xi действительна, если значение логической функции f(x1, x2,

..., xn) изменяется при изменении xi. В противном случае эта переменная для данной функции фиктивна, т.е. не является ее аргументом.

Необходимость ввода этих двух последних понятий возникла по следующей причине. При анализе некоторой неизвестной логической функции (логической схемы), для которой необходимо сформировать аналитическое выражение, не все подключаемые для этого анализа логические переменные могут быть аргументами этой функции, что и выявляется в итоге проведенного анализа. В дальнейшем будет показано, что любые логические операции над логическими переменными можно свести к определенной совокупности элементарных логических функций, например, таких как «И», «ИЛИ», «НЕИЛИ».

Элементарные логические операции в компьютерах выполняются также над двоичными числами, поразрядно.

Элементы, реализующие простейшие логические функции, схематически представляются в виде прямоугольников, на поле которых изображается символ, обозначающий функцию, выполняемую данным элементом. На рис. 4.1 и в таблице 4.6 показаны условные обозначения элементов, реализующих логические функции «И», «ИЛИ», «НЕ». Входные переменные принято изображать слева, а выходные – слева. Считается, что передача информации происходит слева на право.

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

При переходе от логических функций к логическим схемам обычно принимается, что логической единице (1) соответствует импульсный сигнал стандартной амплитуды, например, высокого уровня, а логическому нулю. (0) – низкого уровня и обычно фиксированной

54

длительности. Причем, все входные сигналы должны поступать на каждый элемент одновременно.

Как любую логическую функцию можно реализовать при помощи соответствующей комбинации элементарных логических функций, так и любую логическую схему можно сформировать при помощи соответствующей комбинации логических элементов.

Заметим, что каждый реальный логический элемент обладает некоторым временем задержки изменения выходного сигнала по отношению к входному. Однако в комбинационных схемах при их формальном описании временем задержки логических элементов пренебрегают.

Таблица 4.6 Примеры логических операций над двумя двоичными числами

Логическое умножение	Логическое сложение	Отрицание
«И»	«ИЛИ»	«НЕ»
01011010	0101010	01011010
11110000	1111000	10100101
01010000	1111010

х1	у	х1	у	х1	у
	&		1		1
х2		х2
		«И»
			«ИЛИ»		«НЕ»

Рис. 4.1. Условные обозначения элементов, реализующих логические функции

«И», «ИЛИ», «НЕ»

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

55

Таблица 4.7 Примеры графического изображения элементов логических схем

91-1984 IEEE/ANSI

Традиционное изображение логических

Логические

элементов

функции

A

«НЕ»

A

1

у

(NOT Gate,

or Inverter)

y А

y А

A

«И»

&

A

y

(AND Gate)

y A B A B

В

у

B

A & B

«ИЛИ»

A

A

y

(OR Gate)

≥

y A B A B

1

у

B

В

A

«И-НЕ»

A

y

(NAND Gate)

&

B

y A B A B

у

В

A

«ИЛИ-НЕ»

≥1

у

A

y

(NOR Gate)

В

y A B A B

B

A				Сложение по модулю 2
	М	y	A	y
				(XOR Gate)
	2
			B	y A B
				AB AB

B

		«И»		«ИЛИ»	A B Y
			A	Y	1	1 1
	A	Y			1 0 0
					0	1 0
					0	0 0
	B		B
			A		1	1 0
	A	Y		Y	1 0 0
					0	1 1
					0	0 0
	B		B

56

	91-1984 IEEE/ANSI		Традиционное изображение логических		Логические
				элементов	функции
			A		1	1	0
	A	Y		Y	1 0 1
					0	1	0
					0	0	0
	B		B
			A	Y	1	1 0
	A	Y			1 0 0
					0	1 0
					0	0 1
	B		B
			A	Y	1	1 1
	A	Y			1 0 1
					0	1 1
					0	0 0
	B		B
			A		1	1 1
	A	Y		Y	1 0 0
					0	1 1
					0	0 1
	B		B
			A		1	1 1
	A	Y		Y	1 0 1
					0	1 0
					0	0 0
	B		B
			A		1	1 0
	A	Y		Y	1 0 1
					0	1 1
					0	0 1
	B		B

57

Продолжение таблицы 4.7

ИНТЕРПРЕТАЦИЯ ОБОЗНАЧЕНИЯ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ Интерпретация двух вариантов обозначений

логического элемента «ИЛИ»

А

					A B
	A		B
						Выходной сигнал будет
						низким, только если на
						каком-либо
В						из входов будет низкий

Низкий уровень сигнала

Возбуждаемый низким уровнем сигнала

						Выходной сигнал будет
						высоким, если все
А						входные сигналы будут
				A	B	высокими
В
						Высокий уровень
						сигнала

Возбуждаемый высоким уровнем сигнала

При анализе или синтезе логических цепей ЭВМ надо учитывать следующее обстоятельство.

Осуществить логические функции на практике позволяют различные, так называемые логические (цифровые) полупроводниковые схемы – вентили, выходные сигналы которых однозначно определяются комбинациями уровней сигналов на входах этих схем. Причем, как входные, так и выходные сигналы этих вентилей могут быть импульсными или потенциальными и имеют два фиксированных значения: высокий (H) или низкий (L) уровень. Когда логической «1» соответствует высокий уровень, тогда логическому «0» – низкий.

Если логической «1» соответствует наличие сигнала (высокого или низкого уровня), то в таком случае говорят, что логические схемы работают в положительной логике. Если же логической «1» соответствует отсутствие сигнала, то считается, что схемы работают в

отрицательной логике. Существует также и смешанная логика, то есть когда в рассматриваемом электронном узле одни вентили работают в положительной логике, а другие

–в отрицательной.

Валгебре логики имеются четыре основных закона: переместительный (свойства коммутативности); сочетательный (свойства ассоциативности); распределительный (свойства дистрибутивности) инверсии (правило де Моргана).

Некоторые законы обычной алгебры применимы и к алгебре логики.

Переместительный закон:

для умножения	(А·В) = (В·А);
для сложения	(A+ B) = (B + A).

58

Сочетательный закон:

для умножения	A· (B·C) = (A·B) ·С;
для сложения	A + (B + С) = (A + B) + С.

Распределительный закон: A· (B + С) = A·B + A·C; (A+ B) ·C = A·C + В·C.

Алгебра логики имеет ряд специфических аксиом и теорем, основные из которых, необходимые для анализа и синтеза логических цепей или схем, приведены в таблице 4.8.

Таблица 4.8

Специфические аксиомы и теоремы алгебры логики

1)

A = 1, если A 0

A = 0, если A 1

2)

Если A = 0, то A 1

Если A=1, то A 0

3)

0 + 0 = 0

0 0 = 0

4)

0 + 1 = 1

1 0 = 0

5)

1 + 1 = 1

1 1 = 1

6)

0 1

1 0

7)

A 0 = A

A 1 = A;

8)

A 1 = 1

A 0 = 0;

9)

A A = A

A A = A;

10)

A A 1

A A 0

11)

A B

A B

A

B

A

B

Правило де Моргана

12)

и

A B

A B

A

B

A

B

Правило двойного отрицания

13)

( A ) A

Закон склеивания

14)

A B A B A

(A B) (A B) A

Аксиомы и теоремы, записанные во второй колонке (т.е. слева), называются двойственными аксиомам и теоремам, записанным в третьей колонке (т.е. справа).

Двойственность определяется как изменение всех знаков операции «И» на знаки операции «ИЛИ», всех знаков операции «ИЛИ» на знаки операции «И», всех нулей на единицы и всех единиц на нули.

Двойственность является одним из основных свойств алгебры логики и означает, что если f(A, B, C) и f (A, B, C) - двойственные функции, то

f (A, B,C) f (A, B,C ).

Законы де Моргана являются одной из иллюстраций свойства двойственности и, как уже отмечалось, могут быть сформулированы в виде:

A B C A B C ;

59

A B C A B C .

Из законов Моргана следует, что, имеется возможность выражать конъюнкцию через дизъюнкцию и отрицание, или дизъюнкцию - через конъюнкцию и отрицание. Законы де Моргана и следствия из них справедливы для любого количества переменных.

Функция сложения по модулю 2 представляется следующим образом:

A B A B A B.

Для этой функции справедливы следующие аксиомы:

A A 0; A A A A; A		1;	A 1		; A 0 A.
	A			A

На основании рассмотренных аксиом и свойств элементарных логических функций можно, например, вывести правила представления функций «И», «ИЛИ», «НЕ» через функцию сложения по модулю 2 и наоборот:

A + B = A B AB;

А В = (A B) (A + B).

Функции «И», «ИЛИ», «НЕ» через функцию Шеффера выражаются следующим образом:

A B A B;

A B A B A B.

Функция Пирса может описываться следующими выражениями:

A B A B A B.

Для этой функции справедливы следующие аксиомы:

A A		;	A 0		;	A		0;	A 1 0.
	A			A			A

Функции «И», «ИЛИ», «НЕ» выражаются через функцию Пирса следующим образом:

A B (A A) (B B);	A B (A B) (A B);		A A.
		A

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

связку «ИЛИ», а знак умножения " " либо знаки , и &, означают логическую связку «И» [9, 14]. Булево выражение представляет собой формулу, состоящую из логических констант и логических переменных, соединенных знаками логических операций.

Поскольку каждая логическая функция реализуется с помощью определенного набора устройств, то, следовательно, чем меньше элементов содержит выражение, тем проще схема, реализующая соответствующую ему функцию. Таким образом, значительный интерес представляет изучение методов минимизации логических функций.

Различают аналитические и табличные методы минимизации.

В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, такие преобразования требуют определенных выкладок и проверки на наличие ошибок. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно и др. Эти методы наиболее пригодны для обычной технической практики [9, 14].

Аналитический метод минимизации логических функций состоит в последовательном применении к некоторой формуле законов и правил алгебры логики. Однако этот метод не поддается четкой алгоритмизации. Действия, используемые при реализации этого метода, определяются видом исходного преобразуемого выражения, а также навыками исполнителя.

60

Отсутствие алгоритмизации процесса минимизации значительно повышает вероятность появления ошибок и возможность получения не полностью минимизированной логической функции.

Метод непосредственного преобразования наиболее пригоден для простых формул, когда последовательность преобразований очевидна.

Рассмотрим пример применения метода непосредственных преобразований на примере минимизации функции трех переменных, заданной ее СНДФ:

y f (A, B,C) (A B C) (A B C ) (A B C) (A B C ) (A B C).

Объединим попарно первое и третье, второе и третье, а также четвертое и пятое элементарные произведения:

y (A B C A B C) (A B C A B C) (A B C A B C).

Следует отметить, что одно и то же элементарное произведение при объединении можно использовать несколько раз. В рассматриваемом примере элементарное произведение

A B C используется два раза. После вынесения за скобки получим:

y B C (A A) A B (C C) A B (C C) B C A B A B.

Полученная логическая функция проще исходной СНДФ, однако, она не является минимальной. Объединив второе и третье элементарные произведения, после вынесения за скобку А окончательно получим:

y B C A (B B) B C A.

Нетрудно заметить, в каждой паре объединяемые элементарные произведения различаются лишь одной переменной, которая входит в первое произведение с отрицанием, а во второе - без отрицания. Такие элементарные произведения называют соседними. К

соседним произведениям применима операция склеивания (т.е. A B A B A ), в результате которой уменьшается число суммируемых произведений и на единицу сокращается количество переменных.

Рассмотрим еще один пример. Необходимо выбрать наименьшее значение из трёх переменных A, B, C.

Первый вариант анализа дает следующие результаты:

если	A<B	и	A<C	то наименьшее =A,
если	A>=B	и	B<C	то наименьшее =B,
если	A>=C	и	B>=C	то наименьшее =C.

Проведенный анализ дал неоптимальный результат. Сократим его, вынеся за скобки некоторые сравнения:

если A<B то

если A<C то наименьшее = A, иначе наименьшее = C. иначе

если B<C то наименьшее = B, иначе наименьшее = C.

В оптимизированном варианте примера всего три сравнения вместо шести. Более того, если в первом примере для достижения результата всегда выполняется шесть сравнений, то во втором примере всегда выполняется только два сравнения.

Стремление к алгоритмизации поиска элементарных произведений привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно.

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

Поэтому они строятся или по таблице истинности анализируемой функции, или же по ее

СНДФ.

61

Напомним, что каждая строка таблицы истинности, для которой функция равна единице, соответствует минтерму функции, представленной в СНДФ. Строка, для которой функция равна нулю, является макстермом функции, представленной в СНКФ.

Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции четырех переменных квадратов будет 16, для пяти переменных – 32 и т.д. Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так,

чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем -

без. Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0. Иногда в углу квадрата ставят номер набора. Такой способ используется, если функция задана числовым образом, но он неудобен для процедуры минимизации.

Перечислим последовательность действий, выполняемых для минимизации функции по методу Карно:

1)исходная функция, подлежащая минимизации, должна быть представлена в НДФ. Затем ее надо представить в СНДФ. Или же составляется таблица истинности минимизируемой функции. Как уже отмечалось, между строками таблицы истинности и клетками (ячейками) на карте Карно существует взаимно однозначное соответствие. Когда карта Карно составляется по СНДФ минимизируемой функции, то очевидно, что каждая переменная без отрицания заменяется ее значением 1, а с отрицанием – 0;

2)затем строится карта Карно по принципу, описанному выше. Представим систему координат, в которой, например, для функции двух переменных по горизонтальной оси откладываются значения одного аргумента, а по вертикали – другого. На пересечении соответствующих координат получаем ячейку, куда записывается значение функции (0 или 1), соответствующее данному набору. Если функция представлена в СНДФ, то в ячейке соответствующей существующему минтерму записывается 1, а в ячейке несуществующего

минтерма – 0;

3)после этого объединяются в группы смежные ячейки, в которых записаны единицы, следующим образом: объединяется обязательно четное количество соседних ячеек с единицами, как по вертикали, так и по горизонтали. Причем, каждая ячейка с 1 может попасть одновременно в две группы, полученные в результате объединения единиц, как по вертикали, так и по горизонтали;

4)каждой группе ставится в соответствие новый минтерм для изображения исходной функции в форме минимальной НДФ;

5)изображение каждого нового минтерма формируется по следующему алгоритму:

а) переменная, которая в каждой ячейке образованной группы имеет значение только 0, изображается ее инверсией;

б) переменная, которая в каждой ячейке группы имеет значение только 1, изображается без инверсии;

в) переменная, которая в пределах образованной группы меняет свое значение, не изображается, т.е. отбрасывается.

Таким образом, карту Карно можно рассматривать как графическое представление совокупности всех (существующих и не существующих) минтермов функции в СНДФ данного числа логических переменных.

Вернемся к таблицам 6.8 и 6.9. Карта Карно для функции трех переменных имеет 2n=23=8 ячеек, а для четырех переменных 24=16 ячеек, выделенных в таблице цветом.

Карта размечается системой координат, соответствующих значению входных переменных. Например, верхняя строка карты для функции трех переменных соответствует нулевому значению переменной А, а нижняя – ее единичному значению. Каждый столбец этой карты характеризуется значениями двух переменных: В и С.

Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значений переменных В и С вычисляется функция, размещаемая в ячейках этого столбца. Так для случая карты Карно функции четырех переменных функция, расположенная в ячейках столбца с координатами 01, вычисляется при значениях переменных С=0 и D=1. Функция,

62