Algebraic Approach to Logical Inference Implementation
1323
monotonous, therefore, it is nonempty and contains the C-n-tuple C
22
= [{h}∗].
The monotonous block T
11
contains a C-n-tuple [{A}{b}]. After reducing these
C-n-tuples to the same relation diagram, their intersection equals the C-n-tuple
C
0
= [{A}{b}{h}∗]. After swapping the attributes in accordance with the relation
diagram of the initial D-system Q, this C-n-tuple is transformed into the C-n-tuple
[{A}{h}{b}∗], which is the substitution for the D-system Q. With Theorems 11
and 12, we can verify that this substitution is correct.
This example shows that, in the same D-system, relations stated in Theorems 19
and 20 can be used more than once, and that in some cases solving a problem in
polynomial time is possible. Obviously, for an arbitrary D-system, the algorithm
for finding non-conflict and monotonous blocks is polynomially dependent on the
dimensions of this system. Furthermore, if a D-system has any monotonous blocks,
its nonemptiness is checked through an algorithm that is polynomially dependent
on the matrix dimensions of this D-system; and if a D-system has any non-conflict
blocks, another D-system of smaller dimensions can be used to check nonemptiness
of the initial D-system.
In algorithms for solving CNF satisfiability problems and enclosure checks for
NTA objects, such as for C-n-tuples in C-systems, matrix properties of NTA objects
are widely used. At present, satisfiability recognition algorithms are developed to
the greatest extent in propositional calculus. It has been proven [10] that, if a CNF
is represented as a D-system that contains only three equally distributed (with the
probability of 1/3) symbols: 1, 0 and Ø, this CNF is solvable, on the average, in
polynomial time, this time being less than or equal to a third degree polynomial to
the number of conjuncts.
5.3 New Features of Logical Inference In NTA
Previous sections were concerned with using NTA structures for implementing
known methods of logical inference. New implementations of logical procedures
based on the suggested algebraic approach are presented below.
Suppose that we have a system of axioms A
1
, . . . , A
n
represented as NTA objects.
Let us describe methods for solving the following two problems through NTA.
1. Problem of correctness check for a consequence. If we have an alleged conse-
quence B, the proof procedure is a correctness check for the following generalized
inclusion:
(A
1
∩
G
. . . ∩
G
A
n
) ⊆
G
B.
(4)
This relation allows correctness checks not only for the inference rules of classical
logic, but also for rules specific to a certain knowledge system.
2. Problem of derivation of arbitrary consequences. In order to solve this problem,
we first calculate an NTA object A = A
1
∩
G
. . . ∩
G
A
n
, after which we choose
the B
i
for which A ⊆
G
B
i
is true. The authors have developed algorithms
that allow to calculate possible corollaries for a known A using the relation (4).
1324
B. Kulik, A. Fridman, A. Zuenko
Below we will consider A as a C-system. If it is not true for a given A, it can
be transformed into a system using algorithms for transforming D-n-tuples or
D-systems into C-systems.
The following premises are commonly used for searching for possible conse-
quences:
1. consequence Bi should preferably use only a small number of variables from the
axioms A
1
, . . . , A
n
;
2. the variables used are often determined based on semantic analysis of the given
reasoning system.
Let us consider formal methods (i.e. without taking semantic restrictions into
account) for solving Problem 2.
Decreasing the number of variables in B
i
is possible through eliminating some
attributes from A. Obviously, after this the transformation relation A ⊆
G
B
i
is
true. Eliminating attributes from a C-system yields a projection whose properties
determine the subsequent operations for consequence derivation. Such projection
can be complete, i.e. can contain all elementary n-tuples for their relation diagram,
or incomplete, if the opposite is true. If a projection is complete, it means that the
consequence is a tautology and thus holds no interest for us; this is why we will
consider incomplete projections only.
Let us form a group of incomplete projections for the A. In this case, all the
variety of ways to form possible consequences B
i
can be expressed by the following
three rules:
1. keep one of the incomplete projections as a B
i
;
2. choose any projection as a B
i
, provided that it includes at least one incomplete
projection;
3. for the NTA object chosen according to the rules above, construct, by adding
elementary n-tuples or C-n-tuples, an incomplete NTA object that covers it.
As an example, let us prove correctness of one of the inference rules in natural
calculus called the dilemma rule:
A → C, B → C, A ∨ B
C
.
It is implied that the formulas below the solidus are derived from the ones
above it. The upper formulas can be considered axioms, and the lower ones can
be considered corollaries to these axioms. By transforming the conjunction of the
formulas above the solidus into a D-system within the [ABC] relation diagram, we
get U p[ABC] =
{0}
Ø
{1}
Ø
{0}
{1}
{1}
{1}
Ø
. The lower part of the rule can be expressed
as a C-n-tuple Dn[C] = [{1}]. In order to prove by NTA methods that the given
Algebraic Approach to Logical Inference Implementation
1325
rule is true, we need to verify the relation U p[ABC] ⊆
G
Dn[C]. In this case, when
the Up is a D-system and the inclusion check does not come down to algorithms
of polynomial difficulty (see Table 2), it is rational to calculate U p[ABC] ∩
G
Dn[C]
and to check if the derived system is empty by using methods from the Section 5.2
and from [9].
Transforming U p[ABC] into a C-system (this operation is often more laborious;
then emptiness check for a D-system) yields U p[ABC] =
{1}
{0}
{1}
∗
{1}
{1}
. In
this case, the inclusion check U p[ABC] ⊆
G
Dn[C] is feasible by an algorithm of
polynomial hardness.
This problem is a good example for implementing search for arbitrary conse-
quences. Let us find incomplete projections in the C-system U p[ABC]. These
projections are [C], [AB], [AC] and [BC]. For the first projection, we get U p[C] =
{1}
{1}
= [{1}], which corresponds to the logical formula of the C. The projections
[AC] and [BC] ultimately yield the same result. The projection [AB] corresponds
to the formula A ∨ B.
The suggested approach allows to use algebraic methods for solving problems
of logical inference. Moreover, it allows to see the essence of logical inference in
classical logic in a new light. We know that if A ⊆ B is true, it means that B
is a necessary condition or a property of A. The relation (4) shows that a logical
consequence is correct not only because it has been obtained using inference rules
whose meaning may not always be clear, but also because it is a necessary condition
for existence of the antecedent.
Above, we have already considered some examples of using algebraic approach
for processing basic structures of data and knowledge. Let us now analyze in detail
some ways of using NTA in certain existing program systems.
6 CONCLUSION
This article suggests using algebraic approach based on general theory of multiplace
relations for solving logical analysis problems, the mathematical base for this ap-
proach being NTA, which is considered a Boolean structure in abstract algebra. The
suggested generalized operations and relations significantly broadens the analytical
scope and application field of NTA objects as compared to those of mathematical
structures currently used for modeling and analyzing relations, e.g. in theory of
binary relations or in relational algebra.
The research data given above shows that NTA allows to unify processing various
data and knowledge structures in artificial intelligence systems. Todays knowledge
representation languages are declarative, which makes it difficult to find efficient
algorithms for information systems that use heterogeneous structures, as well as
for assessing operation speed of an algorithm. Conversely, in n-tuple algebra, many
declarative commands can be represented as relatively simple procedures. As for im-
1326
B. Kulik, A. Fridman, A. Zuenko
plementing logical inference procedures in n-tuple algebra, these can include, beside
the known logical calculus methods, new algebraic methods for checking correctness
of a consequence or for finding corollaries to a given axiom system.
In some cases, NTA provides a faster solution to standard logical analysis tasks
as it considers not only feasibility of certain substitutions, but also the inner struc-
ture of knowledge to be processed.
NTA allows to efficiently parallelize logical
inference algorithms, i.e. to process knowledge in a way similar to that of tabular
data processing in relational DBMS. Matrix properties of NTA objects allow to fur-
ther decrease laboriousness of intellectual procedures. We found new structural and
statistical classes of CNF with polynomially identifiable satisfiability properties in
NTA. Consequently, many algorithms whose complexity evaluation is theoretically
high, e.g. exponential, can in practice be solved in polynomial time, on the aver-
age. This substantiates that using algebraic approach is practical not only for data
management, but also for knowledge processing.
We are planning to conduct future research in the following directions:
• context-oriented database (knowledge base) management systems [3, 20];
• research on additional means of immersing NTA structures into measure spa-
ces [14];
• modelling intelligent dynamic systems [12, 18] within situational approach [4, 5].
Acknowledgment
The authors would like to thank the Russian Foundation for Basic Research (grants
12-07-00302, 11-08-00641, 12-07-00550, 12-07-00689), the Department for Nanotech-
nologies and Information Technologies of RAS (project 2.11 of the current Pro-
gramme of Basic Scientific Researches), and the Chair of RAS (project 4.3 of the
Program #16) for their help in partial funding of this research.
REFERENCES
[1] Chang, C.-L.—Lee, R. C.-T.: Symbolic Logic and Mechanical Theorem Proving,
Academic Press 1973.
[2] Davis, M.—Putnam, H.: A Computing Procedure for Quantification Theory. J.
Assoc. Comput. Mach., Vol. 3, 1960, pp. 201–215.
[3] Ezhkova, I.: Is Universal Expert System Possible? Software & Systems. Vol. 1, 1991,
No. 2, pp. 19–29.
[4] Fridman, A. Ya.: Situative Approach to Modelling and Structure Control of Nature-
Technical Complexes. In: Proceedings 4
th
International Conference “System Identi-
fication and Control Problems” (SICPRO ’05), Moscow, Russia (Institute of Control
Science, Moscow Russia), 2005, pp. 1075–1108 (in Russian).
[5] Fridman, A. Ya.—Fridman, O. V.: Situative Approach to Modelling of Perfor-
mance and Safety in Nature-Technical Complexes. In: Juha Lindfors (Ed.): Applied
Algebraic Approach to Logical Inference Implementation
1327
Information Technology Research – Articles by Cooperative Science Network, Uni-
versity of Lapland, Finland, 2007, pp. 44–59.
[6] Gentzen, G.: Untersuchungen ber das Logische Schließen. Math. Z., Vol. 39, 1934,
pp. 176–210, pp. 405–431.
[7] Hilbert, D.—Ackermann, W.: Grundz¨
uge der Theoretischen Logik. Berlin 1928.
[8] Kolmogorov, A. N.—Fovin, S. V.: Elements of the Theory of Functions and
Functional Analysis, 1: Metric and Normed Spaces. Graylock, Rochester, N. Y. 1957.
[9] Kulik, B. A.: A Logic Programming System Based on Cortege Algebra. Journal of
Computer and Systems Sciences International, Vol. 33, 1995, No. 2, pp. 159–170.
[10] Kulik, B. A.: New Classes of Conjunctive Normal Forms with a Polynomially Re-
cognizable Property of Satisfiability. Automation and Remote Control, Vol. 56, 1995,
No. 2, pp. 245–255.
[11] Kulik, B. A.: Representation of Logical Systems in a Probabilistic Space in Terms of
Cortege Algebra, 1 – Elements of Cortege algebra. Automation and Remote Control,
Vol. 58, 1997, No. 1, pp. 102–114.
[12] Kulik, B. A.: Reliability Analysis of the Systems with Many States on the Basis
of the Algebra of Tuples. Automation and Remote Control, Vol. 64, 2003, No. 7,
pp. 1029–1034.
[13] Kulik, B. A.: A Generalized Approach to Modelling and Analysis of Intelligent Sys-
tems on the Cortege Algebra Basis. In: Proceedings Sixth International Conference
on System Identification and Control Problems (SICPRO ’07), Moscow, Russia 2007,
pp. 679–715 (in Russian).
[14] Kulik, B. A.: N -Tuple Algebra-Based Probabilistic Logic. Systems Analysis and
Operations Research, Vol. 46, 2007, No. 1, pp. 111–120.
[15] Kulik, B. A.—Fridman, A.—Zuenko,A.: Logical Analysis of Intelligence Sys-
tems by Algebraic Method. In: Cybernetics and Systems 2010: Proceedings of Twen-
tieth European Meeting on Cybernetics and Systems Research (EMCSR 2010), 2010,
Vienna, Austria, pp. 198–203 (ISBN 3-85206-178-8).
[16] Mendelson, E.:. Introduction to Mathematical Logic. 4
th
ed., Chapman & Hall 1997.
[17] Russel, S.—Norvig, P.: Artificial Intelligence: A Modern Approach. Second Edi-
tion, Prentice Hall 2003.
[18] Sokolov, B. V.—Fridman, A. Ya.: Integrated Situational Modelling of Industry-
Business Processes for Every Stage of Their Life Cycle. In: Proceedings 4
th
Interna-
tional IEEE Conference “Intelligent Systems” (IS 2008), Varna, Bulgaria 2008, Vol. 1,
pp. 8-35–8-40.
[19] Zuenko, A. A.—Fridman, A. Ya.: Logical Inference in Semantic Analysis of Ad-
hoc Path Queries. In: Proceedings 11
th
National Conference in Artificial Intelligence
with Foreign Collaboration (CAI-2008), Dubna, Russia 2008, Vol. 1, pp. 298–304 (in
Russian).
[20] Zuenko, A. A.—Fridman, A. Ya.: Context Approach in Support Systems for Open
Subject Domains. Artificial Intelligence and Decision Making 3, 2008, pp. 41–51 (in
Russian).
1328
B. Kulik, A. Fridman, A. Zuenko
[21] Zuenko, A. A.—Fridman, A. Ya.: Development of N -Tuple Algebra for Logical
Analysis of Databases with the Use of Two-Place Predicates. Journal of Computer
and Systems Sciences International, Vol. 48, 2009, No. 2, pp. 254–261.
Boris
Kulik graduated from Leningrad Mining Institute and
worked for the USSR Ministry of Geology from 1971 to 1989
in automation of drilling control.
Then he took up research
on logic, mathematics and artificial intelligence and received his
Ph. D. in 1996. Since 1997 he has worked in St. Petersburg Insti-
tute of Problems in Machine Science of the Russian Academy of
Sciences. He received his Doctor of Science (Physics and Mathe-
matics) degree in 2008. At present, he teaches mathematics at
the St. Petersburg University of Culture and Art. He has pub-
lished 70 scientific papers including 4 monographs.
Alexander
Fridman graduated from Leningrad Electro-Tech-
nical Institute in 1975 and worked in Baku (Azerbaijan) for Rus-
sian Shipbuilding Ministry until 1989, when he moved to Apa-
tity (Murmansk region, Russia) and began working for Russian
Academy of Sciences (RAS). He received his Ph. D. in 1976, Doc-
tor of Science degree in 2001 and Professor degree in 2008. At
present he is the head of Laboratory on Information Technologies
for Control of Industry-Natural Complexes in the Institute for
Informatics and Mathematical Modelling of Technological Pro-
cesses of RAS and Professor of Applied Mathematics Chair in
Kola Branch of Petrozavodsk State University. He has 185 scientific publications including
1 monograph, 21 tutorials and 16 certificates for inventions.
Alexander
Zuenko a researcher of the Institute for Informatics
and Mathematical Modelling of Technological Processes (RAS),
graduated from the Petrozavodsk State University in 2005 and
received his Ph. D. in 2009. His scientific activities relate to de-
veloping software for modelling open subject domains, as well as
to knowledge representation and processing. He has 25 scientific
publications.
Dostları ilə paylaş: |