Редактирование: Математическая Логика, 05 семинар (от 21 ноября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 8: | Строка 8: | ||
# A<sub>0</sub> ← A<sub>1</sub>, …, A<sub>n</sub>;, где левая часть (A<sub>0</sub>) — заголовок, правая часть (A<sub>1</sub>, …, A<sub>n</sub>;) — тело, A<sub>i</sub> = P(t<sub>1</sub>, t<sub>n</sub>), i = <span style="whitespace:no-break; border-top:solid 1px #000000">0…n</span> — правило. Имеет два способа истолкования: | # A<sub>0</sub> ← A<sub>1</sub>, …, A<sub>n</sub>;, где левая часть (A<sub>0</sub>) — заголовок, правая часть (A<sub>1</sub>, …, A<sub>n</sub>;) — тело, A<sub>i</sub> = P(t<sub>1</sub>, t<sub>n</sub>), i = <span style="whitespace:no-break; border-top:solid 1px #000000">0…n</span> — правило. Имеет два способа истолкования: | ||
## С точки зрения человека: если выполняются A<sub>1</sub>;, … ,A<sub>n</sub>, то выполняется A<sub>0</sub>. Например, если записано P(x) ← P(f(x)), R(c), то оно трактуется следующим образом: «Если предмет ''c'' обладает свойством ''R'' и ''f''(''x'') обладает свойством ''P'', то ''x'' обладает свойством ''P''» | ## С точки зрения человека: если выполняются A<sub>1</sub>;, … ,A<sub>n</sub>, то выполняется A<sub>0</sub>. Например, если записано P(x) ← P(f(x)), R(c), то оно трактуется следующим образом: «Если предмет ''c'' обладает свойством ''R'' и ''f''(''x'') обладает свойством ''P'', то ''x'' обладает свойством ''P''» | ||
- | ## С точки зрения компьютера: чтобы решить задачу A<sub>0</sub>, необходимо сначала решить задачи A<sub>1</sub>, …, A<sub>n</sub>. То есть, если интерпретировать предыдущий пример, то получим, что для решения задачи P(x) необходимо решить | + | ## С точки зрения компьютера: чтобы решить задачу A<sub>0</sub>, необходимо сначала решить задачи A<sub>1</sub>, …, A<sub>n</sub>. То есть, если интерпретировать предыдущий пример, то получим, что для решения задачи P(x) необходимо решить задаи R(x) и P(f(x)) |
# Программные утверждения второго рода — факты (такой способ принят в Прологе) <div class="definition">'''Факт''' — правило без тела.</div> | # Программные утверждения второго рода — факты (такой способ принят в Прологе) <div class="definition">'''Факт''' — правило без тела.</div> | ||
#: Факты записываются следующим образом: A<sub>0</sub> ← ;, где левая часть (A<sub>0</sub>) — заголовок; A<sub>0</sub> — факт | #: Факты записываются следующим образом: A<sub>0</sub> ← ;, где левая часть (A<sub>0</sub>) — заголовок; A<sub>0</sub> — факт | ||
- | ## | + | ## Интепретация человеком: «я считаю, что A<sub>0</sub> истинно» |
## Интерпретация с точки зрения компьютера: «задача A<sub>0</sub> априори решена» | ## Интерпретация с точки зрения компьютера: «задача A<sub>0</sub> априори решена» | ||
- | Работа | + | Работа логиячской программы состоит в том, чтобы решить заданный набор задач ('''запрос''', '''целевое утвреждение'''). Вид запроса: |
? C<sub>1</sub>, …, C<sub>n</sub> | ? C<sub>1</sub>, …, C<sub>n</sub> | ||
Строка 39: | Строка 39: | ||
Жена(Eve, Adam) ← ; | Жена(Eve, Adam) ← ; | ||
Далее: | Далее: | ||
- | Отец(Adam, | + | Отец(Adam, Avel) |
- | После этого надо записать, что | + | После этого надо записать, что Абель — сын Адама, Евы, а также тот факт, что Ева — мать Абеля. |
Через несколько страниц учёный попадёт в затруднительное положение, поскольку вносить надо всё больше. Но можно описывать не все связи, можно описать правила: | Через несколько страниц учёный попадёт в затруднительное положение, поскольку вносить надо всё больше. Но можно описывать не все связи, можно описать правила: | ||
Сын(X, Y) ← Отец(Y, X); | Сын(X, Y) ← Отец(Y, X); | ||
- | «Если Y — | + | «Если Y — отчец X, то X — отец Y». Или, другими словами, чтобы проверить, является ли X сыном Y, надо проверить, является ли Y отцом X. Тогда: |
Супруг(X, Y) ← Муж(X, Y); | Супруг(X, Y) ← Муж(X, Y); | ||
Супруг(X, Y) ← Жена(X, Y); | Супруг(X, Y) ← Жена(X, Y); | ||
Строка 106: | Строка 106: | ||
Родственник(X, Y) ← Предок(X, Y) | | Родственник(X, Y) ← Предок(X, Y) | | ||
Предок(Y, X) | | Предок(Y, X) | | ||
- | + | Предок(Z, X), Предок(Z, Y), X ≠ Y; | |
Далее — программные вещи. | Далее — программные вещи. | ||
Строка 115: | Строка 115: | ||
Составные типы данных: | Составные типы данных: | ||
- | * В Си, Алголе, … основным составным типом является массив, | + | * В Си, Алголе, … основным составным типом является массив, отличитильным признаком которого является произвольная адресация |
- | * В Прологе, Лиспе основным составным типом является список, | + | * В Прологе, Лиспе основным составным типом является список, отличитильным признаком которого является последовательная адресация |
Список — более естественный тип данных с точки зрения рекурсии. | Список — более естественный тип данных с точки зрения рекурсии. |