- •Предисловие
- •Глава1. Логика классическая
- •1.1. Логика высказываний
- •1.1.1. Алгебра высказываний
- •1.1.1.2. Правила записи сложных формул
- •1.1.1.3. Законы алгебры высказываний
- •1.1.1.4. Эквивалентные преобразования формул
- •1.1.1.5. Нормальные формы формул
- •1.1.2. Исчисление высказываний
- •1.1.2.1. Интерпретация формул
- •1.1.2.2. Аксиомы исчисления высказываний
- •1.1.2.3. Метод дедуктивного вывода
- •1.1.2.4. Метод резолюции
- •Вопросы и задачи
- •Расчетно-графическая работа
- •1. 2. Логика предикатов
- •1.2.1. Алгебра предикатов
- •1.2.1.1. Логические операции
- •1.2.1.2. Правила записи сложных формул
- •1.2.1.3. Законы алгебры предикатов
- •1.2.1.4. Эквивалентные преобразования формул
- •1.2.1.2. Предварённая нормальная форма
- •1.2.1.3. Сколемовская стандартная форма
- •1.2.2. Исчисление предикатов
- •1.2.2.1. Интерпретация формул
- •1.2.2.2. Аксиомы исчисления предикатов
- •1.2.2.3. Правила унификации предикатов
- •1.2.2.4. Метод дедуктивного вывода
- •1.2.2.5. Метод резолюции
- •1.2.3. Логическое программирование
- •1.2.3.1. Основы логического программирования*
- •1.2.3.2. Подготовка среды Visual Prolog для работы
- •1.2.3.3. Описание логических задач на языке Prolog
- •Вопросы и задачи
- •Расчетно-графическая работа
- •Формула
- •1.3. Логика реляционная
- •1.3.1. Реляционная алгебра*
- •1.3.1.1. Унарные операции
- •1.3.1.2. Бинарные операции
- •1.3.2. Реляционное исчисление*
- •1.3.3. Языки реляционной логики
- •Вопросы и задачи
- •Расчетно-графическая работа
- •Глава 2. Неклассическая логика
- •2.1. Нечёткая логика
- •2.1.1. Нечёткие множества
- •2.1.2. Нечёткая алгебра
- •2.1.2.1. Операции над нечёткими множествами
- •2.1.2.2. Законы нечёткой алгебры
- •2.1.2.3. Свойства нечётких отношений
- •4.4.2. Экспертные системы
- •Вопросы и задачи
- •Расчетно-графическая работа
- •2.2. Модальная логика
- •2.2.1. Темпоральная (или временнáя) логика*.
- •Ответы и решения
- •Литература
- •Предметный указатель
1.1. Логика высказываний |
49 |
т. е. (F1 → F2 ),(F2 → F1)
(F1 ↔ F3 ).
П11. Правило удаления логической связки «↔»: если формула (F1↔F2) истинна, то истинными являются фор-
мулы (F1→F2) и (F2→F1), т.е. |
|
|
(F1 ↔ F2 ) |
|||
|
(F1 |
↔ F2 ) |
или |
|||
|
(F |
→ F ) |
(F |
→ F ). |
|
|
1 |
2 |
|
2 |
1 |
|
П12. Правило объединения формул (F1→F3) и (F2→F3): если формулы (F1→F3) и (F2→F3) истины, то ис-
тинной является формула ((F1 F2)→F3), т.е. (F1 → F3 ),(F2 → F3 )
(F1 F2 ) → F3 ).
Это - аксиома А8.
1.1.2.3. Метод дедуктивного вывода
Выводом формулы В из множества формул F1, F2,…, Fn называется такая последовательность формул, что любая Fi есть либо аксиома, либо выводима из множества предшествующих ей формул F1, F2,…, Fn.
В этом случае формулу B называют заключением, а последовательность формул F1, F2,…, Fn, - схемой дедук-
тивного вывода.
Схему дедуктивного вывода записывают так: F1, F2,…, Fn | B,
где «| » означает «верно, что B выводима из F1, F2, …,
Fn».
Известна другая форма записи этой схемы:
F1,F2 ,...,Fn
B.
где над чертой записывают множество истинных посылок и аксиом F1, F2, …, Fn, а под чертой - заключение В.
50 |
Математическая логика |
На языке математики схема дедуктивного вывода* есть доказательство теоремы (теорема Эрбрана):
| F1&F2&. . . &Fn→B.
Истинность этой теоремы доказывается так: «если все
Fi=и, то F1&F2&. . . &Fn=и, а если B=и, то по таблице истинности импликации F1&F2&. . . &Fn→B=и».
Используя правила эквивалентных преобразований теоремы, можно показать дедуктивный характер вывода заключения:
•| (F1&F2&...&Fn→B),
•| (¬(F1&F2&...&Fn ) B),
•| (¬F1 ¬F2 ... ¬Fn B),
•| (¬F1 ¬F2 ... ¬Fn-1 (Fn→B)),
.....................................................
•| (F1→(F2 →...→(Fn-1→(Fn→B))...).
Таким образом, вывод заключения всегда логически следует из множества посылок и аксиом. Вывод заключения опирается на два основных правила:
а) если F1 и (F1→F2 ) выводимые формулы, то F2 также выводимая формула, т.е. F1,F1 → F2 Это правило называют
F2.
modus ponens (m. p.) или прямое доказательство.
b) если ¬F2 и (F1→F2) выводимые формулы, то ¬F1
также выводимая формула, т.е. ¬F2 ,(F1 → F2 ) Это правило на-
¬F1.
зывают modus tollens (m. t.) или доказательство «от противного».
Эти правила являются основными при выводе заключения, так как устанавливают отношение следования меж-
* лат. deductio – выведение или логическое умозаключение.
1.1. Логика высказываний |
51 |
ду двумя формулами.
Пример 1.36. «Всякое общественно опасное деяние (А) наказуемо (В). Преступление (С) есть общественно опасное деяние (А). Дача взятки (D) - преступление (C). Следовательно, дача взятки наказуема ?» [9].
Формальна запись этого суждения:
(A → B),(C → A),(D →C)
(D → B).
Дедуктивный вывод:
•F1=A→B – посылка,
•F2=С→А – посылка,
•F3=D→C – посылка,
•F4=C→B - заключение по формулам F1 и F2 и правилу П9,
•F5=D→B - заключение по формулам F3 и F4 и правилу П9, ч.т.д*.
•
Процесс дедуктивного вывода удобно демонстрировать с помощью графа (см. рис. 1.1), вершинами которого являются формулы, а дугами – отношения между формулами согласно аксиомам и правилам введения и удаления логических связок.
Пример 1.37. «Если Петров говорит неправду (A), то
* - что и требовалось доказать.
52 |
Математическая логика |
он заблуждается (В) или сознательно вводит в заблуждение других (С). Петров говорит неправду и явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других» [9].
Формальна запись этого суждения:
(A → (B C)),(A & ¬B)
C.
Дедуктивный вывод:
•F2=A&¬B – посылка,
•F3=A - заключение по формуле F2 и правилу П2,
•F4=¬B - заключение по формуле F2 и правилу П2,
•F5=(В С)≡(¬B→C) - заключение по F1, F3 и правилу m. p.;
•F6=C - заключение по формулам F4, F5 и правилу m. p.,
ч.т.д.
На рис. 1.2 показан граф вывода этой задачи.
Пример 1.38. “Если Петров не трус (A), то он поступит в соответствие с собственными убеждениями (B). Если Петров честен (C), то он не трус (A). Если Петров не честен ¬(C), то он не признает своей ошибки (D). Но Петров признает свои ошибки (D). Следовательно, он поступит со-
1.1. Логика высказываний |
53 |
гласно собственным убеждениям (B)?"[9] Формальна запись этого суждения:
(A → B),(C → A),(¬C → D),¬D
B
Дедуктивный вывод:
•F1=A→B –посылка,
•F2=C→A – посылка,
•F3=¬C→D – посылка,
•F4=¬D – посылка,
•F5=C→B - заключение по формулам F1, F2 и правилу П9,
•F6=¬B→¬C - заключению по формуле F5 и прави-
лу П6,
•F7=¬B→D - заключение по формулам F3 и F6 и правилу П9,
•F8=B - заключение по формулам F4, F7 и правилу
m. t., ч.т.д.
На рис. 1.3 показан граф вывода этой задачи.
Пример 1.39. Доказать истинность заключения:
54 |
Математическая логика |
(A B),(A →C),(B → D)
(C D).
Дедуктивный вывод:
•F1=(A→C) - посылка,
•F2=(A B)→(C B) - заключение по F1 и правилу П7,
•F3=(B→D) - посылка,
•F4=(C B)→(C D) - заключение по F3 и правилу П7,
•F5=(A B)→(C D) - заключение по F2 и F4 и правилу П9,
•F6=(A В) - посылка,
•F7=(C D) - заключение по F5 и F6 и правилу m. p., ч.т.д. На рис. 1.4 показан граф вывода этой задачи.
Пример 1.40. Доказать истинность заключения:
(A → B) & (C → D),(D & B → E),¬E
(¬C ¬A).
Дедуктивный вывод:
•F1=(D&B→E) - посылка,
•F2=¬E - посылка,
•F3=¬(D&B) - заключение по F1 и F2 и правилу m. t.,
•F4=(А→В)&(С→D) - посылка,
•F5=(A→В) - заключение по F4 и правилу П2,
1.1. Логика высказываний |
55 |
•F6=(С→D) - заключение по F4 и правилу П2,
•F7=(¬B→¬A) - заключение по F5 и правилу П6,
•F8=(¬D ¬B) - заключение по F3 и закону де Моргана,
•F9=(D→¬B) - заключение по F8,
•F10=(D→¬A) - заключение по F7 и F9 и правилу П9,
•F11=(С→¬A) - заключение по F6 и F10 и правилу П9,
•F12=(¬С ¬A) - заключение по FII, ч.т.д.
На рис. 1.5 показан граф вывода этой задачи.
Пример 1.41. Доказать истинность заключения:
((A B) → C),(C → (D M)),(M → N),(¬D &¬N)
¬A.
Дедуктивный вывод:
•F1=(¬D&¬N) - посылка,
•F2=¬N - заключение по F1 и правилу П2,
•F3=(M→N) - посылка,
•F4=¬M - заключение по F2 и F3 и правилу m. t,
•F5=¬D - заключение по F1 и правилу П2,
56 |
Математическая логика |
•F6=(¬D&¬M) - заключение по F4 и F5 и правилу П1,
•F7=¬(D М) – заключение по F6 и закону де Моргана,
•F8=(( A B)→C) - посылка,
•F9=(С→ (D М)) - посылка,
•F10=((A B)→(D M)) - заключение по F8 и F9 и правилу П9,
•F11=¬(A B) - заключение по F7 и F10 и правилу m.t.,
•F12=(¬А&¬B) - заключение по F11 и закону де Моргана,
•F13=¬A - заключение по F12 и правилу П2, ч.т.д.
На рис. 1.6 показан граф вывода этой задачи.
Пример 1.42. “Если команда А выигрывает в футболе то город А’ торжествует, а если выигрывает команда В, то торжествовать будет город В’. Выигрывают или А или В. Однако, если выигрывают А, то город В’ не торжествует, а если выигрывают В, то не будет торжествовать город А’. Следовательно, город В’ будет торжествовать тогда и только тогда, когда не будет торжествовать город А’”[3].
1.1. Логика высказываний |
57 |
Формальна запись этого суждения:
(A → A') &(B → B'),(A B),(A →¬B')&(B →¬A')
B' ↔ ¬A').
Дедуктивный вывод:
•F1=(A→A’)&(B→B’) – посылка,
•F2=(A→A’) - заключение по формуле F1 и правилу П2,
•F3=(B→B’) - заключение по формуле F1 и правилу П2,
•F4=(A→¬B’)&(B→¬A’) - посылка,
•F5=(A→¬B’) - заключение по формуле F4 и правилу П2,
•F6=(B→¬A’) - заключение по формуле F4 и правилу П2,
•F7=(B’→¬A) - заключение по формуле F5 и правилу П6,
•F8=(A’→¬B) - заключение по формуле F6 и прави-
лу П6,
•F9=(A B) – посылка,
•F10=¬A→B - заключение по формуле F9,
58 |
Математическая логика |
•F11=¬A→¬A’ - заключение по формулам F6, F10 и правилу П9,
•F12= B’→¬A’ - заключение по формулам F7, F11 и правилу П9,
•F13= ¬A’→¬A - заключение по формуле F2 и правилу П6,
•F14=¬A’→B - заключение по формулам F10, F13 и правилу П9,
•F15=¬A’→B’ - заключение по формулам F3, F14 и правилу П9,
•F16= (B’→¬A’)&(¬A’→B’) ≡ (B’↔¬A’) – заключение по формулам F12, F15 и правилу П1, ч.т.д.
На рис. 1.7 показан граф вывода этой задачи.