Содержание
- 2. Силлогизмы Аристотеля Типы категорических суждений: А – общеутвердительное суждение «Всякое S суть Р» Е – общеотрицательное
- 3. Алгебра высказываний Примеры высказываний: «Москва – столица России» - истинное, «5 – четное число» – ложное,
- 4. Основные логические эквивалентности – примеры тавтологий 1. Коммутативность: A∨ B = B ∨ A, A∧ B
- 5. Формальные теории Составляющие формальной теории: Алфавит. 2. Формулы 3. Аксиомы 4.Правила вывода Определение. Выводом формальной теории
- 6. Исчисление высказываний 1. Алфавит составляют: • Пропозициональные буквы (от англ. proposition – высказывание) – заглавные буквы
- 7. Теорема о дедукции. Построение вывода в логике высказываний Теорема дедукции. Пусть Γ – множество формул, A,
- 8. Метод резолюций в логике высказываний Правила преобразование в предложение : 1. Замена импликации по формуле: A→
- 9. Примеры применения метода резолюций Пример 1. Методом резолюций доказать теорему ├¬A→(A→ B) . Доказательство. Запишем инверсию
- 10. Примеры применения метода резолюций Пример 2. Методом резолюций доказать теорему ├ A→(B→ A∧ B). Доказательство. Запишем
- 11. Предикаты. Квантор общности. Определение. n-местным предикатом на множестве X называется n-местная функция, каждый аргумент которой принадлежит
- 12. Предикаты. Квантор существования Пусть дан n -местный предикат A(x1, x2 ,..., xn ) на множестве X
- 13. Эквивалентности для кванторов Имеют место эквивалентности: ∃xi A = ¬∀xi¬A. ∀xi A = ¬∃xi¬A. ¬∃xiA =
- 14. Исчисление предикатов – теория 1 порядка 1. Алфавит составляют: • Предметные константы – это имена (обозначения)
- 15. Исчисление предикатов – теория 1 порядка 3. Аксиомы теории первого порядка делятся на два класса: •
- 16. Законы логики предикатов Имеет место следующие равносильности: 1) ¬ ∀x F(x) = ∃ x ¬ F(x)
- 17. Теоремы о подстановках. Предваренная нормальная форма. Пусть F(x) – формула, t – терм. Тогда имеют место
- 19. Скачать презентацию
Силлогизмы Аристотеля
Типы категорических суждений:
А – общеутвердительное суждение
«Всякое S суть
Силлогизмы Аристотеля
Типы категорических суждений:
А – общеутвердительное суждение
«Всякое S суть
Е – общеотрицательное суждение
«Никакое S не суть Р»
I – частноутвердительное суждение
«Некоторые S суть Р»
О – частноотрицательное суждение
«Некоторые S не суть Р»
Пример парадокса:
“Сказанное Платоном – ложно, - говорит Сократ. – Сказанное Сократом – истинно, - говорит Платон”
силлогизм
Алгебра высказываний
Примеры высказываний: «Москва – столица России» - истинное, «5 –
Алгебра высказываний
Примеры высказываний: «Москва – столица России» - истинное, «5 –
не высказывание, т.к. неизвестно, какое значение примет х
Логические операции - отрицание « ¬ », конъюнкция – двухместная логическая операция ∧ («и») – по высказываниям А, В определяет высказывание А ∧ В («А и В»), которое истинно тогда и только тогда, когда оба высказывания А, В истинны. Дизъюнкция – двухместная логическая операция ∨ («или») – по высказываниям A, B определяет высказывание A∨В («A или B»), которое истинно тогда и только тогда, когда хотя бы одно из высказываний A, B – истинно. Импликация – двухместная логическая операция → («если…, то…») – по высказываниям А, В определяет высказывание А→В («если А, то В»), которое ложно тогда и только тогда, когда А - истинно, В – ложно. А называется посылкой, В – заключением. Эквиваленция – двухместная логическая операция ↔ («если и только если…, то…») определяет высказывание А ↔ В («если и только если А, то В»), которое истинно тогда и только тогда, когда А, В оба истинны или оба ложны.
Основные логические эквивалентности – примеры тавтологий
1. Коммутативность: A∨ B = B
Основные логические эквивалентности – примеры тавтологий
1. Коммутативность: A∨ B = B
2. Ассоциативность:
( A∨ B )∨ C = A∨ (B ∨ C), A∧ (B ∧C) = (A∧ B)∧C.
3. Дистрибутивность:
A∨ (B ∧C) = (A∨ B)∧ (A∨ C), A∧ (B ∨ C) = (A∧ B)∨ (A∧C).
4. Идемпотентность: A∨ A = A, A∧ A = A.
5. Закон двойного отрицания: ¬¬A = A.
6. Закон исключения третьего: A∨ ¬A = 1.
7. Закон противоречия: A ∧ ¬A = 0.
8. Законы де Моргана:
¬(A ∨ B) = ¬A ∧ ¬B, ¬(A ∧ B) = ¬A ∨ ¬B.
9. Свойства операций с логическими константами:
A∨1 =1, A∨ 0 = A, A∧1 = A, A∧ 0 = 0 .
Здесь A, B и C – любые буквы.
Формальные теории
Составляющие формальной теории:
Алфавит. 2. Формулы 3. Аксиомы 4.Правила вывода
Определение.
Формальные теории
Составляющие формальной теории:
Алфавит. 2. Формулы 3. Аксиомы 4.Правила вывода
Определение.
Определение. Говорят, что формула A выводима из множества формул Γ (обозначение: Γ ├ A), если существует вывод A1, A2 , …, An , где An = A, и есть три возможности:
• Ai ∈Γ ;
• Ai - аксиома;
• Ai получаются из предыдущих формул по правилам вывода.
Исчисление высказываний
1. Алфавит составляют:
• Пропозициональные буквы (от англ. proposition – высказывание)
Исчисление высказываний
1. Алфавит составляют:
• Пропозициональные буквы (от англ. proposition – высказывание)
• Логические связки: ¬,→.
• Скобки: (, ).
Иногда в исчислении высказываний допускаются формулы с другими логическими связками, но при этом учитывается, как они выражаются через инверсию и импликацию. Так, A∧ B = ¬(A→¬B), A∨ B = ¬A→ B .
2. Формулы определяются следующим образом.
Определение. 1) Всякая пропозициональная буква есть формула. 2) Если A, B – формулы, то формулами являются также ¬A, A→ B. 3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).
3. Аксиомы задаются тремя схемами аксиом:
А1. A→(B→ A).
А2. (A→(B→C))→((A→ B)→(A→C)).
А3. (¬B→¬A)→((¬B→ A)→ B).
4. Правило вывода Modus ponens (сокращенно MP) – правило отделения
A, A→B├B .
Теорема о дедукции. Построение вывода в логике высказываний
Теорема дедукции. Пусть Γ
Теорема о дедукции. Построение вывода в логике высказываний
Теорема дедукции. Пусть Γ
Справедлива и обратная теорема.
Теорема. Γ ├ A→ B ⇒Γ , A├B .
Докажем, что выводима формула (¬B→¬A)→(A→ B).
Сокращенно это записывается так: ├(¬B→¬A)→(A→ B).
По теореме, обратной теореме дедукции, посылку можно перенести в левую часть: ¬B→¬A├ A→ B. Проделаем эту операцию еще раз: ¬B→¬A, A├B .
Таким образом, нам нужно доказать, что из формул ¬B→¬A и A выводима формула B. Сначала мы запишем гипотезы.
1. ¬B→¬A – гипотеза.
2. A – гипотеза.
Формулу B удобно получить из аксиомы А3. Поэтому запишем эту аксиому:
3. (¬B→¬A)→((¬B→ A)→ B) А3.
К формулам 1 и 3 можно применить правило вывода Modus ponens
4. (¬B→ A)→ B. МР 1, 3.
Посылку в формуле 4 можно получить из аксиомы А1, если заменить B на ¬B:
5. A→(¬B→ A). А1 с подстановкой вместо B – ¬B.
Далее дважды применяем правило Modus ponens:
6. ¬B→ A. МР 2, 5.
7. B . МР 6, 4.
Метод резолюций в логике высказываний
Правила преобразование в предложение :
1. Замена
Метод резолюций в логике высказываний
Правила преобразование в предложение :
1. Замена
2. Преобразование выражений с инверсиями по закону двойного отрицания:
¬¬A = A, законам де Моргана: ¬(A∨ B) = ¬A ∧¬B, ¬(A∧ B) = ¬A∨ ¬B. В результате инверсии остаются только перед буквами.
3. Приведение формулы к конъюнктивной нормальной форме с помощью дистрибутивных законов:
A∧ (B ∨ C) = (A∧ B)∨ (A∧C),
A∨ (B ∧C) = (A∨ B)∧ (A∨ C).
4. Преобразование конъюнктивной нормальной формы во множество предложений AB⇒ A,B.
Правило резолюций. Даны предложения: С1 = P ∨ C1′ , С2 = ¬P ∨C2′ , где P - пропозициональная буква, C′1 и C2′ – предложения (в частности, пустые или содержащие только одну букву или ее отрицание). Правило резолюций формулируется так: С1 , С2 ├ C1′ ∨ C2′ . С1 , С2 называются резольвируемыми предложениями, а C1 ′ ∨ C2′ – резольвентой.
Примеры применения метода резолюций
Пример 1. Методом резолюций доказать теорему ├¬A→(A→ B)
Примеры применения метода резолюций
Пример 1. Методом резолюций доказать теорему ├¬A→(A→ B)
Доказательство. Запишем инверсию исходной формулы:
¬(¬A→(A→ B)).
Заменим все импликации по соответствующей формуле:
¬(¬A→(A→ B)) = ¬(¬¬A∨ (¬A∨ B)).
Применим закон двойного отрицания и закон де Моргана:
¬(¬A→(A→ B)) = ¬(A∨ (¬A∨ B)) = ¬A∧¬(¬A∨ B) =
= ¬A∧¬¬A∧¬B = ¬A∧ A∧¬B .
Получаем предложения: ¬A, A, ¬B. Резольвируем их:
1. ¬A – предложение.
2. A – предложение.
3. ¬B – предложение.
4. ?. R 1, 2.
Примеры применения метода резолюций
Пример 2. Методом резолюций доказать теорему
├ A→(B→ A∧
Примеры применения метода резолюций
Пример 2. Методом резолюций доказать теорему
├ A→(B→ A∧
Доказательство. Запишем инверсию исходной формулы:
¬(A→(B→ A∧ B)).
Заменим все импликации по соответствующей формуле:
¬(A→(B→ A∧ B)) = ¬(¬A∨ (¬B ∨ A∧ B)).
Применим закон двойного отрицания и закон де Моргана:
¬(A→(B→ A∧ B)) = ¬¬A∧¬(¬B ∨ (A∧ B)) =
= A∧ B ∧¬(A∧ B) = A∧ B ∧ (¬A∨ ¬B).
Получаем предложения: A, B , ¬A∨ ¬B.
1. A – предложение.
2. B – предложение.
3. ¬A∨ ¬B – предложение.
4. ¬B. R 1, 3.
5. ?. R 2, 4.
Предикаты. Квантор общности.
Определение. n-местным предикатом на множестве X называется n-местная функция,
Предикаты. Квантор общности.
Определение. n-местным предикатом на множестве X называется n-местная функция,
Примеры. 1. Предикат A(x) ="x ≤ 2" на множестве X = R – одноместный.
2. Предикат B(x, y) ="xy > 0" на множестве X = R2 – двуместный.
Пусть дан n -местный предикат A(x1, x2 ,..., xn ) на множестве X , означающий, что для набора (x1, x2 ,..., xn ) выполнено свойство A, и пусть xi – одна из переменных. Тогда запись ∀xiA(x1, x2 ,..., xn ) означает, что для всех значений переменной xi свойство A выполнено. Символ ∀ называется квантором всеобщности (общности). Предикат ∀xi A(x1, x2 ,..., xn ) является (n −1)-местным. Он зависит от переменных x1, x2 ,..., xi−1, xi+1,..., xn . Если дан одноместный предикат P(x) , то утверждение ∀xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.
Пример. На множестве X = R дан предикат A(x) ="x ≤ 2". Высказывание ∀x(x ≤ 2) ложно.
11
Предикаты. Квантор существования
Пусть дан n -местный предикат A(x1, x2 ,..., xn
Предикаты. Квантор существования
Пусть дан n -местный предикат A(x1, x2 ,..., xn
Примеры.
1. На множестве X = R дан предикат A(x) =" x ≤ 2". Высказывание
∃x(x ≤ 2) истинно.
2. Х={1,2,3,…} – множество натуральных чисел;
а) Р(x):= «x делится на 2». Р(2)= «истина», Р(3)= «ложь»;
б) Р(x1, x2): «x1≥ x2». Р(1,2)= «ложь», Р(3,2)= «истина».
12
Эквивалентности для кванторов
Имеют место эквивалентности:
∃xi A = ¬∀xi¬A. ∀xi A =
Эквивалентности для кванторов
Имеют место эквивалентности:
∃xi A = ¬∀xi¬A. ∀xi A =
¬∃xiA = ∀xi¬A. ¬∀xi A = ∃xi¬A.
∀x∀yP(x, y) = ∀y∀xP(x, y) , ∃x∃yP(x, y) = ∃y∃xP(x, y) .
Разноименные кванторы можно переставлять только следующим образом:
∃x∀yP(x, y)→∀y∃xP(x, y) , ∃y∀xP(x, y)→∀x∃yP(x, y) .
Обратные формулы неверны.
Пример. Очевидно, что высказывание ∀x∃y(x + y = 0) ( X = R) истинно. Поменяем кванторы местами. Получим высказывание ∃y∀x(x + y = 0), которое является ложным.
Выражения с кванторами можно преобразовывать следующим образом:
∀x(P(x) ∧Q(x)) = ∀xP(x) ∧∀xQ(x) , ∃x(P(x) ∨Q(x)) = ∃xP(x) ∨ ∃xQ(x)
13
Исчисление предикатов – теория 1 порядка
1. Алфавит составляют:
• Предметные константы –
Исчисление предикатов – теория 1 порядка
1. Алфавит составляют:
• Предметные константы –
• Предметные переменные – буквы конца латинского алфавита с натуральными индексами: x1 , x2 , …, y1 , y2 , …
• Предикатные буквы – заглавные буквы латинского алфавита с натуральными индексами, означающие операции над переменными и константами.
• Логические связки: ¬,→.
• Квантор всеобщности ∀ .
• Синтаксические символы – скобки (, ) и запятая.
2. Формула определяется несколькими этапами. Вначале вводится понятие терма.
Определение. 1) Предметные константы и предметные переменные есть термы. 2) Если t1 , t2 , …, tn , – термы, то в результате применения к ней функции получится терм. 3) Символ является термом тогда и только тогда, когда это следует из 1) и 2).
Определение. элементарная формула образуется при применении предикатной буквы к термам.
Пример. если "≤ " - предикатная буква, то sin x ≤ cosax – элементарная формула.
Определение. 1) Всякая элементарная формула есть формула.2) Если A, B – формулы, то формулами являются также символы ¬A, A→ B, ∀yA. 3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).
Исчисление предикатов – теория 1 порядка
3. Аксиомы теории первого порядка делятся
Исчисление предикатов – теория 1 порядка
3. Аксиомы теории первого порядка делятся
• Логические аксиомы:
1) A→(B→ A).
2) (A→(B→C))→((A→ B)→(A→C)).
3) (¬B→¬A)→((¬B→ A)→ B).
4) ∀xi A(xi )→ A(t), где терм t свободен для переменной xi в формуле A(xi ) .
5) ∀xi (A→ B)→(A→∀xiB), где xi – несвободная переменная в формуле A.
Отметим, что аксиомы 1) – 3) – тавтологии, 4) и 5) – общезначимые формулы.
• Собственные аксиомы.
У каждой теории первого порядка свои собственные аксиомы.
4. Правила вывода.
1) Modus ponens (МР).
A, A→B├B .
2) Правило обобщения Gen.
A├∀xA.
15
Законы логики предикатов
Имеет место следующие равносильности:
1) ¬ ∀x F(x) = ∃
Законы логики предикатов
Имеет место следующие равносильности:
1) ¬ ∀x F(x) = ∃
2) ∀x(F(x) ∧ G(x)) = ∀xF (x) ∧ ∀xG(x), ∃x(F(x) ∨ G(x))=∃F(x) ∨ ∃xG(x);
3)∀x ∀y F(x, y) =∀y ∀ x F(x, y), ∃ x ∃y F(x, y)= ∃y∃ x F(x, y);
4)∀x (F(x)∧С) = ∀x F(x) ∧ С, ∀x (F(x) ∨ С)= ∀x F(x) ∨ С;
5)∃x (F(x)∧С) = ∃ x F(x) ∧ С, ∃ x (F(x) ∨ С) = ∃ x F(x) ∨ С;
6)С → ∀x F(x) = ∀x ( С → F(x)), С→ ∃ x F(x) = ∃ x (С → F(x)).
Эти равносильности называются также законами логики предикатов.
Формула С не содержит вхождений переменной x.
Применяются также законы:
F↔G: = (F→G) ∧ (G→ F), F→ G: = ¬ F∨ С.
¬ F=F, ¬ (F∨С)= ¬ F∧¬ G, ¬ (F∧G)= ¬ F∨¬ G
С помощью равносильностей можно преобразовывать формулы.
Формула ЛП G называется логическим следствием формулы F, если G
истинна во всех интерпретациях, в которых F истинна. Запись: F→ G.
Имеют место логические следования:
7)∃x(F(x)∧G(x)) ∃xF(x)∧∃xG(x), ∀x F(x)∨∀ ∃xG(x)⇒∀x(F(x)∨G(x)) ;
8)∀ xF(x)→H⇒ ∃x(F(x) → H), ∃xF(x)→H⇒ ∀ x(F(x) → H),
где формула Н не содержит вхождений переменной х.
16
Теоремы о подстановках.
Предваренная нормальная форма.
Пусть F(x) – формула, t – терм.
Теоремы о подстановках.
Предваренная нормальная форма.
Пусть F(x) – формула, t – терм.
Формула ∀xF(x)→F(t),где t – терм, свободный для переменной x в формуле F, есть тавтология.
Формула F(t) →∃ x F(x), где t – терм, свободный для переменной x в формуле F, есть тавтология.
Формула ЛП F называется находящейся в ПНФ, если она имеет вид:
Q1 x1 … Qn xn F0 ,где Qi, i= 1..n – один из кванторов (∀,∃), x i≠ xj, если i≠j,
F0 – формула, не имеющая кванторов.
Пример - Формула ∀x∀y∃z (Q(x,y) →R(z)) находится в ПНФ.
Для любой формулы ЛП существует логически эквивалентная ей форму-
ла, находящаяся в ПНФ. Приведение данной формулы ЛП к ПНФ можно произвести с помощью равносильностей (1-6) и следований (7-8).
17