Лекция №6
6.1 Метод Квайка – Мак-Класски нахождения
сокращённой ДНФ двоичной функции.
П???? функция f задана в виде СДНФ. Метод, предложенный Квайком в 1952 г. заключается в следующем:
применим к элементарным конъюнкциям СДНФ операцию «неполного склеивания»:
,
до тех пор, пока в результате применения этой операции не перестанут появляться новые конъюнкции;
в полученной ДНФ выполняем операции поглощения:
, пока это возможно.
Теорема 6.1.1: В результате выполнения пунктов 1, 2 получается сокращённая ДНФ функции f.
Доказательство: Сначала заметим, что из всякой импликанты функции f можно с помощью «операции расклеивания» получить дизъюнкцию импликант длины n.
Поскольку все импликанты длины n входят в СДНФ, то в результате применения операции неполного склеивания в СДНФ на первом этапе (пункт 1) метода будут получены все, в том числе и простые, импликанты функции f.
После применения второго этапа (пункт 2), очевидно, в ДНФ останутся только простые импликанты, т.е. полученная в результате ДНФ будет сокращенной.
Теорема доказана.
Мак-Класски в 1956 г. предложил удобную интерпретацию этого метода. Прежде всего заметим, что склеиваться могут только конъюнкции одинакового ранга, отличающиеся по одной переменной. Будем записывать конъюнкции в виде вектора ( ).
Индексом конъюнкции назовём .
Учитывая это замечание, разобьём все импликанты в СДНФ на группы в соответствии со значениями их индексов. Сам метод при этом заключается в заполнении таблицы специального вида.
Пример 6.1.2. Пусть f – функция, геометрическое представление которой дано на рисунке 5.2.1. Её СДНФ имеет вид:
Имеем
ИндексСДНФШаг 1Шаг 2Шаг 311000*1_00*
10_0*1__0______21100*
1010*
0101*
0011*11_0*
1_10*
101_
01_1
_011
0_11____________31110*
1011*
0111*__________________Таблица 6.1.3.
Применяя операцию неполного склеивания к импликантам длины n (СДНФ) производим заполнение колонки таблицы. При этом в СДНФ звёздочкой отмечаются использованные импликанты (они будут поглощаться на втором этапе). Затем операция склеивания применяется к конъюнкциям ранга (n-1) и т.д. Как только заполнение таблицы прекратилось, выбираются все не отмеченные звёздочкой импликанты и из них составляется сокращённая ДНФ. Для рассмотренного примера сокращённой ДНФ будет:
.
6.2 Метод нахождения тупиковых ДНФ.
Для изложения метода нахождения тупиковых ДНФ нам потребуется одно свойство ДНФ монотонных функций.
Утверждение 6.2.1: Минимальная ДНФ монотонной функции совпадает с её сокращённой ДНФ.
Доказательство: Сначала покажем, что все простые импликанты монотонной функции не содержат переменных с отрицаниями. Действительно, в противном случае наряду с простой импликантой функция имела бы импликанту (в силу её монотонности). Склеивая эти две импликанты, получаем противоречие с простотой импликанты .
Покажем теперь, что все простые импликанты входят в минимальную ДНФ. Пусть - простая импликанта. Тогда на наборе импликанта принимает значение 1. Все остальные импликанты должны быть равны на этом наборе нулю, так как в них обязательно должны входить переменные из множества . Следовательно, импликанта должна входить в минимальную ДНФ, поскольку иначе функция f на этом наборе будет равна 0.
Утверждение доказано.
Метод Петрика нахождения тупиковых ДНФ.
Рассмотрим таблицу, строки которой соответствуют простым импликантам функции f, а столбцы – конъюнкциям совершенной ДНФ (СДНФ). В каждую клетку записываем единицу, если соответствующая простая импликанта поглощает элементарную конъюнкцию и ноль – в противном случае. Такая таблица называется «импликантной таблицей».
Для функции из примера 6.1.2 она имеет вид:
СДНФ
Сокр.
ДНФ
1000
1100
1010
0101
0011
1110
1011
0111P11__011100100P2101_00100010P3_00100001010P40_1100001001P501_100010001Таблица 6.2.2
Согласно определению, каждая тупиковая ДНФ определяется таким набором строк, что в таблице, образованной этими строками в каждом столбце имеется одна единица, причём из этого набора нельзя удалить ни одной строки так, чтобы при этом ни один столбец не стал нулевым.
Пусть в общем случае в таблице имеется N столбцов и m строк. Поставим в соответствие простым импликантам сокращённой ДНФ переменные P1 … Pm. Фиксируем некоторую дизъюнкцию простых импликант. Будем считать, что Pi = 1, если i-ая простая импликанта
входит в эту дизъюнкцию и Pi = 0, в противном случае. Запишем в виде формалы условие того, что рассматриваемая дизъюнкция является ДНФ функции. Для этого необходимо, чтобы в каждом столбце таблицы была хотя бы одна единица, т.е.
(6.2.3) ,
где – элемент матрицы (таблицы), стоящий в i-ой строке и j-м столбце, .
Эту формулу можно трактовать как КНФ некоторой двоичной функции от переменных P1 … Pm, которая принимает значение 1 только на тех наборах переменных, которые соответствуют некоторым ДНФ исходной функции, и значение 0 – на наборах, которые соответствуют наборам импликант, не являющихся ДНФ исходной функции.
Заметим, что функция монотонна, так как формула 6.2.3 не содержит переменных с отрицаниями. Поэтому согласно утверждению 6.2.1 для нахождения её сокращённой ДНФ достаточно раскрыть скобки в формуле 6.2.3, а затем произвести все поглощения. Наконец, остаётся заметить, что в силу указанного выше свойства этой функции, её простые импликанты и только они будут давать тупиковые ДНФ исходной функции f.
Для таблицы 6.2.2 функция равна:
Отсюда P1P3P5 даёт для f тупиковую форму: ,
а P1P2 P4P5 даёт: .
Лекция №7
7.1 Алгебраические системы. Булевы алгебры.
Определение 7.1.1: Множество M с заданными на нём операциями и отношениями называется алгебраической системой. При этом M называется основным множеством системы, а множество символов, используемых для обозначения определённых на M операций и отношений называется сигнатурой алгебраической системы.
Алгебраическую систему с основным множеством M и сигнатурой , состоящий из символов операций fi арностей ni и отношений Rj арностей mj , обозначают в виде M( ), или подробнее M( ). При этом набор натуральных чисел 1, …, nk; m1, … ,ml> называется типом алгебраической системы M( ).
Если на алгебраической системе определены только операции, то она называется алгеброй.
Если на алгебраической системе только отношения, то она называется моделью.
Пример 7.1.2: N(+,*;=,<) – алгебраическая система;
Пример 7.1.3: N(+,*) – алгебра;
Пример 7.1.4: N(+,<) – модель.
Пример 7.1.5: Алгебрами являются полугруппы, группы, кольца, поля и т.д.
В математической логике особую роль играют так называемые булевы алгебры.
Определение 7.1.6: Булевой алгеброй называется множество B с двумя бинарными операциями « », « », и одной унарной операцией «’» и двумя нуль-арными операциями (т.е. выделенными элементами) 0, 1, удовлетворяющими условиям (при любых ):
1. ,
2. ,
3. ,
4. ,
5. ,
6. ,
7. ,
8. ,
9. ,
10. ,
11. ,
12. .
Несложно показать, что из условий 1-12 следуют равенства:
, , , , , .
Например, выведем из условий 1-12 равенство :
.
Элементы 0 и 1 булевой алгебры B называют её нулём и единицей. Иногда их обозначают в виде 0B и 1B.
Пример 7.1.7: Пусть 2M – обозначение множества всех подмножеств множества M, - бинарная операция пересечения множеств, - бинарная операция объединения множеств. Для A M обозначим A’=M\A, A’ – дополнение множества A. «’» - унарная операция, и M – нуль-арные операции, играющие роль 0 и 1. Тогда 2M( , , ,M) - булева алгебра.
Пример 7.1.8: Пусть M – множество всех положительных делителей числа m, равного произведению некоторых различных простых чисел. Определим операции « », « » и «’» следующим образом: для любых M положим , , .
Число 1 M играет роль нуль-арной операции 0.
Число m M играет роль нуль-арной операции 1.
Тогда M( , ,’,1,m) - булева алгебра.
Определение 7.1.9: Пусть - бинарное отношение на на M. Бинарное отношение на множестве M называется отношением частичного порядка (или просто отношением порядка), если оно рефлексивно, транзитивно, антисимметрично. Связное отношение частичного порядка называется линейным порядком. Отношение порядка обозначается через « ». Если и , то пишут .
Множество M с заданным на нём отношением частичного или линейного порядка « » называется, соответственно, частично или линейно упорядоченным множеством.
В некоторых случаях при изучении частично упорядоченных множеств используются их геометрические изображения – диаграммы. При построении диаграмм частично упорядоченного множества M( ) различные элементы из M отождествляются с различными точками плоскости так, что:
точка лежит левее (или ниже) точки если ;
точка соединяется отрезком с отличной от неё тачкой , если и не существует точки , отличной от a, b, удовлетворяющей условию (в этом случае говорят, что b непосредственно следует за a или a непосредственно предшествует b).
Пример 7.1.10: M = 2{1,2,3}
Положим для любых A,B M, .
Тогда диаграмма для M( ) представляется следующим рисунком:
{2,3}
{1,2,3}
{1,3}
{1,2}
{3}
{2}
{1}
Рисунок 7.1.11.
Пример 7.1.12: M={ }.
n
n-1
3
2
1
Положим a b «натуральное число a» «натурального числа b». Тогда диаграмма для M( ) имеет следующий вид:
Рисунок 7.1.13.
Пример 7.1.14: M={1,2,3,4,5,6}
6
4
Положим a b a | b для любых a, b M. Тогда диаграмма для M( ) имеет следующий вид:
5
3
2
1
Рисунок 7.1.15.
Интересно отметить связь булевых алгебр с частично упорядоченными множествами.
Пусть B – произвольная булева алгебра. Для произвольных элементов a, b B положим
a b a b=b.
Из условий 6.4.2 следует, соответственно, что так определённое отношение « » на B рефлексивно, антисимметрично и транзитивно. В итоге имеем частично упорядоченное множество B( ). Диаграмма для B( ) называется диаграммой булевой алгебры B.
Таким образом на рисунке 7.1.11 изображена диаграмма булевой алгебры всех надмножеств множества {1,2,3}.
7.2 Изоморфизм алгебраических систем.
В математике при изучении алгебраических систем их обычно классифицируют по темам и по свойствам. Так получаются классы полугрупп, групп, колец, полей, булевых алгебр и т.д. В каждом таком классе алгебраические системы изучаются с точностью до изоморфизма.
Определение 7.2.1: Алгебраические системы A, B одной и той же сигнатуры типа 1, …, nk; m1, … ,ml> называются изоморфными, если существует биективное отображение :A B, такое, что
для любой операции и любых элементов A выполняется равенство: ;
для любого отношения и любых элементов A:
При этом само отображение называется изоморфизмом системы A на систему B.
Пример 7.2.2: Пусть B1 – булева алгебра всех подмножеств множества M={a1 … an},
B2 – булева алгебра всех делителей числа m = p1 p2 … pn, где p1 p2 … pn – различные простые числа.
Определим отображение :B1 B2 положив и .
Легко видеть, что , ; , а также , ,
для любых подмножеств A, B множества M. Это и означает, что есть изоморфизм булевой алгебры B1 на булеву алгебру B2.
Замечание 7.2.3: Легко видеть, что отношение изоморфизма является отношением эквивалентности на любом множестве алгебраических систем одной сигнатуры и потому все такие системы разбиваются на классы изоморфных систем. Из определения 7.2.1 видно, что изоморфные алгебраические системы сигнатуры с точки зрения свойств операций и отношений отличаются лишь обозначениями элементов. Отождествив в системах из определения 7.2.1 элементы a и (a), мы получим одну и ту же алгебраическую систему. Тем самым достигается существенная экономия сил и времени при изучении всего многообразия алгебраических систем.
Замечание 7.2.4: Понятие изоморфизма естественным образом распространяется на алгебраические системы различных, но однотипных сигнатур. При этом необходимо только предварительно установить между операциями (а также между отношениями) систем взаимно однозначное соответствие, сохраняющее арности. Так, если операции fi соответствует операция , то условие 1 определения 7.2.1 запишется в виде:
.
В частности, если fi – бинарная операция « », а f – бинарная « », то последнее равенство будет иметь вид:
.
Пример 7.2.5: Рассмотрим алгебры R+( ) и R(+), где R+ – множество всех положительных действительных чисел; R – множество всех действительных чисел.
Положим , для любого x R+,
где a – некоторое положительное число, a 1. Тогда условие 1 определения 7.2.1 гарантируется в этом случае известным свойством логарифмов:
.
Замечание 7.2.6: Этот пример 7.2.5 показывает, что в некоторых случаях переход к изоморфной алгебре позволяет существенно упростить вычисления. В этом проявляется ещё одна положительная роль понятия изоморфизма. |
