close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Представление иерархий с
помощью логики
Пример иерархии –
родословное древо
Иван
Борис
Галина
Константин
Анна
Владимир
Дарья
Елена
Логическое представление
исходных данных
Универсальное множество: {А, Б, В, Г, Д, Е, К, И}
Предикаты:
Женщина(x) - x является женщиной,
Мужчина(x) - x является мужчиной,
Родитель(x,y) - x является родителем y
Значения предикатов:
Мужчина(Б)=Истина, Мужчина(В)=Истина,
Мужчина(К)=Истина, Мужчина(И)=Истина
Женщина(А)=Истина, Женщина(Г)=Истина,
Женщина(Д)=Истина, Женщина(Е)=Истина,
Родитель(И,Б)=Истина, Родитель(И,К)=Истина,
Родитель(Г,Б)=Истина, Родитель(Г,К)=Истина,
Родитель(Б,В)=Истина, Родитель(Б,Д)=Истина,
Родитель(А,В)=Истина, Родитель(А,Д)=Истина,
Родитель(А,Е)=Истина.
Для других значений переменных предикаты ложны.
Представление высказываний
о положении в иерархии
x (Мужчина(x) & y Pодитель(x,y))
Существует такой мужчина x,
который является родителем y
(x является отцом y)
x
y
x (Мужчина(x) & y (Pодитель(x,y) & z Pодитель(y,z)))
Существует такой мужчина x,
который является родителем y,
который является родителем z
(x является дедом z)
x (Мужчина(x) & y (Pодитель(y,x) & z Pодитель(y,z)))
Существует такой мужчина x,
y
у которого есть родитель y,
который является родителем z
(x является братом z)
x
x
y
z
z
Проверка истинности.
Пример 1
x (Мужчина(x) & y Pодитель(x,y))
1) Подставим вместо x значение А:
Мужчина(А) = Ложь. Дальше не проверяем.
При x=A формула ложна
2) Подставим вместо x значение Б (ищем ребенка Б):
Мужчина(Б) = Истина. Далее будем подбирать значение y
2.1) Подставим вместо y значение A
Родитель(Б,А) = Ложь. При y=A формула ложна
2.2) Подставим вместо y значение Б
Родитель(Б,Б) = Ложь. При y=Б формула ложна
2.3) Подставим вместо y значение В
Родитель(Б,В) = Истина.
При y=В формула истинна
При x=Б и y=В формула истинна, Б является отцом В
Проверка истинности.
Пример 2 (начало)
x (Мужчина(x) & y Pодитель(x,y) & z Pодитель(y,z)))
1) Подставим вместо x значение А:
Мужчина(А) = Ложь. Дальше не проверяем.
При x=A формула ложна
2) Подставим вместо x значение Б:
Мужчина(Б) = Истина.
Далее будем подбирать значение y (ищем ребенка Б):
2.1-2.2) При y=A и y=Б формула ложна
2.3) При y=В Родитель(Б,В) = Истина
Далее будем подбирать значение z (ищем ребенка В):
2.3.1) При z=А Родитель(В,А) = Ложь
2.3.2-2.3.8) Аналогично перебираем все остальные
значения, получаем, что Родитель(В,z) = Ложь при
каждом значении z.
Нужно искать другое значение y
(У В нет детей, ищем другого ребенка Б)
Проверка истинности.
Пример 2 (продолжение)
x (Мужчина(x) & y Pодитель(x,y) & z Pодитель(y,z)))
2) При x=Б Мужчина(Б) = Истина.
2.4) При y=Г Родитель(Б,Г) = Ложь
2.5) При y=Д Родитель(Б,Д) = Истина
Далее будем подбирать значение z (ищем ребенка Д):
2.5.1) При z=А Родитель(Д,А) = Ложь
2.5.2-2.5.8) Аналогично перебираем все остальные
значения, получаем, что Родитель(Д,z) = Ложь при
каждом значении z.
Нужно искать другое значение y
(У Д нет детей, ищем другого ребенка Б)
2.6-2.8) При y=Е, y=И, y=К формула ложна
Нужно искать другое значение x
(У Б нет внуков, ищем другого мужчину)
Проверка истинности.
Пример 2 (продолжение)
x (Мужчина(x) & y Pодитель(x,y) & z Pодитель(y,z)))
3) При x=В Мужчина(В) = Истина
Далее будем подбирать значение y (ищем ребенка В)
3.1) При y=А Родитель(В,А) = Ложь
3.2-3.8) Аналогично перебираем все остальные
значения, получаем, что Родитель(В,y) = Ложь при
каждом значении y.
Нужно искать другое значение x
(У В нет детей, ищем другого мужчину)
4-6) При x=Г, x=Д, x=Е формула ложна
7) При x=И Мужчина(И) = Истина (ищем ребенка И):
Далее будем подбирать значение y (ищем ребенка И):
7.1) При y=А Родитель(И,А) = Ложь
7.2) При y=Б Родитель(И,Б) = Истина (ищем ребенка Б):
7.2.1) При z=А, z=Б формула ложна
7.2.3) При z=В Родитель(Б,В) = Истина
Проверка истинности.
Пример 2 (окончание)
x (Мужчина(x) & y Pодитель(x,y) & z Pодитель(y,z)))
При x=И Мужчина(И) = Истина,
при y=Б Родитель(И,Б) = Истина,
при z=В Родитель(Б,В) = Истина,
вся формула истинна, И является дедом В
1/--страниц
Пожаловаться на содержимое документа