In Abschnitt 2.3 haben wir die Prädikatenlogik als Wissensrepräsentationsformalismus eingestuft. In ihrer vollen Ausdrucksstärke stellt sie uns hinsichtlich der komplexitätsmäßigen Berechenbarkeit vor möglicherweise unlösbare Probleme. Natürlich braucht man die volle Ausdruckstärke nie wirklich ganz, so daß sich die Frage nach einer Teillogik ergibt, die einen Kompromiß zwischen Ausdrucksstärke einerseits und Berechenbarkeit andererseits darstellt. Eine solche Teillogik ist bis heute nicht gefunden. Allerdings gibt es Teillogiken, die bei der Suche nach der Teillogik (wenn es denn eine solche gibt) wichtige Hinweise geben.
Eine von diesen Teillogiken ist die Hornlogik, die (neben anderem -- siehe zB. Abschnitt 3.4) der Programmiersprache PROLOG zugrundeliegt und dadurch indirekt eine große Bedeutung in der Wissensrepräsentation erlangt hat; wir dürfen sie hier als bekannt voraussetzen [Llo84]. Es ist unbestritten, daß die Ausdrucksstärke der Hornlogik nicht ausreicht, da sie zB. eine natürliche Verwendung von Disjunktion, Negation und Quantoren nicht oder nur bedingt ermöglicht. Andererseits ist bereits sie selbst berechnungsmäßig derzeit in aller Allgemeinheit unlösbar, so daß die Kompromißlinie, die eine Teillogik eingrenzt, offenbar anders gezogen werden muß.