Квант логики предикатов и скобки

Взято с: https://cs.nyu.edu/faculty/davise/ai/pred-examples.html

Пусть U будет вселенной, содержащей людей и песни. Пусть L — язык со следующими примитивами.

c(P,S) --- Person P composed song S.
l(P,S) --- Person P likes song S.
s(P,S) --- Person P sings song S.
m(S) --- Song S is in a major key.
Constants: a --- Amy; b --- Barry; d --- David; y -- Yankee Doodle.

Дэвиду нравятся некоторые песни, которые написала Эми (т.е. по крайней мере одна песня). существует(S) c(a,S) ^ l(d,S).

Есть ли разница в значении между exists(S) c(a,S) ^ l(d,S) и exists(S) [c(a,S) ^ l(d,S)]?


logic predicate first-order-logic
person toast    schedule 19.08.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

exists(S) c(a,S) ^ l(d,S) неоднозначно. Это может означать либо exists(S) [c(a,S) ^ l(d,S)], либо exists(S) [c(a,S)] ^ l(d,S). Эти две формулы разные. Первая — это замкнутая формула, которую также часто называют предложением, вторая — это формула со свободными переменными.

Вы можете лучше понять разницу между двумя формулами. Применяя правило переименования к закрытой подформуле последней, вы получаете

exists(R) [c(a,R)] ^ l(d,S)

Эта формула означает, что a сочинил какую-то песню, а d нравится песня S.

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

По моему опыту, логические связки обычно связывают сильнее, чем квантификаторы. Если принять это соглашение, двусмысленность разрешается в отношении первого варианта, то есть ожидается, что exists(S) c(a,S) ^ l(d,S) будет означать exists(S) [c(a,S) ^ l(d,S)]. Однако вы должны проверить это, прежде чем полагаться на него.

person Dmitri Chubarov    schedule 20.08.2018