Доказательство того, что H пересекает K, является подгруппой в Прологе (H и K являются подгруппами) - PullRequest
Новая
       28

Доказательство того, что H пересекает K, является подгруппой в Прологе (H и K являются подгруппами)

0 голосов
/ 06 апреля 2020

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

h (== H) g тогда и только тогда, когда hg ^ {- 1} принадлежит H. Доказательство того, что это отношение эквивалентности (рефлексивное (симметрия c, транзитивная) эквивалентна доказательству того, что H является подгруппой.

Я сделал этот следующий код, и когда я пытаюсь доказать, что H пересекается, K является подгруппой, я получаю ошибку. Я новичок в Прологе, так что, возможно, я что-то неправильно понял. В математическом доказательстве не требуется говорить явную форму отношения эквивалентности, поэтому я его опускаю.

В программе я обозначаю hg и kg как H и K. H пересекается с K как hkg. 

inside(X,H) :- equals(H,X,e).



equals(hkg,e,e).
equals(hkg,x,e).
equals(hkg,y,e).
equals(hkg,z,e).
equals(hkg,X,Y) :- equals(hg,X,Y),equals(kg,X,Y).


reflexive(H) :- forall(inside(X,H),equals(H,X,X)).


symmetric(H) :- forall(equals(H,X,Y),equals(H,Y,X)).


transitive(H) :- forall(equals(H,X,Y),equals(H,Y,Z),equals(H,X,Z)).


subgroup(H) :- reflexive(H),symmetric(H),transitive(H).
subgroup(hg).
subgroup(kg).

На данный момент он не проходит тест на рефлексивность (первый тест). Не могли бы вы показать мне, что не так с этой программой? Если вам нужны дополнительные разъяснения, не стесняйтесь спрашивать.

1 Ответ

1 голос
/ 06 апреля 2020

Пролог не так уж хорош для доказательства теорем. То, как он вызывает предикаты в программе logi c, основано на доказательстве теоремы разрешения (и, следовательно, ограничено предложениями Хорна), но это не означает, что язык позволяет особенно хорошо моделировать проблемы и методы доказательства теорем. В частности, потому что Пролог работает над целями p(X,Y), для которых он пытается найти кортежи (x,y), которые делают эти цели ИСТИННЫМИ, как определено программой logi c, а не работают с предложениями S, которые переписаны согласно некоторому выводу подход (Natural Deduction, Sequent Calculus) для некоторых Logi c (Classical, Intuitionisti c et c.) до получения окончательного значения S'. Обратите особое внимание на то, что нигде в поле зрения нет квантификаторов, потому что никто не пишет S, который может понадобиться. Это не значит, что на Прологе нельзя построить доказательство теорем, но есть какой-то способ go для , который .

В этом случае для 

reflexive(H) :- forall(inside(X,H),equals(H,X,X)).

Вы уже в беде, потому что пролог-доказательство reflexive(hg) означает

На самом деле go и найдите любое X такое, что inside(X,hg) 

inside(X,hg) :- equals(hg,X,e).

На самом деле go и найдите любое X такое, что equals(hg,X,e)

, потому что мне нужно убедиться, inside(X,hg) (и утверждение ∀X: равно (hg , X, E) => внутри (X, HG) позволит мне сделать это)

... и нет в этой программе logi c.

Рефлексивность должна быть пусто истинной 

?- reflexive(hg).
true.

Красиво, но бесполезно.

...