Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. III. Постановка темы урока.
  2. Начало урока.
  3. Начало урока.
  4. Начало урока.
  5. Охар-те сущ-ть организац-управленческой деят-ти педагога ПУ. Раскройте содерж осн-х пед требований к орг-ии пед контроля в процессе проведения теортич урока.
  6. Ход урока.
  7. Ход урока.
  8. Ход урока.
  9. Ход урока.

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 ; два кортежа реализуют одинаковый тип в своих отношениях они удовлетворяют одним и тем же формулам.

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

 

Ход урока.


Дата добавления: 2014-12-15; просмотров: 16 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2021 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав