Propositional logic
≈ 14 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Propositional logic is a branch of classical logic. It is also called statement logic, sentential calculus, propositional calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called first-order propositional logic to contrast it with System F, but it is distinct from first-order logic. It deals with propositions (which can be true or false) and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives representing the truth functions of conjunction, disjunction, implication, biconditional, and negation. Some sources include other connectives, as in the table below. Unlike first-order logic, propositional logic does not deal with non-logical objects, predicates about them, or quantifiers. However, all the machinery of propositional logic is included in first-order logic and higher-order logics. In this sense, propositional logic is the foundation of first-order logic and higher-order logic. Propositional logic is typically studied with a formal language, in which propositions are represented by letters, which are called propositional variables. These are then used, together with symbols for connectives, to make propositional formulas. Because of this, the propositional variables are called atomic formulas of a formal propositional language.…
Propositional logic is a branch of classical logic. It is also called statement logic, sentential calculus, propositional calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called first-order propositional logic to contrast it with System F, but it is distinct from first-order logic. It deals with propositions (which can be true or false) and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives representing the truth functions of conjunction, disjunction, implication, biconditional, and negation. Some sources include other connectives, as in the table below. Unlike first-order logic, propositional logic does not deal with non-logical objects, predicates about them, or quantifiers. However, all the machinery of propositional logic is included in first-order logic and higher-order logics. In this sense, propositional logic is the foundation of first-order logic and higher-order logic. Propositional logic is typically studied with a formal language, in which propositions are represented by letters, which are called propositional variables. These are then used, together with symbols for connectives, to make propositional formulas. Because of this, the propositional variables are called atomic formulas of a formal propositional language. While the atomic propositions are typically represented by letters of the alphabet, there is a variety of notations to represent the logical connectives. For the benefit of readers who may only be used to a different variant notation for the logical connectives, the following table shows the main notational variants for each of the connectives in propositional logic. Other notations have been used historically, such as Polish notation. For the history of each of these symbols, see the respective articles as well as the article "Logical connective". The most thoroughly researched branch of propositional logic is classical truth-functional propositional logic, in which formulas are interpreted as having precisely one of two possible truth values, the truth value of true or the truth value of false. The principle of bivalence and the law of excluded middle are upheld. By comparison with first-order logic, truth-functional propositional logic is considered to be zeroth-order logic.
Sentences
Propositional logic, as currently studied in universities, is a specification of a standard of logical consequence in which only the meanings of propositional connectives are considered in evaluating the conditions for the truth of a sentence, or whether a sentence logically follows from some other sentence or group of sentences.
Language
The language (commonly called \mathcal{L} ) of a propositional calculus is defined in terms of: a set of primitive symbols, called atomic formulas, atomic sentences, atoms, placeholders, prime formulas, proposition letters, sentence letters, or variables, and a set of operator symbols, called connectives, logical connectives, logical operators, truth-functional connectives, truth-functors, or propositional connectives. A well-formed formula is any atomic formula, or any formula that can be built up from atomic formulas by means of operator symbols according to the rules of the grammar. The language \mathcal{L} , then, is defined either as being identical to its set of well-formed formulas, or as containing that set (together with, for instance, its set of connectives and variables). Usually the syntax of \mathcal{L} is defined recursively by just a few definitions, as seen next; some authors explicitly include parentheses as punctuation marks when defining their language's syntax, while others use them without comment. \phi ::= a_1, a_2, \ldots ~ | ~ \neg\phi ~ | ~ \phi ~ \& ~ \psi ~ | ~ \phi \vee \psi ~ | ~ \phi \rightarrow \psi ~ | ~ \phi \leftrightarrow \psi This clause, due to its self-referential nature (since \phi is in some branches of the definition of \phi ), also acts as a recursive definition, and therefore specifies the entire language. To expand it to add modal operators, one need only add ... | ~ \Box\phi ~ | ~ \Diamond\phi to the end of the clause. For a given language \mathcal{L} , an interpretation, valuation, Boolean valuation, or case, is an assignment of semantic values to each formula of \mathcal{L} . For a formal language of classical logic, a case is defined as an assignment, to each formula of \mathcal{L} , of one or the other, but not both, of the truth values, namely truth (T, or 1) and falsity (F, or 0). An interpretation that follows the rules of classical logic is sometimes called a Boolean valuation. An interpretation of a formal language for classical logic is often expressed in terms of truth tables. Since each formula is only assigned a single truth-value, an interpretation may be viewed as a function, whose domain is \mathcal{L} , and whose range is its set of semantic values \mathcal{V} = \{\mathsf{T}, \mathsf{F}\} , or \mathcal{V} = \{1, 0\} . For n distinct propositional symbols there are 2^n distinct possible interpretations. For any particular symbol a , for example, there are 2^1=2 possible interpretations: either a is assigned T, or a is assigned F. And for the pair a , b there are 2^2=4 possible interpretations: either both are assigned T, or both are assigned F, or a is assigned T and b is assigned F, or a is assigned F and b is assigned T. Since \mathcal{L} has \aleph_0 , that is, denumerably many propositional symbols, there are 2^{\aleph_0}=\mathfrak c , and therefore uncountably many distinct possible interpretations of \mathcal{L} as a whole. Where \mathcal{I} is an interpretation and \varphi and \psi represent formulas, the definition of an argument, given in , may then be stated as a pair \langle \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} , \psi \rangle , where \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} is the set of premises and \psi is the conclusion. The definition of an argument's validity, i.e. its property that \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} \models \psi , can then be stated as its absence of a counterexample, where a counterexample is defined as a case \mathcal{I} in which the argument's premises \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} are all true but the conclusion \psi is not true. As will be seen in , this is the same as to say that the conclusion is a semantic consequence of the premises. \mathcal{I}(\neg P) = \mathsf{T} if, and only if, \mathcal{I}(P) = \mathsf{F} \mathcal{I}(P \land Q) = \mathsf{T} if, and only if, \mathcal{I}(P) = \mathsf{T} and \mathcal{I}(Q) = \mathsf{T} \mathcal{I}(P \lor Q) = \mathsf{T} if, and only if, \mathcal{I}(P) = \mathsf{T} or \mathcal{I}(Q) = \mathsf{T} \mathcal{I}(P \to Q) = \mathsf{T} if, and only if, it is true that, if \mathcal{I}(P) = \mathsf{T} , then \mathcal{I}(Q) = \mathsf{T} \mathcal{I}(P \leftrightarrow Q) = \mathsf{T} if, and only if, it is true that \mathcal{I}(P) = \mathsf{T} if, and only if, \mathcal{I}(Q) = \mathsf{T} Instead of \mathcal{I}(\varphi) , the interpretation of \varphi may be written out as |\varphi| , or, for definitions such as the above, \mathcal{I}(\varphi) = \mathsf{T} may be written simply as the English sentence " \varphi is given the value \mathsf{T} ". Yet other authors may prefer to speak of a Tarskian model \mathfrak{M} for the language, so that instead they'll use the notation \mathfrak{M} \models \varphi , which is equivalent to saying \mathcal{I}(\varphi) = \mathsf{T} , where \mathcal{I} is the interpretation function for \mathfrak{M} .
Proof systems
Proof systems in propositional logic can be broadly classified into semantic proof systems and syntactic proof systems, according to the kind of logical consequence that they rely on: semantic proof systems rely on semantic consequence ( \varphi \models \psi ), whereas syntactic proof systems rely on syntactic consequence ( \varphi \vdash \psi ). Semantic consequence deals with the truth values of propositions in all possible interpretations, whereas syntactic consequence concerns the derivation of conclusions from premises based on rules and axioms within a formal system. This section gives a very brief overview of the kinds of proof systems, with anchors to the relevant sections of this article on each one, as well as to the separate Wikipedia articles on each one.
Semantic proof systems
Semantic proof systems rely on the concept of semantic consequence, symbolized as \varphi \models \psi , which indicates that if \varphi is true, then \psi must also be true in every possible interpretation.
Truth tables
A truth table is a semantic proof method used to determine the truth value of a propositional logic expression in every possible scenario. By exhaustively listing the truth values of its constituent atoms, a truth table can show whether a proposition is true, false, tautological, or contradictory. See .
Semantic tableaux
A semantic tableau is another semantic proof technique that systematically explores the truth of a proposition. It constructs a tree where each branch represents a possible interpretation of the propositions involved. If every branch leads to a contradiction, the original proposition is considered to be a contradiction, and its negation is considered a tautology. See .
Syntactic proof systems
LK, in Gentzen notation Syntactic proof systems, in contrast, focus on the formal manipulation of symbols according to specific rules. The notion of syntactic consequence, \varphi \vdash \psi , signifies that \psi can be derived from \varphi using the rules of the formal system.
Axiomatic systems
A Hilbert-style axiomatic system, or Hilbert system, is a set of axioms or assumptions from which other statements (theorems) are logically derived. In propositional logic, axiomatic systems define a base set of propositions considered to be self-evidently true, and theorems are proved by applying deduction rules to these axioms. See .
Natural deduction
Natural deduction is a syntactic method of proof that emphasizes the derivation of conclusions from premises through the use of intuitive rules reflecting ordinary reasoning. Each rule reflects a particular logical connective and shows how it can be introduced or eliminated. See .
Sequent calculus
The sequent calculus is a formal system that represents logical deductions as sequences or "sequents" of formulas. Developed by Gerhard Gentzen, this approach focuses on the structural properties of logical deductions and provides a powerful framework for proving statements within propositional logic. Further, using the theorem that \varphi \models \psi if, and only if, (\varphi \to \psi) is valid, we can use a truth table to prove that a formula is a semantic consequence of a set of formulas: \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} \models \psi if, and only if, we can produce a truth table that comes out all true for the formula \left( \left(\bigwedge _{i=1}^n \varphi_i \right) \rightarrow \psi \right) (that is, if \models \left( \left(\bigwedge _{i=1}^n \varphi_i \right) \rightarrow \psi \right) ).
Proof example in P 2
As an example, a proof of A \to A in P 2 is given below. First, the axioms are given names: (A1) (p \to (q \to p)) (A2) ((p \to (q \to r)) \to ((p \to q) \to (p \to r))) (A3) ((\neg p \to \neg q) \to (q \to p)) And the proof is as follows: A \to ((B \to A) \to A) (instance of (A1)) (A \to ((B \to A) \to A)) \to ((A \to (B \to A)) \to (A \to A)) (instance of (A2)) (A \to (B \to A)) \to (A \to A) (from (1) and (2) by modus ponens) A \to (B \to A) (instance of (A1)) A \to A (from (4) and (3) by modus ponens)
Solvers
One notable difference between propositional calculus and predicate calculus is that satisfiability of a propositional formula is decidable. Deciding satisfiability of propositional logic formulas is an NP-complete problem. However, practical methods exist (e.g., DPLL algorithm, 1962; Chaff algorithm, 2001) that are very fast for many useful cases. Recent work has extended the SAT solver algorithms to work with propositions containing arithmetic expressions; these are the SMT solvers.
See also
Higher logical levels
First-order logic Second-order propositional logic Second-order logic Higher-order logic
Related topics
Boolean algebra (logic) Boolean algebra (structure) Boolean algebra topics Boolean domain Boolean function Boolean-valued function Categorical logic Combinational logic Combinatory logic Conceptual graph Disjunctive syllogism Entitative graph Equational logic Existential graph Implicational propositional calculus Intuitionistic propositional calculus Jean Buridan Laws of Form List of logic symbols Logical graph Logical NOR Logical value Mathematical logic Operation (mathematics) Paul of Venice Peirce's law Peter of Spain (author) Propositional formula Symmetric difference Tautology (rule of inference) Truth function Truth table Walter Burley William of Sherwood
Notes
References
Further reading
Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY. Chang, C.C. and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands. Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978. Korfhage, Robert R. (1974), Discrete Computational Structures, Academic Press, New York, NY. Lambek, J. and Scott, P.J. (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK. Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.
Related works
External links
Formal Predicate Calculus, contains a systematic formal development with axiomatic proof forall x: an introduction to formal logic, by P.D. Magnus, covers formal semantics and proof theory for sentential logic. Chapter 2 / Propositional Logic from Logic In Action Propositional sequent calculus prover on Project Nayuki. (note: implication can be input in the form !X|Y , and a sequent can be a single formula prefixed with > and having no commas) Propositional Logic - A Generative Grammar A Propositional Calculator that helps to understand simple expressions
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369692082 under CC BY-SA 4.0; modifications have been made.