Дискретно-непрерывная математика (стр. 89 )

2.2. Порядковая логика

Рассмотрим конечное множество из п элементов .

Расположим элементы в порядке неубывания Введем над множеством А операцию выделения произвольного порядкового элементаэтого множества (r-операцию)

(2.1)

Здесь r называется рангом операции. Функцияназывается r-функ-цией. Легко видеть, что r-операция обобщает операции конъюнкции и дизъюнкции БЛ, переходя в них соответственно при r = 1 и r =п. Результа­том r-операции над элементами множества А является один из элементов этого же множества

Определение 2.1. Произвольная функция, аргументы которой взяты из множества А и которая представляется в виде суперпозиции r-опе­раций над А с различными значениями ранга r, называется функцией поряд­ковой логики.

Простейший пример такой функции - сама r-функция (2.1) Более сложный пример — функция

Любая функция порядковой логики на любом наборе аргументов принимает значение одного из аргументов. Это связано с тем, что r-операции, суперпозицией которых представляется выра­жение у, всегда имеют своим результатом одну из переменных, участвую­щих в операции. Таким образом, область значений функции f— мно­жество А.

Задать функцию порядковой логики можно, перечислив все п! вариантов упорядочения аргументов и указав для каждого варианта аргумент аi, значение которого принимает функция. Такое задание функции порядковой логики - частный случай первичного задания любой функции БЛ (см. § 1.2). Поэтому от такого, первичного задания функции порядковой логики можно перейти к ее аналитическому представлению с помощью суперпозиции операций БЛ —конъюнкции (1.6) и дизъюнкции (1.7) (операция отрицания (1.8) здесь не участвует, так как r--операция всегда имеет своим результатом значение одной из перемен­ных, но не ее отрицания).

Методика переxода та же, что и для функций Б Л.

Пример 2.1. Функция порядковой логики —

медиана — задана табл. 2.

Таблица 2

Найти аналитическое представление этой функ­ции с помощью БЛ.

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

Объединяя при помощи операций конъюнкции БЛ первую строку при вто­ром условии со второй строкой при втором условии, первую строку при первом условии с третьей строкой при втором условии и вторую строку при первом условии с третьей строкой при первом условии, найдем

Объединяя теперь три строки в одну с помощью операции дизъюнкции БЛ, получим искомое представление

Из сказанного выше ясно, что функции порядковой логики — это спе­циальный класс функций БЛ. Поэтому логические выражения порядковой логики можно подвергать эквивалентным преобразованиям с целью их приведения к наиболее простому или удобному виду, используя общие законы БЛ (§ 1.3). Однако есть и ряд специфических законов поряд­ковой логики. Это

— закон тавтологии

(2.2)

— переместительный закон

(2.3)

где — любая перестановка множества аргументов

—распределительный закон

(2.4)

гдеи два его важнейших частных случая:

(2.5)

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

2.3. Понятие порядкового логического определителя

Рассмотрим некоторое множество из непересекающихся подмножеств:

(2.6)

содержащее числовых элементов Элементы каждого подмножества Qi упорядочены:

(2.7)

Элементы различных подмножеств Qi могут находиться между собой в любом отношении Некоторые подмножества Qi могут быть

бесконечными Не исключается случай, когда

так что возможно

Множество (2.6) удобно записать в виде квазиматрицы q-го порядка:

(2.8)

в которой различные строки представляют различные упорядоченные под­множества Qi. Видим, что квазиматрица (2.8) отличается от обычной прямоугольной матрицы неодинаковой длиной строк, упорядоченностью элементов в каждой строке согласно (2.7). Представление произвольного множества Aq в виде объединения (2.6) упорядоченных подмножеств Qi является способом учета его частичной упорядоченности. На языке матрич­ной записи (2.8) множества Aq такое представление означает, что элементы в строках уже упорядочены и новые задачи могут быть связаны лишь с взаимным упорядочением элементов различных строк.

В частном случае, когда множество Aq неупорядоченное, все подмно­жества Qi / содержат по одному элементу и матричная запись множества Aq принимает вид матрицы-столбца

В другом частном случае, когдамножество Aq упорядоченное, оно со­держит всего лишь одно подмножество Qi, включающее все элементы множества Aq, матричная запись множества Aq принимает вид матрицы-строки

Расположим все элементы aij квазиматрицы общего вида (2.8) в поряд­ке убывания

(2.9)

Здесь а(r) — r-й порядковый элемент множества Aq.

Определение 2.2. Порядковым логическим определителем r-го ранга от квазиматрицы называется r-функция f(r) от множества элементов квазиматрицы.

Таким образом, порядковый логический определитель r-го ранга выде­ляет r-й по величине элемент исходной квазиматрицы Aq.

Логический определитель (ЛО) служит некоторой числовой характе­ристикой квазиматрицы. Его порядок q по определению тот же, что и квазиматрицы Aq. Обозначается ЛО r-го ранга от квазиматрицы Aq так:

(2.10)

Для каждой квазиматрицы Aq имеется целое семейство определите­лей получаемых варьированием параметра r. Последовательное вычис­ление определителей этого семейства означает взаимное упорядочение элементов различных строк исходной квазиматрицы.

По числу элементов в строках квазиматрица Aq и соответствующие ей определители могут быть конечными, бесконечными и полубесконечными. Последнее означает, что имеются строки с конечными бесконечным числом элементов. Специально отметим определитель-столбец, соответ­ствующий квазиматрице-столбцу:

(2.11)

и определитель-строку, соответствующий квазиматрице-строке

(2.12)

В (2.11) и (2.12) n может быть конечной величиной или бесконечностью.

2.4. Свойства логических определителей

Эти свойства устанавливаются следующими предложениями.

Лемма 2.1. Величина ЛО является монотонно неубывающей функцией ранга, т. е. если r>р.

Лемма 2.2. Перестановка местами любых двух строк ЛО не меняет его величины.

Доказательства лемм 2.1 и 2.2 следуют из определения ЛО