As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order (...) fragments can be used for constructing a tableau algorithm for the corresponding monodic fragment of FOTL. Some example instantiations of the framework are presented. (shrink)

In this paper, we present a goal-directed proof procedure for abductive reasoning. This procedure will be compared with Aliseda’s approach based on semantic tableaux. We begin with some comments on Aliseda’s algorithms for computing conjunctive abductions and show that they do not entirely live up to their aims. Next we give a concise account of goal-directed proofs and we show that abductive explanations are a natural spin-off of these proofs. Finally, we show that the goal-directed procedure solves the problems (...) we encountered in Aliseda’s algorithms. (shrink)

In this paper, we present a goal-directed proof procedure for abductive reasoning. This procedure will be compared with Aliseda’s approach based on semantic tableaux. We begin with some comments on Aliseda’s algorithms for computing conjunctive abductions and show that they do not entirely live up to their aims. Next we give a concise account of goal-directed proofs and we show that abductive explanations are a natural spin-off of these proofs. Finally, we show that the goal-directed procedure solves the problems (...) we encountered in Aliseda’s algorithms. (shrink)

We describe a class of semantic extensive entailment game with algorithmic players, related to game-theoretic semantics, and generalized to classical first-order semantic entailment. Players have preferences for parsimonious spending of computational resources, and compute partial strategies, under qualitative uncertainty about future histories. We prove the existence of local preferences for moves, and strategic fixpoints, that allow to map eeg game-tree to the building rules and closure rules of Smullyan's semantic tableaux. We also exhibit a strategy profile that solves the (...) fixpoint selection problem, and can be mapped to systematic constructions of semantic trees, yielding a completeness result by translation. We conclude on possible generalizations of our games. (shrink)

If semantic consequence is analyzed with extensive games, logical reasoning can be accounted for by looking at how players solve entailment games. However, earlier approaches to game semantics cannot achieve this reduction, by want of explicitly dened preferences for players. Moreover, although entailment games can naturally translate the idea of argumentation about a common ground, a cognitive interpretation is undermined by the complexity of strategic reasoning. We thus describe a class of semantic extensive entailment game with algorithmic players, who have (...) preferences for parsimonious spending of computational resources and thus compute partial strategies under qualitative uncertainty about future histories. We prove the existence of local preferences for moves and of strategic fixpoints that allow to map game-trees to tableaux proofs, and exhibit a strategy prole that solves the fixpoint selection problem, and can be mapped to systematic constructions of semantic trees, yielding a completeness result by translation. We then discuss the correspondence between proof heuristics and strategies in our games, the relations of our games to gts, and possible extensions to other entailment relations. We conclude that the main interest of our result lies in the possibility to bridge argumentative and cognitive models of logical reasoning, rather than in new meta-theoretic results. All proofs are given in appendix. (shrink)

By introducing and extending description logic (DLs) and growing up their application in knowledge representation and especially in OWLs and semantic web scope, many shortcomings and bugs were identified that weren’t resolvable in classical DLs and so logicians and computer scientists intended to non-classical and non-monotonic reasoning tools. In this paper, I discuses about abduction problem solvers, and by introducing A-Box abduction in description logics (DLs), such as ALC, discuss about decidability and complexity in different introduced algorithms, and report shortly (...) our team’s advantages in developing and implementation of ΑBox abduction in DLs. (shrink)

The Polish logician Roman Suszko has extensively pleaded in the 1970s for a restatement of the notion of many-valuedness. According to him, as he would often repeat, “there are but two logical values, true and false.” As a matter of fact, a result by W´ojcicki-Lindenbaum shows that any tarskian logic has a many-valued semantics, and results by Suszko-da Costa-Scott show that any many-valued semantics can be reduced to a two-valued one. So, why should one even consider using logics with more (...) than two values? Because, we argue, one has to decide how to deal with bivalence and settle down the tradeoff between logical 2-valuedness and truth-functionality, from a pragmatical standpoint. -/- This paper will illustrate the ups and downs of a two-valued reduction of logic. Suszko’s reductive result is quite non-constructive.We will exhibit here a way of effectively constructing the two-valued semantics of any logic that has a truth-functional finite-valued semantics and a sufficiently expressive language. From there, as we will indicate, one can easily go on to provide those logics with adequate canonical systems of sequents or tableaux. The algorithmic methods developed here can be generalized so as to apply to many non-finitely valued logics as well —or at least to those that admit of computable quasi tabular two-valued semantics, the so-called dyadic semantics. (shrink)

A concise yet rigorous introduction to logic and discrete mathematics. This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade. The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics of classical (...) logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual. Key Features: Suitable for a variety of courses for students in both Mathematics and Computer Science. Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection of the most important fields of discrete mathematics Concise, clear and uncluttered presentation with numerous examples. Covers some applications including cryptographic systems, discrete probability and network algorithms. Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study. (shrink)

Mathematical Logic for Computer Science is a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of computer science students. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and yet sufficiently elementary for undergraduates. To provide a balanced treatment of logic, tableaux are related to deductive proof systems.The logical systems presented are:- Propositional calculus (including binary decision diagrams);- Predicate calculus;- Resolution;- Hoare (...) logic;- Z;- Temporal logic.Answers to exercises (for instructors only) as well as Prolog source code for algorithms may be found via the Springer London web site: http://www.springer.com/978-1-85233-319-5 Mordechai Ben-Ari is an associate professor in the Department of Science Teaching of the Weizmann Institute of Science. He is the author of numerous textbooks on concurrency, programming languages and logic, and has developed software tools for teaching concurrency. In 2004, Ben-Ari received the ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education. (shrink)

We investigate a simple game paradigm for intuitionistic logic, inspired by Wajsberg’s implicit inhabitation algorithm and Beth tableaux. The principal idea is that one player, ∃ros, is trying to construct a proof in normal form while his opponent, ∀phrodite, attempts to build a counter-model. The determinacy of the game implies therefore both completeness and semantic cut-elimination.

Solving numeric, logic and language puzzles and paradoxes is common within a wide community of high school and university students, fact witnessed by the increasing number of books published by mathematicians such as Martin Gardner, Douglas Hofstadter [in one of the best popular science books on paradoxes ], inspired by Gödel’s incompleteness theorems), Patrick Hughes and George Brecht and Raymond M. Smullyan, inter alia. Books by Smullyan are, however, much more involved, since they introduce learning trajectories and strategies across several (...) subjects of mathematical logic, as difficult as combinatorial logic, computability theory, and proof theory. These books provide solutions to their suggested exercises. Both statements and their solutions are written in the natural language, introducing some informal algorithms. As an exercise in Mathematics we wonder if an easy proof system could be devised to solve the amusing equations proposed by Smullyan in his books. Moreover, university students of logic could well train themselves in constructing deductive systems to solve puzzles instead of a non-uniform treatment one by one. In this paper, addressing students, we introduce one such formal systems, a tableaux approach able to provide the solutions to the puzzles involving either propositional logic, first order logic, or aspect logic. Let the reader amuse herself or himself! (shrink)

In this paper a uniform methodology to perform natural\ndeduction over the family of linear, relevance and intuitionistic\nlogics is proposed. The methodology follows the Labelled\nDeductive Systems (LDS) discipline, where the deductive process\nmanipulates {\em declarative units} -- formulas {\em labelled}\naccording to a {\em labelling algebra}. In the system described\nhere, labels are either ground terms or variables of a given {\em\nlabelling language} and inference rules manipulate formulas and\nlabels simultaneously, generating (whenever necessary)\nconstraints on the labels used in the rules. A set of natural\ndeduction style (...) inference rules is given, and the notion of a\n{\em derivation} is defined which associates a labelled natural\ndeduction style ``structural derivation'' with a set of generated\nconstraints. Algorithmic procedures, based on a technique called\n{\em resource abduction\/}, are defined to solve the constraints\ngenerated within a structural derivation, and their termination\nconditions discussed. A natural deduction derivation is then\ndefined to be {\em correct} with respect to a given substructural\nlogic, if, under the condition that the algorithmic procedures\nterminate, the associated set of constraints is satisfied with\nrespect to the underlying labelling algebra. Finally, soundness\nand completeness of the natural deduction system are proved with\nrespect to the LKE tableaux system \cite{daga:LAD}.\footnote{Full\nversion of a paper presented at the {\em 3rd Workshop on Logic,\nLanguage, Information and Computation\/} ({\em WoLLIC'96\/}), May\n8--10, Salvador (Bahia), Brazil, organised by Univ.\ Federal de\nPernambuco (UFPE) and Univ.\ Federal da Bahia (UFBA), and\nsponsored by IGPL, FoLLI, and ASL.}. (shrink)

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

In this paper we present tableau methods for two-dimensional modal logics. Although models for such logics are well known, proof systems remain rather unexplored as most of their developments have been purely axiomatic. The logics herein considered contain first-order quantifiers with identity, and all the formulas in the language are doubly-indexed in the proof systems, with the upper indices intuitively representing the actual or reference worlds, and the lower indices representing worlds of evaluation—first and second dimensions, respectively. The tableaux (...) modulate over different notions of validity such as local, general, and diagonal, besides being general enough for several two-dimensional logics proposed in the literature. We also motivate the introduction of a new operator into two-dimensional languages and explore some of the philosophical questions raised by it concerning the relations there are between actuality, necessity, and the a priori, that seem to undermine traditional intuitive interpretations of two-dimensional operators. (shrink)

We offer tableaux systems for logics of essence and accident and logics of non-contingency, showing their soundness and completeness for Kripke semantics. We also show an interesting parallel between these logics based on the semantic insensitivity of the two non-normal operators by which these logics are expressed.

The tableaux-constructions have a number of properties which advantageously distinguish them from equivalent axiomatic systems . The proofs in the form of tableaux-constructions have a full accordance with semantic interpretation and subformula property in the sense of Gentzen’s Hauptsatz. Method of tatleaux-construction gives a good substitute of Gentzen’s methods and thus opens a good perspective for the investigations of theoretical as well as applied aspects of logical calculi. It should be noted that application of tableau method in modal, (...) tense, relevant and other non-classical logics is connected with serious difficulties. Tableaux variants are constructed only for a few normal modal systems. As to relevant and paraconsistent logic, the absence of its tableau variants may be considered as a question of special interest. We shall formulate the tableaux for propositional modal system S4.1, S4.2, S4.3, S4.4 and relevant R∗ and E ∗ using Beth’s tableaux construction with indexed formulas. (shrink)

Motivated by H. Curry’s well-known objection and by a proposal of L. Henkin, this article introduces the positive tableaux, a form of tableau calculus without refutation based upon the idea of implicational triviality. The completeness of the method is proven, which establishes a new decision procedure for the (classical) positive propositional logic. We also introduce the concept of paratriviality in order to contribute to the question of paradoxes and limitations imposed by the behavior of classical implication.

In this work, we shall study structural abduction and how ways of searching for solutions to the corresponding abductive problems could be modeled. Specifically, we shall define modal semantic tableaux for normal modal systems and study its applications to structural abduction. This method even makes structural abduction clearer and, as it shall be seen, when a radical change of logic is epistemologically required, the corresponding tableau will have pertinent information to suggest it.

In the paper, we examine tableau systems for R. Epstein’s logics of content relationship: D (Dependence Logic), DD (Dual Dependence Logic), Eq (Logic of Equality of Content), S (Symmetric Relatedness Logic) and R (Nonsymmetric Relatedness Logic) (cf. Epstein in Philos Stud 36:137–173, 1979, Epstein in Rep. Math. Logic 21:19–34, 1987, Klonowski in Logic Log Philos 30(4):579–629, 2021, Krajewski in J Non Class Logic 8:7–33, 1991). The first tableau systems for those logics were defined by Carnielli. However, his approach has some (...) limitations, for example, it requires a proof of functional completeness and axiomatization. Notwithstanding the first two constraints, it does not include all Epstein logics, e.g., logic Eq. Unlike Carnielli’s approach, here we use set-assignment semantics to determine those logics. Since syntax and semantics of a given logic usually determine a minimal syntax and structure of a tableau system for the logic along with other properties, we propose a uniform tableau framework for the logics determined by set-assignment semantics. What distinguishes our tableau systems is that they combine the features of tableaux for propositional logics and syllogistic logics when the problem of content of propositions is analysed in tableau proofs. To denote the content of propositions in the proofs, we use generalised labels (see Jarmużek and Goré in Landscapes in Logic, College Publications, London, 2021). (shrink)

Algorithms can now identify patterns and correlations in the (big) datasets, and predict outcomes based on those identified patterns and correlations with the use of machine learning techniques and big data, decisions can then be made by algorithms themselves in accordance with the predicted outcomes. Yet, algorithms can inherit questionable values from the datasets and acquire biases in the course of (machine) learning, and automated algorithmic decision-making makes it more difficult for people to see algorithms as biased. While researchers have (...) taken the problem of algorithmic bias seriously, but the current discussion on algorithmic fairness tends to conceptualize ‘fairness’ in algorithmic fairness primarily as a technical issue and attempts to implement pre-existing ideas of ‘fairness’ into algorithms. In this paper, I show that such a view of algorithmic fairness as technical issue is unsatisfactory for the type of problem algorithmic fairness presents. Since decisions on fairness measure and the related techniques for algorithms essentially involve choices between competing values, ‘fairness’ in algorithmic fairness should be conceptualized first and foremost as a political issue, and it should be (re)solved by democratic communication. The aim of this paper, therefore, is to explicitly reconceptualize algorithmic fairness as a political question and suggest the current discussion of algorithmic fairness can be strengthened by adopting the accountability for reasonableness framework. (shrink)

Should decision-making algorithms be held to higher standards of transparency than human beings? The way we answer this question directly impacts what we demand from explainable algorithms, how we govern them via regulatory proposals, and how explainable algorithms may help resolve the social problems associated with decision making supported by artificial intelligence. Some argue that algorithms and humans should be held to the same standards of transparency and that a double standard of transparency is hardly justified. We give two arguments (...) to the contrary and specify two kinds of situations for which higher standards of transparency are required from algorithmic decisions as compared to humans. Our arguments have direct implications on the demands from explainable algorithms in decision-making contexts such as automated transportation. (shrink)

We show how to correct the analytic tableaux system from the paper Olkhovikov and Wansing, 259–279, 2018).

Wittgensteinian predicate logic (W-logic) is characterized by the requirement that the objects mentioned within the scope of a quantifier be excluded from the range of the associated bound variable. I present a sound and complete tableaux calculus for this logic and discuss issues of translatability between Wittgensteinian and standard predicate logic in languages with and without individual constants. A metalinguistic co-denotation predicate, akin to Frege’s triple bar of the Begriffsschrift, is introduced and used to bestow the full expressive power (...) of first-order logic with identity on W-logic in the presence of constants. (shrink)

Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with interactions between time and (...) knowledge. We discuss some complications that occur, even in the single-agent case, when interactions between time and knowledge are assumed and show how the method of incremental tableaux can be adapted to work in EXPSPACE, respectively 2EXPTIME, for these logics, thereby also matching the upper bounds obtained for them by Halpern and Vardi. (shrink)

In this dissertation we present proof systems for several modal logics. These proof systems are based on analytic (or semantic) tableaux. -/- Modal logics are logics for reasoning about possibility, knowledge, beliefs, preferences, and other modalities. Their semantics are almost always based on Saul Kripke’s possible world semantics. In Kripke semantics, models are represented by relational structures or, equivalently, labeled graphs. Syntactic formulas that express statements about knowledge and other modalities are evaluated in terms of such models. -/- This (...) dissertation focuses on modal logics with dynamic operators for public announcements, belief revision, preference upgrades, and so on. These operators are defined in terms of mathematical operations on Kripke models. Thus, for example, a belief revision operator in the syntax would correspond to a belief revision operation on models. -/- The ‘dynamic’ semantics of dynamic modal logics are a clever way of extending languages without compromising on intuitiveness. We present ‘dynamic’ tableau proof systems for these dynamic semantics, with the express aim to make them conceptually simple, easy to use, modular, and extensible. This we do by reflecting the semantics as closely as possible in the components of our tableau system. For instance, dynamic operations on Kripke models have counterpart dynamic relations between tableaux. -/- Soundness, completeness, and decidability are three of the most important properties that a proof system may have. A proof system is sound if and only if any formula for which a proof exists, is true in every model. A proof system is complete if and only if for any formula that is true in all models, a proof exists. A proof system is decidable if and only if any formula can be proved to be a theorem or not a theorem in a finite number of steps. All proof systems in this dissertation are sound, complete, and decidable. -/- Part of our strategy to create modular tableau systems is to delay concerns over decidability until after soundness and completeness have been established. Decidability is attained through the operations of folding and through operations on ‘tableau cascades’, which are graphs of tableaux. -/- Finally, we provide a proof-of-concept implementation of our dynamic tableau system for public announcement logic in the Clojure programming language. (shrink)

The book presents logical foundations of dual tableaux together with a number of their applications both to logics traditionally dealt with in mathematics and philosophy (such as modal, intuitionistic, relevant, and many-valued logics) and to various applied theories of computational logic (such as temporal reasoning, spatial reasoning, fuzzy-set-based reasoning, rough-set-based reasoning, order-of magnitude reasoning, reasoning about programs, threshold logics, logics of conditional decisions). The distinguishing feature of most of these applications is that the corresponding dual tableaux are built (...) in a relational language which provides useful means of presentation of the theories. In this way modularity of dual tableaux is ensured. We do not need to develop and implement each dual tableau from scratch, we should only extend the relational core common to many theories with the rules specific for a particular theory. (shrink)

In this paper we present a new hierarchy of analytical tableaux systems TNDC n, 1≤n<ω, for da Costa's hierarchy of propositional paraconsistent logics Cn, 1≤n<ω. In our tableaux formulation, we introduce da Costa's “ball” operator “o”, the generalized operators “k” and “(k)”, for 1≤k, and the negations “~k”, for k≥1, as primitive operators, differently to what has been done in the literature, where these operators are usually defined operators. We prove a version of Cut Rule for the TNDC (...) n, 1≤n<ω, and also prove that these systems are logically equivalent to the corresponding systems Cn, 1≤n<ω. The systems TNDC n constitute completely automated theorem proving systems for the systems of da Costa's hierarchy Cn, 1≤n<ω. (shrink)

The inference systems proposed for solving SAT are unsound for solving MaxSAT and MinSAT, because they preserve satisfiability but not the minimum and maximum number of clauses that can be falsified, respectively. To address this problem, we first define a clause tableau calculus for MaxSAT and prove its soundness and completeness. We then define a clause tableau calculus for MinSAT and also prove its soundness and completeness. Finally, we define a complete clause tableau calculus for solving both MaxSAT and MinSAT, (...) in that the minimum number of generated empty clauses provides an optimal MaxSAT solution and the maximum number provides an optimal MinSAT solution. (shrink)

Machine intelligence already helps medical staff with a number of tasks. Ethical decision-making, however, has not been handed over to computers. In this proof-of-concept study, we show how an algorithm based on Beauchamp and Childress’ prima-facie principles could be employed to advise on a range of moral dilemma situations that occur in medical institutions. We explain why we chose fuzzy cognitive maps to set up the advisory system and how we utilized machine learning to train it. We report on (...) the difficult task of operationalizing the principles of beneficence, non-maleficence and patient autonomy, and describe how we selected suitable input parameters that we extracted from a training dataset of clinical cases. The first performance results are promising, but an algorithmic approach to ethics also comes with several weaknesses and limitations. Should one really entrust the sensitive domain of clinical ethics to machine intelligence? (shrink)

The forward convergence constraint is important to time analysis. Without it, given two future moments to the same point, the time branches. This is unacceptable if one assumes that time is linear. Nevertheless, one may wish to consider time-branching in order to discuss future possibilities. One can have both a linear order for the time and branching through the combination of the tense logic semantics with those of an alethic logic which allows the evaluation of the timelines of other possible (...) worlds. In this paper, I give the semantics and the tableaux systems for some alethic-tense logics. I review one in which worlds differ on their time orders, another in which they agree on the time order, a pair of conditional tense logics ), and the first-order version of MT. A brief philosophical discussion arises from every system. (shrink)

In recent years, the ethical impact of AI has been increasingly scrutinized, with public scandals emerging over biased outcomes, lack of transparency, and the misuse of data. This has led to a growing mistrust of AI and increased calls for mandated ethical audits of algorithms. Current proposals for ethical assessment of algorithms are either too high level to be put into practice without further guidance, or they focus on very specific and technical notions of fairness or transparency that do not (...) consider multiple stakeholders or the broader social context. In this article, we present an auditing framework to guide the ethical assessment of an algorithm. The audit instrument itself is comprised of three elements: a list of possible interests of stakeholders affected by the algorithm, an assessment of metrics that describe key ethically salient features of the algorithm, and a relevancy matrix that connects the assessed metrics to stakeholder interests. The proposed audit instrument yields an ethical evaluation of an algorithm that could be used by regulators and others interested in doing due diligence, while paying careful attention to the complex societal context within which the algorithm is deployed. (shrink)

It is well-established that algorithms can be instruments of injustice. It is less frequently discussed, however, how current modes of AI deployment often make the very discovery of injustice difficult, if not impossible. In this article, we focus on the effects of algorithmic profiling on epistemic agency. We show how algorithmic profiling can give rise to epistemic injustice through the depletion of epistemic resources that are needed to interpret and evaluate certain experiences. By doing so, we not only demonstrate how (...) the philosophical conceptual framework of epistemic injustice can help pinpoint potential, systematic harms from algorithmic profiling, but we also identify a novel source of hermeneutical injustice that to date has received little attention in the relevant literature: epistemic fragmentation. Epistemic fragmentation is a structural characteristic of algorithmically-mediated environments that isolate individuals, making it more difficult to develop, uptake and apply new epistemic resources. This, in turn, can impede the identification and conceptualisation of emerging harms in these environments. We trace the occurrence of hermeneutical injustice back to the fragmentation of the epistemic experiences of individuals, who are left more vulnerable by the inability to share, compare, and learn from shared experiences. (shrink)

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.

In this paper we give an analytic tableau calculus P L 1 6 for a functionally complete extension of Shramko and Wansing’s logic. The calculus is based on signed formulas and a single set of tableau rules is involved in axiomatising each of the four entailment relations ⊧ t, ⊧ f, ⊧ i, and ⊧ under consideration—the differences only residing in initial assignments of signs to formulas. Proving that two sets of formulas are in one of the first three entailment (...) relations will in general require developing four tableaux, while proving that they are in the ⊧ relation may require six. (shrink)

Algorithms wield increasing control over our lives—over which jobs we get, whether we're granted loans, what information we're exposed to online, and so on. Algorithms can, and often do, wield their power in a biased way, and much work has been devoted to algorithmic bias. In contrast, algorithmic neutrality has gone largely neglected. I investigate three questions about algorithmic neutrality: What is it? Is it possible? And when we have it in mind, what can we learn about algorithmic bias?

Priest has provided a simple tableau calculus for Chellas's conditional logic Ck. We provide rules which, when added to Priest's system, result in tableau calculi for Chellas's CK and Lewis's VC. Completeness of these tableaux, however, relies on the cut rule.

Algorithmic communications pose several challenges to democracy. The three phenomena of filtering, hypernudging, and microtargeting can have the effect of polarizing an electorate and thus undermine the deliberative potential of a democratic society. Algorithms can spread fake news throughout the society, undermining the epistemic potential that broad participation in democracy is meant to offer. They can pose a threat to political equality in that some people may have the means to make use of algorithmic communications and the sophistication to be (...) immune from attempts at manipulation, while other people are vulnerable to manipulation by those who use these means. My concern here is with the danger that algorithmic communications can pose to political equality, which arises because most citizens must make decisions about what and who to support in democratic politics with only a sparse budget of time, money, and energy. Algorithmic communications such as hypernudging and microtargeting can be a threat to democratic participation when persons are operating in environments that do not conduce to political sophistication. This constitutes a deepening of political inequality. The political sophistication necessary to counter this vulnerability is rooted for many in economic life and it can and ought to be enhanced by changing the terms of economic life. (shrink)

Throughout the last decade, there has been an increased interest in various forms of dynamic epistemic logics to model the flow of information and the effect this flow has on knowledge in multi-agent systems. This enterprise, however, has mostly been applicationally and semantically driven. This results in a limited amount of proof theory for dynamic epistemic logics. In this paper, we try to compensate for a part of this by presenting terminating tableau systems for full dynamic epistemic logic with action (...) models and for a hybrid public announcement logic. The tableau systems are extensions of already existing tableau systems, in addition to which we have used the reduction axioms of dynamic epistemic logic to define rules for the dynamic part of the logics. Termination is shown using methods introduced by Braüner, Bolander, and Blackburn. (shrink)

Algorithms influence every facet of modern life: criminal justice, education, housing, entertainment, elections, social media, news feeds, work… the list goes on. Delegating important decisions to machines, however, gives rise to deep moral concerns about responsibility, transparency, freedom, fairness, and democracy. Algorithms and Autonomy connects these concerns to the core human value of autonomy in the contexts of algorithmic teacher evaluation, risk assessment in criminal sentencing, predictive policing, background checks, news feeds, ride-sharing platforms, social media, and election interference. Using these (...) case studies, the authors provide a better understanding of machine fairness and algorithmic transparency. They explain why interventions in algorithmic systems are necessary to ensure that algorithms are not used to control citizens' participation in politics and undercut democracy. This title is also available as Open Access on Cambridge Core. (shrink)

From picture to photography and back. Tableau vivants, in their gestural synthetic dimension, represent for Diderot the apex of expression that the image can make explicit. Nothing closer to Wall’s poetics. His works show outstanding attention to detail: from scenic design to protagonists’ costumes, from light to actors’ action. And the result is exactly what Diderot saw in the eyes of people observing Chardin’s art: imagination at work.

The paper describes tableaux based proof methods for temporal logics of knowledge allowing non-trivial interaction axioms between the modal and temporal components, namely those of synchrony and no learning and synchrony and perfect recall. The interaction axioms allow the description of how knowledge evolves over time and makes reasoning in such logics theoretically more complex. Such logics can be used to specify systems that involve the knowledge of processes or agents and which change over time, for example agent based (...) systems, knowledge games or security protocols. Soundness, completeness and termination results for the tableaux are proved. (shrink)

This is the first paper on constructive concurrent dynamic logic . For the first time, either for concurrent or sequential dynamic logic, we give a satisfactory treatment of what statements are forced to be true by partial information about the underlying computer. Dynamic logic was developed by Pratt [V. Pratt, Semantical considerations on Floyd–Hoare logic, in: 17th Annual IEEE Symp. on Found. Comp. Sci., New York, 1976, pp. 109–121, V. Pratt, Applications of modal logic to programming, Studia Logica 39 257–274] (...) for nondeterministic sequential programs, and by Peleg [D. Peleg, Concurrent dynamic logic, Journal of the Association for Computing Machinery 34 , D. Peleg, Communication in concurrent dynamic logic, Journal of Computer and System Sciences 35 ] for concurrent programs, for the purpose of proving properties of programs such as correctness. Here we define what it means for a dynamic logic formula to be forced to be true knowing only partial information about the results of assignments and tests. This informal CCDL semantics is formalized by intuitionistic Kripke frames modeling this partial information, and each such frame is interpreted as an idealized concurrent machine . In CCDL, proofs and deductions are ω-height, ω-branching, well-founded labeled subtrees of ωω. These are a generalization of the signed tableaux of Nerode [A. Nerode, Some lectures in modal logic, Technical Report, M.S.I. Cornell University, 1989, CIME Logic and Computer Science Montecatini Volume, Springer-Verlag Lecture Notes, 1990, A. Nerode, Some lectures in intuitionistic logic, Technical Report, M.S.I. Cornell University, 1988, Marktoberdorf Logic and Computation NATO Summer School Volume, NATO Science Series, 1990 ] stemming from the prefix tableaux of Fitting [M.C. Fitting, Proof Methods for Modal and Intuitionistic Logic, Reidel, 1983]. We demonstrate the correctness of our tableau proofs, define consistency properties, prove that consistency properties yield models, construct systematic tableaux, prove that systematic tableaux yield a consistency property, and conclude that CCDL is complete. This infinitary semantics and proof procedure will be the primary guide for defining, in a sequel, the correct finitary CCDL based on induction principles. FCCDL is suitable for implementation in constructive logic software systems such as Constable’s NUPRL or Huet-Coquand’s CONSTRUCTIONS. Our goal is to develop a constructive logic programming tool for specification and modular verification of programs in any imperative concurrent language, and for the extraction of concurrent programs from constructive proofs. Subsequent papers will introduce analogous logics for declarative and functional concurrent languages. (shrink)

Algorithmic systems and predictive analytics play an increasingly important role in various aspects of modern life. Scholarship on the moral ramifications of such systems is in its early stages, and much of it focuses on bias and harm. This paper argues that in understanding the moral salience of algorithmic systems it is essential to understand the relation between algorithms, autonomy, and agency. We draw on several recent cases in criminal sentencing and K–12 teacher evaluation to outline four key ways in (...) which issues of agency, autonomy, and respect for persons can conflict with algorithmic decision-making. Three of these involve failures to treat individual agents with the respect they deserve. The fourth involves distancing oneself from a morally suspect action by attributing one’s decision to take that action to an algorithm, thereby laundering one’s agency. (shrink)

The ever-increasing application of algorithms to decision-making in a range of social contexts has prompted demands for algorithmic accountability. Accountable decision-makers must provide their decision-subjects with justifications for their automated system’s outputs, but what kinds of broader principles should we expect such justifications to appeal to? Drawing from political philosophy, I present an account of algorithmic accountability in terms of the democratic ideal of ‘public reason’. I argue that situating demands for algorithmic accountability within this justificatory framework enables us to (...) better articulate their purpose and assess the adequacy of efforts toward them. (shrink)

Decision-making assisted by algorithms developed by machine learning is increasingly determining our lives. Unfortunately, full opacity about the process is the norm. Would transparency contribute to restoring accountability for such systems as is often maintained? Several objections to full transparency are examined: the loss of privacy when datasets become public, the perverse effects of disclosure of the very algorithms themselves, the potential loss of companies’ competitive edge, and the limited gains in answerability to be expected since sophisticated algorithms usually are (...) inherently opaque. It is concluded that, at least presently, full transparency for oversight bodies alone is the only feasible option; extending it to the public at large is normally not advisable. Moreover, it is argued that algorithmic decisions preferably should become more understandable; to that effect, the models of machine learning to be employed should either be interpreted ex post or be interpretable by design ex ante. (shrink)