Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 9

7), то же самое можно сказать следующим образом. Пусть имеется дискретная система с конечным числом состояний 5=(зо..., з ), на вход которой мажет быть подано входное воздействие из множества (хь ..., х ). Всякое входное воздействие однозначно переводит состояние си. стемы в некоторое другое состояние и, следовательно, является преобразованием множества Я.

Последовательности воздействий — это композиции преобразований; следовательно, множество всех последовательностей является полугруппой с образующими (хь..., х ). Если такая полу- группа оказывается группой, то по любой входной последовательности и заключительномусостояниюсистемы можно однозначно определить начальное состояние системы. Алгебраические системы. Решетки.

До снх пор рассматривались алгебры, т.е. множества, на которых заданы операции. Множества, на которых кроме операций, заданы отношения, называются алгебраическими системами [4), Таким образом, алгебры можно считать частным случаем алгебраических систем (в которых множество отношений пусто), Другим частным случаем алгебраических систем являются модели — множества, на которых заданы только отношения. Понятие изоморфизма для алгебраических систем вводится аналогично тому, как это было сделано ранее для алгебр, с той разницей, что к условию (2.1) сохранения операций добавляется условие сохранения отношений при изоморфизме.

Рассмотрим здесь лишь один пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и ее применениях. Этот пример — решетка. Пусть задано частично упорядоченное множество М, Отношение порядка в дальнейшем будем обозначать ~. Для элементов а и Ь из М их верхней гранью называется любой элемент с~М, такой, что с)а, с)Ь, а их нижней гранью— любой элемент Ы ~а М, такой, что д~а, г((Ь, В общем случае для некоторых элементов а и Ь верхняя или нижняя грань может не существовать или быть неединственной, причем различные верхние (или нижние) грани могут быть несравнимы.

Решеткой называется частично упорядоченное множество, в котором для любых двух элементов а и Ь существует нх пересечение а(1Ь с — такая нижняя грань а и Ь, что любая другая нижняя грань а и Ь меньше с; их объединение а()Ь=д — такая верхняя грань пи Ь,что любая другая верхняя грань а н Ь больше г(. Таким образом, решетка— это алгебраическая система (М; (; (1, Я с одним бинарным отношением и двумя бинарными операциями. Отметим, что операции ('1 и () здесь понимаются как абстрактные операции алгебраической системы н отличаются от теоретико-множественных операций объединения и пересечения, определенных в $ 1.1 (в частных случаях могут с ними совпадать — см.

ниже пример 2,4, в). Пересечение и объединение ассоциативны (предлагаем читателю это доказать!), поэтому можно говорить о пересечении и объединении любого конечного подмножества элементов решетки. Пример 2.4. а. Любое полностью упорядоченное множество (например, множество целых чисел) можно превратить в решетку, определив для любых а, ЬеиМ а(.)Ь= шах (а, Ь), а(1Ь=ш(п (а, Ь). б. Определим на У отношение частичного порядка следующим образом: а~(Ь, если а делит Ь. Тогда а() Ь вЂ” наименьшее общее кратное а и Ь, а(1Ь вЂ” наибольший общий делитель а, Ь.

Например, 9 () 12=36, 9()12=3, 5 Д 7=1, 5 ()7=35. в. Система всех подмножеств зз(А) =(Мг) любого множества частично упорядочена по включению: М,(Мь если и только если М,ыМь Эта система является решеткой, элементами которой являются множества, а операциями— обычные теоретико-множественные операции объединения и пересечения (см. пример 2.1, в). г.

Рассмотрим множество В, двоичных векторов длины и, частично упорядоченное так, как это сделано в примере 1.!4, б. Для двоичных векторов это упорядочение выглядит так: с(п), если в векторе ш единицы стоят на всех тех местах, на которых они стоят в с (и, быть может, еще на некоторых). Например, (010) ((О11), а (010) и (100) несравнимы. Множество В, упорядоченное таким образом, является решеткой; в ней о()ы — это вектор, в котором единицы стоят на тех (и только тех) местах, где есть единицы либо в о, либо в н), а о()ю — это вектор, в котором единицы стоят на тех и только тех местах, где единицы есть и в о, и в ш. Например, (010) () (100) = (110), (010) () () (100) =(000).

При доказательстве теоремы 1.2 было установлено взаимно однозначное соответствие между множеством В и системой всех подмножеств любого множества А мощности и. Легко проверить, что это соответствие является изоморфизмом соответствующих решеток; таким образом, решетка, описанная в примере 2А, в, и решетка из настоящего примера изоморфны. д. На множестве Р=(л),...,л ) всех возможных разбиений конечного множества М решетка строится следующим образом. Частичный порядок: л;(лг, если любые два элемента М, которые находятся в одном блоке разбиения ль находятся в одном блоке разбиения л;; иначе говоря, если любой блок л; является подмножеством некоторого блока л,.

Например, для М=(а, Ь, с, с(, е, Д разбиение л,=(аЬ, с, аге, !) меньше разбиения лз=(аЬ7, са)е). Минимальным разбиением является разбиение л,„ы=(а, Ь, с, с(, е, !), в котором каждый блок состоит из одного элемента; максимальным разбиением является разбиение л „„= =(аЬса)е!), состоящее из одного блока. Пересечение л; и лг — это разбиение лю в котором два элемента содержатся в одном блоке, если и только если они содержатся в одном блоке и в ль и в ль Например, для пзбгЂ =(а, Ьс, с!е,!)л)()лз=(а, Ь,с,аг,е,!). Объединение л; и лг— это разбиение ль в котором два элемента содержатся в од- 48 ном блоке, если и только если они содержатся в одном блоке в гп или в пь Например,п ()пз= (аЬс, Не, 1). Конечное упорядоченное множество можно изобразить диаграммой, в которой элементам соответствуют точки; из точки а ведет стрелка в точку Ь, если а<Ь и нет такого с, что а<с<Ь. Например, решетка Вз изображается диаграммой на рис.

2.1, а. На языке диаграмм хорошо иллюстрируются все основные понятия, связанные с решетками: а<Ь, если и только Ф е Я7 а1 Ю) а б) Рис. 2.! 4 — 750 если существует путь нз стрелок, ведущий из а и Ь; верх няя грань а и Ь вЂ” это элемент, в который есть путь из а и из Ь; нижняя грань а и Ь вЂ” это элемент, из которого есть путь и в а, и в Ь. Когда упорядоченное множество не является решеткой? В двух случаях: 1) когда какие-либо два элемента не имеют верхней или нижней грани (на рис.2.!,б элементы г( и е, с и г( не имеют верхней грани, элементы Ь и с не имеют нижней грани); 2) когда для некоторой пары элементов наименьшая верхняя (или наибольшая нижняя) грань не единственна (на рис. 2.1, в все элементы имеют верхние и нижние грани, однако Ь и с имеют две наименьшие и несравнимые верхние грани, г( и е имеют дае наибольшие нижние грани, поэтому изображенное на этом рисунке множество не является решеткой).

Конкретный пример первого случая можно получить нз решетки удалением некоторых ее элементов На рис. 2.1, а видно, что после удаления 101 Вз остается решеткой, а после удаления 111 — нет. Удалением элементов из решетки можно получить и пример второго случая: если в В4 удалить все элементы, кроме 0000, 0100, 0010, 0111, 1110, 1111, то диаграмма для оставшихся элементов в точности совпадет с рис, 2.1, е. Решетка, в которой пересечение и объединение существуют для любого подмножества ее элементов, называется полной.

Ввиду отмеченной ранее ассоциативности пересечения и объединения конечная решетка всегда полна. Объединение всех элементов полной структуры — это максимальный элемент решетки, называемый единицей структуры. Пересечение всех элементов полной решетки — это мини* мальный элемент решетки, называемый нулем решетки. Решетка нз примера 2.4, в всегда полна (в том числе н для бесконечного А).

Единицей этой решетки служит само множество (содержащее любое свое подмножество), нулем — пустое множество. ГЛАВА ТРЕТЬЯ ВВЕДЕНИЕ В ЛОГИКУ вй. ЛОГИЧЕСКИЕ ФУНКЦИИ (ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ) В этой главе особую роль будут играть двухэлементноэ множество В и двоичные переменные, принимающие значения нз В. Его элементы часто обозначают О и 1, однако они не являются числами в обычном смысле (хотя по некоторым свойствам и похожи на них), Наиболее распространенная интерпретация двоичных переменных — логическая: «д໠— «нет», «истинно» (И) — «ложно» (Л). В контексте, содержащем одновременно двоичные н арифметические величины и функции, зта интерпретация обычно фиксируется явно: например, в языках. программирования (АЛГОЛ и др.) вводится специальный тип переменной— логическая переменная, значения которой обозначаются (гпе и 1а1зе.

В данной главе (за исключением й 3.4) логическая интерпретация двоичных переменных не является обязательной; поэтому будем считать, что В =(О, 1), рассматривая О и 1 как формальные символы, не имеющие арифметического смысла. Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики. Функцией алгебры логики (илн логической функцией) от п переменных называется п-арная операция на В. Первый термин более точен, однако второй более распространен, особенно в приложениях. Он и будет использо60 ваться в дальнейшем. Итак, логическая функция )(х„... ...,х,) — это функция, принимающая значения О, 1.

Множество всех логических функций обозначается Рм множество всех логических функций п переменных — Ра(п). Алгебра, образованная й-элементным множеством вместе со всеми операциями на нем, называется алгеброй 'и-значной логики, а п-арные операции на к-элементном множестве называются й-зночными логическими функциями п переменных; множество всех й-значных логических функций обозначается Р,. В настоящей книге й-значные логики расТаблица 8.1 сматриваться ие будут; речь идет только о логических функциях из Р .

Всякая логическая функция и переменных может быть задана таблицей, в левой части которой перечислены все 2" наборов значений переменных (т. е. двоичных векторов длины п), а в правой части — значения функции на этих наборах. Например, табл. 3.1 задает функцию х, ха хз 0 О О О О 1 О 1 О о 1 О О 1 О 1 1 1 О 1 1 1 трех переменных. Наборы, на которых функция )=1, часто называют единичными наборами функции Т, а множество единичных наборов — единичным множеством Т'. Соответственно наборы, на которых !=О, называют нулевыми наборами !. В табл. 3.1 наборы расположены в определенном порядке — лексико-графическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа.