next up previous
Next: INFERENCE ALGORITHM Up: FORMALISATION OF A MANY-VALUED Previous: FORMALISATION OF A MANY-VALUED

Mv-Atom Completeness

The sub-language we consider is the negation free fragment of tex2html_wrap_inline1490 . Namely we define an Mv-Horn-Rule as an mv-rule tex2html_wrap_inline1476 such that tex2html_wrap_inline1480 and q are atomic symbols and V=[a,1] is an upper interval of truth-values of tex2html_wrap_inline1370 with a > 0, and tex2html_wrap_inline1694 . Then, we define the restricted many-valued propositional sub-language tex2html_wrap_inline1696 as the following 4-tuple:

displaymath1698

being tex2html_wrap_inline1700 = Mv-Atoms( tex2html_wrap_inline1460 ) tex2html_wrap_inline1462 Mv-Horn-Rules( tex2html_wrap_inline1460 ), where Mv-Horn-Rules( tex2html_wrap_inline1460 ) denotes the set of Mv-Horn-Rules that can be built from tex2html_wrap_inline1454 and tex2html_wrap_inline1370 . Within this sub-language, the not-introduction and not-elimination inference rules of Mv-SC have no sense. Accordingly, we define the sub-calculus Mv-RSC by axioms A1, A2 and the Weakening, Composition and Specialisation inference rules. Deduction in Mv-RSC will be denoted by tex2html_wrap_inline1718 . It is interesting to remark that, in the restricted language tex2html_wrap_inline1696 , the Specialisation inference rule takes this form:

tabular216



since it is easy to show from the definition of tex2html_wrap_inline1728 that tex2html_wrap_inline1730 .

The soundness of tex2html_wrap_inline1718 is naturally inherited from tex2html_wrap_inline1734 . Moreover, we shall show the following completeness result for mv-atom deduction.

  theorem224

As usual, we will prove that if tex2html_wrap_inline1746 then tex2html_wrap_inline1748 . To do that we shall make use of standard logical machinery adapted to our particular case.

definition231

Therefore, a set of mv-formulas tex2html_wrap_inline1754 will be RSC-consistent if tex2html_wrap_inline1754 is not RSC-inconsistent.

definition236

In the following we assume that tex2html_wrap_inline1754 denotes a set of mv-formulas from tex2html_wrap_inline1770 . Next step is to prove that if tex2html_wrap_inline1754 is RSC-consistent then tex2html_wrap_inline1754 is satisfiable.

lemma242

If tex2html_wrap_inline1754 is RSC-consistent and tex2html_wrap_inline1786 , the only possibility is to have tex2html_wrap_inline1788 such that tex2html_wrap_inline1790 , that is tex2html_wrap_inline1792 , and thus we also have tex2html_wrap_inline1794 .

lemma249

Suppose tex2html_wrap_inline1754 is consistent, otherwise the result is trivial, and suppose that tex2html_wrap_inline1806 and tex2html_wrap_inline1808 are inconsistent. Then, it must be the case that tex2html_wrap_inline1810 with tex2html_wrap_inline1812 and tex2html_wrap_inline1814 . Analogously, tex2html_wrap_inline1788 with tex2html_wrap_inline1818 and tex2html_wrap_inline1820 . Therefore, tex2html_wrap_inline1822 , tex2html_wrap_inline1824 and tex2html_wrap_inline1826 . Thus, we have that tex2html_wrap_inline1828 , and so, tex2html_wrap_inline1830 is inconsistent.

lemma265

Suppose tex2html_wrap_inline1840 is inconsistent for any tex2html_wrap_inline1842 . Then, by repeated application of previous lemma, tex2html_wrap_inline1844 is also inconsistent, but (p, [0,1]) is an axiom, thus tex2html_wrap_inline1754 itself should be inconsistent: contradiction.

lemma269

Let tex2html_wrap_inline1854 be the set of propositional variables tex2html_wrap_inline1454 . Define tex2html_wrap_inline1858 , and for i > 0 define tex2html_wrap_inline1862 , a being a truth-value such that tex2html_wrap_inline1866 is consistent. By the previous lemma such an a always exists. Finally, let tex2html_wrap_inline1870 . Then it is easy to check that tex2html_wrap_inline1872 is maximally atomic-consistent:

lemma279

Let tex2html_wrap_inline1754 be consistent and let tex2html_wrap_inline1872 be a maximally atomic extension of tex2html_wrap_inline1754 . Define a valuation tex2html_wrap_inline1900 as follows: tex2html_wrap_inline1902 if tex2html_wrap_inline1904 .

Then it is easy to show that tex2html_wrap_inline1906 is a model of tex2html_wrap_inline1754 . Namely, we have to show that, for any tex2html_wrap_inline1910 , we have that tex2html_wrap_inline1912 . We consider only the case tex2html_wrap_inline1914 . Let tex2html_wrap_inline1916 . We shall show then that tex2html_wrap_inline1918 . If tex2html_wrap_inline1920 , then tex2html_wrap_inline1424 , and obviously, by definition, tex2html_wrap_inline1924 . Suppose otherwise that a > b. Since tex2html_wrap_inline1872 is consistent, so tex2html_wrap_inline1930 is. But, using modus ponens, tex2html_wrap_inline1932 and thus tex2html_wrap_inline1934 . Since tex2html_wrap_inline1936 tex2html_wrap_inline1938 tex2html_wrap_inline1940 is consistent, tex2html_wrap_inline1942 , that is, tex2html_wrap_inline1944 . In other words, since V is an upper interval there must exist tex2html_wrap_inline1948 such that tex2html_wrap_inline1950 . Let tex2html_wrap_inline1952 . Since V is an upper interval, tex2html_wrap_inline1956 , and therefore we have tex2html_wrap_inline1958 , and the lemma is proved.

Finally, from this lemma, Theorem 2 is a direct corollary.

corollary300

If tex2html_wrap_inline1966 then, by Lemma 1, tex2html_wrap_inline1968 , i.e. tex2html_wrap_inline1970 is RSC-consistent, thus, by Lemma 5, tex2html_wrap_inline1970 is satisfiable, thus there exists tex2html_wrap_inline1526 model of tex2html_wrap_inline1754 such that tex2html_wrap_inline1978 , i.e. tex2html_wrap_inline1748 .


next up previous
Next: INFERENCE ALGORITHM Up: FORMALISATION OF A MANY-VALUED Previous: FORMALISATION OF A MANY-VALUED

Josep Puyol-Gruart
Wed Jun 11 15:38:47 MET DST 1997