Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Ход урока. 1. Мультиотношение. Сиг­натура мультиотношения.

1. Мультиотношение. Сиг­натура мультиотношения.

2. Реляционные структуры.

3. Сигнатура структу­ры.

4. Элементарно эквивалентные структуры.

5. Обеднение, обогащение структуры.

6. Группа как реляционная структура.

7. Функциональное отношение. n-местные функции (о-местные функции).

8. График n-местной функции.

9. Сигнатура функции. Структура сигнатуры функции.

10. Ограничение структуры (подструктура).

11. Конечно порожденная структура.

12. Изоморфизм двух структур одной и той же сигнатуры.

Подформулами формулы являются те формулы, которые по­являются в процессе ее образования из атомных формул. Ин­дукцией по сложности, определим кванторный ранг формулы:

- если атомна, то

- если , то

- если или то

- если или

Формулы с нулевым кванторным рангом, т.е. те, которые не содержат кванто­ров, называются булевыми формулами или свободными формулами.

Определим множество свободных переменных формулы:

- если атомна, то совпадает со множеством всех переменных, присутствующих в формуле

- если или , то

- если

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

Если , то говорят, что формула есть предложение. Переменная х, которая находится в области действия квантора называется связанной; одна и та же переменная может входить несколько раз, и свободно и связанно, в одну и ту же формулу.

Теория моделей занимается в основном семантикой, т.е. приданием смысла формальным предложениям, и потом ее исследованием. Семантика теории моделей достаточно элементарна: она состоит в приписывании "значе­ния истинности", истинной или ложной, формуле. Для этого, сначала нужно уточнить, как отношение R представляется символом r, и также, если форму­ла содержит свободные переменные, уточнить, какими элементами носителя R интерпретируется эти переменные.

Когда формула записывается в виде , где переменных , то

подразумевается, что все свободные переменные присутствуют среди но, возможно, не все лежат в

Рассмотрим m -арное отношение R, формулу элементов носителя R. Индукцией по сложности определим выражение

Сначала предположим, что атомна:

- если имеет вид х = у, то тогда и только тогда, когда а и b равны;

- если имеет вид , то тогда и только тогда, когда

Перейдем теперь к индукции: - если R не удовлетворяет

- если R удовлетворяет или R удовлетворяет

- , если R удовлетворяет и удовлетворяет

- , если существует b из носителя R, такой, что R удовлетворяет

- , если для любого b из носителя R,

Две формулы и называются синонимами или эквивалентными, если они имеют всегда одинаковое значение: для любого кортежа и для любого отношения R тогда и только тогда, когда

Например, легко видеть, возвращаясь к определению выполнимости, сле­дующие эквивалентности:

16) Если х - переменная, не входящая свободно в g:

17) Если х - переменная, не входящая свободно в g:

18) Если y, z не встречаются в :

где - формула, полученная из заменой каждого свободного вхождения уна z.

19) Если y, z не встречаются в :

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

- по правилу 4 (ассоциативность дизъюнкции) пишем вме­сто или вместо ее эквивалента, поскольку порядок, в котором берется дизъюнкция не влияет на выполнимость. И для того, чтобы писать дизъюнкцию формул пишут или ещё - точно так же используются записи

- введем запись как сокращение для ; читается " влечёт g "; выполнимость означает, что либо не выполняется, либо g выполняется.

Очевидно, что формула, которая может быть истинной или ложной; простой факт записи этой формулы не предполагает никакой связи между и g, в частности, не говорит, что влечёт g: это имеет место только, если истинна.

- также вводится символ двойной импликации как сокращение для

- по правилу 2 можно было ввести как сокращение и по правилу 13 квантор можно было ввести как сокращение ; с противоположной точки зрения, можно было наоборот ввести как первичный символ, добавляя подходящие правила для выполнимости формул, в которых он появляется.

- На практике скобки убираются с помощью разбиения символов на три группы: 1-ая группа состоит из ; 2-ая - из ; 3-я - из ; и применяем к ним правила приоритета, которые совпадают с теми, что применяются для выражений эле­ментарной арифметики.

- Запись означает"существует единственный х".

Имеется ряд соглашений касающихся бинарных отношений; часто пишут хrу вместо r(x,y), вместо .

Например,

Говорят, что две формулы являются почти эквивалентными, если для любого а взятого из носителя отношения R, с непу­стым носителем, .

Формула называ­ется пренексной или говорят, что она в пренексной форме, если все ее кванторы стоят впереди. Например, если и g без кванторов, то не пренексна, в то время как пренексны; эти три формулы почти эквивалентны, если х не входит свободно в g, а у в При­вести формулу к пренексной форме означает найти пренексную формулу, ей почти эквивалентную.

Отметим, что любая фор­мула имеет эквивалентную ей пренексную формулу, т.е. эквивалентную даже для пустых отношений. Булева часть формулы также допускает различные преобразования; на­пример, можно её привести к "дизъюнктивной форме", записывая как дизъ­юнкцию конъюнкций атомных формул или их отрицаний (воспользуйтесь пра­вилами с 1) по 11)).

4.2 Связи с «челноком»

Некоторые понятия о формулах зависят от определения, но существен­ный факт, который не зависит от выбора определения, следующий:

Теорема Фраиссе Две п-ки элементов а и b из баз т-арных отношений RuS являются р-эквивалентными тогда и только тогда, когда в R, и в S удовлетворяют одним и тем же формулам языка одного т-арного отношения, кванторный ранг которых не превышает р.

Следствие теоремыФраиссе:

Два m-арных отношения эле­ментарно эквивалентны когда на них выполняются одни и те же пред­ложения; если R, расширение S, то это расширение элементарно любая п-ка из носителя отношения S удовлетворяет одним и тем же

формулам в S и в R; два кортежа реализуют одинаковый тип в своих отношениях они удовлетворяют одним и тем же формулам.

Как следствие конечности числа классов р- эквивалентности выводим, что с точностью до эквивалентности существует лишь конечное число формул кван­торного ранга р от свободных переменных такая формула эквива­лентна дизъюнкции формул вида Только булевы избыточности и избы­точность кванторов или еще переименование связанных переменных порожда­ют бесконечное число таких формул. Формула , характеризующая класс С, является совсем не пренексной; приведение ее к пренексному виду сильно повысило бы ее кванторный ранг. В "челночном" методе Фраиссе стараются наоборот привести формулу как можно менее пренексному виду.

Ход урока.