Геометрическая модель

Если рассматривать булеву функцию 3х переменных, на геометрической модели в трехмерном пространстве, то областью определения функции будет множество вершин трехмерного куба, а каждому геометрическому образу будет соответствовать элементарное произведение определенного ранга: вершинам куба – конституэнты единицы (конъюнкции третьего ранга); ребрам куба (2го ранга), гряням – 1-го ранга. Если функция f в вершинах с номерами конституэнт 0 и 7, а в остальных вершинах равна единице, то она может быть задана своей СДНФ в виде f= !X!YZ v !XY!Z v !XYZ v !x!y!z v x!yz v zy!z

При отыскании геометрически минимальной формы в первую очередь проверяют, есть ли грани, которые накрывали бы вершины куба, где f = 1; Если найдены такие грани, то запись их в виде соответствующей буквы представляет простые импликанты заданной функции. Как видно из рисунка таких граней для данной функции нет, следовательно и не существует в данной функции однобуквенных простых импликант. Затем находят все ребра, которые накрывают соседние вершины, где f = 1; Это ребра: 1-3, 3-2, 2-6, 6-4, 4-5, 5-1 каждое из которых является простой импликантой, то есть дизъюнкция этих простых импликант является сокращенной ДНФ: f=!xz V !xy V y!zv x!z v x!y v !yx

Но это еще даже не минимальная ДНФ и даже не тупиковая ДНФ. Минимальны и тупиковые ДНФ можно получить удалив из сокращенной ДНФ лишние простые импликанты. То есть удалив ребра накрывающие те вершины, которые уже накрыты другими ребрами – простыми импликантами. Могут быть удалены либо ребра 1-3, 6-4 либо ребра 3-2, 4-5; 2-6, 5-1 в результате такого подхода получается три тупиковые ДНФ:

F=!xyVy!zVx!yV!yz

F=!xzvy!zvx!zv!yz

F=!xzv!xyvx!zvx!y

Можно применить и другой подход, для удаления лишних импликант, а именно удалить ребра 1-3; 2-6; 4-5; или 3-2 6-4 5-1 в результате получим соответствующие минимальные ДНФ:

F = !xyvx!zv!yz

F = !xzvy!zvx!y

Количество букв, в различных ДНФ составляет: 18 в совершенной, 12 в сокращенной, 8 в тупиковых, 6 в минимальных.

Можно так же сделать следующие 2 вывода:

3. Имеются три тупиковые и 2 минимальные ДНФ;

4. Не всякая тупиковая ДНФ является минимальной.

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

Иногда для сокращения объемов таблицы значений истинности, пользуются неполной таблицей выписывая в нее только те наборы для которых f = 1 или те наборы, для которых f =0;

Вторым так же уже известным способом является задание ее с помощью совершенной нормальной формы ДНФ. Или КНФ (Конъюктивной нормальной формы) При этом берут ДНФ или КНФ функции, в зависимости от того, какая из них является более простой. Если функция принимает значение f = 1 меньшее число раз, чем ½ * 2^n то удобнее задать или использовать для задания этой функции ее совершенную ДНФ. Если же меньше половины всех наборов, соответствуют значениям функции f =0, то рациональнее записывать в дизъюнктивной форме отрицание функции, то есть !f переходя затем если это необходимо, к совершенной КНФ. Ранее рассматривалась так же задание функции с помощью цифровых эквивалентов СДНФ и КНФ. Такой способ задания Булевых функций отличается лишь компактностью записи, а видоизмененным способом задания фнкции с помощью СДНФ является задание ее с помощью вершин n-мерного куба. В тех случаях, когда предыдущие способы задания недопускают простого задания функции, например при n > 4 могут оказаться полезными задание функции с помощью нормальной формы и задание ее с помощью прямоугольной таблицы имеющей 2 ^ (n/2) строк и 2 ^ n -(n/2) столбцов. Где n/2 – целое число ближайшее к n/2 Например, некоторая функция 5 переменных может быть задана следующим видом

F(x,y,z,u,v)= xyvxz!uv!x!yzu!v можно задать ее так же с помощью таблицы, которая вляется прямоугольной таблицей 2 ^n/2 * 2^ n-(n/2)

ТАБЛИЦА

Единицы в этой таблице располагаются так, что бы комбинируя дизъюнкции из конъюнкций соответствующих пересечению строк и столбцов получить в результате упрощений необходимый член дизъюнктивной формы, в виде которой записана функция. Например, простановка единиц в пересечении всех столбцов с первой строкой означает, что дизъюнктивная форма данной функции содержит конъюнкцию x y соответствующую этой строке в виде отдельного члена (так как дизъюнкция всех конституэнт единицы трех переменных z u v = 1 )

Конъюнкция соответствующая единице в таблице на пересечении последней строки в второго столбца дает последний член дизъюнктивной формы рассматриваемой функции xy!z u!v

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

Xyzu!vVx!yzu1V

Точно так же дизъюнкция конъюнкций … имеет вид

Каждая из этих 2х дизъюнкций может быть преобразована следующим образом с учетом закона исключения третьего:

Составляет дизъюнкцию из результатов этих двух равенств получим второй член дизъюнктивной формы, в который разложена функция

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

Способы задания булевых функций с помощью прямоугольных таблиц позволяет рассматривать достаточно компактные записи, позволяет просматривать до 8 переменных. И почти эквивалентен другим способам задания… Целесообразно рассмотреть основные и наиболее применяемые из них.

3. Метод неопределенных коэффициентов используется при минимизации следующим образом: составляется дизъюнктивная нормальная форма минимизируемой функции, в которой содержится все возможные конъюнкции. Первого-второго и третьего ранга с соответствующими неопределенными коэффициентами. В общем случае равными нулю или 1. Всего при n элементов данная запись будет содержать 3^n -1 членов. Задавая различные наборы значений переменных и приравнивая полученные выражения соответствующим значениям функций на этих наборах получают систему 2^n уравнений для определения коэффициентов. Усовершенствования этого метода является метод «минимизирующих карт»

4. Предположим, что нужно минимизировать функцию трех переменных, которая задана в ДНФ. F = xyzV x!yz V !xyz

Разумеется эту функцию можно минимизировать «с ходу», но для демонстрации этого метода сделаем это при помощи минимизирующих карт. Для этого на основании дизъюнктивной формы составим таблицу содержащую 2^n строк и 2^n-1 столбцов.

В последнем столбце – значение функции.

Минимизация этой заданной функции состоит из трех шагов:

4. Вычеркивание тех строк, в которых функция равна нулю.

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

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

Который основан на преобразовании СДНФ с помощью неполного склеивания и элементарное в сокращенную ДНФ

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

Иногда требуется неоднократное применение операции развертывания, для получения из данной импликанты конституэнты 1-цы

Пусть дана функция совершенной ДНФ.

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

..

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

2012-12-18 Лекция 23

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

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

F(x,y,z) = !(xy)V!(yz)V!xzVx!zVyzVxy

Импликантную матрицу покажем в таблице:

Для каждой простой импликанты находят конституэнту единицы, которой ею поглощается. То есть …

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

Рассматриваемая функция имеет 2 такие формы

F(x,y,z) = !x!y V x!zV yz

And

F(x,y,z) = !y!zV!xzVxy

Блейк-Порецкий основан на использовании операции обобщенного склеивания.

A*xVB!x=AxVB!xvAB

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

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

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

Известно что функциональные задачи управления в АСУ не могут быть решены без получения информации о состоянии системы. Получение такой информации в виде удобном для последующей реализации является предметом и целью систем сбора и предварительной обработки информации. Одна из основных задач таких систем – автоматическое обнаружение событий характеризующих отклонение хода процесса в системе от установленных. На основании анализа информации поступающей от отдельных объектов и характеризующие их состояния и внешние условия обнаруживаются признаки, контролируемого события и формируется сигнал о наступлении события при наличии совокупности характеризующих его признаков. Затем обработанная информация поступает в систему управления и используется там для формирования управляющих воздействий. Методы автоматического обнаружения событий включая сюда классификацию контролируемых событий и признаков решения задач о принципиальной возможности обнаружения событий различных классов, разработку критериев эффективности методов обнаружения событий различных классов относят к области распознавания образов. Здесь имеет смысл подчеркнуть лишь одну особенность этих методов, которая состоит в составлении алгоритмов выявления минимально необходимой информации требуемой для обнаружения.

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

Прдположим, что задана в виде конъюнкции дизъюнкций некоторая булева функция f = (a11, V a12 … V a1i..n)… (Am1vam2v…vamim), где ai,j принадлежит A = {a11,…an} (I =1,..m), (j = 1,…li)

UAij=Ai,j = 1…li, UAi = A, i=1..,m \

Тестом А* называется подмножество элементов из А, такое что в каждой скобке существует по крайней мере 1 элемент, принадлежащий А*. Минимальным тестом называется подмножество A*min содержащее минимальное число элементов из А. Булева функция f определена на всех 2 ^n наборов логических переменных а1 … аn и принимает значение 1 на всех наборах из А являющихся тестом для f(). Здесь предполагается что в выражении для f произведены все упрощения с помощью аксиом алгебры логики. Задача нахождения минимальных тестов может быть сформулирована как задача нахождения простых импликант минимальной длины. Записав инверсию для функции f(), получим ДНФ этой функции и если учесть что все упрощения функции f были осуществлены, то это может быть минимальная ДНФ. !f= !a11 * !a12… !a1l1 v…V!am1* !am2 … !amlm

Импликантами функции f являются все возможные выборки A* элементов из А такие что А* && Ai != A*, где Ai’ = {ai1’ , aip’}, Ai’ = A|Ai,

Ai = {ai1,..aili}(I = 1,..m) следовательно минимальной простой импликантой (минимальным тестом) является выборка содержащая наименьшее число элементов из А и не входящее полностью не в одно из подмножеств Ai’ при I = 1 to n Если среди подмножеств Аi со штрихом содержит подмножество Aj’ при j принадлежит (1..m), Pj = min Pi (так как f!=0, то Pj < n)

То для функции f () существует по крайней мере n-pj тестов содержащих не более pj+1 членов. Таким образом, процесс нахождения минимальных простых импликант (минимальных тестов) следует начинать с рассмотрения выборок по Pj элементов.

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

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

Пусть дана функция совершенной ДНФ.

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

..

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

2012-12-18 Лекция 23

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

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

F(x,y,z) = !(xy)V!(yz)V!xzVx!zVyzVxy

Импликантную матрицу покажем в таблице:

Для каждой простой импликанты находят конституэнту единицы, которой ею поглощается. То есть …

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

Рассматриваемая функция имеет 2 такие формы

F(x,y,z) = !x!y V x!zV yz

And

F(x,y,z) = !y!zV!xzVxy

Блейк-Порецкий основан на использовании операции обобщенного склеивания.

A*xVB!x=AxVB!xvAB

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

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

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

Известно, что функциональные задачи управления в АСУ не могут быть решены без получения информации о состоянии системы. Получение такой информации в виде удобном для последующей реализации является предметом и целью систем сбора и предварительной обработки информации. Одна из основных задач таких систем – автоматическое обнаружение событий характеризующих отклонение хода процесса в системе от установленных. На основании анализа информации поступающей от отдельных объектов и характеризующие их состояния и внешние условия обнаруживаются признаки, контролируемого события и формируется сигнал о наступлении события при наличии совокупности характеризующих его признаков. Затем обработанная информация поступает в систему управления и используется там для формирования управляющих воздействий. Методы автоматического обнаружения событий включая сюда классификацию контролируемых событий и признаков решения задач о принципиальной возможности обнаружения событий различных классов, разработку критериев эффективности методов обнаружения событий различных классов относят к области распознавания образов. Здесь имеет смысл подчеркнуть лишь одну особенность этих методов, которая состоит в состалении алгоритмов выявления минимально необходимой информации требуемой для обнаружения.