Метод минимизации ФАЛ по Квайну 1 страница

Определение: Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя.

Этот метод минимизации ФАЛ заключается в следующем:

1. Находят Сок. ДНФ.

2. Находят все возможные тупиковые ДНФ.

3. Из найденных ТДНФ выбирают минимальную.

Иногда в Сок. ДНФ содержатся лишние импликанты. Как уже видели в сокращенной ДНФ:

f(Х₁, Х₂, Х₃)= Х₁Х₃ Х₂Х₃ Х₁Х₂

импликанта Х₂Х₃ может быть исключена. Ни одной операции склеивания и поглощения к этой форме применить нельзя, т.к. это Сок. ДНФ, т.е. дизъюнкция простых импликант. Можно применить операцию развертывания по Х₁:

f= Х₁Х₃ Х₂Х₃ (Х₁ Х₁) Х₁Х₂ = Х₁Х₃ Х₁Х₂ Х₃ Х₁Х₂ Х₃ Х₁Х₂

Т.к. Х₁Х₃ покрывает Х₁Х₂Х₃

и Х₁Х₂ покрывает Х₁Х₂Х₃, то f= Х₁Х₃ Х₁Х₂

ТЕОРЕМА:

Всякая минимальная ДНФ является тупиковой. Обратное утверждение не справедливо. Доказательство очевидно.

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

Существует несколько различных способов отыскания тупиковых форм.

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

Рассмотрим произвольную ДНФ. Если в ней выбросить любое произведение, то оставшееся выражение будет принимать нулевое значение на тех наборах, что и исходная форма, т.к. x₁¹ x₂²... x_iⁱ = 0 только тогда все члены x₁¹ x₂²... x_iⁱ = 0. Однако, если отброшенное произведение (импликанта) обращалось в единицу, и функция принимала единичное значение на этом единственном наборе, то оставшееся выражение может уже не принять единичное значение на данном наборе. Это означает, что импликанта не была лишней. Если же с помощью проверки установить, что оставшееся выражение обращается в единицу, импликанта – лишняя, и ее можно отбросить. Пример 1: Пусть дана f(x₁x₂x₃) = x₁x₂

x₁x₃

x₂x₃ 1. Отбросим член x₁x₂: f^l = x₁x₃

x₂x₃ x₁x₂ = 1 => x₁ = 0, x₂ = 0 f^l = 0*x₃

1*x₃ = x₃ Т.к. x₃

1 то x₁x₂ исключить нельзя 2. Отбросим член x₁x₃: f^ll = x₁x₂

x₂x₃ x₁x₃ = 1 => x₁ = 1, x₃ = 1 f^ll = 0*x₂

x₂ * 1

1 => x₁x₃ исключить нельзя. 3. Отбросим член x₂x₃: f^lll = x₁x₂

x₁x₃; x₂x₃ = 1 => x₂ = 0, x₃ = 1 f^lll = x₁

x₁ *1 = 1 => x₂x₃- член лишний. Если проверка показывает, что несколько импликант одновременно являются лишними, то исключить их одновременно из выражения ДНФ нельзя. Это можно выполнять лишь поочередно. Пример 2: f(x₁x₂x₃x₄) = x₁x₃x₄

x₂x₃x₄

x₁x₂x₄

x₁x₂x₃

x₂x₃x₄ 1. испытаем 1 член: x₁x₃x₄ = 1; x₁ = 0; x₃ = 1; x₄ = 1 f(x₁x₂x₃x₄) = x₂

0=x₂ Т.е. член x₁x₃x₄ исключить нельзя. 2. испытаем 2 член: x₂x₃x₄ = 1; x₂ = 0; x₃ = x₄ = 1 f(x₁x₂x₃x₄) = x₁

x₁

0 = 1 Т.е. член x₂x₃x₄ лишний. 3. испытаем 3 член: x₁x₂x₄; x₁ = 1; x₂ = 0 x₄ = 1 f(x₁x₂x₃x₄) = 0

x₃

0 = 1 Т.е. член x₁x₂x₄ лишний. 4. испытаем 4 член: x₁x₂x₃; x₁ = 1; x₂ = x₃ = 0 f(x₁x₂x₃x₄) = 0

x₄ x₄ = 1, Т.е. член x₁x₂x₃ лишний. 5. испытаем 5 член: x₂x₃x₄; x₂ = x₃ = x₄ = 0 f(x₁x₂x₃x₄) = 0

x₁ = x₁, Т.е. член x₂x₃x₄ лишний. Исключим одновременно члены 2, 3, 4 f = x₁x₃x₄

x₂x₃x₄ Проверим значения f одновременно на тех наборах, на которых обращаются в единицу все отброшенные члены. x₂x₃x₄; x₁x₂x₄; x₁x₂x₃; => x₁x₃x₄

x₂x₃x₄ x₁x₂x₃

x₂ = 0; x₃ = x₄ = 1 => f₁ = x₁ 0
x₁ = 1; x₂ = 0; x₄ = 1 => f₂ = 0 0
x₁ = 1; x₂ = x₃ = 0 => f₃ = 0 x₄

т.е. видно, что во всей совокупности этого сделать нельзя Исключим член x₂x₃x₄, получим: f(x₁x₂x₃x₄) = x₁x₃x₄

x₁x₂x₄

x₁x₂x₃

x₂x₃x₄ Проверим, не являются ли в этом выражении лишними те члены, которые оказались лишними в исходном выражении, т.е.: x₁x₂x₄ и x₁x₂x₃. 1. проверим x₁x₂x₄: x₁ = 1; x₂ = 0; x₄ = 1 f(x₁x₂x₃x₄) = 0

x₃

0 = x₃ т.е. член x₁x₂x₄ не лишний 2. проверим x₁x₂x₃: x₁ = 1; x₂ = x₃ = 0 f (x₁x₂x₃x₄) = 0

x₄

x₄ = 1, т.е. член x₁x₂x₃ лишний, Поэтому f(x₁x₂x₃x₄) = x₁x₃x₄

x₁x₂x₄

x₂x₃x₄ - тупиковая форма. Проверяя затем, начав с исключения третьего члена, получим другую тупиковую форму. Затем выберем из них минимальную. Недостаток метода заключается в том, что при большом числе членов он становится громоздким, поскольку связан с перебором различных вариантов. Машинная реализация данного метода вследствие этого сложна. При автоматизации поиска минимальных форм метод практически не используется.

Метод Квайна – Мак – Класки Основное неудобство метода Квайна состоит в том, что при поиске простых импликант необходимо производить попарные сравнения вначале всех конститутент единицы, затем полученных в результате склеивания произведений. С целью упрощения этой процедуры Мак – Класки предложил алгоритм, существо которого сводится к следующему: 1. вводится понятие цифрового эквивалента для каждого произведения по следующему правилу: некоторому произведению ставится в соответствие цифровой эквивалент с использованием цифр 0 и 1 и – (прочерк). Переменной, входящей в произведение в прямом виде ставится в соответсвие единица (1), в инверсном – нуль (0), отсутствие переменной обозначается прочерком; 2. в любом произведении переменные располагаются только в одном порядке, а именно – по возрастанию индексов; 3. склейке подлежат только те произведения, в которых прочерки расположены соответственно, количество нулей (или единиц) отличается на единицу и они расположены так же соответственно. Пример: Произведению x1x2x4 для функции, зависящей от пяти переменных нужно поставить в соответствие следующий цифровой набор: x1x2x4: 11-0- Приведем графическое изображение процесса поиска простых импликант для функции, представленной в следующей СДНФ: f(x1x2x3x4) = x1x2x3x4

x1x2x3x4

x1x2x3x4 запишем выражение функции в виде дизъюнкции цифровых эквивалентов: f(x1x2x3x4) = 1101

1010

0101

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

Цифровые эквиваленты конституенты единицы	Отметки о склейке	Результат склейки	Отметки о склейке
	*	10-0	-
	*
	*	-101	-
	*

Итак, простые импликанты:

10-0 и -101, т.е. f(x1x2x3x4) = x1x2x4 x2x3x4

Метод импликантных матриц

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

Пример:

Простые импликанты	Конституенты единицы
A	B	C	D	E	F
r	*			*	*
p	*				*
q			*		*
m			*
n	*					*

Из матрицы видно, что в минимальную форму функции обязательно войдут импликанты n (покрывает конституенту F), импликанта r (покрывает конституенту D). То же справедливо отностительно импликанты p. Что касается остальных, то нужно выбрать минимальную совокупность.

Итак:

f1min = n r p q

f2min = n r p m

Т.е. данная функция имеет две одинаково минимальные формы.

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

Минимизирующие диаграммы Этот метод графической минимизации был изложен Карно, который ввел в употребление специальные карты. Эти карты позволяют для функции, зависящей от небольшого числа аргументов (до пяти - шести) находить результаты всех возможных склеек. Карты впоследствии были усовершенствованы Вейчем, а сам метод иногда именуется как метод минимизации с помощью диаграмм Вейча. Рассмотрим существо способа для функций, зависящих от 2, 3 и 4-х переменных. Функции 2-х переменных

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

xy склеивается с xy и с xy;
xy склеивается с xy и с xy;
xy склеивается с xy и с xy;
xyсклеивается с xy и с xy;

Более того, эта же диаграмма дает и результат склейки: это название или строки, или столбца. При минимизации по данному методу заполняется диаграмма функции 2-х переменных по следующему правилу: если то или иное произведение входит в СДНФ функции, то в соответствующую ему клетку диаграммы ставится единица, и нуль – в противном случае. Если в диаграмме находится хотя бы две соседние единицы, то это означает, что два произведения склеиваются, а результатом склейки является произведение (в данном случае из одной буквы), именем которого названа данная строка или столбец. Пример: f(x,y) = xy

Выделим в диаграмме соседние единицы, и результат склейки дает минимальную форму функции: fmin(x,y) = x

y Заметим, что результатом склейки является результат покрытия конституент единицы исходной функции простыми импликантами. В данном случае переменными, которыми названы строки и столбцы диаграммы. Функции 3-х переменных Для минимизации функций, зависящих от трех переменных, применяется следующая диаграмма:

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

x₁x₂x₃	x₁x₂x₃
x₁x₂x₃	x₁x₂x₃

Склеим попарно произведения, стоящие в строках:

x₁x₂	x₁x₂
x₁x₂	x₁x₂

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

x₂	x₂
x₂	x₂

Как видно, результат склейки – произведение x2. Именно эта переменная покрывает все четыре конституенты единицы СДНФ функции.

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

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

Пример:

f(x1x2x3) = x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3

fmin(x1x2x3) = x3 x1x2

Видим, что две единицы, соответствующие конституентам x1x2x3 и x1x2x3, покрываются произведением x1x2.

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

Все, что было сказано относительно функций 2-х, 3-х переменных справедливо и в данном случае. Но данная диаграмма обладает дополнительной особенностью: при поиске минимальной формы функции необходимо считать склееными правый край с левым и верхний с нижним. Говорят, что для удобства целесообразно считать данную диаграмму написанной на поверхность тора. Пример: f(x1,x2,x3,x4) = x1x2x3x4

x1x2x3x4

x1x2x3x4 Составим диаграмму:

fmin(x1,x2,x3,x4) = x1x4

x3x4 Заметим, что на основании свойства диаграммы четыре единицы, стоящие в угловых клетках диаграммы соответствуют конституентам, которые склеиваются между собой. Итак, дадим формализированное описание метода. Опредение. Правильной конфигурацией ранга К называется совокупность единиц (нулей), образующая прямоугольник площадью 2к. Для минимизации функции, зависящей от n аргументов, отыскиваются правильные конфигурации вначале n-1 ранга, затем n-2 ранга и т.д. Далее определяется накрытие найденных правильных конфигураций совместной проекцией соответствующих строк и столбцов, которая выделяет данную правильную конфигурацию.

Рис. 4.1. Определение правильных конфигураций C– правильная конфигурация A,B,D– проекции конфигурации А*В– результат склеек Свойства диаграмм Вейча С помощью диаграмм Вейча можно находить: 1. минимальную форму по СКНФ 2. минимальную форму по ДНФ и КНФ функции 3. все одинаково минимальные формы 4. минимальную форму неполностью определенных функций. Пусть f(x1x2x3) задана не в виде СДНФ, а в ДНФ: f(x1x2x3) = x1x2

x1x2x3

x1x2 Заполним соответствующую диаграмму:

Так как x1x2 = x1x2 (x3

x3) = x1x2x3

x1x2x3, то в соответствующие клетки диаграммы поставлены единицы. Поэтому: fmin(x1,x2,x3) = x2x3

x1x2

x1x2 Преимущество метода: простота и наглядность для небольшого числа аргументов. Недостатки: неприменяемость метода для большого числа аргументов (> 6) вследствие сложности диаграмм и потери наглядности.

В лекции представлена минимизация неполностью определенных функций, дан синтез функций в базисах штрих Шеффера и стрелка Пирса, даны подходы к минимизации конъюнктивных форм.

Очень часто, если не в большинстве случаев, работа конкретного устройства описывается с помощью неполностью определенной функции, так как некоторые комбинации входных сигналов не подаются или являются запрещенными. Определение. Неполностью определенной функцией является такая переключательная функция, значения которой на некоторых наборах аргументов могут быть произвольными (т.е. равными "0" или "1"). Определение. Пусть функция f(x1,x2,...xn) не определена на "р" наборах аргументов. Тогда полностью определенную функцию

(x1,x2,...xn) будем считать эквивалентной к f(x1,x2,...xn), если ее значения на тех наборах, на которых f(x1,x2,...xn) определена, совпадают. Очевидно, существует 2р различных функций, эквивалентных f(x1,x2,...xn). Задача минимизации f(x1,x2,...xn) состоит в выборе такой эквивалентной

(x1,x2,...xn), которая имеет простейшую форму. Введем две вспомогательные эквивалентные функции

0(x1,x2,...xn),

1(x1,x2,...xn), которые принимают на запрещенных наборах аргументов значения 0 и 1 соответственно. ТЕОРЕМА. МДНФ неполностью определенной f(x1,x2,...xn) совпадает с дизъюнкцией самых коротких импликант

1(x1,x2,...xn), которые совместно накрывают все конституенты единицы

0(x1,x2,...xn), и ни одна из которых не является лишней. Пример: Пусть задана f(x1,x2,...xn) в виде следующей таблицы:

f(x₁,x₂,...x_n)

Числовые эквиваленты наборов

Тогда

0(x1x2x3x4) = 0 5 8 12 15 = x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 = 0000 0101 1000 1100 1111,

1(x1x2x3x4) = 0 1 2 3 5 8 10 12 13 14 15 = 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111

Найдем простые импликанты 1(x1x2x3x4)

Конституенты единицы ₁	Отметки о склейке	Импликанты	Отметки о склейке	Импликанты
	*	000- 00-0 -000	*	00- - 00- - -0-0
	*	*
*	*
*	00-1 0-01 001- -010 1-00	*
	*	-
*	*	1- -0
*	*
*	*
	*	-101 1-10 110- 11-0	-
*
*	-	11- -
-
	*	111-	*

Простые импликанты 1(x1x2x3x4)

1(x1x2x3x4) = 0-01 -101 110- 11-0 00- - -0-0 1- -0 11- -

Построим импликантную матрицу.

Конституенты единицы ₀
Простые импликанты ₁
0-01		+
-101		+
110-				+
11-0				+
00--	+
-0-0	+		+
1--0			+	+
11--				+	+

Выполним оптимальное покрытие конституент единицы 0 простыми импликантами 1 и получаем минимальную форму функции f(x1x2 x3 x4)

f1min(x1x2 x3 x4) = 11- - -0-0 -101 = x1x2 x2x4 x2x3x4

f2min(x1x2 x3 x4) = 11- - -0-0 0-01 = x1x2 x2x4 x1x3x4

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

Пример:

Рассмотрим функцию f(x1x2 x3 x4) и найдем ее минимальную форму. Заполнить диаграмму Вейча по следующим правилам: в клетки диаграммы поставим единицы, которые соответствуют конституентам единицы, нули – для отсутствующих конституент и символ неопределенности – "*" (звездочка) – в остальные.

Видно, что в клетки для конституент: x1x2x3x4, x1x2x3x4, x1x2x3x4 целесообразно "поставить" единицы вместо символов неопределенности, так как в этом случае образуется правильная конфигурация 2-го ранга, которая покрывается произведением x2x3.

Аналогично и в клетку x1x2x3x4 нужно "поставить" единицу.

Итак, fmin(x1x2 x3 x4) = x2x3 x1x4 x3x4 x1x2.

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

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

Синтез переключательных функций в одноэлементном базисе Операция (стрелка) Пирса f8(x1,x2)

x₁
x₂
f₈

Эту функцию можем представить, записав по "единицам":

f8(x1,x2) = x1x2 = x1 x2

или

x1 x2 = x1x2

На основе принципа суперпозиции:

f(x1,x2,...xn) = x1 x2 x3 ... xn = x1x2x3...xn

Применяя правило де Моргана:

x1 x2 x3 ... xn = x1x2x3...xn = x1 x2 x3 ... xn

или:

x1 x2 x3 ... xn = x1 x2 x3 ... xn

т.е.

x1 x2 x3 ... xn = x1 x2 x3 ... xn

Рассмотрим некоторые соотношения для операции Пирса:

x x = xx = x

x1 x2 = x1x2 = x2x1 = x2 x1

x1 x2 x3 = (x1x2) x3 = x1x2x3 x1 (x2x3),

т.е. операция Пирса не обладает свойством ассоциативности

x1 x2 x3 = (x1 x2) x3 = x1 (x2 x3)

x1 x2 x3 x4 = (x1 x2) (x3 x4)

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

1. раскрываются скобки

2. выполняются операции инверсии

3. выполняются операции Пирса

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

Допустим, что ФАЛ задана в конъюктивной форме

f = Q1Q2Q3... Qn

Подставим член Qi в виде:

Qi = (xr xp xq ... xw xf xe ... xz)

Возьмем двойное отрицание от обеих частей этого равенства, применив правило де Моргана

Qi = (xr xp xq ... xw xf xe ... xz) = (xr * xp * xq *... xw * xf * xe *... * xz)

Применяя соотношение, полученное на основе принципа суперпозиции:

Qi = (xr xp xq ... xw xf xe ... xz)

Или, применяя это преобразование к исходной форме, получим:

f = Q1 Q2 Q3 ... Qn

Итак: чтобы от КНФ перейти к базису Пирса и инверсии необходимо:

1. заменить операции дизъюнкции операциями Пирса

2. заменить операции конъюнкции операциями Пирса

3. заключить в скобки все те группы букв, которые соответсвуют конъюнктивным членам.

Пример:

f(x1x2 x3) = (x1 x2 x3) (x1 x4) (x2 x4) = (x1 x2 x3) (x1 x4) (x2 x4)

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

Принципиально можно избавиться от отрицаний, применив соотношение: xi = xi xi, но тогда нельзя будет утверждать, что полученная форма будет минимальной!

Операция штрих Шеффера

x₁
x₂
f₁₄

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

f14 (x1,x2) = x1 x2 (запись функций по нулям)

x1| x2 = x1 x2 = x1 x2 = x1x2 = x1 x2

на основе принципа суперпозиции:

x1 | x2 |... | xn = x1x2...xn

Рассмотрим некоторые эквивалентности:

x | x = x x = x

x1 | x2 | x3 = (x1 x2)| x3 = x1| (x2 x3)

x1 | x2 | x3| x4 = (x1 x2)| (x3 x4)

Сформулируем правила перехода от ДНФ функции к выражению с использованием операции "Штрих Шеффера".

1. заменить все операции дизъюнкции на операции Шеффера

2. заменить все операции конъюнкции на операции Шеффера

3. группы букв, которые соответствуют дизъюнктивным членам, заключить в скобки.

Пример:

f(x1x2 x3) = x1x2 x3 x1x2 x1x2x3 = = (x1|x2|x3)|(x1|x2)|(x1|x2|x3)

То же самое можно утверждать относительно минимальной формы.

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

Минимальные конъюнктивные нормальные формы

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

Рассмотрим построение МКНФ.

В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

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

f(x1x2x3) = x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 = (x1 x2 x3) (x1 x2 x3) (x1 x2 x3),

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

2. При задании функции в произвольной конъюктивной форме, применяя

формулы развертывания:

x = (x y)(x y) = xx xy yx yy (x y) = (x y z)(x y z)

............,

получить СКНФ.

3. Выполнить все операции неполного склеивания:

(x y)(x y) = x(x y)(x y)

и поглощения: x(x y) = x, получить сокращенную КНФ.

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

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

По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.

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

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

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

В данном разделе курса рассматриваются способы представления чисел в ЭВМ, методы выполнения арифметических операций, которые отличны от методов, получивших широкое распространение на практике. Как известно, еще в 19 веке производство операций над числами, содержащими много разрядов, представлялось сложной задачей, решить которую могли только профессионалы. Именно в это время были разработаны основные правила выполнения операций над многозначными числами узбекским математиком Аль-Хорезми. Общие закономерности, по которым строились эти правила, впоследствии получили название АЛГОРИТМА. Они настолько широко вошли в жизнь, что, производя эти операции над многозначными числами, мы не задумываемся над тем, что выполняем строгую систему правил. Система счисления. Способ представления изображения произвольных чисел с помощью некоторого конечного множества символов назовем системой счисления. В повседневной практике мы пользуемся, как правило, десятичной системой счисления. Ответ на вопрос: " Почему именно эта система счета получила наибольшее распространение? " - сейчас дать затруднительно. В литературе, как правило, в качестве обоснования приводится тот факт, что на руках человека - в сумме 10 пальцев. Вряд ли это обоснование можно принимать всерьез. На практике мы сталкиваемся и с более сложными, в частности, со смешанными системами. Например, система счета времени, где за единицу принята секунда, минута, час, сутки, неделя, месяц, год. Или система счета денег, до недавнего времени применявшаяся в Англии (пенс, шиллинг, фунт): 12п = 1ш, 20ш = 1ф. Или еще более интересная - римская система счета, которая исользует символы: I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000. Эта система является особой и применяется редко (циферблат, архитектура, история и т.д.) Системы счисления принято делить на:

Позиционные.
Непозиционные.
Символические.

Начнем с последних. В этих системах каждому числу ставится в соответствие свой символ. Эти системы не находят широкого применения в силу естественной их ограниченности (алхимия, кодированные сообщения) -бесчисленного множества символов, которое требуется для изображения всех возможных чисел. Поэтому эти системы из рассмотрения опустим. Позиционные системы счисления. Само название этих систем указывает на связь значимости числа и его изображения от позиции. Позиция - некоторое место, в котором может быть представлен лишь один символ. Примером позиционной системы счисления является десятичная система. В этой системе число представляется в виде полинома "n" степени, а изображается совокупностью некоторых символов, каждый из которых имеет различный вес в зависимости от позиции, которую он занимает. a4a3a2a1 - число; a1, a2, a3, a4 - символы. Всем позициям приписывается различный вес, который чаще всего выбирается как целая степень основания системы. Основание системы счисления - число, которое является мощностью множества различных символов, допустимых в каждой позиции числа. Так для десятичной системы допускаемыми являются символы: 0, 1, 2, 3,..., 9. Обозначим через "p" основание системы счисления. Тогда веса позиций числа могут быть представлены так: ... p3 p2 p1 p0. Само число, изображение которого имеет вид, например, a4a3a2a1 может быть представлено так: a0p0 + a1p1 + a2p2 + a3p3 - это развернутая запись числа в позиционной системе. Например: 97310 = 3*100 + 7*101 + 9*102 = 3 + 70 + 900. В отличие от системы счета времени, десятичная система является однородной, т.е. одних и тех же десятичных символов достаточно, чтобы изобразить любое число. В то время как в смешанных системах нужно придумывать все новые и новые символы для того, чтобы изобразить следующее по величине число. Таким образом, однородность - одно из важных свойств позиционных систем. Любое число X в позиционной системе счисления можно представить в виде: n X = ±pm Σ aip-i, i=1 где m - число позиций или разрядов, отведенное для изображения целой части числа. n - общее число разрядов в числе. ai - любой допустимый символ в разряде, т.е. ai = {0, 1, 2,..., p-1}. p - основание системы счисления. Например: - 961,13 = - (9*102 + 6*101 + 1*100 + 1*10-1 + 3*10-2). 1. Заметим, что число, равное основанию системы счисления, т.е. "p", в самой системе с основанием "p" записывается только в двух позициях (разрядах), а именно так: pp = 10p 2. Заметим также, что разделение числа на две части - дробную и целую - имеет смысл лишь в позиционных системах. 3. Заметим, что основание системы для представления числа мы можем выбрать произвольное. Такой же произвол мы можем допустить и в назначении весов разрядов. Однако наиболее целесообразно считать его, как и в десятичной системе, естественным, т.е. ввести в качестве степеней основания числа натурального ряда: 4.... +3, +2, +1, 0, -1, -2, -3...

Выбор системы счисления. Возникает естественный вопрос, является ли общепринятая система счисления с основанием 10 оптимальной? Если да, то с каких позиций? Вопрос заслуживает внимания, т.к. одна из первых ВМ (ENIAC) использовала именно десятеричную систему. Прямой и однозначный ответ на этот вопрос невозможен. Можно дать много различных ответов и все они будут справедливы лишь для каких-то определенных условий. Введя общее представление числа в позиционной системе, мы усомнились в достоинствах десятеричной не потому, что она вдруг проявила свои отрицательные качества, а потому что ее преимущества явны лишь при ручных методах счета. Нас же интересуют, прежде всего, такие системы счисления, которые будут удобны и экономичны при автоматических вычислениях с помощью ЭВМ. Мы должны также помнить, что необходимо для этого иметь саму ЭВМ. Покажем, что десятеричная система не устарела. Например, для производства экономичных расчетов обычно приходится иметь дело с очень большими объемами числовой информации. Тогда с введением новой системы пришлось бы воспользоваться следующей цепочкой действий:

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

⇐ Предыдущая 1 234 5 6 Следующая ⇒

Поделиться с друзьями:

Дата добавления: 2017-01-28; Мы поможем в написании ваших работ!; просмотров: 433 | Нарушение авторских прав

Поиск на сайте:

Лучшие изречения:

2101 -

| 1776 -

Ген: 0.152 с.