Приведенный упорядоченный дизъюнкт. Применение операции сокращения при нахождении упорядоченной бинарной резольвенты.

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 6

Обрамленная литера.

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

13. Подчеркнутая литера. Приведенный упорядоченный дизъюнкт. Применение операции сокращения при нахождении упорядоченная бинарная резольвента. OL –вывод.

Подчеркнутая литера.

Если в резольвенте литера L является отрицанием какой-либо обрамленной литеры, то литера подчеркивается. ù P –отрицание обрамленной литеры. Если встречается подчеркнутая литера, то в качестве второго бокового дизъюнкта центральной пары используется центральный дизъюнкт. S = {P V R, P Vù R,ù P V R, ù P V ù R}

Дизъюнкт является приведенным и упорядоченным, если его последняя литера является подчеркнутой (унифицирование с отрицанием обрамленной литеры).

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

L –вывод.

Линейный вывод дизъюнкта  из S с начальным дизъюнктом  называется L-выводом, если выполняется следующие условия:

1) Для i=1,2,…n-1,  является упорядоченной бинарной резольвентой дизъюнкта (центральный упорядоченный дизъюнкт) и (боковой упорядоченный дизъюнкт).

2) Резольвированная литера в (или в упорядоченном факторе дизъюнкте ) является последней литерой .

3)  является либо некоторым дизъюнктом  (j<i) (если  - приведенный упорядоченный дизъюнкт) либо является дизъюнктом S.

4) Если  - есть некоторый дизъюнкт (j<i), то  – приведенный упорядоченный дизъюнкт

5)В выводе нет тавтологий

К аттестации повторить вопросы из теории предикатов первого порядка:

(ВОПРОС № 2)

1. Область интерпретации.

Множество называется областью интерпритации, если это область изменения переменных х,у.

2. Предметные константы.

Предметные константы – это имена предметов (например: 0,1, π…)

3. Предикат первого порядка.

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

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

4. Область определения предиката.

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

5. Функциональные символы.

Функциональные символы – это обозначения для функции. В качестве символов можно использовать любые знаки. Важно, чтобы каждому символу была прописана валентность, которая определяет, со сколькими аргументами он может встречаться в формуле.

6. Синтаксические правила записи предикатов.

Синтаксические правила записи предикатов: константы, переменные, предикатные имена, функциональные имена.

7. Терм.

а) всякая предметная переменная и предметная постоянная есть терм

б) если f_iⁿ функциональная буква и t₁, t₂,…,t_n  - термы, то f_iⁿ (t₁, t₂,…,t_n ) –терм

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

Пример: a,x₁,f₁²(x,a)

8. Правила образования термов.

9. Атом.

10. Правила образования атомов.

Предикатные буквы, примененные к термам, порождают элементарные формулы или атомы, точнее: если A_i ⁿ - предикатная буква, а t₁,t₂,...,t_n - термы, то A_i ⁿ (t₁,t₂,...,t_n) - элементарная формула или атом.

11. Связки.

12. Отрицание. Таблица истинности.

Отрицание - это инверсия, делает истинное высказывание ложным.

13. Логическое умножение. Таблица истинности.

ЛУ (конъюнкция) - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное выражение ложно.

14. Логическое сложение. Таблица истинности.

ЛС (дизъюнкция) - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны.

15. Импликация. Таблица истинности.

Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

16. Эквивалентность. Таблицы истинности.

Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

17. Исключающее ИЛИ.

Исключающее ИЛИ (сложение по модулю 2) – A+B, “либо,либо” – строгая дизъюнкция. Результат выполнения операции является истинным тогда и только тогда, когда один из аргументов является истинным, а второй ложным.

18. Конъюнктивно-нормальная форма.

Конъюнкти́вная норма́льная фо́рма (КНФ) - нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.

А₁ ᴧ А₂ ᴧ А₃ ᴧ…ᴧ А_n

19. Дизъюнкт.

Дизъюнкт – дизъюнктивный одночлен с не более чем одним положительным литералом. B₁

20. Дизъюнктивно-нормальная форма.

Дизъюнкти́вная норма́льная фо́рма (ДНФ) - нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов.

А₁ v А₂ v А₃ v…v А_n

21. Конъюнкт.

конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. B1 ᴧ B2

22. Кванторы существования. и всеобщности.

Квантор всеобщности - ∀х А(х). (для всех, для каждого, для любого)

Квантор существования - ∃х А(х). (существует, найдется, существует хотя бы для одного).

∀ это условие, которое верно для всех обозначенных элементов в отличие от квантора ∃, где условие верно, только для каких-то отдельных элементов указанногомножества.

23. Переменные квантора.

Оператор предикатов применяется к формулам, содержащим лишь одну свободную переменную, даёт высказывание.

Вхождение переменной в формулу называется связанным, если оно находится в области действия квантора, использующего эту переменную, или же оно является вхождением в этот квантор. Вхождение переменной в формулу называется свободным, если оно не является связанным. Например в ∀ оба вхождения x связанные, а единственное вхождение y свободно.

24. Формулы исчисления предикатов первого порядка.

25. Область действия квантора.

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

26. Связанные и свободные переменные.

Вхождение переменной x в формулу называется связанным, если оно совпадает с вхождением в кванторный комплекс (∀x) или (∃x) или находится в области действия этого комплекса, иначе вхождение называется свободным. Если хотя бы одно из вхождений переменной в формулу свободно, то переменная называется свободной в этой формуле. Если хотя бы одно из вхождений переменной в формулу связанно, то переменная называется связанной.

27. Замкнутая формула.

Формула без свободных переменных называется замкнутой формулой.

28. Правила перестановки кванторов.

Справедливы следующие тождества

∃x ∃y P(x,y)≡∃y ∃x P(x,y), ∀x ∀y P(x,y)≡∀y ∀x P(x,y).

Разноименные кванторы можно переставлять не всегда.

Для каждой формулы А и любых предметных переменных х и у формула ∃х∀уА⇒∀у∃хА - логически общезначима, а обратная импликация, т.е. формула ∀у∃хА⇒∃х∀уА - не всегда является логически общезначимой.

29.  Правила преобразования формулы, включающей кванторы.

1. Исключить импликацию, выразив ее через V,ù,&;

2. Добиться того, чтобы ù относилось только к элементарным формулам;

3. Провести стандартизацию переменных для вынесения кванторов за скобки;

4. Вынести кванторы за скобки, т.е получить п.н.ф;

5. Исключить кванторы ∃.

30. Интерпретация в исчисления предикатов первого порядка.

31. Примеры интерпретаций.

Пример с замкнутой формулой. Дадим интерпретацию формуле ∀x∃y (P(x,y)). Множество М – множество всех женщин, а вместо P(x,y) – х мама у. Тогда формула превратится в логическое ∀x∃y (х есть мама у). Второй пример: вместо М множества - множество N всех натуральных чисел, а вместо P(x,y) подставим «х с у», определенное на N^2.. Тогда формула превратится в ∀x∃y (x <y) – для каждого положительного числа существует большее по сравнению с ним натуральное число.

32. Выполнимость формул.

Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе – существует модель), при которых формула А принимает истинные значения.

33. Опровержимость формул.

Опровержимая формула - замкнутая формула данной системы, отрицание которой выводимо в этой системе.

34. Невыполнимость формул.

Формула А логики предикатов называется невыполнимой, если она тождественно ложна на всякой области (на всякой модели).

Например, формула является невыполнимой формулой логики предикатов.

35. Обще значимость формул.

Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).

 - общезначимая формула логики предикатов.

ЗАДАЧА

1. Выполнить интерпретацию.
2. Провести формализацию целевого утверждения и правил.
3. Провести нормализацию и построить множество дизъюнктов для доказательства целевого утверждения.
4. Доказать методом линейной резолюции.

К аттестации подготовить:

полный конспект лекций с выполненными домашними заданиями:

1. Задание: конспект (предикаты первого порядка)
2. Задание о формализации правила тонущего тела.
3. Формализация задачи о футболе.
4. Блок схема метода резолюций для высказываний.
5. Блок схема алгоритма унификации для термов
6. Блок схема алгоритма унификации атомов

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология