Two notions of compactness in Gödel logics

Compactness is an important property of classical propositional logic. It can be defined in two equivalent ways. The first one states that simultaneous satisfiability of an infinite set of formulae is equivalent to the satisfiability of all its finite subsets. The second one states that if a set of formulae entails a formula, then there is a finite subset entailing this formula as well.In propositional many-valued logic, we have different degrees of satisfiability and different possible definitions of entailment, hence the questions of compactness is more complex. In this paper we will deal with compactness of Gödel, Gödel_Δ, and Gödel_～ logics.There are several results (all for the countable set of propositional variables) concerning the compactness (based on satisfiability) of these logic by Cintula and Navara, and the question of compactness (based on entailment) for Gödel logic was fully answered by Baaz and Zach (see papers [3] and [2]).In this paper we give a nearly complete answer to the problem of compactness based on both concepts for all three logics and for an arbitrary cardinality of the set of propositional variables. Finally, we show a tight correspondence between these two concepts     

The Decision Problem of Modal Product Logics with a Diagonal,and Faulty Counter Machines

In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity (also known as the ‘diagonal’) relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them.     

Connection Tableau Calculi with Disjunctive Constraints

Automated theorem proving amounts to solving search problems in usually tremendous search spaces. A lot of research therefore focuses on search space reductions. Our approach reduces the search space which arises when using so-called connection tableau calculi for first-order automated theorem proving. It uses disjunctive constraints over first-order equations to compress certain parts of this search space. We present the basics of our constrained-connection-tableau calculi, a constraint extension of connection tableau calculi, and deal with the efficient handling of constraints during the search process. The new techniques are integrated into the automated connection tableau prover Setheo.     

模态逻辑的集合论语义与互模拟不变性

含有命题变元的非良基集合能够被看作解释模态语言的模型。任给非良基集合a,一个命题变元p在a上真当且仅当p属于a。命题联结词的解释与古典命题逻辑相同。一个公式3A在a上真当且仅当存在集合b属于a,使得A在b上是真的。在一个集合中,属于关系被看作可及关系。在这种思想下,我们可以定义从模态语言到一阶集合论语言的标准翻译。对任意模态公式A和集合变元x,可以递归定义一阶集合论语言的公式ST(A,x)。在关系语义学下,van Benthem刻画定理是说,在带有唯一的二元关系符号R的一阶语言中,任何一阶公式等价于某个模态公式的标准翻译当且仅当这个一阶公式在互模拟下保持不变。因此,模态语言是该一阶关系语言的互模拟不变片段。同样,我们可以在集合上定义互模拟关系,证明van Benthem刻画定理对于集合论语义和集合上的互模拟不变片段成立,即模态语言是一阶集合论语言的集合互模拟不变片段。     

The complexity of satisfiability for fragments of hybrid logic—Part I

The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments.In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators.     

The Undecidability of Propositional Adaptive Logic

We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and can be -complete. These classifications are exact. For first order theories even finite sets of premises can generate such consequence sets in either calculus.     

Free-Variable Tableaux for Propositional Modal Logics

Free-variable semantic tableaux are a well-established technique for first-order theorem proving where free variables act as a meta-linguistic device for tracking the eigenvariables used during proof search. We present the theoretical foundations to extend this technique to propositional modal logics, including non-trivial rigorous proofs of soundness and completeness, and also present various techniques that improve the efficiency of the basic naive method for such tableaux.     

Satisfiability on hypergraphs

In [4] R.Cowen considers a generalization of the resolution rule for hypergraphs and introduces a notion of satisfiability of families of sets of vertices via 2-colorings piercing elements of such families. He shows, for finite hypergraphs with no one-element edges that if the empty set is a consequence ofA by the resolution rule, thenA is not satisfiable. Alas the converse is true for a restricted class of hypergraphs only, and need not to be true in the general case. In this paper we show that weakening slightly the notion of satisfiability, we get the equivalence of unsatisfiability and the derivability of the empty set for any hypergraph. Moreover, we show the compactness property of hypergraph satisfiability (in the weaker sense) and state its equivalence to BPI, i.e. to the statement that in every Boolean algebra there exists an ultrafilter.     

A Completeness Proof for a Logic with an Alternative Necessity Operator

We show the completeness of a Hilbert-style system LK defined by M. Valiev involving the knowledge operator K dedicated to the reasoning with incomplete information. The completeness proof uses a variant of Makinson's canonical model construction. Furthermore we prove that the theoremhood problem for LK is co-NP-complete, using techniques similar to those used to prove that the satisfiability problem for propositional S5 is NP-complete.     

The Finite Model Property for Logics with the Tangle Modality

The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, and shows that they have the finite model property for Kripke frame semantics. The logics are specified by a variety of conditions on their validating frames, including local and global connectedness properties. Some of the results have been used to obtain completeness theorems for interpretations of tangled modal logics in topological spaces.     

Efficiently checking propositional refutations in HOL theorem provers

This paper describes the integration of zChaff and MiniSat, currently two leading SAT solvers, with Higher Order Logic (HOL) theorem provers. Both SAT solvers generate resolution-style proofs for (instances of) propositional tautologies. These proofs are verified by the theorem provers. The presented approach significantly improves the provers' performance on propositional problems, and exhibits counterexamples for unprovable conjectures. It is also shown that LCF-style theorem provers can serve as viable proof checkers even for large SAT problems. An efficient representation of the propositional problem in the theorem prover turns out to be crucial; several possible solutions are discussed.     

可满足性问题的归约技术

通过一个恰当的归约变换,可以将一个CNF公式变换为另一个具有某种特殊结构或性质的公式,使其两者具有相同的可满足性。一个典型的归约是将一般的CNF公式变换为3．GVF公式。通过构造一些恰当的工具,可以将公式类变换为所要求的正则类。极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足。我们提供了一种归约技术,通过构造恰当的极小不可满足公式作为工具,将公式类变换为具有正则结构的公式类。研究正则结构的公式的复杂性及性质很有意义。如,将一个从3．CNF公式变换为（3,4）一CNF公式,这里（3,4）一CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4。因此,（3,4）．SAT是一个NP．完全问题,并且正N-部图的诸多良好性质对于研究正则结构的SAT问题具有许多潜在的作用。     

Monodic Packed Fragment with Equality is Decidable

We prove decidability of satisfiability of sentences of the monodic packed fragment of first-order temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.     

On The Computational Consequences of Independence in Propositional Logic

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline.     

A QBF-based formalization of abstract argumentation semantics

We introduce a unified logical theory, based on signed theories and Quantified Boolean Formulas (QBFs) that can serve as the basis for representing and computing various argumentation-based decision problems. It is shown that within our framework we are able to model, in a simple and modular way, a wide range of semantics for abstract argumentation theory. This includes complete, grounded, preferred, stable, semi-stable, stage, ideal and eager semantics. Furthermore, our approach is purely logical, making for instance decision problems like skeptical and credulous acceptance of arguments simply a matter of entailment and satisfiability checking. The latter may be verified by off-the-shelf QBF-solvers.     

Lexical, morphological, and syntactic aspects of verb production in agrammatic aphasics

Agrammatic aphasics do not exhibit a normal pattern of verb production; their spontaneous speech is said to lack verbs, and the verbs that are produced lack inflection. The current article focuses on the lexical, morphological, and syntactic aspects of verbs in spontaneous speech of a group of Dutch agrammatic speakers. Dutch is a so-called verb-second language in which the finite verb in the matrix clause is in the second position and nonfinite verbs are in the final position. The analysis shows that agrammatic speakers are sensitive to this relation; they virtually never produce finite verbs in the final clause position or nonfinite verbs in the second position. Nevertheless, they produce significantly fewer finite clauses than do non-brain-damaged speakers. The diversity of the lexical verbs in spontaneous speech is also lower than in non-brain-damaged speakers, but this is due to less variation in the finite lexical verbs. Hence, it is suggested that the problems with verbs in Dutch agrammatic spontaneous speech are restricted to finite lexical verbs. In an experiment, it was evaluated whether these problems with finite lexical verbs are caused by a morphological deficit or a syntactic deficit. The data show that a syntactic deficit is more likely; Dutch agrammatic speakers produce finite verbs in the base-generated position (i.e., in the embedded clause) significantly better than finite verbs that have been moved to the second position (i.e., in the matrix clause). From these data, the authors conclude that in Dutch, a verb-second language, agrammatic aphasics demonstrate specific problems with moved finite verbs, although they are perfectly aware of the relation between verb position and verb finiteness. This syntactic problem affects not only the proportion of finite verbs but also the diversity of the verbs and, hence, communicative contents.     

A computational model for solving problems from the Raven’s Progressive Matrices intelligence test using iconic visual representations

We describe a computational model for solving problems from Raven’s Progressive Matrices (RPM), a family of standardized intelligence tests. Existing computational models for solving RPM problems generally reason over amodal propositional representations of test inputs. However, there is considerable evidence that humans can also apply imagery-based reasoning strategies to RPM problems, in which processes rooted in perception operate over modal representations of test inputs. In this paper, we present the “affine model,” a computational model that simulates modal reasoning by using iconic visual representations together with affine and set transformations over these representations to solve a given RPM problem. Various configurations of the affine model successfully solve between 33 and 38 of the 60 problems on the Standard Progressive Matrices, which matches levels of performance for typically developing 9- to 11-year-old children. This suggests that, for at least a sizeable subset of RPM problems, it is not always necessary to extract amodal symbols in order to arrive at the correct answer, and iconic visual representations constitute a sufficient form of representation to successfully solve these problems. We intend for the affine model to serve as a complementary computational account to existing propositional models, which together may provide an integrated, dual-process account of human problem solving on the RPM.     

Probability Semantics for Quantifier Logic

By supplying propositional calculus with a probability semantics we showed, in our 1996, that finite stochastic problems can be treated by logic-theoretic means equally as well as by the usual set-theoretic ones. In the present paper we continue the investigation to further the use of logical notions in probability theory. It is shown that quantifier logic, when supplied with a probability semantics, is capable of treating stochastic problems involving countably many trials.     

Solving the $100 modal logic challenge

We present the theoretical foundation, design, and implementation, of a system that automatically determines the subset relation between two given axiomatizations of propositional modal logics. This is an open problem for automated theorem proving. Our system solves all but six out of 121 instances formed from 11 common axiomatizations of seven modal logics. Thus, although the problem is undecidable in general, our approach is empirically successful in practically relevant situations.