Search

In this paper we address the problem of handling inconsistencies in tables with missing values (also called nulls) and functional dependencies. Although the traditional view is that table instances must respect all functional dependencies imposed on them, it is nevertheless relevant to develop theories about how to handle instances that violate some dependencies. Regarding missing values, we make no assumptions on their existence: a missing value exists only if it is inferred from the functional dependencies of the table. We propose a formal framework in which each tuple of a table is associated with a truth value among the following: true, false, inconsistent or unknown; and we show that our framework can be used to study important problems such as consistent query answering, table merging, and data quality measures - to mention just a few. In this paper, however, we focus mainly on consistent query answering, a problem that has received considerable attention during the last decades. The main contributions of the paper are the following: (a) we introduce a new approach to handle inconsistencies in a table with nulls and functional dependencies, (b) we give algorithms for computing all true, inconsistent and false tuples, (c) we investigate the relationship between our approach and Four-valued logic in the context of data merging, and (d) we give a novel solution to the consistent query answering problem and compare our solution to that of table repairs., In the present version a few changes have been made with respect to the previous version: 1/ The following proofs of lemmas 1, 2, 3 and of Proposition 2 have been rewritten. 2/ A new definition of consistent answer is given and compared with existing approaches based on repairs

We apply a non-classical four-valued logic in the process of reasoning regarding strategies for cops in a modified game of “Cops and Robber” played on a graph. We extend the game by introducing uncertainty in a form of random failures of detecting devices. This is realized by allowing that a robber can be detected in a node only with the given probability PA. Additionally, with the probability PF, cops can be given a false-positive, i.e., they are informed that the robber is located at some node, whereas it is located somewhere else. Consequently, non-zero PFintroduces a measurement noise into the system. All the cops have access to information provided by the detectors and can communicate with each other, so they can coordinate the search. By adjusting the number of detectors, PA, and PFwe can achieve a smooth transition between the two well-known variants of the game: “with fully visible robber” and “with invisible robber”. We compare a simple probabilistic strategy for cops with the non-parametric strategy based on reasoning with a four-valued paraconsistent logic. It is shown that this novel approach leads to a good performance, as measured by the required mean catch-time. We conclude that this type of reasoning can be applied in real-world applications where there is no knowledge about the underlying source of errors which is particularly useful in robotics.

The four-valued semantics of Belnap–Dunn logic, consisting of the truth values True, False, Neither, and Both, gives rise to several nonclassical logics depending on which feature of propositions we wish to preserve: truth, nonfalsity, or exact truth (truth and nonfalsity). Interpreting equality of truth values in this semantics as material equivalence of propositions, we can moreover see the equational consequence relation of this four-element algebra as a logic of material equivalence. In this paper, we axiomatize all combinations of these four-valued logics, for example, the logic of truth and exact truth or the logic of truth and material equivalence. These combined systems are consequence relations which allow us to express implications involving more than one of these features of propositions.

This paper presents the essence of an investigation of a complex technical object with the use of four-valued logic. To this end, an intelligent diagnostic system (DIAG 2) is described. A special feature of this system was its capability of inferring k at {k = 4, 3, 2}, in which case the logic {k = 4} is applied. An important part of this work was to present the theoretical foundations describing the essence of inference in the four-valued logic contemplated. It was also pointed out that the basis for classification of states in the multiple-valued logic of the diagnostic system (DIAG 2) was the permissible interval of changes in the values of diagnostic signal features. Four-valued logic testing was applied to a system of wind turbine equipment. Keywords: technical diagnostics, diagnostic inference, multiple-valued logic, artificial intelligence

This short and informal article shows that, although Godel's theorem is valid using classical logic, there exists some four-valued logical system that is able to prove that arithmetic is both sound and complete. This article also describes a four-valued Prolog in some informal, brief and intuitive manner.

In this paper, we consider a set of quite interesting three- and four-valued logics and prove the normalisation theorem for their natural deduction formulations. Among the logics in question are the Logic of Paradox, First Degree Entailment, Strong Kleene logic, and some of their implicative extensions, including RM3 and RM3⊃. Also, we present a detailed version of Prawitz’s proof of Nelson’s logic N4 and its extension by intuitionist negation.

This study aims to introduce a modal extension M4CC of Arieli, Avron, and Zamansky's ideal paraconsistent four-valued logic 4CC as a Gentzen-type sequent calculus and prove the Kripke-completeness and cut-elimination theorems for M4CC. The logic M4CC is also shown to be decidable and embeddable into the normal modal logic S4. Furthermore, a subsystem of M4CC, which has some characteristic properties that do not hold for M4CC, is introduced and the Kripke-completeness and cut-elimination theorems for this subsystem are proved. This subsystem is also shown to be decidable and embeddable into S4.

There were two methods of doing modular transformations from Entity Relationship Diagrams to Class Diagrams according to international researchers. In order to establish which method would best suit software engineers, we conducted a survey by giving a group of students in the computer science field, whom we considered potential future software engineers. The results we got were valid, but did not match those of any of the international researchers. We found that this situation could only be explained using Eastern Four-Valued logic, also known by such names as Catuskoti and Tetralemma.

We will consider languages that contain two different sources of semantic pathologies: sentences that do not express a proposition and sentences that, even though they do express a proposition, are neither true nor false. When those languages are given a three-valued semantics, all pathological sentences are lumped together and assigned the third truth value. In this paper we will first present the case of languages with definite descriptions, where a distinction between these two forms of pathological sentences can be drawn. Then we will explore a four-valued semantics which can distinguish between the two kinds of pathological sentences.; Patologia semantikoen bi iturri desberdin dituzten hizkuntzetan jarriko dugu arreta: proposizio bat adierazten ez duten perpausetan eta, proposizio bat adierazten duten arren, ez egiazko eta ez faltsu diren perpausetan. Hizkuntza horiei hiru baliodun semantika bat ematen zaienean, perpaus patologiko guztiak bildu egiten dira eta hirugarren egibalioa esleitzen zaie. Lan honetan, hasteko, deskripzio definitudun hizkuntzen kasua aurkeztuko dugu; horietan, marraz daiteke bi perpaus patologiko mota horien arteko bereizketa. Gero, lau baliodun semantika bat arakatuko dugu, perpaus patologikoen bi motak bereiz ditzakeena.

The development of recursion theory motivated Kleene to create regular three-valued logics. Remove it taking his inspiration from the computer science, Fitting later continued to investigate regular three-valued logics and defined them as monotonic ones. Afterwards, Komendantskaya proved that there are four regular three-valued logics and in the three-valued case the set of regular logics coincides with the set of monotonic logics. Next, Tomova showed that in the four-valued case regularity and monotonicity do not coincide. She counted that there are 6400 four-valued regular logics, but only six of them are monotonic. The purpose of this paper is to create natural deduction systems for them. We also describe some functional properties of these logics.

The trilattice \(\textit{SIXTEEN}_3\) is a natural generalization of the well-known bilattice \(\textit{FOUR}_2\). Cut-free, sound and complete sequent calculi for truth entailment and falsity entailment in \(\textit{SIXTEEN}_3\) are presented.

The use of positive and negative reasons in inference and decision aiding is a recurrent issue of investigation as far as the type of formal language to use within a DSS is concerned. A language enabling to explicitly take into account such reasons is Belnap's logic and the four valued logics derived from it. In this paper, we explore the interpretation of a continuous extension of a four valued logic as a necessity degree (in possibility theory). It turns out that, in order to take full advantage of the four values, we have to consider ''sub-normalised'' necessity measures. Under such a hypothesis four valued logics become the natural logical frame for such an approach.

Based on the semantic concepts developed by M.~Dunn and N.~Belnap, a four-valued language containing only two logical symbols is proposed. We show that this language is functionally complete with regard to the given semantics. Specifically, we prove that every truth-function is expressed by a formula of the language. To do this, we define two concepts akin to the disjunctive and conjunctive normal forms. Using these concepts, we establish that every truth-function for a four-valued semantics can be represented by a formula in a disjunctive form or in a conjunctive form.

This paper discusses an implementation of four speech acts: assert, concede, request and challenge in a paraconsistent framework. A natural four-valued model of interaction yields multiple new cognitive situations. They are analyzed in the context of communicative relations, which partially replace the concept of trust. These assumptions naturally lead to six types of situations, which often require performing conflict resolution and belief revision.The particular choice of a rule-based, Datalog¬¬-like query language 4QL as a four-valued implementation framework ensures that, in contrast to the standard two-valued approaches, tractability of the model is achieved.

Service level agreements (SLAs) are typically used to specify rules regarding the consumption of services that are agreed between the providers of the service-based applications (SBAs) and their consumers. An SLA includes a list of terms that contain the guarantees that must be fulfilled during the provisioning and consumption of the services. Since the violation of such guarantees may lead to the application of potential penalties, it is important to assure that the SBA behaves as expected. In this paper, we propose a proactive approach to test SLA-aware SBAs by means of identifying test requirements, which represent situations that are relevant to be tested. To address this issue, we define a four-valued logic that allows evaluating both the individual guarantee terms and their logical relationships. Grounded in this logic, we devise a test criterion based on the modified condition decision coverage (MCDC) in order to obtain a cost-effective set of test requirements from the structure of the SLA. Furthermore by analyzing the syntax and semantics of the agreement, we define specific rules to avoid non-feasible test requirements. The whole approach has been automated and applied over an eHealth case study.

Łukasiewicz's four-valued modal logic is surveyed and analyzed, together with Łukasiewicz's motivations to develop it. A faithful interpretation of it in classical (non-modal) two-valued logic is presented, and some consequences are drawn concerning its classification and its algebraic behaviour. Some counter-intuitive aspects of this logic are discussed in the light of the presented results, Łukasiewicz's own texts, and related literature.

The paper presents some new results concerning the axiomatization of double threshold preference structures. Such structures, which have been introduced in order to model a situation of hesitation between the strict preference and the indifference, were not axiomatized through the use of a single characteristic relation. We give two theorems for this purpose, exploiting a four valued logic recently introduced by the authors as a preference modeling language under hesitation. © 1998 John Wiley & Sons, Ltd., FLWIN, SCOPUS: ar.j, info:eu-repo/semantics/published

Inaccurate determination, uncertainty, imprecision and ambiguity are often present in complex decision situations where decision aid is requested. Instead of reducing complexity via quantitative models of preferences, as traditional preference modeling does, it may be necessary to represent these situations explicitly. There exist operational methods that face these problems, the principal reference being the partial comparability theory. The lack of an axiomatization however limits the operational potentialities of this theory. In the paper an axiomatic foundation of the partial comparability theory is outlined based on a sound and complete four valued logic (the truth values “true”, “false”, “unknown”, “contradictory” are accepted). This logic is extended to the first order predicate calculus. Four basic preference relations are thus defined, namely: strict preference, weak preference, indifference and incomparability. The operational perspectives are discussed in the paper as some problems in multicriteria methods can be solved in a much easier and natural way. Moreover non monotonic reasoning devices could be built enhancing the potentialities of the theory.

This paper discusses refinement of programs that may raise and catch exceptions. We show that exceptions are expressed by a class of predicate transformers built on Arieli and Avron’s four-valued logic and develop a refinement framework for the four-valued predicate transformers. The resulting framework enjoys several refinement laws that are useful for stepwise refinement of programs involving exception handling and partial predicates. We demonstrate some typical usages of the refinement laws in the proposed framework by a few examples of program transformation.

When monitoring a system w.r.t. a property defined in a temporal logic such as LTL, a major concern is to settle with an adequate interpretation of observable system events; that is, models of temporal logic formulae are usually infinite words of events, whereas at runtime only finite but incrementally expanding prefixes are available.In this work, we review LTL-derived logics for finite traces from a runtime-verification perspective. In doing so, we establish four maxims to be satisfied by any LTL-derived logic aimed at runtime verification. As no pre-existing logic readily satisfies all of them, we introduce a new four-valued logic Runtime Verification Linear Temporal Logic RV-LTL in accordance to these maxims. The semantics of Runtime Verification Linear Temporal Logic (RV-LTL) indicates whether a finite word describes a system behaviour which either (i) satisfies the monitored property, (ii) violates the property, (iii) will presumably violate the property, or (iv) will presumably conform to the property in the future, once the system has stabilized. Notably, (i) and (ii) correspond to the classical semantics of LTL, whereas (iii) and (iv) are chosen whenever an observed system behaviour has not yet lead to a violation or acceptance of the monitored property.Moreover, we present a monitor construction for RV-LTL properties in terms of Moore machines signalizing the semantics of the so far obtained execution trace w.r.t. the monitored property. © The Author, 2010. Published by Oxford University Press. All rights reserved.

Bilattices, due to M. Ginsberg, are a family of truth-value spaces that allow elegantly for missing or conflicting information. The simplest example is Belnap's four-valued logic, based on classical two-valued logic. Among other examples are those based on finite many-valued logics and on probabilistic-valued logic. A fixed-point semantics is developed for logic programming, allowing any bilattice as the space of truth values. The mathematics is little more complex than in the classical two-valued setting, but the result provides a natural semantics for distributed logic programs, including those involving confidence factors. The classical two-valued and the Kripke-Kleene three-valued semantics become special cases, since the logics involved are natural sublogics of Belnap's logic, the logic given by the simplest bilattice.

This paper extends the basic rough set formalism introduced by Pawlak [1] to a rule-based knowledge representation language, called Rough Datalog, where rough sets are represented by predicates and described by finite sets of rules. The rules allow us to express background knowledge involving rough concepts and to reason in such a knowledge base. The semantics of the new language is based on a four-valued logic, where in addition to the usual values TRUE and FALSE, we also have the values BOUNDARY, representing uncertainty, and UNKNOWN corresponding to the lack of information. The semantics of our language is based on a truth ordering different from the one used in the well-known Belnap logic [2, 3] and we show why Belnap logic does not properly reflect natural intuitions related to our approach. The declarative semantics and operational semantics of the language are described. Finally, the paper outlines a query language for reasoning about rough concepts.

In this paper we discuss a model of quantum computer in which a state is an operator of density matrix and gates are general quantum operations, not necessarily unitary. A mixed state (operator of density matrix) of n two-level quantum systems is considered as an element of 4^n-dimensional operator Hilbert space (Liouville space). It allows to use a quantum computer model with four-valued logic. The gates of this model are general superoperators which act on n-ququat state. Ququat is a quantum state in a four-dimensional (operator) Hilbert space. Unitary two-valued logic gates and quantum operations for an n-qubit open system are considered as four-valued logic gates acting on n-ququat. We discuss properties of quantum four-valued logic gates. In the paper we study universality for quantum four-valued logic gates., 17 pages

International audience; The principle of concordance/discordance was introduced by B. Roy in his very early work on Multiple Criteria Decision Analysis. Although such a principle is grounded by strong evidence from real life decision situations, the way in which it has been implemented in existing MCDA methods allows only for its partial and limited use. Indeed, the principle lacks a theoretical frame enabling a more general use in decision analysis. The paper presents a possible generalisation of this principle under the concepts of positive and negative reasons. For this purpose, a new formalism, (a four valued logic) is suggested. Under such a formalism the concordance test is seen as the evaluation of the existence of positive reasons supporting the sentence “x is at least as good as y”, while the discordance test can be viewed as the evaluation of the existence of negative reasons against the same sentence. A number of results obtained in preference modelling and aggregation shows the potentiality of this approach.

International audience; It has long been recognized that the concept of inconsistency is a central part of com-monsense reasoning. In this issue, a number of authors have explored the idea of reasoning with maximal consistent subsets of an inconsistent stratified knowledge base. This paradigm, often called "coherent-based reasoning", has resulted in some interesting proposals for para-consistent reasoning, non-monotonic reasoning, and argumentation systems. Unfortunately, coherent-based reasoning is computationally very expensive. This paper harnesses the approach of approximate entailment by Schaerf and Cadoli [SCH 95] to develop the concept of "approximate coherent-based reasoning". To this end, we begin to present a multi-modal propo-sitional logic that incorporates two dual families of modalities: 2S and 3S defined for each subset S of the set of atomic propositions. The resource parameter S indicates what atoms are taken into account when evaluating formulas. Next, we define resource-bounded consolidation operations that limit and control the generation of maximal consistent subsets of a stratified knowledge base. Then, we present counterparts to existential, universal, and argumentative inference that are prominent in coherence-based approaches. By virtue of modalities 2S and 3S, these inferences are approximated from below and from above, in an incremental fashion. Based on these features, we show that an anytime view of coherent-based reasoning is tenable.

We address the problem of integrating information coming from different sources. The information consists of facts that a central server collects and tries to combine using (a) a set of logical rules, i.e. a logic program, and (b) a hypothesis representing the server's own estimates. In such a setting incomplete information from a source or contradictory information from different sources necessitate the use of many-valued logics in which programs can be evaluated and hypotheses can be tested. To carry out such activities we propose a formal framework based on Belnap's four-valued logic. In this framework we work with the class of programs defined by Fitting and we develop a theory for information integration. We also establish an intuitively appealing connection between our hypothesis testing mechanism on the one hand, and the well-founded semantics and Kripke-Kleene semantics of Datalog programs with negation, on the other hand.

In his well-known paper “How computer should think” Belnap (1977) argues that four-valued semantics is a very suitable setting for computerized reasoning. In this paper we vindicate this thesis by showing that the logical role that the four-valued structure has among Ginsberg's bilattices is similar to the role that the two-valued algebra has among Boolean algebras. Specifically, we provide several theorems that show that the most useful bilattice-valued logics can actually be characterized as four-valued inference relations. In addition, we compare the use of three-valued logics with the use of four-valued logics, and show that at least for the task of handling inconsistent or uncertain information, the comparison is in favor of the latter.

Bilattices and d-frames are two different kinds of structures with a four-valued interpretation. Whereas d-frames were introduced with their topological semantics in mind, the theory of bilattices has a closer connection with logic. We consider a common generalisation of both structures and show that this not only still has a clear bitopological semantics, but that it also preserves most of the original bilattice logic. Moreover, we also obtain a new bitopological interpretation for the connectives of four-valued logic.

Belnap offers two arguments for the usefulness of four-valued logic. I argue that one of them, which rests on interpreting valuations as states of our information, when taken seriously collapses into an argument for two-valued logic in which relevance is lost, and that the other, resting on Scott's thesis, is not an argument for its usefulness