§2. Функции алгебры логики.

Функцией алгебры логики называется любая п-местная функция из { 0, 1} в { 0, 1} . Множество всех функций алгебры логики обозначается через С1.

Будем говорить, что функция f( x1, …, xi-1, xi, xi+1, …, xn) существенно зависит от переменной xi , если существует такая последовательность a1,…, ai-1, ai+1, …, an из 0 и 1, что f( a1, …, ai-1, 0, ai+1, …,an) ¹ f( a1, …, ai-1, 1, ai+1, …,an). Переменные, от которых функция f( x1, …, xn) существенно зависит, называются существенными переменными для функции f( x1, …, xn), остальные – фиктивными. Будем отождествлять функции, из которых добавлением фиктивных переменных можно получить одну и ту же функцию.

Пусть имеется некоторое множество G функций алгебры логики. Каждой п-местной функции f из Gf. Пусть v0, v1, v2… -- счетное множество символов, называемых переменными. Определим понятие терма: сопоставим функциональный символ

(а) переменная есть терм;

(б) если f— n-местная функция из G и T1,…, Tn – термы, то f(T1,…, Tn) – терм;

(в) других термов нет.

§1. Алгебра высказываний.

Алфавитом называется любое непустое множество. Элементы этого множества называются символамиалфавита. Словом в алфавите V называется произвольная конечная (возможно, пустая) последовательность символов из V . Произведением слов a и b называется слово ab. Слово b называется подсловом слова а , если a = a1ba2 для некоторых слов a1 и a2. Слово b может входить как подслово в слово а несколько раз. Результатом замены данного вхождения подслова b в слово a1ba2 на слово сa1сa2. данного называется слово

Результатом подстановки Sbaa в слово a вместо символа a слова b называется слово, полученное из аа на слово b. одновременной заменой всех вхождений подслова

Рассмотрим алфавит V = V 1 È V 2 È V 3, где

V 1 = {A0, A2, A3…}, V 2 = {ù , & , È , É }, V 3 = { ( , ) }.

Символы из V 1 называются переменными высказываниями или пропозициональными переменными. Символы из V 2 называются логическими связками. Связка ù называется отрицанием, & -- конъюнкцией, Èдизъюнкцией, É -- импликацией. Скобки из V 3 называются вспомогательными символами. --

Глава 2. Отношения

§ 7. Составные отношения

Подобно тому как мы устанавливали внутренние связи в файлах, для выделения некоторых данных из информации (например, ПОСТАВЩИК и МЕСТО РАСПОЛОЖЕНИЯ 3 посредством файлов DEL и SUP4 в примере 6.3) часто приходится связывать бинарные от-"^ношения друг с другом. Руководствуясь предыдущими рассуждениями, можно определить это понятие следующим образом.

Определение. Пусть заданы множества А, В и С и отношения а между А и В и р между В а С. Определим отношение между А и С следующим образом: оно действует из А в В посредством о, а затем из В в Ссоставным и обозначают р ° о, т. е. посредством р. Такое отношение называют

(роо)(д)=р(о(а)). /

Следовательно, (х, y)e(p^•a), если существует zeB такое, что (х, z)ea и (г, у)<=р. Отсюда следует, что Q^ffla °= о"'^. Чтобы проиллюстрировать ситуацию, рассмотрим рис. 2.11.

Глава 2. Отношения

6.Отношения на базах данных и структурах данных

Определение. При обработке данных наборы, из п элементов называют записями; элементы этих наборов называют полями. Записи, определяющие отношение, обычно содержатся в файле. Если потребовать, чтобы несколько файлов содержали совокупность записей, удовлетворяющих некоторым отношениям, то мы получим (относительную) базу данных.

Замечание. Для случая обработки данных мы сейчас употребили термин “поле”. В гл. 5 мы будем употреблять этот термин в математическом смысле, однако в данном случае это не приводит к недоразумению.

Глава 2. Отношения

§ 5. Отношения порядка

Поскольку из понятия равенства (скажем, между числами) возникает математическое понятие эквивалентности, некоторые неравенства могут также использоваться как модели для более широкого класса отношений.

Частичным порядком на множестве А назовем отношение, которое рефлексивно, антисимметрично и транзи-тивно. Порядок (называемый также отношением порядка) — это обобщение отношения ^ на N. Поэтому можно легко проверить требуемые три свойства. Заметим, что мы могли бы в качестве определения взять отношение <. Тогда отношение порядка было бы только тран-зитивно. Поэтому свойство транзитивности является наиболее важным для отношения порядка.

Определив отношение =S, можно определить отношение < следующим образом:

a<b^>a<b и aҐ-b. Аналогично, если задано <, то

а ^ Ь -“=*- о=Ь или о < Ь.

Глава 2. Отношения

§ 4. Разбиения и отношения эквивалентности

Во многих вычислительных задачах берутся большие множества и разбиваются таким образом, чтобы все интересующие нас ситуации можио было исследовать на нескольких правильно выбранных примерах. Например, один из путей получения качественной оценки характеристик языка программирования—это посмотреть конкретные программы, написанные на этом языке. Однако каждый интересный язык, включая такие языки высокого уровня, как Паскаль и Фортран, порождает бесконечно много программ, и, следовательно, мы должны выбирать программы так, чтобы они правильно отражали достоинства и недостатки языка. Чтобы быть более конкретными, давайте в дальнейшем предполагать, что язык имеет три основные управляющие структуры и четыре метода доступа и более у него нет никаких особых свойств. Мы могли бы в качестве примера взять семь программ, каждая из которых включает только одпу характеристику языка (хотя, вообще говоря, каждая программа может использовать более чем одну характеристику языка). Исследование этих программ тогда могло бы покрыть большую часть свинств языка

Глава 2. Отношения

§ 3. Свойства отношений

Очевидно, что общие отношения, будучи только подмножествами произведения множеств, не особенно интересны, поскольку о них можно сказать очень мало. Однако, когда отношения удовлетворяют некоторым дополнительным условиям, относительно них можно сделать более содержательные утверждения. В этом параграфе мы рассмотрим некоторые из основных свойств, которыми могут быть наделены отношения. Говорят, что свойство имеет место, если только выполнено соответствующее условие.

Определение. Пусть р — отношение на множестве А- Тогда:

а) р рефлексивно, если хрх для любого х е А;

б) р симметрично, если -тру влечет урх;

в) р транзитивно, если хру и ypz влечет хрг;

г) р антисимметрично, если хру и урх влекут х =y.

Терминология, вподоппая здесь, вероятно, является повой для читателя, однако он, по-видимому, знаком с этими понятиями. Иоясшш их на следующих примерах.