- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
161
отрезка [0,1], а операции вводятся по формулам (5.2), считается стандартной логикой Лукасевича – логикой L1 [15].
Такие слова наводят на всякие мысли, хотя и неясно – на какие (Алиса)1.
Л. Кэррол
§ 3. Понятие нечеткого множества
Основателем теории нечетких множеств является Л. Заде. Л. Заде писал (см. предисловие к книге [16]): «Теория нечетких множеств – это, по сути дела, шаг на пути к сближению точности классической математики и всепроникающей неточности реального мира, к сближению, порожденному непрекращающимся человеческим стремлением к лучшему пониманию процессов мышления и познания»
Пусть U - произвольное непустое множество в обычном понимании (иногда называемое универсальным множеством), а А является его подмножеством, А U.
Тот факт, что элемент х множества U есть элемент подмножества А или, как говорят, принадлежит А, обычно обозначают так х A. Для выражения этой принадлежности можно использовать и другое понятие - характеристическую функцию µА(х), значения которой указывают, является ли (да или нет) х элементом А:
µА(х)= 1, |
если х А, |
0, |
если х А. |
Рассмотрим пример. Пусть U=(-∞ ,∞ ), А=[-2,3], тогда µА(х) имеет вид изображенный на рис. 5.1.
|
Очевидны следующие свойства характеристических функций: |
||||||||||
1) |
(А=В) тогда и только тогда, когда х(µА(х) = µВ(х)); |
|
|
|
|||||||
2) µСА(х) = 1- µA(х); |
|
|
|
|
|
1 |
|
|
|
||
|
|
|
|
|
|
|
|
||||
3) |
µА∩В( х) = 1, |
если х А∩ В, |
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|||
|
0, |
если х А∩В |
-2 |
0 |
3 |
|
|||||
|
|
|
|
= min(µА(х), µВ(х)); |
Рис. 5.1. |
|
1 Эта фраза Алисы из «Алисы в Зазеркалье» взята из книги: М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, см [10]. В переводе Н. Димуровой произведения «Алиса в Зазеркалье» фраза Алисы приводиться без первых двух слов эпиграфа, да и остальная часть нечетко совпадает с эпиграфом, даже без указанной части.
|
162 |
|
4) µА В( х) = 1, |
если х А В, |
= max(µА(х), µВ(х)). |
0, |
если х А В |
|
Отметим, что рассмотренная характеристическая функция принимает только два значения 0 или 1.
Представим теперь, что характеристическая функция µ(х) может принимать любое значение в интервале [0,1]. В соответствии с этим мера принадлежности х подмножеству А может быть любой из [0,1], т.е. х может быть элементом А более или менее, менее чем более и т.п. Таким образом, понятие принадлежности получает интересное обобщение. Дадим строгое определение.
Пусть U - множество и х элемент U. Тогда нечетким подмножеством А* множества U называется множество упорядоченных пар
А*={ х, µА*(х) }, где х U, µА*(х) [0,1];
функцию µА*(х) называют функцией принадлежности, а U- универсальным или базовым множеством.
Рассмотрим множество людей различного возраста и попытаемся выделить подмножество молодых людей, т.е. задать функцию µ(х), 0≤µ(х)≤1. Ясно, что каждый может ввести свое понимание функции µ(х). На рис. 5.2 приведены графики некоторых возможных таких функций µ(х); при этом на оси 0х указаны возраст в годах, на 0у – значения функции µ(х).
Рис. 5.2.
На множестве (-∞,∞), например, можно ввести понятие действительных чисел очень близких к нулю. Например, можно определить функцию принадлежности µА*(х) нечеткого подмножества А* действительных чисел
очень близких к нулю по формуле: µА*(х) = 1 . 1 +10х2
График этой функции, представлен на Рис. 5.3.
1 µА*(х)
0,5
Х
-2 |
-1 |
0 |
0,316 |
1 |
2 |
Рис. 5.3.
163
Ясно, что понятие действительных чисел очень близких к нулю тоже вводится неоднозначно, следовательно, и в этом случае можно получить различные функции принадлежности µА*(х). Таким образом, выбор функции µА*(х), в общем, может быть различным.
Носителем нечеткого подмножества А* называется (обычное)
подмножество В множества U, содержащее те элементы из U, для которых
µА*(х)>0. Носитель для А* обозначают как suppА* (suppА*={х U: µА*(х)>0}).
Два нечетких подмножества А* и В* множества U называются равными
тогда и только тогда, когда х U: µА*(х) = µВ*(х). Будем говорить, что А* содержится в В*, если
х U: µА*(х) ≤ µВ*(х)
и обозначать А* В*.
Считаем, что нечеткие подмножества А* и В* множества U дополняют друг друга, если
х U: µА*(х) = 1- µВ*(х). |
(5.3) |
||||
и обозначать: В*= |
|
* или А*= |
|
* . |
|
А |
В |
|
|||
Введем пересечение (∩) и объединение ( ) |
нечётких подмножеств. |
Пусть А* и В* нечеткие подмножества множества U, тогда их пересечение и объединение есть нечеткие подмножества множества U
имеющие соответственно следующие функции принадлежности: |
(5.4) |
х U: µА*∩В*(х) = min(µА*(х), µВ*(х)), |
|
х U: µА* В*(х) =mах(µА*(х), µВ*(х)). |
(5.5) |
Положим, что универсальное множество U является |
конечным |
множеством, например, U={u1,u2,…,un} и А* его нечёткое подмножество с функцией принадлежности µА*(х). Тогда имеем А*={ х, µА*(х) }, где х U,
µА*(х) [0,1], т. е. А*={ u1, µ1 , u2, µ2 ,…, un, µn }, где µi= µA*(ui). В таких случаях используют специальную форму записи, именно пишут:
А*= µ1/ u1+µ2/u2+…+µn/un, |
(5.6) |
или
n
А*= ∑µi / ui .
i=1
В этих записях указывается элемент универсального множества ui (ui U) и µi (µi= µA*(ui)) – степень принадлежности элемента ui нечёткому подмножеству А*. В этих записях символ «+» не означает операцию сложения, а служит разделителем элементов множества А*. Если µi =0, то, как правило, элементы
164
µi/ui в (5.6) опускаются. Рассмотрим пример. Пусть универсальное множество U состоит из 10 элементов, означающих возраст (в годах):
U={5, 10, 20, 30, 40, 50, 60, 70, 80, 90}.
На этом множестве с помощью следующей таблицы заданы нечёткие подмножества, характеризуемые словами молодой, взрослый и старый. В таблице для каждого элемента ui из U указаны степени принадлежности ui указанным нечетким подмножествам.
Элементы |
из U |
|
Нечёткие подмножества |
||
(годы) |
|
Молодой |
|
Пожилой |
Старый |
5 |
|
1 |
|
0 |
0 |
10 |
|
1 |
|
0 |
0 |
20 |
|
0,8 |
|
0,1 |
0 |
30 |
|
0,5 |
|
0,3 |
0,1 |
40 |
|
0,2 |
|
0,5 |
0,3 |
50 |
|
0,1 |
|
0,7 |
0,5 |
60 |
|
0 |
|
1 |
0,8 |
70 |
|
0 |
|
1 |
1 |
80 |
|
0 |
|
1 |
1 |
90 |
|
0 |
|
1 |
1 |
Из таблицы можно записать, что носитель нечёткого подмножества А*-
молодой равно:
supp(А*)=supp(молодой)={ui U: µi >0}={5, 10, 20, 30, 40,50}.
Нечёткое подмножество А* можно записать в виде:
А*=1/5+1/10+0,8/20+0,5/30+0,2/40+0,1/50.
Если В* нечёткое подмножество пожилой, то записываем:
В*=0,1/20+0,3/30+0,5/40+0,7/50+1/60+1/70+1/80+1/90.
Пересечение этих подмножеств, очевидно, равно следующему:
А*∩ В*=0,1/20+0,3/30+0,2/40+0,1/50.
Известно, что для произвольных (обычных, чётких) подмножеств А, В, и С множества U выполняются следующие соотношения.
А =A – инволютивность;
A B=B A |
– коммутативность; |
A∩B=B∩A |
A (B C)=(A B) C |
– ассоциативность; |
||
A∩(B∩C)=(A∩B)∩C |
|||
|
|||
A (B∩C)=(A B)∩(A C) |
– дистрибутивность; |
||
A∩(B C)=(A∩B) (A∩C) |
|||
|
|||
A =A |
|
|
|
A U=U |
– свойства операций с и с U; |
||
A∩= |
|||
|
|
A∩U=A
A B= A ∩B
A∩B= A B
A A=A
A∩A=A
А∩(А В)=А А (А∩В)=А A A=U
A ∩A=
Если А*, В*, и С* нечеткие подмножества универсального (обычного) множества U, то можно доказать, что выполняются все приведённые свойства за исключением последних двух соотношений (свойства дополнения), т. е. для нечетких подмножеств имеем следующие соотношения.
1)А* =A* – инволютивность;
2)A* B*=B* A*
3)A*∩B*=B*∩A*
4)A* (B* C*)=(A* B*) C*
5)A*∩(B*∩C*)=(A*∩B*)∩C*
6)A* (B*∩C*)=(A* B*)∩(A* C*)
7)A*∩(B* C*)=(A*∩B*) (A*∩C*)
8)A* =A*
9)A* U=U
10)A*∩=
11)A*∩U=A*
12)A* B*= A* ∩B*
13)A*∩B*= A* B*
14)A* A*=A*
15)A*∩A*=A*
16)А*∩(А* В*)=А*
17)А* (А*∩В*)=А*
– ассоциативность;
– дистрибутивность;
Здесь U является обычным множеством, для которого полагаем, что его характеристическая функция введена как: µU(х)=1 для всех х U. Множествотоже является обычным множеством, для которого полагаем, что его характеристическая функция введена как: µ (х)=0 для всех х U.
Как уже указано, свойства дополнения в общем случае не выполняются, т.е. существуют А* и В* такие, что:
A* A* ≠ U,
В* ∩В* ≠ .