Основные равносильности, содержащие кванторы

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности, содержащие
кванторы»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

Законы де Моргана
1.
2.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
2

3. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

Коммутативные законы для
одноименных кванторов
3.
4.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
3

4. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

Дистрибутивные законы для
кванторов
5.
6.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
4

5. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

Законы ограничения
действия кванторов
7.
8.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
5

6. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

9.
10.
11.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
6

7. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ТЕОРИИ ПРЕДИКАТОВ

12.
13.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
7

8. ПЕРЕИМЕНОВАНИЕ СВЯЗАННЫХ ПЕРЕМЕННЫХ

Заменяя связанную переменную
формулы А другой переменной, не
входящей в эту формулу, в кванторе и
всюду в области действия квантора,
получаем формулу, равносильную А.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
8

9. ДЛИНА ФОРМУЛЫ

Длина формулы - общее число
входящих в нее символов предикатов,
логических символов и кванторов.
Пример
Длина формулы – 5
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
9

10. ПРИВЕДЕННАЯ ФОРМА ФОРМУЛЫ

Приведенная форма формулы –
это формула, в которой имеются
только символы ∧,∨,¬, причем
¬ относится только к символу
предикатов.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
10

11. ПРИМЕРЫ

Приведенные формулы:
1.
2.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
11

12. ПРИМЕРЫ

Не приведенные формулы:
3.
4.
5.
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
12

13. ПРИВЕДЕННАЯ ФОРМА ФОРМУЛЫ

Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
13

14. НОРМАЛЬНАЯ ФОРМА ФОРМУЛЫ

Приведенная формула называется
нормальной, если она не содержит
символов
кванторов,
или
все
символы кванторов стоят впереди
формулы (т.е. логические символы и
символы предикатов стоят в области
действия каждого квантора)
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
14

15. ПРИМЕРЫ

Нормальная формула:
Приведенная формула:
Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
15

16. НОРМАЛЬНАЯ ФОРМА ФОРМУЛЫ

Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
16

17. НОРМАЛЬНАЯ ФОРМА ФОРМУЛЫ

Курс «Математическая логика и теория алгоритмов»
Тема «Основные равносильности , содержащие кванторы»
17

18.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013