- •1.(30) Основные понятия мЛиТа
- •2. История развития теории алгоритмов.
- •3. Роль алгоритма в науке и технике.
- •4. Понятие алгоритма.
- •5. Алгоритмический процесс.
- •6. Основные вопросы теории алгоритмов.
- •7. Классификация алгоритмов.
- •8. Свойства алгоритмов.
- •9. Понятие предиката
- •10. Интерпретация. Модель
- •12. Нормальные алгорифмы Маркова.
- •13. Гипотеза Черча.
- •14. Машина Тьюринга.
- •15. Рекурсивные функции.
- •2) Тождественные функции любого числа независимых
- •16. Алгоритмически неразрешимые проблемы
- •17. Понятие о сложности
- •18. Временная и вычислительная сложность алгоритмов.
- •19. Понятие р- и np-задач.
- •21. Темпоральные логики. Нечеткая и модальные логики.
- •22. Примеры задач np-класса.
- •24. Дедуктивные теории
- •25. Свойства дедуктивных теорий
- •26. Формальные аксиоматические теории
- •27. Свойства выводимости
- •31.(38) Логические функции
- •34. Кванторы
- •39. Алгоритм Сортировка слиянием.
- •40. Алгоритм Пузырьковая сортировка.
- •41. Алгоритм Сортировка вставками.
- •42. Алгоритм Сортировка Шейкером.
- •43. Алгоритм Быстрая сортировка.
- •44. Алгоритм Сортировка подсчетом.
- •47. Логика высказываний.
- •48. Булева алгебра и основные логические тождества.
- •49. Пропозициональные буквы, связки и формы (формулы логики
- •50. Исчисление высказываний (теория l)
21. Темпоральные логики. Нечеткая и модальные логики.
Основоположником понятия лингвистической переменной является Л. Заде.
Он же заложил основы применения этой переменной к приближенным
рассуждениям. Главная цель введения лингвистической переменной и логики,
основанной на этих переменных, является формализация приближенных
рассуждений, используя теорию нечетких множеств.
В этой логике используются нечёткие количественные понятия (почти все,
много, мало, несколько и т.п.), нечёткие истинностные значения (существенно
истинный, очень истинный, более или менее истинный, ложный и т. п.), а
также иные нечеткие понятия (молодой, редкий, дорогой, красивый, почти
невозможный, невероятный и т.п.).
Лингвистической называется переменная, значениями которой являются
слова или предложения естественного или искусственного языка. Например,
ВОЗРАСТ - можно рассматривать как числовую переменную, а можно
рассматривать как лингвистическую переменную, принимающую следующие
лингвистические значения: очень молодой, молодой, вполне молодой, не
молодой, не молодой и не очень старый, старый и т.п. При этом для каждого
из перечисленных значений нужно задать характеристическую функцию,
называемую смыслом этого значения.
Более точно лингвистическая переменная описывается набором:
(Х, Т(Х), U, G , М)
в котором:
Х - название лингвистической переменной,
Т(Х) - множество лингвистических значений переменной Х,
U - универсальное множество,
G - синтаксические правила, порождающие названия переменной, т.е.
правила определения синтаксических значений,
М - семантические правила, которые ставят в соответствие каждой нечеткой
переменной ее смысл М(Х), т.е. характеристическую функцию для Х.
Отметим, что при определении U и Т(Х) множество понимается в обычном
классическом смысле, а не имеется в виду нечеткие множества. Причём
всюду, когда имеем дело с нечеткими множествами, пишется «нечеткое
множество», если слово «нечеткое» не записано, то это обозначает, что
нечеткости нет. Кроме того отметим, что множество U может быть как
конечным, так и бесконечным, а множество Т(Х) считается конечным.
Структуру лингвистической переменной можно представить в следующем
виде, см. Рис. 5.5.
Трактовка истинности как лингвистической переменной приводит к
нечеткой лингвистической логике, которая существенно отличается от
двухзначной и многозначной логики. Эта нечеткая логика является основой
того, что можно было бы назвать приближенными рассуждениями.
Лингвистическая переменная ИСТИННОСТЬ может принимать, например,
следующие лингвистические значения: существенно истинный, очень, очень
32
истинный, очень истинный, истинный, не очень истинный, более или менее
истинный, ..., существенно ложный.
Смысл каждого
значения
является
некоторой
функцией
принадлежности
на базовом
множестве [0,1].
Функцию
принадлежности
значения
истинный,
например, можно задать как в предыдущем параграфе, либо, например, с
помощью выражения:
Тогда носителем значения истинный является отрезок [а,1], см. Рис 5.6. Для
значения ложный функцию принадлежности, например, можно задать
выражением: μложный(х) = μистинный(1-х), график см. на Рис. 5.6.
В некоторых случаях считают, что U есть конечное множество, например,
U={0; 0,1; 0,2; 0,3; ...; 0,9; 1}, которое записывают в виде: U=0+0,1+0,2+0,3+...
+0,9+1.
При таком задании U функцию принадлежности значения истинный можно
определить, например, так:
истинный=0,5/0,7+0,7/0,8+0,9/0,9+1/1,
33
где, например, пара 0,5/0,7 означает, что совместимость значения истинности
0,7 со значением истинный равна 0,5.
Для исследований лингвистических переменных вводятся логические
операции - связки ,&,∨. Ясно, что эти операции будут уже не столь
тривиальны. Здесь нужно будет различать, например, соединение союзом
«и» лингвистических значений (положим, истинный и не истинный) от союза
«и» в высказывании «ИСТИННЫЙ и не ИСТИННЫЙ» Построенная таким
образом нечеткая логика используется в так называемых приближенных
рассуждениях. Приближенные рассуждения лежат в основе способности
человека понимать естественный язык, разбирать почерк, играть в шахматы,
принимать решения в сложной и не полностью определенной среде. Данная
логика интенсивно исследуется и находятся ее приложения, в частности,
используется в экспертных системах, в системах читающих рукописный текст
и т.п.
Если исключить невозможное, то то что останется, сколь бы невероятным оно
ни было, должно быть истиной (Шерлок Холмс).
А. К. Дойль
Модальные логики
Назначение различных систем модальной логики состоит в том, чтобы
включить в логику так называемые модальности – прежде всего
необходимости и возможности: того что «должно быть», и того, что «может
быть».
Обычно говорят, что высказывание логически необходимо, если его
истинность может быть установлена независимо от опыта, или чисто
логическим путем. В модальной логике из необходимости высказывания
вытекает его истинность, но не наоборот. Высказывание и его отрицание не
могут быть вместе необходимыми.
Необходимость является, таким образом, более сильным видом истины, чем
фактическая истинность. С самого зарождения логики было подмечено
различие между истинными высказываниями, являющимися таковыми, так
сказать в силу необходимости, и высказываниями истинными случайными,
возможными.
Развитие модальной логики можно разбить на три периода:
К первому периоду относится зарождение модальной логики в античности и
некоторое развитие в средневековье. Модальности были введены
Аристотелем, который считал, что термин «возможность» имеет различный
смысл. Аристотелем введены и исследованы модальные силлогизмы и
некоторые другие аспекты модальностей. Проводя исследование
аристотелевской логики, Лукасевич заключает, что в работах Аристотеля
можно найти все элементы необходимые для построения полной системы
модальной логики, однако Аристотель исходил из двузначной логики, в то
время как модальная логика не может быть двузначной. К идее многозначной
логики Аристотель подошёл вплотную, рассуждая о «будущем морском
сражении». Следуя Аристотелю, Лукасевич в 1920 году построил трёхзначную
логику. Тем самым выявляется идейная связь между модальными и
34
многозначными логиками. Второй период связан с появлением работ К.
Льюиса (примерно 80 лет назад). В этот период строятся формальные
системы (исчисления) модальной логики, выявляются различные черты
модальных понятий. Идея Льюиса состояла в проведении различия между
связками, выражающими логическую необходимость, и связками, не
выражающими такого рода необходимости.
Для третьего периода, начатого работами С. Крипке (конец 1950 годов),
существенно выявление внутреннего единства различных систем, казавшихся
ранее никак не связанными между собой.
35