Deduction of clause forms in database

A deductive database in SQL or any other database system is a tool for drawing conclusions about new facts based on rules and information already in the database. In deductive databases, data records are the language commonly used to express facts, rules, and queries. When expressed in clause form, the formula consists of multiple clauses, each of which consists of multiple literals connected only by logical connectives marked with the OR symbol.

The following quantifiers can be used in the formula -

Universal Quantifier - It can be read as "P(x) holds for all x", which means that P(x) holds for all instances of x in the universe.

For example, trucks have wheels.

Existential Quantifier - This means that P(x) holds for at least one term x in the universe, and is expressed as "there exists an x ​​such that P(x)".

Example: You are cared for by someone.

The clause form formula must be changed to a formula with the following qualities -

Each element in the formula has a quantified value. Therefore, there is no need to explicitly add a universal quantifier for everyone. When the quantifier is removed, all variables in the formula are implicitly quantified by the universal quantifier.

Assume that the formula consists of multiple clauses, and each clause consists of multiple literals connected only by the logical connective OR, so the formula consists of clauses. Every sentence is a disjunction of words.

The sentences themselves are only connected by AND logical connectives to create formulas. Therefore, the clause form of the formula is the conjunction of the clause.

As can be demonstrated, any formula can be changed into clause form. For our purposes, the structure of the individual clauses (each of which is a disjunction of literals) is of primary interest. Remember, these literals can be positive or negative. Consider the following clause -

NOT(P1) OR NOT(P2) OR ..... OR NOT(Pn) OR Q1 OR Q2 OR ..... OR Qm

There are m positive characters and n negative characters in the previous clause. A logical formula similar to the following can be used to express this clause -

P1 AND P2 AND ..... AND Pn => Q1 OR Q2 OR ..... OR Qm

For example, the implicit symbol is "=>".

The second formula is true only if at least one Q is true, which is what the (implicit) sign means. This is true if all p literals i = (1, 2,...,) are true. For the first formula, if any of the P literals i = (1, 2,..., n) is true, then all its negations are also true. Therefore, in this case it is true only if at least one Q is true.

Therefore, the truth values ​​of the above two formulas are always the same because they are comparable.

in conclusion

In clause form, a formula is written as a series of sentences, each of which consists of a number of words connected only by logical connectives of the OR variant.

The above is the detailed content of Deduction of clause forms in database. For more information, please follow other related articles on the PHP Chinese website!