Орехов Логика билеты

61.Схема применения принципа резолюции для доказательства факта логического следствия в АВ. Пример применения принципа резолюции для доказательства факта логического

1. Высказывания. Примеры высказываний. Пропозициональные переменные. Определения основных логических операций.

Высказывание – утверждение, о котором можно сказать истинно оно или ложно. Например, «46 – четное число».

Высказывания в будущем будем обозначать латинскими буквами, которые будем называть

пропозициональными переменными.

В качестве средств связывания используют логические операции, называемые логическими операциями: отрицание, дизъюнкция, конъюнкция, импликация.

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

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

Слово (цепочка) – произвольная последовательность символов данного алфавита.

Если ≡ , , , то , , – подслова .

A,,B,C – пропозициаональные переменные

¬, &, , → - логические связки

Запятая – вспомогательный символ.

Язык алгебры высказываний – множество всех слов алфавита.

Понятие правильно построенной формулы

1)Пп есть ппф

2)Если , – ппф, то ¬ , ¬ , ( & ), ( ), ( → ) – ппф

3)Других ппф нет.

( → ( & )) – ппф

(¬ ) – не ппф

3. Теорема о замене подформулы ппф АВ. Пример

Пусть . , - ппф. подформула .

Тогда результат замены ∫ тоже ппф.

4. Теорема о подстановке формулы вместо пропозициональной переменной в ппф. Пример.

Пусть . – ппф, – пп.

Тогда результат замены ∫С тоже ппф.

5.Значение ппф АВ. Таблица истинности. Пример построения таблицы истинности. Выполнимые, опровержимые, тождественно истинные, тождественно ложные формулы АВ.

Примеры.

Значение ппф определим следующим образом:

1)Если ппф – пп, то её значение (t или f) задается непосредственно

2)Если ппф не является пп, то

1)Если ппф имеет вид ¬, то = тогда и только тогда, когда = .

2)Если ппф имеет вид ( & ), то = тогда и только тогда, когда = , = .

3)Если ппф имеет вид ( ), то = тогда и только тогда, когда = , = .

4)Если ппф имеет вид ( → ), то = тогда и только тогда, когда = , =

Ппф называется выполнимой, если существует такой набор значений пропозициональных переменных 1, … , на котором (1, … , ) =

Ппф называется опровержимой, если существует такой набор значений пропозициональных переменых 1, … , на котором (1, … , ) = .

Ппф называется тождественно истинной, если (1, … , ) = для любого набора значений1, … , . Тождественно истинную формулу будем обозначать . (I большая)

Ппф называется тождественно ложной, если (1, … , ) = для любого набора значений1, … , . Её мы будем обозначать F.

Примеры:

( ) – выполнимая, опровержимая.

( ¬ ) – тождественно истинная

( &¬ ) – тождественно ложная

6. Теорема о подстановке ппф вместо пропозициональной переменной в тождественно истинной формуле.

Пусть , – ппф, – тождественно истинна, P – пропозициональная переменная.

Тогда ∫ – тождественно истинная формула.

7. Теорема о правиле modus ponens

Если формулы и ( → ) тождественно истинны, то формула также тождественно истинна.

8. Эквивалентные формулы алгебры высказываний.

Пусть и – ппф, а 1, … , – пп, такие, что

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

В формулы и входят пропозициональные переменные только из данного набора.

Формулы и назовем эквивалентными, если при любых наборах значений пропозициональных

переменных 1, … , значения и совпадают. Факт эквивалентности будем записывать как

~.

Все тождественно истинные формулы эквивалентны, все тождественно ложные формулы эквивалентны.

9. Теорема о подстановке ппф вместо пропозициональной

переменной в эквивалентные формулы АВ.

Пусть , , - ппф, P – пп.

Тогда, если ~, то ∫ ~ ∫

10. Теорема о замене подформулы на эквивалентную формулу в ппф АВ.

Пусть – подформула ппф , ~1. 1 – результат замены на 1 в ппф . Тогда ~1.

11.Понятие формулы с тесными отрицаниями. Пример.

Ппф АВ называется формулой с тесными отрицаниями, если она не содержит связки →, а если имеются связки ¬, то они относятся только к пп.

( (¬ & )) – формула с тесными отрицаниями

¬( ( → )) – не является формулой с тесными отрицаниями

12. Теорема об эквивалентной формуле с тесными отрицаниями

Для любой ппф алгебры высказываний существует эквивалентная ей формула с тесными отрицаниями.

13.Понятие днф и кнф. Примеры.

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

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

Дизъюнктивной нормальной формой (днф) называется произвольная дизъюнкция элементарных конъюнкций.

Конъюнктивной нормальной формой (кнф) называется произвольная конъюнкция элементарных дизъюнкций.

Примеры:

(( & ) ( & & )) - днф

(( )&( )) – кнф

14.Теорема о существовании эквивалентной днф

Для любой ппф АВ существует эквивалентная ей днф.

15.Теорема о существовании эквивалентной кнф

Для любой ппф алгебры высказываний существует эквивалентная ей кнф.

16. Теоремы о виде тождественно ложной днф, тождественно истинной кнф

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

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

17. Понятия сднф, скнф. Построение сднф, скнф по таблице истинности данной формулы.

Совершенная дизъюнктивная нормальная форма (сднф) – днф, в которой каждая её элементарная конъюнкция зависит от всех входящих в неё пп и каждая пп входит в каждую элементарную конъюнкция ровно один раз.

Совершенная конъюнктивная нормальная форма (скнф) – кнф, в которой каждая её элементарная дизъюнкция зависит от всех входящих в неё пп и каждая пп входит в каждую элементарную дизъюнкцию ровно один раз.

Построение сднф по таблице истинности данной формулы:

1)Находим строки, где итоговая формула принимает значение t.

2)Для каждой такой строки создаем элементарную конъюнкцию по правилу: если пп=t, то просто добавляем, если пп=f, то добавляем со знаком ¬.

3)Из полученных элементарных конъюнкций составляем днф.

4)Получаем что-то типа (( &¬ ) (¬ & )).

Построение скнф по таблице истинности данной формулы:

1)Находим строки, где итоговая формула принимает значение f.

2)Для каждой такой строки создаем элементарную дизъюнкцию по правилу: если пп=f, то просто добавляем, если пп=t, то добавляем со знаком ¬.

3)Из полученных элементарных дизъюнкций составляем кнф.

4)Получаем что-то типа ((¬ )&( ))

18. Построение сднф по данной днф.

1) Убеждаемся что данная нам днф не является тождественно ложной 2) В каждую элементарную конъюнкцию дописываем недостающие пп как (пп ¬пп) 3) Совершаем необходимые преобразования, пока не придем к сднф.

19. Построение скнф по данной кнф

1) Убеждаемся что данная нам кнф не является тождественно истинной 2) В каждую элементарную дизъюнкцию дописываем недостающие пп как (пп&¬пп) 3) Совершаем необходимые преобразования, пока не придем к скнф.

20. Условия существования скнф, сднф

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

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

21. Понятие логического следствия в АВ. Содержательный пример.

Высказывание называется логическим следствием высказываний 1, … , в АВ, если ппф принимает значение t каждый раз, когда все формулы 1, … , принимают значение t.

Факт логического следствия будем записывать как 1, … ,

Замечание 1:

означает что тождественно истинна.

Замечание 2:

не является логическим следствием 1, … , если = , а 1, … , = .

Замечание 3:

Если 1, … , – невыполнимы, то 1, . . , при любом .

Множество посылок называется выполнимым, если существует такой набор пп, что они все одновременно принимают значение t.

Содержательный пример:

1)Если завтра мало пар и не к первой, то я пойду в универ. A – мало пар (если мало, то t)

B – не к первой паре (если не к первой, то t)

C – я пойду в универ (если пойду, то t) Формулировка ((&) → )

A,B,((&) → ) множество посылок, С – заключение

Значит это логическое следствие.

2)Если завтра мало пар, не к первой, а я – девушка, то я пойду в универ.

«Я девушка» - тождественно ложное высказывание, значит множество посылок невыполнимо, значит это логическое следствие по замечанию 3.

22. Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок. Примеры.

Множество посылок называется выполнимым, если существует такой набор пп, что они все одновременно принимают значение t.

Пример:

Если завтра мало пар и не к первой, то я пойду в универ.

A – мало пар (если мало, то t)

B – не к первой паре (если не к первой, то t)

C – я пойду в универ (если пойду, то t) Формулировка (( & ) → )

A,B,(( & ) → ) множество посылок является выполнимым.

Множество посылок называется невыполнимым, если такого набора не существует.

Пример:

Если завтра мало пар, не к первой, а я – девушка, то я пойду в универ.

«Я девушка» - тождественно ложное высказывание, значит множество посылок невыполнимо.