Search

We introduce a new structure, the critical multi-cubic lattice. Notably the critical multi-cubic lattice is the first true generalization of the cubic lattice to higher dimensional spaces. We then introduce the notion of a homomorphism in the category of critical multi-cubic lattices, compute its automorphism group, and construct a Hilbert space over which we represent the group. With this unitary representation, we re-derive the generalized Pauli matrices common in quantum computation while also defining an algebraic framework for an infinite system of qudits. We also briefly explore the critical multi-cubic lattice as a novel implication algebra serving as a logical framework for qudit gates. [ABSTRACT FROM AUTHOR]

Propositional model enumeration, or All-SAT, is the task to record all models of a propositional formula. It is a key task in software and hardware verification, system engineering, and predicate abstraction, to mention a few. It also provides a means to convert a CNF formula into DNF, which is relevant in circuit design. While in some applications enumerating models multiple times causes no harm, in others avoiding repetitions is crucial. We therefore present two model enumeration algorithms which adopt dual reasoning in order to shorten the found models. The first method enumerates pairwise contradicting models. Repetitions are avoided by the use of so-called blocking clauses for which we provide a dual encoding. In our second approach we relax the uniqueness constraint. We present an adaptation of the standard conflict-driven clause learning procedure to support model enumeration without blocking clauses. Our procedures are expressed by means of a calculus and proofs of correctness are provided. [ABSTRACT FROM AUTHOR]

The Tsetlin Machine (TM) is a novel machine learning approach that implements propositional logic to perform various tasks such as classification and regression. The TM not only achieves competitive accuracy in these tasks but also provides results that are explainable and easy to implement using simple hardware. The TM learns using clauses based on the features of the data, and final classification is done using a combination of these clauses. In this paper, we propose the novel idea of adding regularizers to the TM, referred to as Regularized TM (RegTM), to improve generalization. Regularizers have been widely used in machine learning to enhance accuracy. We explore different regularization strategies and their influence on performance. We demonstrate the feasibility of our methodology through various experiments on benchmark datasets. [ABSTRACT FROM AUTHOR]

Accounting for the epistemic contribution of deduction has been a pervasive problem for logicians interested in deduction, such as, among others, Jakko Hintikka. The problem arises because the conclusion validly deduced from a set of premises is said to be "contained" in that set; because of this containment relation, the conclusion would be known from the moment the premises are known. Assuming this, it is problematic to explain how we can gain knowledge by deducing a logical consequence implied by a set of known premises. To address this problem, we offer an alternative account of the epistemic contribution of deduction as the process required to deduce a conclusion or a theorem, understanding such a process not only in terms of the number of steps in the derivation but also, more importantly, in terms of the reason for or justification for every step. That is, we do not know a proposition unless we have a justification or proof of that proposition. With this goal in mind, we develop a justification logic system which exhibits the epistemic contribution of a deductive derivation as the resulting justified formula. [ABSTRACT FROM AUTHOR]

This paper is about sentences of form To be human is to be an animal, To live is to fight, etc. I call them 'infinitive sentences'. I define an augmented propositional language able to express them and give a matrix-based semantics for it. I also give a tableau proof system, called IL for Infinitive Logic. I prove soundness, completeness and a few basic theorems. [ABSTRACT FROM AUTHOR]

We find a bound for the length of a conjunction of some propositional formulas, for which every unsatisfiable formula contains an unsatisfiable subformula. In particular, this technique applies to formulas in conjunctive normal form with restrictions on the number of true literals within every elementary disjunction, as well as for 2-CNFs, for symmetric 3-CNFs, and for conjunctions of voting functions in three literals. A lower bound on the rank of some matrices is used in proofs. [ABSTRACT FROM AUTHOR]

The provability problem in intuitionistic propositional second-order logic with existential quantifier and implication $ (\exists,\to) $ (∃ , →) is proved to be undecidable in presence of free type variables (constants). This contrasts with the result that inutitionistic propositional second-order logic with existential quantifier, conjunction and negation is decidable. [ABSTRACT FROM AUTHOR]

The increased complexity of modern system designs and demands for quicker time to market have made safety-related verification and validation of such systems more challenging. Incorporating safety and risk considerations at the early stages of design is one way to acquire a more robust initial design for novel systems. Inductive fault analysis has its significance at final stages of design, e.g., verification and validation. However, to preclude certain system failure states—especially for the systems with high failure consequences, a designer would innately prefer to trace back and remedy the causes of failure, as compared to a more cumbersome activity of identifying the faults individually and sifting the combinations that lead to the failure of interest. The work presented in this paper is aimed at the development of a backward failure propagation methodology for analyzing the origins of functional failures in a conceptual design of systems including but not limited to nuclear, mechanical, aerospace, process, electrical/electronics, telecommunication, automotive, etc. This method allows the designer to achieve a robust early design based on the analyses of the system's functional dependencies before proceeding to the detailed design and testing stages. The insights provided by the analysis at the conceptual design stage also reduce redesign efforts, testing costs, and project delays. The proposed method is a functional analysis approach that extends the Integrated System Failure Analysis for backward failure propagation. When provided with an abstract system configuration, a system's functional model, and a system's behavioral model, it utilizes a known functional state (typically a failure) to acquire system component modes and the states of other functions. The method includes inversion of the functional failure logic and component behavioral rules using propositional logic and deductive analysis to assess valid states of a system that satisfy the given initial conditions. To test the method's scalability, we applied the proposed method to a simplified representation of the secondary loop of a typical pressurized water reactor. [ABSTRACT FROM AUTHOR]

Natural language does not express all connectives definable in classical logic as simple lexical items. Coordination in English is expressed by conjunction and, disjunction or, and negated disjunction nor. Other languages pattern similarly. Non-lexicalized connectives are typically expressed compositionally: in English, negated conjunction is typically expressed by combining negation and conjunction (not both). This is surprising: if ∧ and ∨ are duals, and the negation of the latter can be expressed lexically (nor), why not the negation of the former? I present a two-tiered model of the semantics of the binary connectives. The first tier captures the expressive power of the lexicon: it is a bilateral state-based semantics that, under a restriction, can express all and only the distinctions that can be expressed by the lexicon of natural language (and, or, nor). This first tier is characterized by rejection as non-assertion and a Neglect Zero assumption. The second tier is obtained by dropping the Neglect Zero assumption and enforcing a stronger notion of rejection, thereby recovering classical logic and thus definitions for all Boolean connectives. On the two-tiered model, we distinguish the limited expressive resources of the lexicon and the greater combinatorial expressive power of the language as a whole. This gives us a logic-based account of compositionality for the Boolean fragment of the language. [ABSTRACT FROM AUTHOR]

In deep learning, large language models are typically trained on data from a corpus as representative of current knowledge. However, natural language is not an ideal form for the reliable communication of concepts. Instead, formal logical statements are preferable since they are subject to verifiability, reliability, and applicability. Another reason for this preference is that natural language is not designed for an efficient and reliable flow of information and knowledge, but is instead designed as an evolutionary adaptation as formed from a prior set of natural constraints. As a formally structured language, logical statements are also more interpretable. They may be informally constructed in the form of a natural language statement, but a formalized logical statement is expected to follow a stricter set of rules, such as with the use of symbols for representing the logic-based operators that connect multiple simple statements and form verifiable propositions.

Logic and logical thinking are present and play an important role in most of the disciplines at the university level but in different ways. In our research, which has been ongoing for several years, we are investigating the use of propositional logic among university students in different study programmes. Our current study evaluated data from 1,429 respondents involving students from 15 universities. The non-standardised knowledge test was previously pilot-tested and consisted of 15 tasks from selected elements of propositional logic in a different natural science subject-specific context. Significant differences in average results were found in terms of students’ gender, age, type of secondary school leaving exam and parents’ highest education level. Our research mainly aimed to compare students’ test scores by students’ fields of study. On average, mathematics-informatics students had the highest success rate of 67.4%, compared to students in engineering (61.0%), economics (57.9%), education (56.6%), science (56.5%) and humanities (54.7%). The result is significant (F = 13.521, p-value < 0.001). Furthermore, we found that the students performed differently in three selected areas of formal logic (F = 1108, df = 2, p < 0.001), with the lowest performance on statement negation tasks. The difference in means across groups of tasks is significant by the gender of the students and by their secondary education level.

Rhetorical structure theory (RST) and relational propositions have been shown useful in analyzing texts as expressions in propositional logic. Because these expressions are systematically derived, they may be expected to model discursive reasoning as articulated in the text. If this is the case, it would follow that logical operations performed on the expressions would be reflected in the texts. In this paper the logic of relational propositions is used to demonstrate the applicability of transitive inference to discourse. Starting with a selection of RST analyses from the research literature, analyses of the logic of relational propositions are performed to identify their corresponding logical expressions and within each expression to identify the inference path implicit within the text. By eliminating intermediary relational propositions, transitivity is then used to progressively compress the expression. The resulting compressions are applied to the corresponding texts and their compressed RST analyses. The application of transitive inference to logical expressions results in abridged texts that are intuitively coherent and logically compatible with their originals. This indicates an underlying isomorphism between the inferential structure of logical expressions and discursive coherence, and it confirms that these expressions function as logical models of the text. Potential areas for application include knowledge representation, logic and argumentation, and RST validation. [ABSTRACT FROM AUTHOR]

This paper proposes a deletion algorithm for the marginal problem in propositional logic. The algorithm is based on the general Davis and Putnam deletion algorithm DP, expressed as a bucket elimination algorithm, representing sets of clauses with the same set of variables employing a Boolean array. The main contribution is the development of alternative procedures when deleting a variable which allow more efficient computations. In particular, it takes advantage of the case in which the variable to delete is determined by a subset of the rest of the variables. It also provides a set of useful results and tools for reasoning with Boolean tables. The algorithms are implemented using Python and the NumPy library. Experiments show that this procedure is feasible for intermediate problems and for difficult problems from hard Bayesian networks cases [ABSTRACT FROM AUTHOR]

The increasing significance of theorem proving-based formalization in mathematics and computer science highlights the necessity for formalizing foundational mathematical theories. In this work, we employ the Coq interactive theorem prover to methodically formalize the language, semantics, and syntax of propositional logic, a fundamental aspect of mathematical reasoning and proof construction. We construct four Hilbert-style axiom systems and a natural deduction system for propositional logic, and establish their equivalences through meticulous proofs. Moreover, we provide formal proofs for essential meta-theorems in propositional logic, including the Deduction Theorem, Soundness Theorem, Completeness Theorem, and Compactness Theorem. Importantly, we present an exhaustive formal proof of the Completeness Theorem in this paper. To bolster the proof of the Completeness Theorem, we also formalize concepts related to mappings and countability, and deliver a formal proof of the Cantor–Bernstein–Schröder theorem. Additionally, we devise automated Coq tactics explicitly designed for the propositional logic inference system delineated in this study, enabling the automatic verification of all tautologies, all internal theorems, and the majority of syntactic and semantic inferences within the system. This research contributes a versatile and reusable Coq library for propositional logic, presenting a solid foundation for numerous applications in mathematics, such as the accurate expression and verification of properties in software programs and digital circuits. This work holds particular importance in the domains of mathematical formalization, verification of software and hardware security, and in enhancing comprehension of the principles of logical reasoning. [ABSTRACT FROM AUTHOR]

Definition: In deep learning, large language models are typically trained on data from a corpus as representative of current knowledge. However, natural language is not an ideal form for the reliable communication of concepts. Instead, formal logical statements are preferable since they are subject to verifiability, reliability, and applicability. Another reason for this preference is that natural language is not designed for an efficient and reliable flow of information and knowledge, but is instead designed as an evolutionary adaptation as formed from a prior set of natural constraints. As a formally structured language, logical statements are also more interpretable. They may be informally constructed in the form of a natural language statement, but a formalized logical statement is expected to follow a stricter set of rules, such as with the use of symbols for representing the logic-based operators that connect multiple simple statements and form verifiable propositions. [ABSTRACT FROM AUTHOR]

Evaluating students' academic performance is crucial for assessing the quality of education and educational strategies. However, it can be challenging to predict and evaluate academic performance under uncertain and imprecise conditions. To address this issue, many research works have employed fuzzy concepts to analyze, predict, and make decisions about students' academic performance. This paper investigates the use of fuzzy concepts in research related to evaluating, analyzing, predicting, or making decisions about student academic performance. The paper proposes a fuzzy model, called FPM (Fuzzy Propositional Model), for reasoning and predicting students' academic performance. FPM aims to address the limitations of previous studies by incorporating propositional logic with fuzzy sets concept, which allows for the representation of uncertainty and imprecision in the data. FPM integrates and transforms if-then rules into weighted fuzzy production rules to predict and evaluate academic performance. This paper tests and evaluates the FPM in two scenarios. In the first scenario, the model predicts and examines the impact of absenteeism on academic performance where there is no clear relation between the two parts of the dataset. In the second scenario, the model predicts the final exam results using the lab exam results, where the data are more related. The FPM provides good results in both scenarios, demonstrating its effectiveness in predicting and evaluating students' academic performance. A comparison study of the FPM's results with a linear regression model and previous work showed that the FPM performs better in predicting academic performance and provides more insights into the underlying factors affecting it. Therefore, the FPM could be useful in educational institutions to predict and evaluate students' academic performance, identify underlying factors affecting it, and improve educational strategies. [ABSTRACT FROM AUTHOR]

Research on intelligent tutoring systems has been exploring data-driven methods to deliver effective adaptive assistance. While much work has been done to provide adaptive assistance when students seek help, they may not seek help optimally. This had led to the growing interest in proactive adaptive assistance, where the tutor provides unsolicited assistance upon predictions of struggle or unproductivity. Determining when and whether to provide personalized support is a well-known challenge called the assistance dilemma. Addressing this dilemma is particularly challenging in open-ended domains, where there can be several ways to solve problems. Researchers have explored methods to determine when to proactively help students, but few of these methods have taken prior hint usage into account. In this paper, we present a novel data-driven approach to incorporate students' hint usage in predicting their need for help. We explore its impact in an intelligent tutor that deals with the open-ended and well-structured domain of logic proofs. We present a controlled study to investigate the impact of an adaptive hint policy based on predictions of HelpNeed that incorporate students' hint usage. We show empirical evidence to support that such a policy can save students a significant amount of time in training and lead to improved posttest results, when compared to a control without proactive interventions. We also show that incorporating students' hint usage significantly improves the adaptive hint policy's efficacy in predicting students' HelpNeed, thereby reducing training unproductivity, reducing possible help avoidance, and increasing possible help appropriateness (a higher chance of receiving help when it was likely to be needed). We conclude with suggestions on the domains that can benefit from this approach as well as the requirements for adoption. [ABSTRACT FROM AUTHOR]

The logical reasoning question-answering is a critical task in natural language processing, as it equips models with human-like logical reasoning intelligence. Existing approaches focus on extracting and leveraging the hidden logical structures within text. However, previous works explore partial logical relationships and neglect the holistic extraction within the text. Moreover, they struggle to fully model logical connections, including long-distance dependencies and local topology information. To address these issues, we propose a novel heterogeneous-branch integration framework. Our framework is based on first-order predicate logic theory and consists of three primary components. First, we construct two heterogeneous logical graphs to model logical relationships within and between propositions. Second, we propose a novel Graph-Masked Transformer with a novel graph-masked multi-head attention mechanism to enable distant node interactions and local sparse relationship modeling. Third, we propose a novel multi-branch fusion module to integrate information from multiple sources and generate answer predictions. The proposed heterogeneous-branch integration framework outperforms the VDGN method by 2.73% in accuracy on the ReClor dataset and 2.15% on the LogiQA dataset. Our code and models will be made available at https://github.com/starry-y/HBI. [ABSTRACT FROM AUTHOR]

The study of coherent association rules based on propositional logic is an important area of association rule mining. Users may get a large number of itemsets for low minsup and lose valuable itemsets for high minsup. Mining without minsup may cause itemset explosions that contain spurious itemsets with low correlations and take a long time to mine. For mining coherence rules, existing approaches consider only the frequent itemsets, ignoring rare itemsets. Moreover, all items in the database are regarded equally important, which is not practical in real-world applications. By using the confidence-lift specified multiple minimum supports combined with propositional logic, we propose an efficient approach called rare correlated coherent association rule mining that addresses all of the problems stated above. We define and incorporate termination bound of support (⁠|${s}_{TB}$|⁠) and termination bound of dissociation (⁠|${d}_{TB}$|⁠) for early pruning of the candidate itemsets. In the proposed approach, support thresholds are automatically applied to the itemsets and coherent association rules are derived from the frequent and rare itemsets with high correlation and confidence. Experimental results obtained from real-life datasets show the effectiveness of the proposed approach in terms of itemsets and rule generation, correlation, confidence, runtime and scalability. [ABSTRACT FROM AUTHOR]

Developing a suggestion of Wittgenstein, I provide an account of truth tables as formulas of a formal language. I define the syntax and semantics of TPL (the language of Tabular Propositional Logic) and develop its proof theory. Single formulas of TPL, and finite groups of formulas with the same top row and TF matrix (depiction of possible valuations), are able to serve as their own proofs with respect to metalogical properties of interest. The situation is different, however, for groups of formulas whose top rows differ. [ABSTRACT FROM AUTHOR]

The Tsetlin Machine (TM) is a recent machine learning algorithm with several distinct properties, such as interpretability, simplicity, and hardware-friendliness. Although numerous empirical evaluations report on its performance, the mathematical analysis of its convergence is still open. In this article, we analyze the convergence of the TM with only one clause involved for classification. More specifically, we examine two basic logical operators, namely, the “IDENTITY”- and “NOT” operators. Our analysis reveals that the TM, with just one clause, can converge correctly to the intended logical operator, learning from training data over an infinite time horizon. Besides, it can capture arbitrarily rare patterns and select the most accurate one when two candidate patterns are incompatible, by configuring a granularity parameter. The analysis of the convergence of the two basic operators lays the foundation for analyzing other logical operators. These analyses altogether, from a mathematical perspective, provide new insights on why TMs have obtained state-of-the-art performance on several pattern recognition problems. [ABSTRACT FROM AUTHOR]

This paper presents the multi-adjoint lattice logic (MLL) and its completeness and soundness. Specifically, the proposed many-valued propositional logic framework is defined on a multi-adjoint algebra whose underlying algebraic structure is a bounded lattice, which embeds the well-known basic logic (BL) given by Hájek on residuated lattices. The consideration of truth-stressing hedges in the multi-adjoint algebra is also studied and, as a consequence, two new logics extensions of MLL arise: the multi-adjoint lattice logic very true intensified (MLL v t) and the multi-adjoint lattice logic ∨-very true intensified (MLL ∨ − v t). Finally, the soundness and completeness of the aforementioned logics are also proven. [ABSTRACT FROM AUTHOR]

The overall purpose of the present work is to lay the foundations for a new approach to bridge logic and probabilistic computation. To this aim we introduce extensions of classical and intuitionistic propositional logic with counting quantifiers , that is, quantifiers that measure to which extent a formula is true. The resulting systems, called cCPL and iCPL , respectively, admit a natural semantics, based on the Borel σ -algebra of the Cantor space, together with a sound and complete proof system. Our main results consist in relating cCPL and iCPL with some central concepts in the study of probabilistic computation. On the one hand, the validity of cCPL -formulae in prenex form characterizes the corresponding level of Wagner's hierarchy of counting complexity classes, closely related to probabilistic complexity. On the other hand, proofs in iCPL correspond, in the sense of Curry and Howard, to typing derivations for a randomized extension of the λ -calculus, so that counting quantifiers reveal the probability of termination of the underlying probabilistic programs. [ABSTRACT FROM AUTHOR]