Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 11
Текст из файла (страница 11)
Покрытием столбцов строками в двумерной таблице называется такое множество строк, при котором для каждого столбца найдется хотя бы одна строка из этого множества, на пересечении с которой этот столбец имеет единицу, причем при вычеркивании хотя бы одного элемента из этого множества строк указанное свойство не выполняется. 2. Построение и покрытие таблицы Квайна. Таблица Квайна — двумерная таблица, каждой строке которой взаимно однозначно соответствует максимальный интервал, столбцу — конституента, а на пересечении т-й строки и т'-го столбца находится единица, если у-я конституента входит в т-й максимальный интервал, в противном случае клехку (т, 1) не заполняют или ставят в ней О. Для рассматриваемого примера таблица Квайна имеет вид табл. 1.15.
Таблица 1ЛЗ Гл. 1. Основы мноеосортных множеств 11.7. Алеоритм — двцеортное множество. Системы счисление 55 54 Максимальный инхервал называется обязательным, если найдется консхитуенха, принадлежащая ему и только ему. Схолбец, соотвехсхвующий этой констихуенхе, содержит холько одну единицу. Множество обязательных интервалов образует ядро покрытия. В данном случае ядром покрытия является множество 1-00, -1Ц, которое покрывает первый, второй, четверхый и пяхый схолбцы. Для образования покрыхия можно взять либо вхорую, либо хретью строку.
В резульхахе получаем два покрыхия: 1-00, — 11, 1-01, 1-00, — 11, 11-1; каждое из них являехся минимальным и имеет сложносхь 6. Для определенности выберем первое из покрыхий, кохорое соотвехствуех минимальной НФК, задающей множесхво М(Мм Мг, Мз) = МгПМзОМгйМз0МгйМз В результате упрощения сложносхь ЦМ) уменъшилась ох 15 до 6. Минимальная НФК находится в результате перебора всех покрытий, осуществляемого с помощью преобразования мультипликатнвно-аддихивной формы в адднтивно-мультипликахивную форму.
Для рассматриваемого примера обозначим четыре схроки хабл. 1.15 соохвехственно буквами а, 6, с, И. Запишем множесхво стран, каждый элемент кохорого покрывает у'-й столбец: у=1~Ах — — (а), у=2 — ьАг=(а,Ь), у = 3 ~ Аз = 16, су, у' = 4-+ Ав = (д), у' = 5 ~ Ав — — (с, а). Покрыхием столбцов строками этой таблицы является множество схрок, покрывающее все схолбцы хаблицы, и при удалении хохя бы одной из эхих строк найдехся непокрытый столбец. Следовательно, если каждое множество А представить в виде объединения его элементов и найти пересечение всех множеств А, ПА., у то каждое пересечение в полученной аддитивной форме соохвехствуех покрытию, а число всех покрыхий равно числу различных пересечений в полученной аддитивно-мульхипликативной форме: Г)А, =оп(аОЬ) П(ЬОс) ИЫИ(сод) = = ай (60 с) й И= аПЬП ИОай сГ1 д. Полученные пересечения ай 6 й д и аГ1 ей И порождаюх два покрыхия: (-00, 1-0, — 1Ц и 1-00, 11 —, -1Ц; каждое из них соответсхвует минимальной НФК заданного множесхва М.
Дальнейшее уменьшение сложносхи выражения, определяющего заданное множество, возможно, если из класса НКФ перейхи в класс скобочных форм Каихора (СФК). Выражение, определяющее множесхво М, называехся скобочной формой Кантора, если кроме первичных терман и знаков операций объединения и пересечения в него входях круглые скобки. В рассмахриваемом примере сложносхь представления множества, равная 6, понижаехся до 5 в результахе применения закона дистрибутивности пересечения относихельно объединения: М(Мм Мг, Мз) = Мз Г1 (Мг 0 Мг) 0 Мг ПМз. Преобразование мультиплнкативно-аддихивнай формы в аддихивно-мультипликативную называется методом Летрика, который может бып определен соответствующим алгорихмам. $ 1Л.
Алгоритм — двусортное миожество. Системы счисления Важным классом многосортного множества является класс, элеменхами которого являюхся алгоритмы. Слово "алгоритм" (а1- бог!1Ьш) является латинской транслихерацией арабского имени хорезмского махематика 1Х века аль-Хорезми. Дадим инхуихивное определение алгорихма. Алгоритмом называется двусортное множесхво (М, Вг), где М вЂ” множество правил (процедур) решения задачи, обладающих следующими свойсхвами: массовости — ннварианхности относихельно входной информации; детерминированности — одназначносхи применения этих правил на каждом шагу; реэультативности — получения после применения этих правил информации, являющейся результахам; элементарности (прозрачности) — отсутствия необходимосхи дальнейшего уточнения правил. Символ Вг — бинарное охношение в множесхве Мр, Вг С Мг, (р;, ру) б Вг, если' после процедуры р; выполняется процедура р .
Алгорихм можно представить в виде графа, каждая вершийа кохорого соохветсхвует правилу, и бинарное охношение Вг определяет порядок выполнения эхих правил. Если при этом вершина является началом илн концом только одной дуги, то правило называехся арифметическим. Если правило является концом холько одной дуги, а началом — более чем одной дуги, хо правило называется логически,и. После выполнения логического правила происходих ветвление вычислихельного процесса согласно полученному результату. Первоначально посхроение алгорихма нельзя выполнихь полносхью формальным образом. Зхо — искуссхво. Рассмотрим, например, посхроение алгорихма перевода целых чисел, заданных в десяхичной системе счисления, в снсхему счисления с основанием Я. Как строихь алгоритм, будех поняхно если догадахъся, что сдвиг на один разряд вправо целого числа (рис.
1.20, а) эквиваленхен делению этого числа на основание сисхемы счисления и Рнс. 1.21 Рнс. 1.20 Гл. 1. Основы многосортных множеств чхо при эхом содержимое нулевого разряда мажет быть выявлено как дробная часть в виде осхатка при целочисленном делении на Я (рис. 1.20, 6). Очевидна, что при переводе дробного числа идея Белое наело Р алгарихма основана на его сдвиге влево на один разряд (эхо эквивалентна умножению на Я); при эхом содержимое 1-го разряда при умножении будет представлять собой целую часхь произведения (рис. 1.21, а).
Охсюда имеем алгоритм перевода дробнога числа с заданной точностью 5 " (рис. 1.21,6). Примечание. В средневековой Европе алгорихмом назывались десяхичная сисхема счисления и искусство счета в ней, хак как благодаря лахинскаму переводу в Х1П веке хракхата альХорезми "Книга а сложении и вычихании на основе индийского исчисления" Европа познакомилась с позиционной системой.
Системой счисления, или ириерацией, называехся совокупнесть приемов и правил для обозначения и наименования чисел. Сисхема счисления задает правила кодированной записи количе- 11.7. Алгоритм — двэсортное множество. Системы сннсленнл 57 ственных эквивалентов, позволяющие для каждого числа однозначно получать его кодовую запись и по каждой кодовой записи— саатвехсхвующий ей количесхвенный эквивалент. По соглашению дробное несло количественный эквивалент записывается в десяхичной системе счисления. Множество элементарных знаков, используемых для кодирования, называют цифрами счисления.
Слово "цифра" — ох арабского слова "сыфр", которое в свою очередь являехся переводом древнеиндийского слова (алфавит "деванагари") "сунья", что означает пустое место (разряд), в кохорое помещается числовой знак при задании количесхвенных отношений. Системы счисления бывают непозиционные и позиционные.
В неяоэиционных сисхемах каждой цифре сопосхавлен некоторый стандартный количесхвенный эквивалент, а количественный зквиваленх кода числа вычисляехся как некоторая функция ох количества зквиваленхных цифр, входящих в запись ахата кода. Примером хакай сисхемы являехся система счисления, в которой Гл. 1. Осноеы миогосоршныг множесте 58 5 1.7. Алгоритм — деусоршиое миожесглео. Системы счисления 59 используется только одна цифра, например 1.
Этой цифре сапаставлен количественный эквивалент, равный единице. Тогда код 1Н1Н означает количественный эквивалент шести, функцией при вычислении количественного эквивалента кода здесь является операция сложения. В ноэиционныя системах каждой цифре некоторый количественный эквивалент сопоставляется не однозначно, а в зависимости от ее положения в коде числа.
Будем рассматривать только линейно упорядоченные записи. Выберем в записи начало отсчета нулевой разряд). Разряды влево от него будем нумеровать 1, , ..., а вправо от него -1, -2, ... Каждой цифре а;, стоящей в разряде с номером у, сопоставляется количественнйй эквивалент ~р(а; ). Функция уу либо одинакова для всех разрядов, либо ее вид изменяется от разряда к разряду.
В дальнейшем будут рассматриваться только позиционные системы с одинаковой функцией всех разрядов. Всякая позиционная система задается тремя компонентами: (А, <р, Р). Здесь А — множество цифр системы; ~р — функция, определяющая для цифр в каждом разряде их количественный эквивалент; г' — функция, определяющая по количественным эквивалентам в записи числа количественный эквивалент самого числа. В зависимости от вида функции Г выделим системы счисления двух типов: аддитибные и мультиаликатиаиые. В системах первого типа Р— функция сложения, а в системах второго типа — функция умножения.
Если для любых цифр А и любого у имеет место равенство ~р(а;, Я = У ° у(аеч 0), то говорят о системе счисления с основанием Ь'. Если 1о(а;,,~) = ру 97(а;, 0) и ру не совпадают при различных у, то скстема оесомаэначнаео тина, а р — веса разрядов. Если в системе с основанием 5 множество цифр состоит нз О, 1,..., Я- 1, то система имеет естественное множество цифр (естесглвенная система счисления); если Я = т+ Й+ 1 и множество цифр — (-т, -т+1, ..., -1, О, 1, 2, ..., Йу, то при т = Й система имеет симметрическое множество цифр (симметрическая система счисления); при Й > т или т > Й система-имеет асимметрическое соответственно в положительную или отрицательную сторону множество цифр (асимметрическая сиспасма счисления).
Наиболее часто используют естественные системы счисления с натуральным основанием. Любое число з в системе с основанием Я представимо в следующем виде: и =в ~~1 (а;] 5', где (а;] — количественный эквивалент цифры а; в нулевом разряде.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
