Свойства n-местных булевых функций

Имеем некоторую n-местную булевую функцию.

Свойство 1: рассматриваем функцию f(x1,x2,xn)(вид 1). Любая местная булева функция вида (1) определена не более чем 2 в степени n наборов ее аргументов. (это было заложено в основу компьютерной техники Буль и Фон Нейман) Таким образом имеем, булев картеж

Каждому набору аргументов можно поставить соответствие (картежу) можно поставить соответствие вершину n-мерного куба.

x₂

01 11

00 10 x₁

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

001, 010, 011, 100, 101, 111…

Будем записывать наборы аргументов (картежей) столбиками и под каждым картежем напишем значение булевой функции

X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

F(x1,x2,x3)

0 0 0 1 0 1 0 1

Если имеется m-наборов аргументов, то всего можно задать 2 в степени m булевых функций.

Свойство номер 2:

Общее число n-местных булевых функций равно B(n) = 2 в степени 2 в степени n.

B(n+1) = (B(n)) *(B(n))

B(1) = 4;

B(2) = 16;

B(3) = 256

B(4) = 65536;

n-местную булеву функцию можно представить с помощью булевых функий от одного и 2х аргументов. Такие булевые функции (1 и 2х местные) принято называть элементарными.

Пример

Одноместная функция B(1)=4;

x
F(x) =0
F(x)= 1
F(x)=x

Рассмотрим двухместную функцию

B(2)=16

Fi(x,y)

x
y
Fi(x,y) = 0
--//--- = 1
--//-- = x
--//-- = y
--//-- = ^x
--//--= ^y

y delta x
X delta y
X~y
X^Y
XvY
X+Y
X=>Y
Y=> Y
Y = X
X | Y
X стрелка вниз Y

Оставшиеся 10 наборов можно разбить на пары. (Fi1(x,y) и fi2(x,y)) где fi2(x,y) = !fi1(x,y)

Если F(x) = !x то f(xi1(x,y))=fi2(x,y)

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

Конъюнкция(соединение) называют логическое произведение или логическое И.

X ^ Y;

X & Y

Конъюнкция функция равная единице, в том и только в том случае, когда оба ее аргумента равны 1;

X, Y – аргументы. Конъюнктивные члены

Для того что бы она была равна нулю необходимо и достаточно что бы один из аргументов был равен нулю.

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

0x0 = 0

0x1 = 0

1x0 = 0

1x1 = 1

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

1 -> Пустое множество

1 -> I

^ ->

Конъюнкция обладает свойством идемпотентностью

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

Fi(x1…xn) ^ fi(x1…xn)

Дизъюнкция – сложение.

1+1 = 1 и 1+1 =0

0 или 0 = 0

0 или 1 = 1

1 или 0 = 1

1 или 1 = 0

Это логическое сложение или операция логического или или операция неразделительного ИЛИ

Дизъюнкция функция равная нулю только тогда когда оба аргумента = 0;

Дизъюнкция напоминает операцию объединения множеств.

Дизъюнкция коммутативна и ассоциативна а так же идемпотентна.

xUx = x

xVx = x

Аналогии этих функций неформальны, а носят глубокий смысл. Если множество x1 и x2 поставим с соответствии с множеством обладающими свойствами p1 и p2 то получим x= x1 U x2 при p1 U p2;

Если положить второй аналог сложения равным нулю, то получим функцию под названием неравнозначность или операцию разделительное ИЛИ. Или сложение по модую два:

x (+) y – логическая сумма

Логическая сумма отлична от обычного суммирования x + y.

X и y – логические слагаемые или дизъюнктивными членами.

0+0 = 0

0+1 = 1

1+0 = 1

1+1 = 0

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

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

X(+)y = x\y U y\x

Разделительное ИЛИ происходит от четвертой операции – симметрической разности

Импликация

X => Y; Влечет

0 => 0; true

0 => 1; true

1 => 0 false

1 => 1 true

импликацию можно опередить как функцию равную нулю тогда и только тогда когда первй элемент равен единицы а второй равен нулю. Операция импликации не коммутативна и она определяет 2 функции. Свойства:

X => Y = XVY

Y => X = XV!Y

Функция Шефффффера (|)

Стрелка пирса (стрелка внииииз)

Ну или штрих шефффера

X | Y = !(X^Y)

0001 => 1110

Функция пирса

X (стрелка вниз)Y = !(XVY)

0111 => 1000

Равнозначность или логическая эквивалентность

X~Y = !(X(+)Y)

0 ||0 = 1001

Эти три операции коммутативны так же как и операции из которых они произошли. То есть (X|Y)|Z = X|(Y|Z) and (XстрелкаY)стрелка Z = X стрелка ()

Равнозначность – ассоциативна.

Функция запрета.

X Y = X => Y; запрет по Y

Y X = Y => X Запрет по X

Можно показать что запрет по У равен запрету по Х

X delta Y = X^ !Y

Y delta X = !X ^ Y

Булева алгебра.

Книга: Колужнин. Что такое математическая логика?

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

Формулой «булева алгебра» - всякое выражение составленное из конечного числа букв U, V, W знаков операций булевой алгебры - V ^ и констант 0, 1 включая ( ) для выполнения различных операций. Будем говорить что формула А(U,VOmega) построена правильна если подстановки в нее (аргументов) произвольных булевых функций формула приводится к вполне определенной булевой функции.

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

Все буквы U,V Omega с индексами и без них, а так же константы 0 и 1 являются правильно построенными функциями

2. Если А и B правильно построенные формулы, то тогда выражение вида (!A),(A^B),(AvB) являются правильно построенными формулами. Для упращения написания правильно построенной формулы вводится правило: При прочих равных условиях в первую очередь выполняется отрицание, затем конъюнкция и после дизъюнкция. При сохранении этого порядка скобки не ставятся.

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

Замечание: В дальнейшем будут рассматриваться лишь правильно построенные формулы.

Одной из основных задач булевой алгебры является установление тождественных соотношений вида А(U,V, Omega…) = B(U,V,Omega) (1)

A,B – формулы, а U, V, Omega – произвольные булевы функции

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

Соотношение:

1. Закон коммутативности для конъюнкции X^Y = Y^X

2. (X ^ Y)^Z = X^(Y^Z)

3. X^X = X Идемпотентности закон

4. X v Y = Y v X

5. (X v Y) v Z = X v (Y v Z)

6. X v X = X

7. X ^ (Y v Z) = (X ^ Y v X ^ Z) – Закон дистрибутивности

8. X ^ Y v Z = (X v Y) ^ (X v Z) – Закон дистрибутивности

7 и 8 аналогичны законам действующие в алгебре множеств

9. правило поглощения X v X ^ Y = X

10. X ^ (X v Y) = X

9, 10 выполняется для любых наборов аргументов

11. Закон двойного отрицания !!X = X (соответствует операции инволюции в алгебре множеств)

12. Законы Де Моргана !(X ^ Y) = !X v !Y

13. !(X v Y) = !X ^ !Y

14. X v !X = 1

15. Закон противоречия: X ^ !X = 0

16. X v 0 = X

17. X v 1 = X

18. X ^ 0 = 0

19. !1 = 0

20. X ^ 1 = X

21. !0 = 1

Следствия из этих соотношений Формулы:

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

Если в формуле 2 хотя бы один член равен нулю, то вся конъюнкция будет равна 0. Если в дизъюнкции формулы 3 хотя бы один из членов равен 1, то вся дизъюнкция будет равна 1

Из соотношений 16 и 20 следует, что в любой дизъюнкции могут быть опущены члены равные нулю, а в любой конъюнкции могут быть опущены любые члены равные 1.

Обозначения:

X с волной – либо X, либо !X

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

1. Всякую конъюнкцию вида X1(с волной), X1(с волной) , Xk(с волной) в которой каждая буква встречается не более 1 раза будем называть элементарной конъюнкцией.

!X1 ^ X1 не элементарно.

2. К элементарным конъюнкциям причисляются так же сами переменные xi, xi(wave), 1

3. Число переменных входящих в элементарную конъюнкцию называется ее длинной.

4. Пусть формула А(U, V, W) содержит n переменных (аргументов), множество переменных входящих в формулу вида А есть M

из элементов М можно составить различные элементарные конъюнкции длиной от нуля до n. Элементарная конъюнкция максимальной длины из выбранных конъюнкций называется конституантой единицы (n-членов). Каждый элемент множества M входит в конституанту ровно 1 раз согласно определению конституанты. Например M={u,v,x,y} где u ^ v ^ !x ^y поэтому для множества из n элементов можно построить 2^n возможных конституант 1

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

5. Число дизъюнктивных нормальных членов входящих в состав ДНФ называется ее длиной. При этом ДНФ может состоять всего из одного члена. И даже предполагают, что ДНФ может иметь нулевую длину и не содержать ни одного члена. ДНФ = 0;

Пусть для

Xi ДНФ единичной длины.

1 – ДНФ

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

Теорема 1: С помощью основных соотношений (1-21) любая формула булевой алгебры может быть приведена к СДНФ.

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

Три этапа:

1. Покажем что эту форму с помощью правил Де Моргана и правила отризация отрицания можно перевести формулу А в формулу B. A(x1,x2,xn) -> B(x1,x2…xn,!x1, !x2…!xn) это значит, что в формуле B могут быть члены !Xi, но не !(Xi ^ xj) то есть к самим переменным. Пример: !((X v Y ^ !Z) v !Y ^ Z) = !(X v Y ^ !Z) ^ !(!y ^ z) = !X ^ !(Y ^ !Z) ^ !(Y ^ !Z) = !x ^ (!Y v !!!Z) ^(!!Y V !Z) = !X ^ (!Y v Z)V(Y v !Z)

2. На втором этапе формулу вида B всегда можно представить в виде ДНФ. Формула вида B строится из членов при помощи операций конъюнкции и дизъюнкции (так как эти операции коммутативные и ассоциативные, а так же обладают двумя свойствами дистрибутивности) (X v Y )^Z = X^Z v Y^Z ; (x v Y) v Z = (X v Z) ^ (Y v Z) можно произвести раскрытие скобок по аналогии с обычной алгеброй. Таким образом можно утверждать, что в формуле вида B можно раскрыть скобки по правилам обычной элементарной алгебры. После преобразований некотрые конъюнкции могут быть равными 1, а дизъюнкции равными нулю, которые могут быть опущены. После раскрытия скобок получим дизъюнкцию некоторых конъюнкций. Это еще не ДНФ. Что бы получить ДНФ нужно все конъюнкции входящие в нее сделать элементарными. ~X ^ X2 ^ … ^ ~Xk еще не элементарно. От повторяющихся членов вида xi можно избавиться при помощи закона идемпотентности для конъюнкции. Если конъюнкция не элементарна, то есть в нее входят члены xi и ~xi, то от них надо избавляться так как xi и ~xi = 0 и тогда вся форма ДНФ = 0. Таким образом используя закон идемпотентности и противоречия можно все неэлементарные конъюнкции сделать элементарными. При этом полученная дизъюнкция может быть не ДНФ так как в ней могут быть одинаковые дизъюнкции, которые можно вывести при помощи закона идемпотентности. Оставшиеся при этом члены составят ДНФ. Закончим этот пример. // окончание примера.

!X ^ (Y v Z) ^ (Y v !Z) = (!X ^ !Y v !X ^ Z) ^ (Y v !Z)= !X^ !Y ^ Y V !X ^ Z ^ Y ^

Любую ДНФ можно привести к равной ей совершенной ДНФ. Воспользуемся первым соотношением и законом исключенного третьего.

Xi ^ 1= xi & x v !x = 1

Пусть имеется в нашей ДНФ дизъюнктивный член не являющийся конституантой единицы.

Xi ^ Xj ^ 1 = Xi ^ Xj ^ (Xk v !Xk) = Xi^ Xj ^ Xk v Xi ^ Xj ^ Xk

Xi ^ !Xi = 0;

Таким образом любую ДНФ можно преобразовать в совершенную и равную ей ДНФ. Например:

Xv!Y ^ Z = X^(Yv!Y)^(Zv!Z)v!YvZ^(Xv!X)= X^ Y ^ Zv X^Y^!ZvX^!Y^ZvX^!Y^!Z СДНФ

Дана ДНФ но не СДНФ.

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

Все выполненные шаги обратимы, то есть от полученной СДНФ можно получить обратный переход к исходной формуле.

Достаточно неравенства А(x1,x2…xn) = B(x1,x2..)?

Теорема 2:

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

Пусть Alpha1 Alpha2 Alphan – некоторый набор значений этих переменных. Общей вид конституанты единицы будет x1(wave)^x2(wave) … ^ xn(wave)

Каждому набору переменных можно поставить в соответствие одну и только одну конституанту единицы вида x1(wave)^x2(wave) … ^ xn(wave), которая обращается на этом наборе в единицу

Из 2^n конституант единиц существует одна и только одна конституэнта единицы равная единице, а остальные равны нулю.

Если Alpha1 = 1, то в x1 она должна входить непосредственно.

Если Alpha2 = 0 то x1 ^ !X2

Правило: Такая конституанта единицы однозначно определяет условие xi(wave)=xi если Alphai = 1

И xi (wave) = 1xi, если Alphai = 0

Только при таком условии (правиле) мы получим нужную нам конституанту единицы. Пример:

{11 x2, x3 x4 x5} построить 2^5 конституент. Зададим этому набору какие-то значения.

{0 1 1 0 1 } тогда получим согласно предыдущему уравнению !x1 ^ x2 ^ x3 ^ !x4 ^ x5 получили требуемую конституенту, которая обращается в единицу.

Конституенту единиц равную единицы на наборе значений аргументов {Alpha1…Alphan} будем называть соответствующей данному набору.

Существует 2^n наборов из которых выберем все те наборы, где функция равна 1 и составим дизъюнкцию из всех коституент единицы соответствующих этим наборам. В результате получим совершенную ДНФ которую обозначим g(x1, x2… xn)

Полученная СДНФ обладает требуемыми свойствами для чего возьмем на любом наборе ДНФ равную единице. На всех наборах значений аргументов , на которых функция f обращается в единицу СДНФ g(x1,x2…xn) так же обращается в единицу. С другой стороны на всех наборах значений аргументов, на которых функция равна нулю СДНФ g так же будет равна нулю в силу своего способа построения, то есть g(x1,x2…xn) = f(x1,x2,xn)

Здесь каждой функции f соотвествует единственное значение совершенной ДНФ в g. (с точностью до перестановки дизъюнктивных и конъюнктивных членов)

Из теоремы 1 и 2 следует теорема 3:

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

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

Пусть имеем 2 формы: а и б! Эквивалентные меж собой. То есть А=Б => g

Переходим по теореме 2.

Доказанные теоремы позволяют проверять тождественные соотношения для чего обе части нужно привести к СДНФ. Затем нужно проверить совпадают ли они.

Наряду с СДНФ для проверки тождественности соотношений булевой алгебры используются конъюнктивные нормальные формы

Определение: Всякую дизъюнкцию вида x1(wave) ^ x2(wave) ^ Xk(wave)в которой каждая переменная встречается не более 1 раза будем называть элементарной дизъюнкцией. В частности к элементарным дизъюнкциям относят константу 0. Длина элементарной дизъюнкции есть число переменных входящих в эту дизъюнкцию. Пусть задано некоторое множество элементов M = {x1,x2,xn}. Элементарную дизюнкцию включающую в себя элементы этого множества будем называть конституентой нуля

Для каждого такого множества переменных существует 2 ^ n конституент нуля. Для любого набора значений аргументов Alpha1 Alpha2 Alphan существует единственная конституента нуля.

Правило.

Если Alphai = 0, то x1 = xi

Если Alphai = 1, то ^Xi = !Xi

При соблюдении этого правила не выполнится основное условие.

Конъюнкция любого числа элементарных дизъюнкций не содержащая 2х одинаковых дизъюнкций называется КНФ. КНФ состоящая из конституент нуля называется совершенной КНФ или СКНФ. Если КНФ равно нулю, то длина ее равна 1.

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

Если рассматривать булеву функцию 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 вывода:

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

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

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

Иногда для сокращения объемов таблицы значений истености, пользуются неполной таблицей выписывая в нее только те наборы для которых 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 переменных. И почти эквивалентен другим способам задания… Целесообразно рассмотреть основные и наиболее применяемые из них.

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

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

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

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

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

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

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

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

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

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

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

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

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

..

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

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

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

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

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

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

Простые имплеканты	Конституенты единицы
!x!y!z	!x!yz	!xyz	x!y!z	Xy!z	xyz
!x!y	*	*
!y!z	*		*	*
!xz		*		*	*
yz			*			*
xy					*	*

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

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

Рассматриваемая функция имеет 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 элементов.