1. РАЗРЕШИМОСТЬ - заключается в том, что должен существовать алгоритм, позволяющий для любой заданной формулы ИВ определять, яв-ся она выводимой или нет. Для проверки разрешимости достаточно рассмотреть формулу ИВ как АВ и проверить, будет ли она тождественно истинной. Если в АВ она тождественно истинна, то она выводима в ИВ.

2. НЕПРОТИВОРЕЧИВОСТЬ - какова бы ни была формула а(альфа), никогда а и (not a) не могут быть одновременно из аксиом этого исчисления с помощью указанных в нем правил ИВ непротиворечиво.

3. ПОЛНОТА - I. аксиоматич. исчисл. наз-ся полным в УЗКОМ смысле, если добавление к списку его аксиом любой невыводимой исчисл. форм. в кач-ве новой аксиомы приводит к противоречивому исчислению. ТЕОРЕМА: ИВ полное в узком смысле. II. аксиоматич. исчисление называется полным в ШИРОКОМ смысле, если любая тождественно истинная формула в нем доказуема (выводима).

4. НЕЗАВИСИМОСТЬ аксиом - заключается в невыводимости аксиомы из ост. аксиом по правилам вывода в данной системе. ТЕОРЕМА: Система аксиом ИВ независима.

20. Проверки выводимости формул ИВ методом резолюций.

D1=D1'vA;

D2=D2'v(not A).

D1'vD2' - РЕЗОЛЬВЕНТА дизъюнктов D1 и D2 по переменной A и обозначается resA(D1, D2) = D1'vD2'

Пример: res(A,(notA))=0 т.к. A&(notA)=0.

Если дизъюнкты D1 и D2 не содержат контарных переменных, то дизъюнктов в них не существует.

Пример:

D1=(notA)vBvC;

D2=Av(not B)vС.

resA (D1,D2)=BvCv(not B)vD;

resB (D1,D2)= (notA)vCvAvD.

ТЕОРЕМА:

1) если res(D1,D2) существует и не равен 0, то D1,D2 |- res(D1,D2).

2) если res(D1,D2)=0, то множество дизъюнктов D1,D2 противоречивы.

ТЕОРЕМА о полноте метода резолюции: мн-во дизъюнктов S противоречиво тогда и только тогда, когда существует резольвента вывод. из S, заканчивающийся нулем.

Где S={D1,D2,...Dn} - множество дизъюнктов.

21. Описание логики предикатов (ЛП). Символы ЛП. Логические функции. Предикаты. Предметные области и предметы. Переменные высказывания и предикаты. Элементарные высказывания и элементарные формулы.

Логика предикатов представляет собой развитие алгебры высказываний. Она содержит в себе всю алгебру высказываний. Но, помимо этого, логика предикатов вводит в рассмотрение высказывания, отнесенные к предметам. В ней уже имеется расчленение высказываний на субъект и предикат.

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

Символы логики предикатов

Ω- некоторое мн-во предикатов

а) х, у, z, ..., а также с числовыми индексами (x1, x2, ..., xn) – предметные переменные. б) a, b, с, ..., а также a1, a2, ..., ап – предметные константы (аналоги собственных имен естественного языка);

будем обозначать переменные, принимающие значения 1 и 0. Их мы назовем переменными высказываниями.

Выражения

обозначают предикаты, т.е. функции, аргументы которых принимают значения из области , а сами функции могут принимать только два значения: 1 и 0. Их мы будем называть переменными предикатами.

---

г) F(a_,G(a,b) – переменные предикаты;

д) логические константы:

е)

(,) – технические знаки (скобки, запятые и пр.);

22. Кванторы всеобщности и существования. Свободные и связные переменные ЛП.

Квантор всеобщности. Пусть R(x) – вполне определенный предикат, принимающий значение 1 или 0 для каждого элемента x некоторой области . Тогда под выражением

мы будем подразумевать высказывание истинное, когда R(x) истинно для каждого элемента x области , и ложно в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет: «для всякого x R(x) истинно». Символ называется квантором всеобщности.

Квантор существования. Пусть R(x) – некоторый предикат. Мы свяжем с ним формулу

,

определив ее значение как истину, если существует области , для которого R(x) истинно, и как ложь в противном случае. Знак называется квантором существования.

Кванторы и относятся к переменной x или что переменная x связана соответствующим квантором.

Предметную переменную, не связанную никаким квантором, мы будем называть свободной переменной.

23. Равносильные и приведенные формулы ЛП. Теорема о существовании приведенной формулы.

Если две формулы  и , отнесенные к некоторой области , при всех заменах переменных предикатов, переменных высказываний и свободных предметных переменных соответственно индивидуальными предикатами, определенными на , индивидуальными высказываниями и индивидуальными предметами из  принимают одинаковые значения 1 или 0, то мы будем говорить, что эти формулы равносильны на области .

Если две формулы равносильны на любых областях , то мы их будем называть просто равносильными.

Для каждой формулы существует равносильная ей приведенная формула.

ВСЕ равносильности, имеющие место в АВ переносятся на ЛП. к ним добавляются равносильности, связанные с кванторами.

24. Нормальные формулы и нормальные формы. Теорема о существовании нормальной формулы.

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

В записи нормальной формулы кванторы, если они есть, предшествуют всем остальным логическим символам. Например, приведенная формула

нормальна, если не содержит кванторов.

Теорема. Для каждой формулы существует равносильная ей нормальная формула.

25. Проблема разрешения в ЛП. Выполнимые, тождественно истинные для некоторой области Ω, тождественно истинные, невыполнимые формулы ЛП.

ПРОБЛЕМА РАЗРЕШЕНИЯ ЛП неразрешима (найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости — и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!», — в зависимости от того, истинно или ложно утверждение. Ответ не требует обоснований, но должен быть верным.) - доказал А.Черч (т.е. установил, что искомый алгоритм не возможен).

---

Формула логики предикатов называется ВЫПОЛНИМОЙ, если она истинна для некоторой области Ω и некоторых предикатов, на ней определенных.

Формула логики предикатов называется ТОЖДЕСТВЕННО ИСТИННОЙ ДЛЯ ОБЛАСТИ Ω, если она истинна для данной области Ω и для всех предикатов, на ней определенных.

Формула логики предикатов называется ТОЖДЕСТВЕННО ИСТИННОЙ или просто истинной, если она истинна для всякой области Ω и для всяких предикатов.

Формула называется ложной или НЕВЫПОЛНИМОЙ, если ни для какой области ни при каких заменах предикатов не является истинной.

26. Решение проблемы разрешения для логики предикатов с одной переменной.

Теорема: Если формула ЛП, содержит только предикат от одной переменной, выполнимый на некоторой области Ω, то она выполнима на области Ω, содержащей не более 2^n (2 в степени n) элементов, где n - число предикатов, входящих в рассматриваемую формулу.

Следствие: Если формула а(альфа), содержит только предикаты, зависящие от 1ой переменной, яв-ся тождественно истинной для всякой области не превышающей 2^n (2 в степени n) элементов, где n - число предикатов a(альфа), то a(альфа) - тождественно истинна.

27. Описание исчисления предикатов (ИП). Символы ИВ. Формулы ИВ. Части формул ИВ.

ИП - Все методы и результаты ИВ можно перенести на ИП.

СИМВОЛЫ логики предикатов:

1. - переменные предметы

2. A,B,C..X переменные высказывания, принимающие значения 1 и 0

3. - переменные предикаты

4. - логические связки

5. () - скобки;

6. и - кванторы.

Определение формулы представляет собой следующую рекурсию:

1. Каждое переменное высказывание есть формула.

2. Каждый переменный предикат есть формула.

3. Если  – формула, а x – предметная переменная, то и – формулы.

4. Если и – формулы, то , , , – формулами.

5. Никаких формул, кроме построенных по пп. 1-4 нет.

ФОРМУЛА ИП:

1)переменное высказывание есть формула.

2)F – символьный переменный предикат, a1...ai – символьная предметная переменная, то F(a1...ai) - формула,

3)если а(альфа) содержит СВОБОДНУЮ ПЕРЕМЕННУЮ x, то Vxа(x) и Эxа(x)–формулы, где х - СВЯЗАННЫЕ ПЕРЕМЕННЫЕ.

Все ф-лы ИВ - ф-лы ИП.

ЧАСТИ формулы:

1)частью каждой элементарной формулы является только она сама.

2)частью ф-лы Vxа (или Эxа, где а - альфа) является она сама и всякая часть ф-лы а(альфа).

3)частями формул a&b, avb, a->b являются сами формулы и все части формул a и b. 4)частью ф-лы (not a(альфа)) является она сама и все части ф-лы а.

28. Кванторы ИП. Область действие квантора в ИП. Коллизия переменных в ИП.
    
    

a-альфа: пусть Vxа (соответсвенно и Эxа) наз-ся формула а.

ОБЛАСТЬ ДЕЙСТВИЯ КВАНТОРА - ближайшая формула.

Условия получения ф-л:

1)в формуле свободные и связанные переменные обозначаются разными буквами; 2)если к.-л. квантор нах-ся в области действия другого квантора, то переменные, связанные этими кванторами обозначаются разными буквами.

---

КОЛЛИЗИЯ переменных в ИП - нарушение пунктов 1) и 2).

пример1: Vx(F(x)->ЭxG(x,y)) - это НЕ формула.

пример2: VxF(x)->ЭxG(x,y) - формула.

29. Аксиомы ИП.

Аксиомами ИП являются следующие формулы для любых формул φ, ψ, χ ИП^Σ, любых переменных x,y,z и любого терма t:

1) A→(B→A);

2) A→(B→C) → ((A→B)→(A→C))

3) (A∧B)→A;

4) (A∧B)→B;

5) (A→B)→((A→C)→(A→(B∧C)));

6) A→(A∨B);

7) B→(A∨B);

8) (A→C)→((B→C)→((A∨B)→C));

9) (A→B)→(¬A→¬B)

10) 1→¬A

11) ¬A→A

12) → F(y);

13) F(y) →

30. Правила образования выводимых формул в ИП (Правила заключения; подстановки в переменное высказывание и переменный предикат; замены свободной предметной переменной; переименования связанных предметных переменных; связывание квантором).

Правило образования выводимых формул:

a-альфа, b-бета.

1)ПРАВИЛО ЗАКЛЮЧЕНИЯ: Если а и a->b - выводимые формулы ИВ, то b - также выводимая формула: ((a,a->b)/?);

2)ПРАВИЛО ПОДСТАНОВКИ в переменное высказывание и переменный предикат: а)замена переменного ВЫСКАЗЫВАНИЯ: пусть а (альфа) содержит переменное высказывание А, тогда мы можем заменить в формуле а букву А всюду, где где она входит любой формулой b (бета), удовлетв. след условиям: 1)свободные переменные в b обозначены буквами, отличными от связанных переменных в a; 2)если А в a нах-ся в области действия квантора, обозначенного к.-л. буквой, то эта буква не входит в b. Такая подстановка называется заменой переменной в b на A. б)замена переменного ПРЕДИКАТА: пусть ф-ла а содержит предикат F(n), перем. b(t1,t2,...tn), ti - свободн. перем., где i изменяется от 1 до n. t1,t2,...,tn -отличны от всех предметных переменных в а. Если для ф-лы b соблюдаются условие 1) и 2) (см. выше) и если F в а нах-ся в обл-и действия квантора, связывающего к.-л. букву, то эта буква не входит в b, то возможна подстановка ф-лы b(бета) в а(альфа) вместо предиката F.

3)ПРАВИЛО ЗАМЕНЫ свободной предметной переменной: а(альфа)-выводимая ф-ла в ИП. а’ получается из а заменой любой свободн. предметной переменной другой свободн. предметной переменной, так что заменяемая переменная заменяется одинаковым образом всюду, где она входит в формулу а, тогда а' - тоже выводимая формула в ИП.

4)ПРАВИЛО ПЕРЕИМЕНОВАНИЯ связанных предметных переменных: если а выв-я в ИП то ф-ла а’ полученная из а заменой связанных предметных другими связанными переменными, отличными от всех свободных предм. переменных в а, то a' также является выводимой формулой в ИП.

5)ПРАВИЛО СВЯЗЫВАНИЯ квантором: 1)если b->а(х) – выв ф-ла в ИП и b не содержит свободн. переменной х, то b->Vxf(х) - выводимая ф-ла в ИП; 2)если а(х)->b выв ф-ла в ИП и b не содержит своб переменной х, то Эxа(х)->b - выводимая ф-ла в ИП.

Примечание:1)среди выв-х ф-л в ИП нах-ся все выв-е ф-лы ИВ; 2)всякая ф-ла выведенная из аксиом по прав-м ИП явл-ся тожд истинной ф-лой.

31. Непротиворечивость ИП.

Исчисление называется противоречивым если выводима ф-ла и её отрицание.

теорема: ИП НЕПРОТИВОРЕЧИВО.

---

Док-во: Все предикаты определены на нек-ой обл-ти Ω. Если Ω состоит из одного эл-та, то все ф-лы ИП можно рассматривать как ИВ. Все аксиомы ИП будут выводимыми ф-ми ИВ, правила ИП -> правила ИВ. Если в ИП ф-ла выводима, то в преобразованной системе она также была бы выводимой, но преобразованная система является ИВ, которая непротиворечива.

32. Определение выводимости формул из набора формул в ИП. Теорема дедукции.

Формула, полученная подстановкой в тавтологию ИВ, доказуема в ИП.

Выводимость в ИП:

Определение. Выводом формулы A из совокупности формул H называется последовательность формул A1, A2, ..., An, удовлетворяющая условиям:

1) A = An;

2) Всякая формула последовательности AI либо доказуема, либо взята из H, либо получена из предыдущих формул последовательности AI по одному из правил выводимости. Формула A называется выводимой из H (обозначается это так: H |- A), если существует вывод этой формулы из H.

Например, A→(B→C) |- B→(A→C) – правило перестановки посылок,

A→(B→C) |- A ∧ B→C – правило соединения посылок,

A ∧ B→C |- A→(B→C) – правило разъединения посылок.

Теорема о дедукции. Если Г U {φ,ψ} – мн-во формул ИП, то из Г,φ-|ψ следует Г-| φ→ψ.

33. Эквивалентные формулы в ИП. Приведенные и нормальные формы формул в ИП. Теорема о существовании нормальной формулы в ИП.

ИП выполнимы все эквивалентности ИВ из теоремы 3.

1) A∧A≡A, A∨A≡A (законы идемпотентности);

2) A∧B≡B∧A, A∨B≡B∨ A (законы коммутативности);

3) (A∧B)∧C≡A∧(B∧C), (A∨B)∨C≡A∨(B∨C) (законы ассоциативности);

4) A∧(B∨C)≡(A∧B)∨(A∧C), A∨(B∧C)≡(A∨B)∧(A∨C) (законы дистрибутивности);

5) ¬(A∧B)≡¬A∨¬B, ¬(A∨B)≡¬A∧¬B (законы де Моргана);

6) ¬¬A≡A (закон двойного отрицания);

7) A→B≡¬A∨B;

8) ⊢A∨¬A.

Утверждение 3. Пусть A, B – формулы ИП переменная x не является свободной переменной формулы B, переменная у не является свободной переменной формулы A. Тогда

1) ¬xA≡x¬A, 1΄) ¬xA≡x¬A,

2) x(A∧B)≡xA∧B, 2΄) x(A∨B)≡xA∨B,

3) x(A∨B)≡xA∨B, 3΄) x(A∧B)≡xA∧B,

4) xA≡x(A) 4΄)xA≡x(A)

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

34. Дедуктивная эквивалентность. Связь эквивалентности и дедуктивной эквивалентности.

Теорема 1 (о дедукции). Пусть φ₁,…,φ_m,φ,ψ – формулы ИП^Σ. Тогда φ₁,…,φ_m,φ⊢ψ φ₁,…,φ_m,⊢φ→ψ.

Следствие 2. Пусть φ и ψ ‑ формулы ИП^Σ. Следующие условия эквивалентны:

1. φ≡ψ;

2. φ⊢ψ и ψ⊢φ.

Два выражения А и В дедуктивно эквиваленты по отношению друг к другу, когда возможно вывести В из А (если принято А) и наоборот, А из В (если принято В).

Обычная эквивалентность не составляет необходимой основы дедуктивной эквивалентности. Если имеется положение QAB то верно, что A дедуктивно эквивалентно B относительно QAB, но если A дедуктивно эквивалентно B относительно определенных положений, то не всегда верно, что имеет место положение QAB.

---

Смотрите также файлы

• Экзаменационные вопросы.docx

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

• Исчисление высказываний.doc

• история билеты(все).docx

• Текст 10000 символов (транспорт Британии).docx