- •Часть 1. Математические основы теории искусственного интеллекта
- •1.1. Общие сведения
- •1.2. Основные операции и функции
- •1.3. Основные понятия
- •1.4. Синтаксис
- •1.5. Функции. Законы и свойства операций и функций
- •1.5.1. Таблицы истинности основных логических функций
- •1.5.2. Операции и функции нечеткой логики
- •1.5.3. Законы и свойства операций
- •1.6. Особенности синтаксиса исчисления предикатов
- •1.6.1. Запись утверждения в языке исчисления предикатов
- •1.6.2. Синтаксические приемы в кванторных утверждениях
- •1.6.3. Отрицание кванторов
- •1.7. Семантика исчисления высказываний
- •1.8. Правила вывода
- •1.8.1. Преобразования к нормальным формам
- •1.8.2. Модус поненс (сокращение посылки)
- •1.8.3. Цепное заключение
- •1.9. Стратегии доказательств в четкой логике
- •1.9.1. Понятие доказательства в логике
- •1.9.2. Доказательство введением допущения
- •1.9.3. Приведение к противоречию
- •1.9.4. Метод резолюций
- •1.9.5. Доказательство теорем методом резолюции в ип
1.5.3. Законы и свойства операций
5 основных законов:
1) Коммутативный
AB=BA
A|B = B|A
Для нечетких множеств:
AB = BA
AB = BA
2) Ассоциативный
A(BC) = (AB)C
A|(B|C) = (A|B)|C
Для нечетких множеств:
A(BC) = (AB)C
A(BC) = (AB)C
3) Свойства операций И, ИЛИ
Для четкой логики:
AT = A
AF = F
A|F = A
A|T = T
Для нечетких множеств:
AU = A
A =
A = A
AU = U
AU = A
A =
A = A
AU = U
4) Свойства отрицания
Для четкой логики:
AA = F
A|A = T
Для нечетких множеств:
AA
AA U
AA
AA U
5) Дистрибутивность
A(B|C) = (AB)|(BC)
A|(BC) = (A|B)(A|C)
Для нечетких множеств:
A(BC) = (AB) (AC)
A(BC) = (AB) (AC)
A(BC) (AB) (AC)
A(BC) (AB) (AC)
Эти пять законов полностью определяют булеву алгебру. Из них можно получить другие законы:
1) Дополнение
~~A=A
2) Идемпотентность
AA = A
A|A = A
Для нечетких множеств:
AA = A
AA = A
AA A
AA A
3) Поглощение
A(A|B) = A|(AB) = A
Можно показать, что свойство поглощения доказывается через свойства операций и дистрибутивный закон:
A(A|B) = (A|F)(A|B) = A|(FB) = A
Законы де Моргана:
~(AB) = ~A | ~B
~(A|B) = ~A ~B
Для нечетких множеств:
~(AB) = ~A ~B
~(AB) = ~A ~B
~(AB) = ~A ~B
~(AB) = ~A ~B
Из таблицы 3 получается еще ряд полезных правил, касающихся преобразований функций. В частности, можно заметить возможность замены импликации дизъюнкцией или инверсией конъюнкции (см. также правила де Моргана):
AB = ~A | B = ~(A~B)
Обратные замены:
A|B= ~AB
AB = ~(A~B)
Высказывание "AэквивалентноB" означает "изAследуетBИ изBследуетA". Аналогичный вывод можно сделать и по таблице истинности. Т.е.
AB = (AB) (BA)
При помощи импликаций и конъюнкции можно записать стандартную конструкцию простого ветвления ЕСЛИ-ТО-ИНАЧЕ. Высказывание "если A, тоB, иначеC" записывается следующим образом:
(AB) (~AC).
1.6. Особенности синтаксиса исчисления предикатов
1.6.1. Запись утверждения в языке исчисления предикатов
Рассмотрим следующие примеры:
1. (x) Поставляется_заводом_А (x)Стоит_меньше (x, 5000р.). Это утверждение истинно для очень большого диапазона значений, т.е. можно сказать, что сформулировано оно неоптимально. Действительно, оно истинно как дляx, поставляемых заводом (значение первого операнда импликацииT), так и дляx, не поставляемых заводом, (значение первого операнда импликацииF).
2. (x) Поставляется_заводом_А (x)Стоит_меньше (x, 5000р.). Здесь утверждается, что обязательно найдется изделие, поставляемое заводом А и стоящее меньше 5000р. Отсюда не следует, что все изделия, поставляемые заводом А, стоят меньше 5000р.
3. (x) Поставляется_заводом_А (x)Стоит_меньше (x, 5000р.). Это утверждение не может быть истинным. Оно означает, что вообще любой объект из всего универсальногомножества объектов поставляется заводом А и стоит меньше 5000р. Вместо конъюнкции здесь правильнее использовать импликацию:
(x) Поставляется_заводом_А (x)Стоит_меньше (x, 5000р.).
4. Можно использовать конъюнкцию нескольких предикатов:
(x) Поставляется_заводом_А (x)Хрупкий (x)Стоит_меньше (x, 5000р.).
В языке исчисления предикатов, как в языке программирования, не должно быть несовпадения типов. Например, если в данном случае Стоит_меньше - предикатный символ, а аргумент предиката Хрупкий имеет тип Объект (не булевский), то неверной будет следующая запись:
(x) Поставляется_заводом_А (x)Хрупкий (Стоит_меньше (x, 5000р.)).
Из рассмотренных примеров можно, в частности, сделать вывод, что за квантором общности часто идет импликация, а за квантором существования - конъюнкция.