Правила описания множеств.
Альтернативой явному перечислению элементов множества является set-нотация, где мы помещаем имя обобщенного элемента множества и через двоеточие описываем его. Например:
T = {x: x – любое слово в строке †this is a rule†} = {†this†, †is†, †a†, †rule†}
Обычно такая запись читается как, «множество всех x, таких что…». Чтобы принадлежать множеству, элемент должен удовлетворять условию, записанному после двоеточия.
Условие, описывающее принадлежность множеству может иметь несколько частей. Например, запись для множества
U = {x: x = <y, z>, y – любое слово в строке †this one list†,
z любой символ в строке †AB†}
означает, что x одновременно удовлетворяет трем условиям:
- x должен быть 2-списком
- x1 должен быть словом в †this one list†
- x1 должен быть символом в †AB†
Поскольку †this one list† содержит 3 слова, а †AB† два символа, множество U будет содержать 6 элементов, а именно:
U = {<†this†, A>, <†this†, B>, <†one†, A>, <†one†, B>, <†list†, A>, <†list†, B>}
Обобщенный элемент множества может быть структурой такой как список или множество. Таким образом, форма записи обобщенного элемента может содержать в себе часть условия. Например, U может быть описано следующим образом:
U = {<y, z>: y – любое слово в строке †this one list†, z любой символ в строке †AB†}
Если описание обобщенного элемента может быть более информативным, это обычно делается, потому что уменьшается количество условий, следующих после двоеточия. Например:
{<x, y>: x – строка, y = x Ñ /}
будет записано как
{<x, x Ñ />: x – строка}
Ситуация когда элементами множества являются другие множества случается настолько часто, что ей дали собственное название. Множеством мощности для любого множества S является множество всех подмножеств S, обозначаемое power(S).
Например, если
T = {†this†, †is†, †a†, †rule†}
тогда
power(T) = {U: U Í T} = {{}, {†this†}, {†is†},…, {†a†, †is†, †rule†}, T}
содержащее одно 0-множество, четыре 1-множества, шесть 2-множеств, четыре 3-множества и одно 4-множество, или 1+4+6+4+1=16 элементов. То, что 16 =24 не случайно. Для каждого из четырех элементов множества есть два варианта построения подмножества – с этим элементом и без него. Таким образом, количество членов в множестве мощности будет 2x2x2x2=16. В общем случае если S – n-множество, то power(S) будет 2n.
Set-нотация наиболее полезна, когда описываемые множества велики или бесконечны. Например, множество
{p: p – Паскаль-программа}
не может быть описано перечислением его элементов.
Операции над множествами.
Множества можно комбинировать для формирования новых множдеств и эти операции особенно полезны.
Объединение: S È T = {x: x Î S или x Î T}
Разность S – T = {x: x Î S, x Ï T} [различность]
Пересечение S Ç T = {x: x Î S, x Î T}
Эти операции легко визуализировать с помощью диаграмм Венна.
| S È T | S – T | S Ç T |
| 
| 
|
Если два множества находятся внутри третьего множества, то их объединение, разность и пересечение, также остаются внутри этого множества, т.е. если S Í U и T Í U, тогда
S È T Í U
S – T Í U
S Ç T Í U
Для любого множества S, пустое множество обнаруживает следующие свойства:
S È {} = S È {} = S
S – {} = S, {} - S = {}
S Ç {} = {} È S = {}
Объединение и пересечение коммутативны, т.е.
S È T = T È S
S Ç T = T È S
и ассоциативны, т.е.
R È (S È T) = (R È T) È S
R Ç (S Ç T) = (R ÇT) È S
Таким образом, нет необходимости в скобках для указания порядка при записи нескольких объединений и пересечений.
Разность не коммутативна и не ассоциативна.
Примеры. Пусть
S = {†this†, †is†, †a†, †set†}
T = {†this†, †is†, †another†, †set†}
тогда
S È T = T È S ={†this†, †is†, †a†, †set†, †another†}
S – T = {†a†}
T – S = {†another†}
S Ç T = {†this†, †is†, †set†}
(S – T) È (S Ç T) = {†this†, †is†, †a†, †set†}
(S – T) È (S È T) = {}
Следующая таблица обобщает характеристики операций над множествами.
| Операция | Символ | Описание | Свойства |
| Объединение | È | S È T = {x: x Î S или x Î T} | ассоциативная, коммутативная |
| Пересечение | Ç | S Ç T = {x: x Î S, x Î T} | ассоциативная, коммутативная |
| Разность | - | S – T = {x: x Î S, x Ï T} | не ассоциативная, не коммутативная |
Отношения и функции.
Любое множество 2-списокв или пар называется отношением. Отношения будут особенно полезны при обсуждении значения программ.
Слово «отношение» может означать правило сравнения, «эквивалентность» или «является подмножеством» и т.д. Формально отношения, которые являются множествами 2-списков, могут описать эти неформальные правила точно, путем включения точно тех пар, чьи элементы состоят в нужной связи друг с другом. Например, отношение между символами и 1-строками содержащими эти символы задается следующим отношением:
C = {<x, Ñx>: x - символ} = {<a, †a†>, <b, †b†>, …}
Поскольку отношение это множество, пустое отношение также возможно. Например, соответствие между четными натуральными числами и их нечетными квадратами – таких не существует. Более того, операции над множествами применимы к отношениям. Если s и r отношения, то существуют
s È r, s – r, s Ç r
поскольку это множества упорядоченных пар элементов.
Частный случай отношения – функция, отношение со специальным свойством, отличающееся тем, что каждый первый элемент находится в паре с уникальным вторым элементом. Отношение r является функцией, если и только если для любого
<x, y> Î r и <x, z> Î r, то y = z.
В таком случае каждый первый элемент может служить именем для второго в контексте отношения. Например, описанное выше отношение C между символами и 1-строками является функцией.
Операции над множествами также применимы к функциям. Хотя результат операции над множествами упорядоченных пар, которые являются функциями, будет обязательно другим множеством упорядоченных пар, а следовательно отношением, но не всегда функцией.
Если f,g –функции, то f Ç g, f – g тоже функции, но f È g, может быть а может и не быть функцией. Например, определим отношение голова
H = {< y, y>: y - строка} = {<a, †a†>, <a, †aa†>, …}
И возьмем отношение C, описанное выше. Тогда из факта, что C Í H:
C Ç H = C
является функцией,
H - С = {< y, y>: y – строка как минимум из 2 символов}
является отношением, но не функцией,
C – H = {}
является пустой функцией, и
C È H = H
является отношением.
Множество первых элементов пар отношения или функции называется областью определения (domain), а множество вторых элементов пар называется областью значений (range). Для элементов отношения , скажем <x, y> Î r, x называется аргументом r, а у называется значением r.
Когда <x, y> Î r и и y является единственным значением для x, value-нотация:
y=r(x)
читается, как «y является значением r для аргумента x» или, более кратко, «y является значением r для x» (функциональная форма записи).
Зададим произвольное отношение r и аргумент x, тогда существуют три варианта их соответствия:
- x Ï domain(r), в таком случае r не определено на x
- x Î domain(r), и существуют различные y, z, такие что <x, y> Î r и <x, z> Î r. В этом случае r неоднозначно определено на x
- x Î domain(r), и существует уникальная пара <x, y> Î r. В этом случае r однозначно определено на x и y=r(x).
Таким образом, функция – это отношение, которое однозначно определено для всех элементов его области определения.
Выделяют три специальные функции:
Пустая функция {}, не имеет аргументов и значений, то есть
domain({}) = {}, range({}) = {}
Функция эквивалентности (identity function), функция I такая,
что если x Î domain(r), тогда I(x) = x.
Постоянная функция, область значений которой задается 1-множеством, то есть всем аргументам соответствует одно и то же значение.
Поскольку отношения и функции являются множествами, они могут быть описаны перечислением элементов или заданием правил. Например:
r = {<†ball†, †bat†>, <†ball†, †game†>, <†game†, †ball†>}
является отношением, поскольку все его элементы - 2-списки
domain(r) = {†ball†, †game†}
range (r) = {†ball†, †game†, †bat†}
Однако, r не является функцией, потому что два разных значения встречаются в паре с одним аргументом †ball†.
Пример отношения, определенного с помощью правила:
s = {<x, y>: слово x непосредственно предшествует слову y
в строке †this is a relation that is not a function†}
Это отношение также может быть задано перечислением:
s = {<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>, <†relation†, †that†>,
<†that†, †is†>, <†is†, †not†>, <†not†, †a†>, <†a†, †function†>}
Следующее правило определяет функцию:
f = {<x, y>: первый экземпляр слова непосредственно предшествующий слову y
в строке †this is a relation that is also a function†}
которая также может быть задана перечислением:
f = {<†this†, †is†>, <†is†, †a†>, <†a†, †relation†>,
<†relation†, †that†>, <†that†, †is†>, <†also†, †a†>}
Значение программ.
Отношения и функции жизненно необходимы для описания для описания значения программ. Используя эти понятия, разрабатывается нотация для описания значения программ. Для простых программ значение будет очевидным, но эти простые примеры послужат освоению теории в целом.
Новые идеи: box-нотация, программа и значение программы.
Множество пар ввод-вывод для всех возможных нормальных запусков программы называется значением программы. Также может быть использованы понятия функция программы и отношение программы. Важно различать значение программы и элементы значения. Для конкретного входа Паскаль-машина, управляемая Паскаль-программой может произвести конкретный выход. Но значение программы это гораздо больше, чем способ выражения результата одного частного выполнения. Оно выражает все возможные выполнения Паскаль-программы на Паскаль-машине.
Программа может принимать вход разбиты на строки и производить выход разбитый на строки . Таким образом пары в значении программы могут быть парами списков состоящих из строк символов.
Box-нотация.
Любая Паскаль-программа – строка символов, передаваемая для обработки Паскаль-машине. Например:
P = †PROGRAM PrintHello (INPUT, OUTPUT); BEGIN WRITELN(‘HELLO’) END.†
Представляет одну из первых программ, рассмотренных в начале части I, в виде строки.
Также эту строку можно записать, опустив маркеры строки, как
P = PROGRAM PrintHello (INPUT, OUTPUT);
BEGIN
WRITELN(‘HELLO’)
END.
Строка P представляет синтаксис программы, а ее значение мы будем записывать как P. Значение P это множество 2-списков (упорядоченных пар) списков символьных строк, в которых аргументы представляют входные данные программы, а значения представляют выходные данные программы, то есть
P = {<L, M>: для входного списка строк L, P выполняется корректно
и возвращает список строк M}
Box-нотация для значения программы держит синтаксис и семантику программы, но ясно разграничивает одно от другого. Для программы PrintHello, приведенной выше:
P = {<L, M: L – любой список строк, а M – 1-список <†HELLO†> } =
{<L, <†HELLO†>>: L – любой список строк }
Помещая текст программы в box:
P = PROGRAM PrintHello (INPUT, OUTPUT); BEGIN WRITELN(‘HELLO’) END
Поскольку P - функция,
PROGRAM PrintHello (INPUT, OUTPUT); BEGIN WRITELN(‘HELLO’) END (L) = <†HELLO†>
для любого списка строк L.
Box-нотация скрывает способ которым программа управляет Паскаль-машиной и показывает только то что сопутствует выполнению. Термин «черный ящик» часто используется для описания механизма рассматриваемого только извне в терминах входов и выходов. Таким образом эта нотация подходит для значения программы с точки зрения ввода-вывода. Например, программа R
PROGRAM PrintHelloInSteps (INPUT, OUTPUT);
BEGIN
WRITE(‘HE’);
WRITE (‘L’);
WRITELN(‘LO’)
END.
Имеет то же значение что и P, то есть R = P.
Программ R также имеет CFPascal имя PrintHelloInSteps. Но поскольку строка †PrintHelloInSteps† является частью строки R, лучше не использовать PrintHelloInSteps в качетсве названия программы R в box-нотации.