Примеры составления логических функций.

Простую логическую функцию иногда можно записать в аналитической форме непосредственно из словесного определения. Покажем это на примере составления функций «Равнозначность» и «Неравнозначность», которые будем использовать в дальнейшем. Функция «Равнозначность» принимает значение 1, если две ее входные переменные имеют одинаковые логические потенциалы: x₁=x₂=1 ИЛИ x1=x2=0. Поэтому ее представляют как . Условное изображение элемента «Равнозначность» приведено на рис.2.3,а.

Функция «Неравнозначность» принимает значение 1, если две ее входные переменные имеют разные логические потенциалы: x₁=1, x₂=0 ИЛИ x₁=0, x₂=1. Поэтому ее представляют в следующем виде:

,

где значок - символизирует функцию «Неравнозначность».

Рис.2.3 Условные изображения элементов «Равнозначность» (а) и «Неравнозначность» (б).

Функцию «Неравнозначность» иначе называют «Исключающее ИЛИ». Ей присуще интересное свойство: если на один ее вход подать лог.1, то логический потенциал, поданный на второй вход, будет на выходе инвертирован; если же вместо лог.1 на один вход подать лог.0, то функция будет вести себя как повторитель логического потенциала, поданного на другой вход. Это легко проверит это самостоятельно. Условное изображение элемента «Неравнозначность» дано на рис. 2.3,б. Вместо приведенного значка (=1) используется значок m2, указывающий на то, что «Исключающее ИЛИ» функционирует по правилам сложения одноразрядных двоичных чисел (сложение по модулю 2): 1+0=1; 0+1=1; 0+0=0; 1+1=0 (при арифметическом сложении единица переносится в соседний более старший разряд).

В общем случае для получения аналитической формы функции используют таблицы истинности.

Пример 2.8. Пусть на выходе некоторого устройства должен появиться сигнал высокого уровня (лог.1, у=1), если на входах устройства действует комбинация сигналов х₁х₂х₃ из набора №1 ИЛИ из набора №2 ИЛИ из набора №3 ИЛИ из набора №6, приведенные в табл.2.4. Если на каждом перечисленном наборе конъюнкция сигналов будет равна лог.1, то на выходе устройства будет сигнал высокого уровня (U¹).

Таким образом, функция, представленная табл.2.4, запишется в виде , (2.9)

где сигналы х₁,х₂,х₃, инвертированы, если они в соответствующих наборах равны лог.0 (иначе конъюнкция не будет равна 1).

Таблица 2.4

Таблица истинности функции y

Номер набора	х3	х2	х1	y	Номер набора	х3	х2	х1	y
0	1	1	1	0	4	0	1	1	0
1	1	1	0	1	5	0	1	0	0
2	1	0	1	1	6	0	0	1	1
3	1	0	0	1	7	0	0	0	0

Такая форма логической функции, как указывалось ранее, называется совершенной дизъюнктивной нормальной формой (СДНФ). Она представляется логической суммой простых конъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде не более одного раза; в такие конъюнкции не входят суммы переменных, а также отрицания произведений двух или более переменных. Входящие в СДНФ конъюнкции называются минтермами или конституентами единиц. Логическая сумма конъюнкций, отличающаяся от (2.9) тем, что все конъюнкции или некоторые из них не содержат всех переменных (в прямом или инверсном виде), представляет собой дизъюнктивную нормальную форму (ДНФ) функции.

Логическую функцию можно составить не только по единичным, но и по нулевым значениям. Из табл.2.4 следует, что на наборах №№0, 4, 5, 7 у =0. Чтобы на каждом указанном наборе имело место у=0, нулю должна равняться дизъюнкция переменных из этого Набора, т.е. каждое слагаемое дизъюнкции; если в данном наборе переменная равна единице, то в дизъюнкцию должна входить ее инверсия. На всех указанных наборах функция из табл.2.4 будет равна 0, если осуществить конъюнкцию составленных дизъюнкций:

. (2.10)

Здесь у =0 обеспечивают: первый сомножитель при (при х₃=x₂=х₁=1, т. е. на наборе № 0), второй сомножитель при (при х₃=0; x₂=х₁=1, т. е. на наборе № 4), третий сомножитель при (при х₃=х₁=0; х₂ =1, т. е. на наборе № 5), четвертый сомножитель при х₃=х₂=х₁=0, т.е. на наборе № 7.

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

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

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

Минимизация логических функций.

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

Пример 2.9. Упростить выражение (2.9).

Решение. Используя закон склеивания для первого и третьего членов, и для второго и четвертого, а также одно из тождеств алгебры логики получим:

=

= .

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

Пример 2.10. Пусть имеется логическая функция . Требуется минимизировать ее.

Решение. Добавим дважды к правой части функции уже имеющийся член х₃,х₂,х₁ (отчего функция не изменится); тогда

=

= .

Это выражение значительно проще исходного.

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

Метод минимизации логических функций с

использованием карт Карно.

Карта Карно построена так, что в ее соседние клетки попадают смежные члены функции — члены, отличающиеся значением одной переменной: в один член эта переменная входит в прямой форме, а в другой — в инверсной. Благодаря этому получается наглядное представление о различных вариантах склеивания смежных членов. В карте Карно содержится столько клеток, сколько комбинаций (наборов) можно составить из прямых и инверсных значений n переменных по n членов в каждой. Так, при n=2 карта содержит четыре клетки (рис.2.4,а), при n= 3 — восемь клеток (рис.2.4,б), при n= 4 - 16 клеток (рис.2.4,в).

Каждая клетка соответствует определенной комбинации переменных. Так, например, левая верхняя клетка карты (см. рис.2.4,а) соответствует комбинации xy,: над столбцом левых клеток указан х, в прямой форме, возле верхней строки записан в прямой форме y. Наборы переменных, на которых F = 1 (в дальнейшем логическую функцию будем обозначать y), т.е. минтермы функции, отмечаются в соответствующих клетках карты 1, в остальные клетки записываются 0 или их оставляют пустыми.

Рис.2.4. Карта Карно функции для двух (а), трех (б) и четырех (в)

переменных

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

Общие правила склеивания членов, занесенных в карту Карно, следующие:

1. Склеиваться могут 2, 4, 8,... членов; при этом соответствующие 1 в клетках для наглядности охватывают прямоугольными контурами.

2. Одним контуром следует объединять максимально возможное количество клеток.

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

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

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

Пример 2.11. Пусть логическая функция задана таблицей истинности (см. табл.2.5). Составить СДНФ и с помощью карт Карно минимизировать ее.

Решение. По приведенной методике составим СДНФ функции:

(2.11)

Таблица 2.5

Таблица истинности функции y

Номер набора	x4	х3	x2	x1	Y	Номер набора	x4	х3	x2	x1	y
0		1	1	1	1	8	0	1	1	1	0
1		1	1	0	1	9	0	1	1	0	0
2		1	0	1	1	10	0	1	0	1	0
3		1	0	0	1	11	0	1	0	0	0
4		0	1	1	0	12	0	0	1	1	1
5		0	1	0	0	13	0	0	1	0	1
6		0	0	1	1	14	0	0	0	1	1
7		0	0	0	1	15	0	0	0	0	1

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

.

Данная форма функции значительно проще первоначальной. Интересно отметить, что она не содержит переменной x₁.

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

x₂

Рис. 2.5. Карта Карно для функции, заданной табл.2.5

Задача 1

81	2
-80	40	2
1	-40	20	2
	0	-20	10	2
		0	-10	5	2
			0	-4	2	2
				1	-2	1
					0

Получилось:81₁₀ = 1010001₂ 

Задача 2

Мы ввели число: 111111₂ в двоичной системе счисления и хотите перевести его в десятичную.  Для этого переведем его сначала в десятичную вот так :  111111₂ = 1∙2⁵+1∙2⁴+1∙2³+1∙2²+1∙2¹+1∙2⁰ = 32+16+8+4+2+1 = 63₁₀  Получилось: 63₁₀ 

Результатперевода: 111111₂ = 63₁₀

_{Задача 3}

10111 и 11100 23+28=51

Задача 4

10001 и 1010 17-10=7

Задача 5

111 и 1001 7*9=63

Задача 6

37 на 64 0.10010100000

26