JPH0823822B2 - Hypothesis set contradiction check method - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to hypothetical reasoning for expressing incomplete knowledge as a hypothesis and making it available for problem solving in an information processing system that uses knowledge to solve a problem. It is a thing. In hypothesis reasoning, believing in one or more hypotheses may conflict with other knowledge in the knowledge base, since the hypotheses themselves are incomplete knowledge. The present invention is convinced that one or more hypotheses are
The present invention relates to a hypothesis set contradiction checking method for checking whether the knowledge base conflicts with other knowledge.

[0002]

2. Description of the Related Art FIG. 5 shows a block diagram of a conventional hypothesis set contradiction checking method. As shown in FIG. 5, the conventional hypothesis set contradiction checking method uses a hypothesis set input unit 50 and a bit string creation unit 5.
1, a bit string set management unit 52, a bit string extraction unit 53, a subset relationship inspection unit 54, a repetition end determination unit 55, a no contradiction notification unit 56, and a contradiction notification unit 57.

First, one or more hypotheses for checking whether or not they are inconsistent with the knowledge in the knowledge base are hypothesis set input unit 50.
When it is input to, the input hypothesis set is passed to the bit string creation unit 51. The operation of the bit string creating unit 51 will be described below.

Each hypothesis is associated with one bit in order from the right side of the bit string in the order in which the hypothesis was registered in the knowledge base. The bit string creating unit 51 sets the bit corresponding to the hypothesis, which is each element of the input hypothesis set, to 1,
A bit string having 0 other than that is created. FIG. 6 shows an example of a hypothesis set which is an input of the bit string creating unit and a bit string created corresponding to it. (1) of FIG. 6 indicates that the input hypothesis set is composed of hypothesis 3, hypothesis 6 and hypothesis 10, and (2) shows that the bit string created corresponding to it is the third and sixth from the right. The 1st and 10th bits are 1s, and the other bits are all 0s. Bits to the left of the tenth from the right are interpreted as all zeros.

The bit string set management unit 52 manages, in the form of a bit string, one or more sets of hypotheses that simultaneously cause contradictions in the knowledge base. Generally, there are zero or more of these bit strings. The bit string extraction unit 53 extracts the bit strings one by one from the bit string set management unit 52,
The result is passed to the subset relation inspection unit 54.

In the following description, the bit string created by the bit string creating unit 51 will be referred to as a bit string a, and the bit string extracted by the bit string extracting unit 53 will be referred to as a bit string b. The subset relation checking unit 54 determines that among the bits of the bit string a, the bit corresponding to the 1 bit of the bit string b is
Check if all are 1. Hereinafter, if all the bits of the bit string a corresponding to the 1 bits of the bit string b are 1, the bit string b is called a subset of the bit string a.

FIG. 7 shows an example in which the bit string b is a subset of the bit string a. In FIG. 7, the second and fourth bits from the right of the bit string b are 1, and the others are 0. On the other hand, in the bit string a, the second, fourth, and sixth from the right side are also 1 and the others are 0. The bits corresponding to the bits of 1 in the bit string b, that is, the second and fourth bits are all 1 in the bit string a, so the bit string b is a subset of the bit string a.

The fact that the bit string b is a subset of the bit string a has the following meaning. In the bit string a, all the bits corresponding to the 1 bits of the bit string b are 1, which means that the hypothesis set represented by the bit string a includes all the elements of the hypothesis set represented by the bit string b. . However, the bit string b is a bit string representing a set of contradictory hypotheses and is taken out from the bit string set management unit 52, and the hypothesis set including all of its elements, that is, the bit string a is also contradictory.

The bit string b becomes a subset of the bit string a only when the logical product of the negation of a and b is calculated for each bit and all the bits are 0, and only then. , Perform bit string subset check by performing this calculation.

In the subset relation checking unit 54, when all the calculation results are 0, that is, when the bit string b is a subset of the bit string a, the contradiction notifying unit 57 notifies the contradiction and processes it. To finish. When the subset relation checking unit 54 does not all the above-mentioned calculation results, the repetition end judging unit 55 judges whether or not the checking is completed for all the bit strings in the bit string set managing unit 52. When the inspection is completed for all the bit strings, the input hypothesis set does not correspond to any contradictory hypothesis set managed by the bit string set management unit 52. Therefore, the no contradiction notifying unit 56 notifies that there is no contradiction and ends the processing. Repeat end determination unit 5
If it is determined in step 5 that all inspections have not been completed, the bit string extraction unit 53 is notified, and of the bit strings managed by the bit string set management unit 52, the bit string that has not been inspected is processed as the bit string b. To continue.

[0011]

In the conventional method, the hypothesis set is replaced with the bit string to perform the inspection so that the subset relation inspection of the bit strings can be performed at high speed on the electronic computer. However, the processing is not yet sufficiently fast, and it is common to spend more than half of the time of the inference processing using the hypothesis for the contradiction checking processing of the hypothesis set. Was causing a decrease in processing speed.

An object of the present invention is to provide a hypothesis set contradiction checking method that solves such problems.

[0013]

A hypothesis set contradiction checking method of the first invention is a hypothesis set contradiction checking method for checking whether a set of one or more hypothesis knowledge is inconsistent with other knowledge in a knowledge base. In, it was found that there is a conflict in the knowledge base with the hypothesis set input unit that inputs the hypothesis set to be tested and the bit string creation unit that creates the bit string corresponding to the hypothesis set input by the hypothesis set input unit. The bit string set management unit that manages the set of hypotheses in the form of a corresponding bit string, a bit string extraction unit that extracts one bit string from the bit string set management unit, and the bit string created by the bit string creation unit is called a bit string a, When the bit string extracted by the bit string extracting unit is called a bit string b, the bit string magnitude relationship for comparing the magnitude relationship as a binary number between the bit string a and the bit string b It operates when the comparison unit and the bit string magnitude relationship comparison unit obtain a comparison result that the bit string a is greater than or equal to the bit string b, and among the bits of the bit string a, the bit string b. The bit string b is larger than the bit string a in the subset relation checking unit that checks whether all the bits corresponding to 1 are 1 and the bit string magnitude relationship comparing unit. In the case, the subset relation checking unit determines, among the bits of the bit string a,
It operates when all the bits corresponding to the 1's of the bit string b are not 1, and the bit string extraction unit determines whether or not all the bit strings in the bit string set management unit have been extracted. A repetition end determination unit, and a consistency notification unit that operates when the repetition end determination unit determines that the repetition has ended and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base. , The subset relation checking unit operates when all of the bits of the bit string a corresponding to the 1's of the bit string b are 1, and the input hypothesis set is It is characterized by comprising a contradiction notifying unit for notifying that the knowledge base is inconsistent with other knowledge.

The hypothesis set contradiction checking method of the second invention is 1
In a hypothesis set contradiction checking method for checking whether a set of one or more hypothesis knowledge is inconsistent with other knowledge in a knowledge base, a hypothesis set input unit for inputting a hypothesis set to be checked, and the hypothesis set input unit When a bit string creation unit that creates a bit string corresponding to the hypothesis set input in step (4) and a hypothesis set known to be inconsistent in the knowledge base are taken as binary numbers in the form of the corresponding bit string, A bit string order management unit that manages the bits so that they are arranged in ascending order,
From the bit string order management unit, a minimum bit string extraction unit that extracts one bit string in the ascending order when the bit string is regarded as a binary number, and the bit string created by the bit string creation unit is called a bit string a, and the minimum bit string extraction unit When the extracted bit string is called a bit string b, the bit string a
And the bit string b as a binary number, the bit string a is greater than or equal to the bit string b in the bit string size relationship comparing unit and the bit string size relationship comparing unit. The bit string a operates among the bits of the bit string a.
All the bits corresponding to the bits that are 1
And the subset relation checking unit checks that all bits of the bits of the bit string a corresponding to the 1 bits of the bit string b are 1 in the subset relationship checking unit. If it is not, the repetition end determination unit that determines whether or not all the bit strings in the bit string order management unit have been extracted by the minimum bit string extraction unit, and the bit string magnitude relationship comparison unit that determines whether the bit string b It is operated when the bit string a is larger than the bit string a and when the repetition end judgment unit judges that the repetition has ended, and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base. Corresponding to the bit that is 1 in the bit string b among the bits in the bit string a in the no-contradiction notifying unit and the subset relation checking unit That bit, all operate in a case in which it is in the 1, characterized in that it comprises a contradiction notification unit hypothesis set input to notify that conflicts with other knowledge present in the knowledge base.

The hypothesis set contradiction checking method of the third invention is 1
In a hypothesis set contradiction checking method for checking whether a set of one or more hypothesis knowledge is inconsistent with other knowledge in a knowledge base, a hypothesis set input unit for inputting a hypothesis set to be checked, and the hypothesis set input unit The bit string creation unit that creates the bit string corresponding to the hypothesis set input in step 1 and the hypothesis set that is known to be inconsistent in the knowledge base are in the form of the corresponding bit string, and the most significant digit position of the bit string is the same. A bit string structure management unit for structuring and managing objects in units, a bit string structure extraction unit for extracting one bit string structure from the bit string structure management unit, and a bit string created by the bit string creation unit for extraction by the bit string structure extraction unit And a most significant bit inspecting unit that inspects whether or not the bit corresponding to the most significant digit of the bit string structure is 1, and the most significant bit inspecting unit. It operates when the bit corresponding to the higher digit is 1, and extracts a partial bit string from the bit string structure extracted by the bit string structure extracting unit, a partial bit string extracting unit and a bit string created by the bit string creating unit. When the bit string a is called and the partial bit string taken out by the partial bit string extracting unit is called a bit string b, all the bits corresponding to the bits of the bit string b which are 1 are 1 And the subset relation checking unit that checks whether or not all the bits corresponding to the 1 bit of the bit string b among the bits of the bit string a are 1. If not, all the partial bits in the bit string structure extracted by the bit string structure extracting unit by the partial bit string extracting unit , A partial bit string repetition end determining unit that determines whether or not all the partial bit strings have been extracted by the bit string repetition end determining unit, and the most significant bit checking unit in the bit string creating unit. It operates when the bit corresponding to the most significant digit of the bit string structure extracted by the bit string structure extracting unit of the created bit string is 0,
When the bit string structure extraction unit determines that the bit string structure is completely extracted from the bit string structure management unit, and the bit string structure repetition end determination unit determines that the repetition is completed. Of the bit string b of the bits of the bit string a in the non-contradiction notifying unit for notifying that the input hypothesis set does not conflict with other knowledge in the knowledge base. A contradiction notifying unit that operates when all the bits corresponding to the bits set to 1 are set to 1 and notifies that the input hypothesis set conflicts with other knowledge in the knowledge base It is characterized by

[0016]

Next, an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of the hypothesis set contradiction checking method of the first invention. This hypothesis set contradiction checking method includes a hypothesis set input unit 10 for inputting a hypothesis set to be checked, and a bit string creation unit 1 for creating a bit string corresponding to the hypothesis set input by the hypothesis set input unit 10.
1, a bit string set management unit 12 that manages a hypothesis set that is known to be inconsistent in the knowledge base in the form of a corresponding bit string, and a bit string extraction unit 13 that extracts one bit string from the bit string set management unit 12. , Bit string creation unit 1
When the bit string created in 1 is referred to as a bit string a and the bit string extracted by the bit string extraction unit 13 is referred to as a bit string b, a bit string magnitude relationship comparison unit 14 that compares the magnitude relationship of the bit string a and the bit string b as a binary number, and a bit string In the magnitude relationship comparison unit 14, the bit string a is better than the bit string b.
It operates when a comparison result that is greater than or equal to is obtained, and among the bits of the bit string a, the bit string b
All the bits corresponding to the bits that are 1
Subset relation inspection unit 1 for inspecting whether or not
5, when the bit string b is larger than the bit string a in the bit string magnitude relationship comparing unit 14, and in the subset relationship checking unit 15 among the bits of the bit string a, the bit string b
All the bits corresponding to the bit which is 1
If not, the bit string extraction unit 13 operates.
A repetition end determination unit 16 that determines whether or not all bit strings in the bit string set management unit 12 have been extracted.
A non-contradiction notifying unit 17 that operates when the repetition end judging unit 16 judges that the repetition has ended and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base, and a subset relation check In the unit 15, the operation is performed when all the bits of the bit string a corresponding to the 1-bits of the bit string b are 1, and the input hypothesis set is stored in the knowledge base. A contradiction notifying unit 18 for notifying that the contradiction with knowledge is provided.

First, when a set of hypotheses is input to the hypothesis set input unit 10, the input hypothesis set is passed to the bit string creation unit 11, and the bit string creation unit 11 uses the same method as described in the conventional method. Create a bit string with.

The bit string set management unit 12 manages, in the form of a bit string, zero or more combinations of one or more hypotheses that cause contradiction if they believe at the same time in the knowledge base. The bit string extraction unit 13 extracts the bit strings from the bit string set management unit 12 one by one, and transfers the bit strings to the bit string size relationship comparison unit 14.

Bit string size relationship comparing unit 14, bit string a
And the bit string b are both binary numbers, and the magnitude relationship is compared. If the bit string a is larger than or equal to the bit string a, the subset relationship checking unit 15 notifies the bit string a and the bit string b.
Is passed. Similar to the conventional method, the subset relation inspection unit 15 inspects whether or not all the bits of the bit string a corresponding to the ones of the bit string b are ones.

When the subset relation checking unit 15 finds that all the corresponding bits of the bit string a are 1, that is, when it is found that the bit string a is inconsistent, the contradiction notifying unit 1
In step 8, the contradiction is notified, and the process ends. When all the corresponding bits of the bit string a are not 1 in the subset relation checking unit 15 and when the bit string b is larger than the bit string a in the bit string magnitude relationship comparing unit 14, the repetition end determination unit is In operation, it is determined whether the bit string extraction unit 13 has extracted all the bit strings from the bit string set management unit 12.

If all the bit strings have been extracted, the input hypothesis set does not correspond to any contradictory hypothesis set managed in the bit string form by the bit string set management unit 12. Then, the no contradiction notifying unit 17 notifies that there is no contradiction and ends the processing. When the repetition end determination unit 16 determines that all the extractions have not been completed, the repetition completion determination unit 16 notifies the bit string extraction unit 13 of the bit strings managed by the bit string set management unit 12 and selects the bit strings that have not yet been extracted. The process is continued as b.

As described above, the hypothesis set contradiction checking method according to the first aspect of the present invention is different from the conventional method in that the magnitude relation of bit strings is compared before the subset relation checking. . If the bit string b is larger than the bit string a when the bit string is regarded as a binary number,
Bit string b cannot be a subset of bit string a. This is clear considering the opposite.

That is, if all the bits in the bit string a corresponding to the 1 bits in the bit string b are 1 and all other bits in the bit string a are 0, the bit strings a and b are It is the same bit string, and naturally,
Even if it is considered as a binary number, it will be the same number. However, if there is at least one bit among the other bits of the bit string a that is 1, when it is regarded as a binary number, the bit string a should be larger by that amount.

In the hypothesis set contradiction checking method according to the first aspect of the present invention, based on the above discussion, the bit string magnitude relationship comparing unit 14
In the case where the bit string a is greater than or equal to the bit string b, the subset relation checking unit 15 checks. In the bit string size relation comparing unit 14, the bit string a
This is because, when is smaller than the bit string b, it is understood that there is no subset relation without performing the processing of the subset relation inspection unit 15. Therefore, the inspection result is the same in both methods.

FIG. 2 is a block diagram showing an embodiment of the hypothesis set contradiction checking method of the second invention. The hypothesis set contradiction checking method of the present invention includes a hypothesis set input unit 20 for inputting a hypothesis set to be checked, a bit string creation unit 21 for creating a bit string corresponding to the hypothesis set input by the hypothesis set input unit 20, A bit string order management unit 22 and a bit string order management unit 22 that manage a hypothesis set known to be inconsistent in the knowledge base in the form of a corresponding bit string so that the bit string is arranged in ascending order when the bit string is regarded as a binary number. From, in ascending order when the bit string is regarded as a binary number,
When the minimum bit string extraction unit 23 that extracts one bit string and the bit string created by the bit string creation unit 21 are called a bit string a, and the bit string extracted by the minimum bit string extraction unit 23 is called a bit string b, two of the bit string a and the bit string b are The bit string magnitude relationship comparing unit 24 and the bit string magnitude relationship comparing unit 24 that compare the magnitude relationship as a decimal number operate when a comparison result that the bit string a is greater than or equal to the bit string b is obtained. Among the bits of a, the subset relation checking unit 25 and the subset relation checking unit 25 for checking whether all the bits corresponding to the 1's in the bit string b are 1's,
It operates when all the bits of the bit string a corresponding to the ones in the bit string b are not all 1, and the minimum bit string extraction unit 23 operates all bit strings in the bit string order management unit 22. Of the bit string b is larger than the bit string a, and the repetition end judging unit 26 judges that the repetition has ended. In the case of the bit string b of the bits of the bit string a in the no-contradiction notifying unit 27 that notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base, It operates when all the bits corresponding to the bits that are 1 are 1, and the input hypothesis set is another knowledge in the knowledge base. It is constituted by a contradiction notification unit 28 to notify that conflict.

First, when a set of hypotheses is input to the hypothesis set input unit 20, the input hypothesis set is passed to the bit string creation unit 21, and the bit string creation unit 21 uses the same method as described in the conventional method. Create a bit string with.

The bit string order management unit 22 manages, in the form of a bit string, zero or more combinations of one or more hypotheses that cause contradiction if they believe at the same time in the knowledge base. The difference from the first invention is that the bit string order management unit 22 manages the bit strings so that they are arranged in ascending order when the bit string is regarded as a binary number.

The minimum bit string extraction unit 23 extracts, from the bit string order management unit 22, the smallest bit string that has not yet been extracted when it is regarded as a binary number,
It is passed to the bit string size relationship comparing unit 24.

The bit string size relationship comparing unit 24 compares the bit string a and the bit string b as binary numbers and compares the size relationships. If the bit string b is larger than the bit string a, the no-contradiction notifying unit 27 notifies that there is no contradiction and ends the process. This process is based on the following discussion.

The bit string order management unit 22 sets the bit string to 2
When they are regarded as a decimal number, they are managed in ascending order, and the minimum bit string extraction unit 23 extracts the bit strings from these in ascending order. Therefore, the bit string magnitude relationship comparison unit 2
If the bit string b is larger than the bit string a in 4, even if the process is repeated thereafter, the minimum bit string extraction unit 2
The bit string passed from 3 is always larger than the bit string b, that is, larger than the bit string a. On the other hand, a bit string larger than the bit string a cannot be a subset of the bit string a as described in the description of the embodiment of the first invention. Therefore, it is possible to conclude that there is no contradiction in the hypothesis set represented by the bit string a, without performing processing on the bit string in the bit string order management unit 22 that has not been compared in magnitude.

In the bit string magnitude relationship comparing unit 24, when the bit string a is larger or equal, the bit string a and the bit string b are passed to the subset relationship checking unit 25.
Similar to the conventional method, the subset relation checking unit 25 checks whether or not all the bits of the bit string a corresponding to the ones of the bit string b are ones.

When the subset relation checking unit 25 finds that all the corresponding bits of the bit string a are 1, that is, when it is found that the bit string a is inconsistent, the contradiction notifying unit 2
In step 8, the contradiction is notified, and the process ends. In the subset relation inspection unit 25, when all the corresponding bits of the bit string a are not 1, the repetition end determination unit operates and the minimum bit string extraction unit 23 sets the bit string order management unit 22.
From, it is determined whether or not all the bit strings have been taken out.

If all the bit strings have been extracted, it means that the input hypothesis set does not correspond to any contradictory hypothesis set managed in the bit string order management unit 22 in the form of a bit string. Then, the no contradiction notifying unit 27 notifies that there is no contradiction and ends the processing. If the repetition end determination unit 26 determines that all extractions are not completed, the minimum bit string extraction unit 23 is notified,
Among the bit strings managed by the bit string order management unit 22, the smallest bit string that has not yet been extracted is set as the bit string b and the processing is continued.

In the second invention, as described above, the bit string order management unit 22 sorts the bit strings in the order of the size when the bit string is regarded as a binary number, and the minimum bit string extraction unit 23 extracts the bit strings. When the bit string b is larger than the bit string a created by the bit string creating unit 21, the subsequent processing can be omitted. Therefore, also in the second invention, the result of the hypothesis set contradiction check is the same as that of the conventional method.

FIG. 3 is a block diagram showing an embodiment of the hypothesis set contradiction checking method of the third invention.

This hypothesis set contradiction checking method includes a hypothesis set input unit 30 for inputting a hypothesis set to be checked, and a bit string creation unit 31 for creating a bit string corresponding to the hypothesis set input by the hypothesis set input unit 30. , A bit string structure management unit 32 that structures and manages a set of hypotheses known to be inconsistent in the knowledge base in the form of a corresponding bit string in units of the same highest digit position of the bit string, and a bit string In the bit string structure extraction unit 33 that extracts one bit string structure from the structure management unit 32 and the bit string created by the bit string creation unit 31, the bit corresponding to the most significant digit of the bit string structure extracted by the bit string structure extraction unit 33 is 1 The most significant bit inspecting unit 34 for inspecting whether or not there is one, and the bit corresponding to the most significant digit in the most significant bit inspecting unit 34 is 1
The bit string structure extracting unit 33 extracts one partial bit string from the bit string structure extracted by the bit string structure extracting unit 33, and the bit string created by the bit string creating unit 31 is called a bit string a. When the partial bit string extracted by the extraction unit 35 is called a bit string b, a subset relation for checking whether or not all the bits of the bit string a corresponding to the 1's of the bit string b are 1's In the inspection unit 36 and the subset relation inspection unit 36, among the bits of the bit string a,
It operates when all the bits corresponding to the bits that are 1 in the bit string b are not all 1, and all the partial bit strings in the bit string structure extracted by the bit string structure extracting unit 33 by the partial bit string extracting unit 35 are Partial bit string repetition end determination unit 3 for determining whether or not it has been taken out
7, when the bit string repetition end determination unit 37 determines that all the partial bit strings have been extracted, and the most significant bit inspection unit 34 extracts the bit string created by the bit string creation unit 31 by the bit string structure extraction unit 33. It operates when the bit corresponding to the most significant digit of the bit string structure is 0, and the bit string structure extraction unit 33 determines whether or not all the bit string structure has been extracted from the bit string structure management unit 32.
And a consistency notification unit 39 that operates when the repetition is judged by the bit string structure repetition end judgment unit 38 and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base, and In the group relation inspection unit 36,
It operates when all the bits of the bit string a corresponding to the ones of the bit string b are 1, and the input hypothesis set conflicts with other knowledge in the knowledge base. And a contradiction notifying unit 310 for notifying the fact.

First, when a set of hypotheses is input to the hypothesis set input unit 30, the input hypothesis set is passed to the bit string creation unit 31, and the bit string creation unit 31 uses the same method as described in the conventional method. Create a bit string with.

The bit string structure management unit 32 manages, in the form of a bit string, zero or more combinations of one or more hypotheses that simultaneously cause contradictions in the knowledge base. The difference from the first invention and the second invention is that the bit string structure management unit 3
2 is that bit strings are managed in the structure described below with reference to FIG.

In FIG. 4, (1) shows an example of a set of bit strings managed by the bit string set management unit in the conventional method, and (3) shows the same set of bit strings as the bit string structure in the third invention. The structure when managed by the management unit 32 is shown. (2) is a tentative structure for explaining that (1) and (3) represent the same bit string set. The leftmost bit string “1000” (1000)
1 ”indicates a set of hypotheses consisting of hypothesis 1 and hypothesis 5, and the second bit string“ 1010 ”from the left indicates hypothesis 2 and hypothesis 4.
Shows a set of hypotheses consisting of.

In (2), these bit strings are classified according to the number of digits of bits, and each digit has a structure enclosed in parentheses. That is, “(10001)” is a 5-digit bit string and “(1010 1100)” is a 4-digit bit string.

In (3), the leftmost bit, which is common to the bit string in parentheses for each digit classified in (2), is expressed as a common one. For example, “(10 10 1100)” in (2) extracts the leftmost fourth digit bit and “(1000 01 01)” along with the remaining partial bit string “(010 110)”.
0100) ”. Here, "1000" is 4
It indicates that it is a bit string of digits, and "010", "10"
“0” is the leftmost “1” removed from “1010” and “1100”, respectively. Further, as described in the conventional method, "010" can be described as "10" because all the bits on the left side of the described leftmost bit are interpreted as 0. Therefore, in (3) of FIG. 4, a structure such as “(1000 10 100)” is used to represent “(10 10 1100)”.

The bit string structure extraction unit 33 extracts from the bit string structure management unit 32 one of the structures which has not been extracted yet in the structure unit enclosed in parentheses for each digit number of the bit string, and outputs it to the most significant bit inspection unit 34. hand over. The most significant bit checking unit 34 includes a bit string created by the bit string creating unit 31,
Of the bit string structure extracted by the bit string structure extracting unit 33, the subset relation with the bit string on the leftmost side, that is, the most significant digit is checked. That is, in the bit string created by the bit string creating unit 31, it is checked whether the bit corresponding to the most significant digit of the bit string structure extracted by the bit string structure extracting unit 33 is 1. When the corresponding bit is 1, the partial bit string extraction unit 35 extracts one of the second and subsequent partial bit strings from the left side of the bit string structure and passes it to the subset relation inspection unit 36. If the corresponding bit is 0 in the most significant bit checking unit 34, the operation moves to the bit string structure repetition end determining unit 38.

As in the conventional method, the subset relation checking unit 36 checks whether or not all the bits of the bit string a corresponding to the ones of the bit string b are ones. .

When the subset relation checking unit 36 finds that all the corresponding bits of the bit string a are 1, that is, when it is found that the bit string a is inconsistent, the contradiction notifying unit 3
In step 10, the contradiction is notified, and the process ends. In the subset relation inspection unit 36, when all the corresponding bits of the bit string a are not 1, the bit string repetition end determination unit operates and the partial bit string extraction unit 35 transfers the bit string structure passed from the most significant bit inspection unit 34. It is determined whether or not all of the second and subsequent partial bit strings from the left are inspected. If not all are inspected, the process is repeated for the partial bit sequence not inspected by the partial bit sequence extraction unit 35. If all the bits have been inspected, the bit string structure repetition end determination unit 38 causes the bit string structure management unit 32 to
From, it is determined whether or not all bit string structures have been extracted.

In the bit string structure repetition end judging section 38,
If all the bit string structures have been extracted, it means that the input hypothesis set does not correspond to any contradictory hypothesis set managed in the bit string structure management unit 32 in the form of a bit string. The notification unit 39 notifies that there is no contradiction and ends the processing. When the bit string structure repetition end determination unit 38 determines that all the extractions have not been completed, the bit string structure extraction unit 33 is notified, and the bit string structure management unit 32 manages the bit string structures that have not yet been extracted. Continue processing with no bit string structure.

As described above, in the third invention, the bit string structure management unit 33 structures the bit string by the number of digits of the bit string, so that the bit string in the structure is a subset of the bit string a in each structural unit. If there is no possibility, it becomes possible to omit the subset relation check for the partial bit string in each structure. Therefore, also in the third invention, the result of the hypothesis set contradiction test is the same as that of the conventional method.

[0048]

The hypothesis set contradiction checking method according to the first aspect of the present invention is different from the conventional method in that the magnitude relation of bit strings is compared before the subset relation checking. The number of inspections by the subset relation inspection unit 15 is reduced as much as when the bit string a is smaller than the bit string b in the bit string magnitude relationship comparison unit 14. Generally, in a computer, the comparison of bit string magnitude relations can be performed faster than the subset relation check. Therefore, the hypothesis set contradiction checking method according to the first invention is faster than the conventional method. The effect is that inspection can be performed.

In the second invention, the bit string order management unit 22
When the bit string b extracted by the minimum bit string extraction unit 23 is larger than the bit string a created by the bit string creation unit 21 by sorting the bit string in the order of the size when the bit string is regarded as a binary number, It is possible to omit the processing. Therefore, the hypothesis set contradiction checking method according to the second invention has an effect that the contradiction check of the hypothesis set can be performed faster than the first invention.

On the other hand, unlike the conventional method and the method according to the first aspect of the invention, the bit string order management unit 22 needs to sort and manage the bit strings, and the processing for registering the bit string in the bit string order management unit 22 is not performed. , Slightly slower. However, in general, the processing of the hypothesis set contradiction check is performed a large number of times compared with the processing of registering the contradictory hypothesis set in the bit string order management unit. It is fully compensated by improvement.

The third aspect of the present invention is a bit string structure management unit 33.
By structuring the bit string having the same number of digits as a unit, the bit string in the structure is a bit string a in each structural unit.
If there is no possibility, it is possible to omit the subset relation check with the partial bit string in the structure. Therefore, the hypothesis set contradiction checking method according to the third aspect of the present invention reduces the number of times the subset relationship between bit strings is checked, as compared with the conventional method, and enables high-speed processing.

On the other hand, the bit string structure management unit 32 needs to structure and manage the bit string, and the process of registering the bit string in the bit string structure management unit 32 is slightly delayed as in the second invention. However, for the same reason as described in the effect of the second invention, the speed decrease at the time of registration can be sufficiently compensated by the speed increase at the time of inspection.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a first invention.

FIG. 2 is a block diagram showing the configuration of an embodiment of the second invention.

FIG. 3 is a block diagram showing the configuration of an embodiment of the third invention.

4 is a diagram showing an example of a bit string structure managed by a bit string structure management unit 32 in FIG.

FIG. 5 is a block diagram showing an example of a conventional method.

FIG. 6 is a diagram showing an example of a bit string created by a bit string creating unit shown in FIGS. 1, 2, 3 and 5.

FIG. 7 is a diagram showing an example of the operation of the subset relation inspection unit of FIGS. 1, 2, 3 and 5.

[Explanation of symbols]

 10, 20, 30, 50 Hypothesis set input unit 11, 21, 31, 51 Bit string creation unit 12, 52 Bit string set management unit 13, 53 Bit string extraction unit 14, 24 Bit string size relationship comparison unit 15, 25, 36, 54 parts Set relation checking unit 16, 26, 55 Repeat end determination unit 17, 27, 39, 56 No contradiction notification unit 18, 28, 57, 310 Contradiction notification unit 22 bit sequence order management unit 23 Minimum bit string extraction unit 32 bit string structure management unit 33 bit string Structure extraction unit 34 Most significant bit inspection unit 35 Partial bit string extraction unit 37 Bit string repetition end determination unit 38 Bit string structure repetition end determination unit

Claims (3)

[Claims] 1. A hypothesis set inconsistency checking method for checking whether one or more sets of hypothesis knowledge are inconsistent with other knowledge in a knowledge base, and a hypothesis set input section for inputting to a hypothesis set to be checked. , A bit string creation unit that creates a bit string corresponding to the hypothesis set input by the hypothesis set input unit, and a bit string set that manages a hypothesis set known to conflict in the knowledge base in the form of the corresponding bit string A management unit, a bit string extraction unit that extracts one bit string from the bit string set management unit, a bit string created by the bit string creation unit is called a bit string a, and a bit string extracted by the bit string extraction unit is called a bit string b. a bit string magnitude relationship comparing unit that compares the magnitude relationship between a and the bit string b as a binary number; and the bit string magnitude relationship comparing unit, The operation is performed when the comparison result that the column a is larger than or equal to the bit sequence b is obtained, and the bit corresponding to the bit that is 1 of the bit sequence b among the bits of the bit sequence a is A subset relation checking unit for checking whether all are 1, and a case where the bit string b is larger than the bit string a in the bit string magnitude relationship comparing unit, and a case where the bit string b is larger than the bit string a It operates when all of the bits of a corresponding to the 1-bits of the bit string b are not 1, and the bit string extraction unit extracts all the bit strings in the bit string set management unit. It is operated when the repetition end judgment unit that judges whether or not the repetition is finished, and when the repetition end judgment unit judges that the repetition is completed, In the consistent relation notifying unit for notifying that the applied hypothesis set is consistent with other knowledge in the knowledge base, and in the subset relation checking unit, the bit string b becomes 1 of the bit string b. And a contradiction notifying unit for notifying that the inputted hypothesis set is inconsistent with other knowledge in the knowledge base, which operates when all the bits corresponding to existing bits are 1. Hypothesis set conflict checking method. 2. A hypothesis set input unit for inputting a hypothesis set to be checked in a hypothesis set conflict checking method for checking whether or not one or more sets of hypothesis knowledge conflict with other knowledge in a knowledge base. , A bit string creation unit that creates a bit string corresponding to the hypothesis set input by the hypothesis set input unit, and a hypothesis set known to be inconsistent in the knowledge base, a bit string in the form of the corresponding bit string, A bit string order management unit that manages the bit string order so that the bit strings are arranged in ascending order when viewed as a binary number; and a minimum bit string extraction unit that extracts one bit string from the bit string order management unit in a small order when viewed as a binary number, When the bit string created by the bit string creating unit is called a bit string a and the bit string extracted by the minimum bit string extracting unit is called a bit string b, the bit string a And a bit string magnitude relationship comparing unit that compares the magnitude relationship of the bit string b as a binary number, and a comparison result that the bit string a is greater than or equal to the bit string b in the bit string magnitude relationship comparing unit. And a subset relation checking unit that checks whether or not all the bits of the bit string a corresponding to the 1's of the bit string b are 1's, and the subset relationship. The check unit operates when all the bits of the bit string a corresponding to the 1-bits of the bit string b are not 1, and the minimum bit string extraction unit manages the bit string order. The repetition end determination unit that determines whether or not all the bit strings in the set have been extracted, and the bit string size relationship comparison unit that sets the bit string b It is operated when the bit string a is larger than the bit string a and when the repetition end judgment unit judges that the repetition has ended, and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base. The non-contradiction notifying unit and the subset relation checking unit operate when all the bits of the bit string a corresponding to the 1's of the bit string b are 1, and input A method for checking a contradiction of a hypothesis set, comprising: a contradiction notifying unit that notifies that the set of hypotheses set is inconsistent with other knowledge in the knowledge base. 3. A hypothesis set input section for inputting a hypothesis set to be checked in a hypothesis set conflict checking method for checking whether or not one or more sets of hypothesis knowledge conflict with other knowledge in a knowledge base. , A bit string creation unit that creates a bit string corresponding to the hypothesis set input by the hypothesis set input unit, and a hypothesis set known to be inconsistent in the knowledge base, in the form of the corresponding bit string, A bit string structure management unit for structuring and managing units having the same high-order digit position as a unit; a bit string structure extraction unit for extracting one bit string structure from the bit string structure management unit; and a bit string created by the bit string creation unit, wherein: A most significant bit inspection unit that inspects whether the bit corresponding to the most significant digit of the bit string structure extracted by the bit string structure extraction unit is 1; It operates when the bit corresponding to the most significant digit in the order bit check unit is 1, and extracts a partial bit string from the bit string structure extracted by the bit string structure extracting unit, a partial bit string extracting unit, and the bit string creating unit. When the bit string created by the section is called a bit string a, and the partial bit string extracted by the partial bit string extracting unit is called a bit string b, the bit corresponding to the bit of the bit string b which is 1 among the bits of the bit string a. , A subset relation checking unit for checking whether all are 1, and among the bits of the bit sequence a, a bit corresponding to a bit of 1 of the bit sequence b in the subset relation checking unit. , The bit string structure extracted by the partial bit string extraction unit and operated by the partial bit string extraction unit Partial bit string repetition end determination unit for determining whether or not all partial bit strings have been extracted, when it is determined that all partial bit strings have been extracted by the bit string repetition end determination unit, and the most significant bit inspection unit, Of the bit string created by the bit string creating unit,
The bit string structure extraction unit operates when the bit corresponding to the most significant digit of the bit string structure is 0, and the bit string structure extraction unit determines whether or not all the bit string structures have been extracted from the bit string structure management unit. And a bit string structure repetition end determination unit that operates, and operates when the repetition is determined by the bit string structure repetition end determination unit, and notifies that the input hypothesis set does not conflict with other knowledge in the knowledge base The non-contradiction notifying unit and the subset relation checking unit operate when all the bits of the bit string a corresponding to the 1's of the bit string b are 1, and input Hypothesis characterized by comprising a contradiction notifying unit for notifying that the set of hypotheses set is inconsistent with other knowledge in the knowledge base. If contradiction inspection system.