- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
13.2. Непосредственное умозаключение
Непосредственное умозаключение строится двумя путями:
Путем преобразования исходного суждения (посылки).
На основе знаний об отношениях между суждениями.
Умозаключение путем обращения суждения.
При таком умозаключении меняются субъект и предикат исходного суждения:
S – P (посылка) |
P – S (заключение) |
Примеры.
1. Все предприниматели платят налоги, следовательно, некоторые плательщики являются предпринимателями.
2. Все ЭВМ являются компьютерами, следовательно, все компьютеры являются ЭВМ.
3. Некоторые студенты работают, следовательно, некоторые трудящиеся являются студентами.
4. Некоторые учащиеся – студенты, следовательно, все студенты – учащиеся.
Обращение бывает двух видов: чистое или простое (примеры 2 и 3, квантор не меняется) и с ограничениями (примеры 1 и 4, квантор меняется на противоположный).
Простое обращение – когда субъект и предикат либо оба распределены, либо оба не распределены.
С ограничением – когда субъект распределен, а предикат нет или наоборот.
Изобразим обращение суждений табл. 81.
Таблица 81
Обращение суждений
С помощью этой таблицы можно определить, когда возможно обращение – опять-таки, тогда, когда связь между суждениями однозначная.
Умозаключение путем превращения суждений.
При превращении меняется качество посылки без изменения количества, при этом предикат заключения является отрицанием предиката посылки.
S есть P |
или |
S есть P |
S не есть P |
S не есть P |
Частноутвердительное превращается в частноотрицательное, общеутвердительное – в общеотрицательное.
Превращению могут быть подвержены все суждения.
Примеры.
Все женщины красивы, следовательно, ни одна женщина не является не красивой.
Некоторые мужчины – джентльмены, следовательно, некоторые мужчины не являются не джентльменами.
Изобразим превращение табл. 82.
Таблица 82
Превращение суждений
Умозаключения путем противопоставления предикату.
Противопоставление предикату – это такое непосредственное умозаключение, при котором предикатом становится субъект, а субъектом понятие противоречащее предикату исходного суждения, причем связка меняется на противоположную:
S есть P |
или |
S не есть P |
P не есть S |
P есть S |
То есть, сначала проводится превращение, а затем обращение (табл. 83*).
Таблица 83
Противопоставление предикату
Пример (рис. 115).
Все студенты сдают экзамены.
Ни один не сдающий экзамен не является студентом.
Рис. 115. Пример противопоставления предикату
Непосредственное умозаключение может основываться и на отношениях между суждениями.
Такие умозаключения выстраиваются по логическому квадрату, если есть одиночная связь между соответствующими значениями истинности.
Если связь неоднозначная, то суждение правильно, если двигаться по ребру, определяющему однозначную связь, например, от O (0) к I (1).
13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
Если посылки и вывод в опосредованном дедуктивном умозаключении являются простыми категорическими суждениями, то такое суждение называется простым категорическим силлогизмом (ПКС). В структуре простого категорического силлогизма имеются две посылки и вывод.
Для того чтобы между посылками и выводом было отношение следования они должны включать общие понятия. Такие общие понятия называются средним термином (М).
Понятие, которое входит в одну из посылок и стоит на месте субъекта в выводе называется субъектом простого категорического силлогизма (S).
Понятие, которое входит в одну из посылок и в вывод и стоит на месте предиката в выводе называется предикатом простого категорического силлогизма (Р).
Посылка, содержащая предикат и средний термин, – большая посылка (БП), которая стоит на первом месте.
Посылка, содержащая субъект и средний термин – меньшая посылка (МП), которая стоит на втором месте.
Вывод содержит субъект и предикат.
Структура ПКС:
БП: |
(М, Р) |
МП: |
(M, S) |
Вывод |
(S, P) |
Правила ПКС [8]:
1. Правила посылок.
а) по крайней мере, одна из посылок должна быть суждением общим. Из двух частных посылок вывод невозможен;
b) если одна из посылок суждение частное, вывод будет частным;
c) по крайней мере, одна из посылок должна быть суждением утвердительным. Из двух отрицательных суждений вывод невозможен;
d) если одна из посылок суждение отрицательное, вывод будет отрицательным.
2. Правила терминов.
a) в ПКС может быть только 3 термина (M, S, P);
b) средний термин должен быть распределен, по крайней мере, в одной из посылок;
c) термин, не распределенный в посылках, не может быть распределен в заключении.