ПО, ЭВМ и АСУ из Таможенного Союза

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » базовые определения » Что общего у резолюции (resolution) и у унификации (unification)?


Что общего у резолюции (resolution) и у унификации (unification)?

Сообщений 1 страница 7 из 7

1

https://en.wikipedia.org/wiki/Resolution_(logic)
https://ru.wikipedia.org/wiki/Правило_резолюций

https://en.wikipedia.org/wiki/Unification_(computer_science)
https://ru.wikipedia.org/wiki/Частный_случай_формулы

John Alan Robinson used first-order syntactical unification as a basic building block of his resolution procedure for first-order logic

1965, J. A. Robinson, A Machine-Oriented Logic Based on the Resolution

Traditionally, a single step in a deduction has been required, for pragmatic and psychological reasons, to be simple enough, broadly speaking, to be apprehended
as correct by a human being in a single intellectual act.
No doubt this custom originates in the desire that each single step of a deduction should be indubitable, even though the deduction as a whole may consist of a long chain of such steps. The ultimate conclusion of a deduction, if the deduction is correct, follows logically from the premisses used in the deduction; but the human mind may well find the unmediated transition from the premisses to the conclusion surprising, hence (psychologically) dubitable. Part of the point, theft, of the logical analysis
of deductive reasoning has been to reduce complex inferences, which are beyond the capacity of the human mind to grasp as single steps, to chains of simpler inferences, each of which is within the capacity of the human mind to grasp as a single transaction.

From the theoretical point of view, however, an inference principle need only be sound (i.e., allow only logical consequences of premisses to be deduced from them) and effective (i.e., it must be algorithmically decidable whether an alleged application of the inference principle is indeed an application of it).

When the agent carrying out the application of an inference principle is a modern computing machine, the traditional limitation on the complexity of inference principles is
no longer very appropriate. More powerful principles, involving perhaps a much greater amount of combinatorial information-processing for a single application, become a possibility.

In the system described in this paper, one such inference principle is used. It is called the resolution principle, and it is machine-oriented, rather than human-oriented, in the sense of the preceding remarks. The resolution principle is quite powerful, both in the psychological sense that it condones single inferences which are often beyond the ability of the human to grasp (other than discursively), and in the theoretical sense that it alone, as sole inference principle, forms a complete system of first-order logic. While this latter property is of no great importance, it is interesting that (as far as the author is aware) no other complete system of first-order logic has consisted of just one inference principle, if one construes the device of introducing a logical axiom, given outright, or by a schema, as a (premiss-free) inference principle. The main advantage of the resolution principle lies in its ability to allow us to avoid one of the major combinatorial obstacles to efficiency which have plagued earlier theorem-proving procedures.

Отредактировано Лис (2019-11-24 14:51:02)

0

2

Я ничего не понял.

Пересказываю своими словами:
У нас есть набор высказываний. Мы называем этот набор высказываний аксиомами. Затем к аксиомам мы применяем операцию логического вывода (резолюцию), и получаем теоремы.

не ясно, как работает операция резолюции. (хорошо бы иметь практические примеры, из области близкой к области интересов, т.е. парсингу)

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

не ясно, как мы превращаем правила грамматики в высказывания, как превращаем входной текст в высказывания, что именно мы пытаемся доказывать (вывод какой теоремы получить).

Отредактировано Лис (2019-11-24 15:04:03)

0

3

«Правило резолюций, применяемое последовательно для списка резольвент, позволяет ответить на вопрос, существует ли в исходном множестве логических выражений противоречие» (q) https://ru.wikipedia.org/wiki/Правило_резолюций
   (что такое "резольвента"? каким образом "правило резолюций ... позволяет ответить на вопрос о существовании противоречия", не ошибка ли это в формулировке мысли?)

«Резольвента (от лат. resolvere — здесь: решать) используется в математике в различных значениях.» (q) https://ru.wikipedia.org/wiki/Резольвента (википедия редиректит на страницу "Правило резолюций", см. "Сепулирование")

«Пра́вило резолю́ций — это правило вывода»

«правило вывода — это эффективная процедура для проверки того, что одна заданная формула в рассматриваемой теории непосредственно за один шаг выводится из других заданных формул»
    (правило — это процедура, всё вам ясно?)

Правило вывода

Модус поненс

(Вы как хотите, а у меня в голове "лампочка не загорается", т.е. я по-прежнему не понимаю, как они при помощи всего этого парсят)

Отредактировано Лис (2019-11-24 19:03:35)

0

4

Лис написал(а):

не ясно, как мы превращаем ... входной текст в высказывания

навскидку два варианта:
либо у нас цепочка (список) из узлов,
либо у нас комплект букв (вершин графа) с рёбрами (эта буква следует вслед за той).

буква (позиция начала, биты в кодировке UTF-8)
следует-за(позиция1, позиция2)

первый вариант более последовательный, навязывающий порядок вычислений
второй вариант более провоцирующий просчёт лишних вариантов

Отредактировано Лис (2019-11-24 19:17:28)

0

5

Лис написал(а):

как мы превращаем правила грамматики в высказывания

Ну, я даже незнаю, например для ДКА.

Для ДКА создадим комплект правил, соответствующих  переходу автомата из состояния в состояние.
(делаем логический вывод для инициализации по первой букве,
и по логическому выводу на каждую следущую букву.)

Последнее правило будем считать формулой всего автомата, если она выводима из формул переходов и формул входной строки, то значит доказуема.

Ну и с другими правилами примерно так же. Если в итоге доказали правило для всей грамматики, значит парсинг удался.
А если нет, то что и как выводить в качестве диагностики?

Надо бы на конкретном примере...

Отредактировано Лис (2019-11-24 19:25:59)

0

6

Но даже если удастся разобраться с процедурой унификации, то это всё не объясняет при чём тут FCG и как она устроена.

Отредактировано Лис (2019-11-24 21:41:26)

0

7

the use of unification for applying constructions to expand linguistic structures in language parsing and production, as pioneered in
Functional Unification Grammar (Kay, 1986), and also used in
Lexical Functional Grammar (Dalrymple et al., 1995) and
Head-driven Phrase structure Grammar (Pollard & Sag, 1994; Sag et al., 2003).

0


Вы здесь » ПО, ЭВМ и АСУ из Таможенного Союза » базовые определения » Что общего у резолюции (resolution) и у унификации (unification)?