- •ВВЕДЕНИЕ
- •Глава 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)
- •Ответы к тестам самоконтроля
166
Используя приведенные соотношения 1)-17), можно проводить упрощения, преобразования.
Однажды Насреддина спросили:
-Ходжа, где истина?
-Я не вижу места, где бы она отсутствовала, так что не могу указать точно место, где она находится.
-Ходжа Насреддин1
§4. Нечеткие высказывания и максиминные операции над ними
Нечетким высказыванием называется предложение, относительно которого можно судить о степени его истинности или ложности. Степень истинности или степень ложности каждого нечеткого высказывания принимает значение из замкнутого интервала [0,1], причем 0 и 1 являются их предельными значениями и совпадают с понятиями лжи и истины для "четких" высказываний. Степень истинности (степень ложности) каждого нечеткого высказывания может принимать, как только некоторые значения из [0,1], так и все значения из [0,1].
Примеры нечетких высказываний: "Два - маленькое число".
"Петров занимается большой общественной работой". "Волга - хорошая машина".
"Молодая была не молода".
Нечеткие высказывания бывают простыми и составными. Составные высказывания образуются из простых с помощью вводимых операций, таких как отрицание, конъюнкция, дизъюнкция, импликация и других. Операции могут вводиться различными способами. Рассмотрим следующий вариант введения операций.
Отрицанием нечеткого высказывания А* называется нечеткое высказывание, обозначаемое А*, степень истинности которого определяется выражением
А* =1-А*.
Конъюнкцией нечетких высказываний А*, В* называется нечеткое высказывание, обозначаемое А*&В*, степень истинности которого определяется следующим образом:
А*&В* = min(А*,В*).
Дизъюнкцией нечетких высказываний А*, В* называется нечеткое высказывание, обозначаемое А* В*, степень истинности которого находится как
А* В* = max(А*,В*).
1 Отметим, что приведенное имя Насреддина не единственно. Его называют в различных краях то Ходжой или Моллой, или Хасаном и, даже, Джохой Насреддином.
167
Импликацией нечетких высказываний А*, В* называется нечеткое высказывание, обозначаемое А* В*, степень истинности которого определяется выражением
А* В* = max(1-А*,В*).
Эквивалентностью нечетких высказываний А*, В* называется нечеткое высказывание, обозначаемое А*≡В*, степень истинности которого определяется выражением
А*≡В* = min(max(1-А*,В*), max(1-В*,А*)).
Введенная нечеткая логика называется нечеткой логикой с максиминными операциями.
Рассматривая А*, В*, С* и т.д. как нечёткие переменные (пропозициональные буквы), можно ввести понятие формулы в нечеткой логике точно также как вводились пропозициональные формы (формулы логики высказываний). Истинностные значения этих формул определяются согласно соотношений введенных для , &, , и ≡. Так, например, имеем:
А* А* = max(A*,1-A*) = |
А*, |
если А* ≥0,5 |
(5.7) |
|
1 − А*, |
если А* <0,5. |
|
Из (5.7) следует, что значение А* А* всегда не меньше 0,5. Рассмотрим теперь формулу:
А*& А* = min(A*,1-A*) = |
А*, |
если А* ≤0,5 |
|
1 − А*, |
если А* >0,5. |
Таким образом, истинностное значение для А*& А* будет всегда не больше
0,5.
Пусть нечеткое подмножество М молодых людей задано функцией принадлежности:
|
|
1, |
|
|
|
если х [0;20], |
|
µмолодой(х)= |
x − 20 |
|
2 |
−1 |
|
||
1 |
+ |
|
|
|
, |
если x > 20. |
|
4 |
|||||||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
Значение функции принадлежности для выбранного значения х, положим х = Тина, можно рассматривать как истинностное значение для нечёткого высказывания «Тина молода». Тогда истинностное значение нечеткого высказывания «Тина молода» будет равно 0,63, если ей 25 лет, см. Рис. 5.4 а). Если же Алёне 18 лет, то истинностное значение высказывания «Алёна молода» равно 1.
Используя нечёткое подмножество М можно ввести нечёткий предикат, например: «х является молодым человеком», т.е.: «х М».
Можно строить и другие нечёткие предикаты, используя, например,
понятия: пожилой, старый, редкий, красивая, дорогой и т.п.
Кроме нечётких предикатов, можно ввести нечёткие кванторы (почти все, много, несколько и т.п.), а также нечёткие истинностные значения
168
(совершенно истинный, очень истинный, истинный, совершенно ложный, очень ложный, ложный и т.п.).
Указанные нечёткие истинностные значения вводятся с помощью подходящих нечётких подмножеств, а они – с помощью функций принадлежности. Например, можно положить, что для х [0,1] имеем:
µсовершенно истинный(х)= х ; |
µсовершенно ложный(х)= |
|
1 − х ; |
2 |
2 |
; |
(5.8) |
µочень истинный(х)=х ; |
µочень ложный(х)=(1-х) |
|
|
µистинный(х)=х; |
µложный(х)=1-х, |
|
|
а вне отрезка [0,1] значения этих функций равны нулю. Графики этих функций представлены на Рис. 5.4 б).
|
|
|
|
|
|
очень ложный |
|
µМ(х) |
|
|
|
|
|
|
|
|
|
|
|
µМ(х) |
|
совершенно истинный |
|
1 |
|
|
|
1 |
|
|
истинный |
0.63 |
|
|
|
|
|
|
очень истинный |
|
|
|
|
|
|
совершенно ложный |
|
|
|
|
|
|
|
|
ложный |
0 |
18 |
25 |
Возраст |
0 |
0.63 |
1 |
х |
|
|
а) |
|
Рис. 5.4 |
б) |
|
|
|
|
|
|
|
|
|
Рассмотрим высказывания:
1)«Тина молода» - совершенно истинно;
2)«Тина молода» - истинно;
3)«Тина молода» - очень истинно;
4)«Тина молода» - очень ложно;
5)«Тина молода» - ложно;
6)«Тина молода» - совершенно ложно.
Для выяснения степени истинности (истинностных значений) высказываний
1)-6) сначала выясним значение у = µмолодой(х), затем по у вычисляем значения µ(у) по (5.8). Пусть Тине 25 лет. Тогда
µмолодой(25)=0,63.
Подставляя значение 0,63 в функции (5.8) получим, что истинностные значения для высказываний 1)-6) равны соответственно:
169
0,79; 0,63; 0,4; 0,14; 0,37; 0,61.
Пусть Х=2А множество подмножеств множества А (А≠) и на Х заданы обычные операции дополнения, пересечения и объединения, т.е. имеем алгебру А= Х; , ∩, . Положим, что V множество обычных (чётких) высказываний (с возможными значениями 1 и 0) с операциями , & и , т. е. имеем алгебру В= V; , &, . Легко видеть, что эти алгебры изоморфны, при этом ( Х) отображается на противоречие, а A на тавтологию. Этот изоморфизм можно продемонстрировать с помощью следующей таблицы.
|
А= Х; , ∩, - алгебра |
В= V; , &, - алгебра |
|
подмножеств множества А |
высказываний |
Основное |
Х – множество подмножеств |
V- множество |
множество |
множества А |
высказываний |
Выделенные |
|
П- противоречие |
элементы из |
|
|
основного |
|
|
множества |
А |
Т-тавтология |
Операции |
- дополнение |
- отрицание |
|
||
|
∩ - пересечение |
& - конъюнкция |
|
- объединение |
- дизъюнкция |
При указанном изоморфизме каждый элемент или операция, записанная в некоторой строке таблицы, для одной из алгебр переходит в соответствующий элемент или операцию, записанную в той же строке для другой алгебры.
Легко показать, что существует изоморфизм между стандартной логикой Лукасевича L1 (с максиминными операциями) и алгеброй нечётких подмножеств с операциями дополнения, пересечения и объединения, введёнными по (5.3), (5.4) и (5.5) соответственно. Действительно, функцию принадлежности µВ(х), х Х, с помощью которой задаётся нечёткое подмножество В на универсальном множестве Х, можно интерпретировать как функцию задающую степени истинности (истинностные значения) утверждения «х является элементом подмножества В» в L1. Обратно, истинностные значения утверждения «х является Р» в L1, где Р нечеткий предикат (такой, как молодой, высокий, красивый и т. п.) можно интерпретировать как значения функции принадлежности нечёткого подмножества со свойством Р, определённого на Х. Изоморфизм тогда следует из того, что логические операции в L1, определённые по формулам (5.2), в точности совпадают с операциями для нечётких подмножеств.
Стандартная логика Лукасевича L1 является лишь одной из возможных бесконечнозначных логик. Другие бесконечнозначные логики со значениями на [0,1] можно строить, например, вводя иначе, чем в L1 операции. Для