Вопрос 8.

Проблемы разрешимости, непротиворечивости и полноты исчисления предикатов.

Проблема разрешимости исчисления предикатов есть проблема поиска эффективной процедуры в доказательстве. Исчисление предикатов – пример неразрешимой формальной системы, т.к. нет единого эффективного алгоритма в доказательстве любой формулы. Наличие кванторов, ограничивающих области определения, наличие сколемовских функций не позволяет использовать таблицы истинности.

Проблема непротиворечивости исчисления предикатов заключена в доказательстве невыводимости формулы и ее отрицания. Исчисление предикатов непротиворечиво, т. к. каждая доказуемая формула является тождественно истинной формулой. Тогда ее отрицание является тождественно ложной формулой и при доказательстве в исчислении предикатов ведет к противоречию.      

Из лекций:

Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет. Если рассматривать формулы, содержащие только одноместные предикаты, то логика предикатов была бы разрешима.

Тезис Черча: Логика предикатов полуразрешима.

Логика называется непротиворечивой, если в ней нельзя вывести одновременно некоторые утверждения и его отрицание. Теорема логики предикатов непротиворечива.

Логика называется полной, если в ней выводимо все, что истинно. Теорема о полноте исчислений предикатов полна.

Теорема Гёделя о неполноте.

Во всякой достаточно богатой теории существует такая истинная формула, что не она, не её отрицание не выводимо в этой теории.

Вопрос 9.

Нечеткие множества, функции принадлежности.

Нечёткое (или размытое, расплывчатое, туманное, пушистое) множество — понятие, введённое Лотфи Заде в 1965 г. Л. Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 или 1.

Под нечётким множеством понимается совокупность

,

где — универсальное множество, а — функция принадлежности (характеристическая функция), характеризующая степень принадлежности элемента нечёткому множеству .

Функция принимает значения в некотором линейно упорядоченном множестве . Множество называют множеством принадлежностей, часто в качестве выбирается отрезок . Если , то нечёткое множество может рассматриваться как обычное, чёткое множество.

Фаззификация и дефаззификация.

Определение: Процесс перехода от четкого представления к нечеткому называется фаззификацией.

В целом весь процесс нечеткого управления можно разбить на несколько шагов: фаззификация или переход к нечеткости, использование нечетких продукционных правил, дефаззификация или устранение нечеткости. При реализации устройств управления, использующих аппарат нечеткой логики, возможно использование специальных микроконтроллеров, которые способны выполнять «нечеткие» команды. Однако такие микроконтроллеры и средства разработки к ним достаточно экзотичны, поэтому представляет интерес реализация «нечетких» систем управления на «обыкновенных» микроконтроллерах распространенных серий. Но при этом необходимо решить ряд проблем, связанных с выполнением операций фаззификации и дефаззификации. Как показал опыт проектирования, при использовании стандартных функций принадлежности фаззификация входных переменных труда не представляет.

Использование при программировании микроконтроллеров языков высокого уровня позволяет легко реализовать работу с нечеткими правилами. Но чтобы исполнительное устройство смогло отработать команду, являющуюся результатом обработки нечетких правил, необходим этап дефаззификации, на котором избавляются от нечеткости. Для устранения нечеткости окончательного результата существует несколько методов [1, 2]. Наиболее часто применяемым методом дефаззификации является вычисление абсциссы центра тяжести фигуры объединенных усеченных множеств для каждого из нечетких правил. Центр тяжести фигуры находится по следующей формуле:

где Si — площадь i–й элементарной фигуры, — значение центра тяжести i–й элементарной фигуры. Элементарная фигура может иметь вид трапеции или прямоугольника. Для вычисления центра тяжести объединенных усеченных множеств при выполнении операции дефаззификации разработан оригинальный алгоритм, позволяющий разбивать эти множества на элементарные фигуры и рассчитывать координаты центров тяжести этих фигур.

Характерные точки определяют элементарные фигуры, на которые распадаются объединенные усеченные множества при определении центров тяжести по формуле (1). Формула (1) может быть преобразована к виду, позволяющему вычислять координату центра тяжести объединенного усеченного множества по координатам характерных точек:

где xi , уi — координаты характерных точек, определяющих границы элементарных фигур.

Методы деффазификации:

1. Метод максимума.

Выбирается тот элемент нечеткого множества, который имеет максимальную степень принадлежности.

2. Метод левого (правого) максимума.

Выбирается наименьший (наибольший) элемент нечеткого множества среди всех элементов имеющих максимальную степень принадлежности.

3. Метод центра тяжести.

4. Модифицированный метод центра тяжести.

Уровень a (0,05…1).

Выполняется a-срез (своего рода отсечение шумов).

5. Метод среднего из максимумов, где m — количество локальных максимумов.

Операции над нечеткими множествами.