Теоретические основы вычислительной техники 3 страница

4) – класс монотонных функций,

5) – класс линейных функций.

Рассмотрим классы:

1) f (0, 0, … 0) = 0

2) f (1, 1, … 1) = 1 т. е. если подставить 0-е значение аргументов, то функция =0 или 1

3)

4) Пусть х_­1i=1, a x_1j=0. Тогда x_1i>x_1j. Функция f(x₁, x₂, … x_n) является монолитной, если для всех случаев, когда во всех наборах выполняется неравенство

Например:

видно, что и , то выполняется:

5) Если , где , то f(x₁,x₂,…,x_n) – называется линейной логической функцией

Пример:

		Сохр. «0»	Сохр. «1»	самодвой-ственные	монотонные	линейные
и		+	+	-	+	-
или		+	+	-	+	-
инверсия		-	-	+	-	+
штрих Шеффера	\	-	-	-	-	-

Из таблицы на основании теоремы о ФП СЛФ:

1) - избыточная СЛФ, но наиболее распространённая (каноническая СЛФ)

2)

3) безызбыточные СЛФ, есть другие безызбыточные ФПСЛФ

4) х₁\х₂

Технический аналог булевой функции – комбинационная схема.

Вывод: для синтеза любой комбинационной схемы достаточно иметь лишь технические устройства, соответствующие ФП СЛФ.

Основные законы и правила.

А. Преобразование выражений в булевой алгебре.

№	логическое сложение	логическое умножение	название закона
	х+0=х		-
	х+1=1		-
	х+х=х		закон идемпотентности
			-
		закон двойного отрицания
	х1+х2=х2+х1	х1х2=х2х1	коммутативный закон
	х1+х1х2=х1	х1(х1+х2)=х1	закон поглощения
			закон Де Моргана (правило)
	(х1+х2)+х3= =х1+(х2+х3)= =х1+х2+х3	(х1х2)х3=х1(х2х3)= =х1х2х3	ассоциативный закон
	х1+х2х3= =(х1+х2)(х1+х3)	х1(х2+х3)= =х1х2+х1х3	дистрибутивный закон (распределительный)

примем обозначения:

В. Теорема разложения.

Любую переключательную функцию n аргументов можно представить в следующем виде:

Следствие:

Теорема о СДНФ (совершенная дизъюнктивная нормальная форма):

Всякую переключательную функцию можно представить:

Доказать самостоятельно.

Теорема о СКНФ (совершенная конъюнктивная нормальная форма):

Доказательство:

ч. т. д.

Пример: Пусть переключательная функция f(x₁,x₂,x₃) задана таблицей

таблица истинности избыточна более чем в 2 раза.

Пример. Упростить логическое выражение

используя законы и правила булевой алгебры.

=

Задание 44. Упростить выражение

Задание 45. Упростить выражение

Задание 46. Привести выражение

к виду содержащему лишь операции и дизъюнкции.

Минимизация выражений в булевой алгебре.

Цель – упростить техническую реализацию (комбинационную схему)

I. Геометрическая интерпретация задачи упрощения и минимизации логических функций.

Если 2 смежные вершины куба заменить ребром, то получим упрощение: возможен алгоритм.

II. Метод Квайна-Мак-Класки.

Определения:

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

Длинной ДНФ называется число попарно различимых конъюнкций в ДНФ.

Кратчайшей ДНФ называют ДНФ с наименьшей, среди всех возможных ДНФ, длинной.

Минимальной ДНФ называется ДНФ у которой наименьший среди всех возможных ДНФ ранг конъюнкции.

Сокращённой ДНФ называется ДНФ состоящая из простейших конъюнкций.

* - отбрасываются члены сокр. ДНФ и проверяется истинность

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

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

Словесное представление логических функций.

Покажем на примере функции конъюнкции. Словесно эту функцию можно представить так: логическая функция принимает значение равное 1 лишь в том случае, когда все её аргументы равны 1.

Табличное представление логических функций.

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

Алгебраическое представление логических функций (в СДН и СКН формах).

Примем обозначение , где n – количество аргументов логической функции. Тогда любую логическую функцию (кроме F=0) можно представить в совершенной дизъюнктивной нормальной форме (СДНФ).

или в совершенной конъюнктивной нормальной форме (СКНФ)

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

- выделяются наборы аргументов (строки ТИ) при которых функция равны 1;

- из аргументов каждого выделенного набора формируется соответствующая конъюнкция (аргументы, значения которых в наборе равны 0, входят в конъюнкцию с инверсией);

- сформированные конъюнкции соединяются знаком дизъюнкций.

При построении СКНФ порядок действий следующий:

- выделяются наборы аргументов при которых функция равна 0;

- из аргументов каждого выделенного набора формируется соответствующая дизъюнкция (аргументы, значения которых в наборе равны 1, входят в дизъюнкцию с инверсией);

- сформированные дизъюнкции соединяются знаками конъюнкций.

Пример. Представить логическую функцию F₁(x₁,x₂,x₃), заданную таблицей истинности, в СДНФ и СКНФ.

Задание 47. Логическая функция F₂(x₁,x₂,x₃) задана ТИ. Представить функцию в СДНФ и СКНФ.

Задание 48. Представить логическую функцию таблицей истинности, а также в СКНФ и СДНФ.

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

Карта Карно – это графическое представление таблицы истинности. Между строками ТИ и клетками карты Карно (КК) существует взаимно однозначное соответствие. Каждая клетка КК заполняется нулём или единицей в соответствии со значением функции, вычисленной при значениях аргументов на пересечении которых расположена данная клетка.

Например, для 2-х переменных ТИ и КК будут выглядеть следующим образом:

Карты Карно для 3-х и 4-х переменных выглядят так:

Следует обратить внимание на расположение наборов аргументов по координатным осям КК. Последовательность наборов определяется изменением значения только одной переменной. Поэтому расположение 00 01 10 11 является неправильным, т. к. при переходе от 01 к 10 изменяются сразу две переменные. Правильным будет расположение 00 01 11 10.

Задание 49. Представить логическую функцию картой Карно.

Задание 50. Представить логическую функцию картой Карно.

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

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

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

Десятичные числа в цифровой форме располагаются в порядке возрастания.

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

При построении F_СДНФ­ в цифровой форме следует выделять в ТИ наборы аргументов 001, 010, 100, 110, 111 и представлять их десятичными числами 1, 2, 4, 6, 7. Тогда

При построении F_CКНФ в цифровой форме выделяем наборы 000, 011, 101, заменяем их на обратные, т. е. на 111, 100, 010 и представляем их десятичными числами 7, 4, 2, располагая по возрастанию:

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

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

Пусть задана функция

Перейдём к обратной функции где N – полное количество наборов аргументов функции. Обратная функция получается путём записи в неё десятичных чисел, отсутствующих в представлении F­_СДНФ. Используя можно получить , где

Пример. Для функции, рассмотренной в предыдущем примере, выполнить переход от F_СДНФ к F­_СКНФ в цифровой форме.

Задана

Перейдём к обратной функции: Так как N=8, то

Следовательно,

Задание 51. Представить логическую функцию F₁, заданную таблицей истинности (табл. 3), в цифровых формах.

Задание 52. Представить логическую функцию F₂, заданную таблицей истинности (табл. 3), в цифровых формах.

Задание 53. Представить в цифровых формах

Задание 54. Представить в цифровой форме и выполнить переход к F_СКНФ.

Задание 55. Представить

в цифровой форме и выполнить переход к F_СДНФ.

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

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

Пример. Представить функцию F­₁ (таблица 3) в строчной форме.

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

Пример. Представить функцию, заданную цифровыми формами

в строчных формах.

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

Задание 56. Представить функцию F₂ (табл. 3) в строчной форме и выполнить переход к цифровой форме представления.

Задание 57. Представить функцию в строчной форме.

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

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

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

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

Минимизация методом Карно (рассмотрим три варианта: А, Б, В).

А. Минимизация в дизъюнктивно нормальной форме (получение МДНФ).

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

Группой клеток называется совокупность соседних клеток, составляющих прямоугольник размерности где а и b = 0, 1, 2, … .

Каждой группе размерности соответствует конъюнкция состоящая из переменных, где n – полное число аргументов логической функции. В конъюнкцию включаются все аргументы, значения которых не изменяются в пределах соответствующей группы. Если переменная в пределах группы равна 0, то она входит в конъюнкцию с инверсией, а если 1 – без инверсии.

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

Два принципа формирования группы:

- каждая группа должна быть как можно больше, т. е. max(a+b);

- число групп должно быть как можно меньше.

Пример. Дана карта Карно для функции 4-х переменных. Получить МДНФ этой функции.

Например, конъюнкция соответствующая 1-ой группе состоит из двух аргументов, т. к. , а для 2-ой группы .

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

В КК для 3-х и 4-х переменных клетки могут объединяться в так называемые разорванные группы, например:

Пример. Дана карта Карно для функций 4-х переменных. Получить МДНФ этой функции.

Задание 58. Получить МДНФ для функции F₁ заданной в таблице 4.

Задание 59. Получить МДНФ для функции F₂ заданной в таблице 4.

Б. Минимизация в конъюнктивной нормальной форме (получение МКНФ).

Здесь возможны 2 способа.