The propositional calculus is a branch of
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
.
[ It is also called propositional logic,][ statement logic,][ sentential calculus,][ sentential logic,][ or sometimes zeroth-order logic.][ Sometimes, it is called ''first-order'' propositional logic][ to contrast it with System F, but it should not be confused with 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
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
, implication, biconditional, and negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
.[ 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 formula''. 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
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
,[ there is a variety of notations to represent the logical connectives. The following table shows the main notational variants for each of the connectives in propositional logic.
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 value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
s, 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''.][
]
History
Although propositional logic had been hinted by earlier philosophers, Chrysippus is often credited with development of a deductive system for propositional logic as his main achievement in the 3rd century BC[ which was expanded by his successor Stoics. The logic was focused on ]proposition
A proposition is a statement that can be either true or false. It is a central concept in the philosophy of language, semantics, logic, and related fields. Propositions are the object s denoted by declarative sentences; for example, "The sky ...
s. This was different from the traditional syllogistic logic, which focused on terms. However, most of the original writings were lost[ and, at some time between the 3rd and 6th century CE, Stoic logic faded into oblivion, to be resurrected only in the 20th century, in the wake of the (re)-discovery of propositional logic.][
]Symbolic logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
, which would come to be important to refine propositional logic, was first developed by the 17th/18th-century mathematician Gottfried Leibniz
Gottfried Wilhelm Leibniz (or Leibnitz; – 14 November 1716) was a German polymath active as a mathematician, philosopher, scientist and diplomat who is credited, alongside Isaac Newton, Sir Isaac Newton, with the creation of calculus in ad ...
, whose calculus ratiocinator was, however, unknown to the larger logical community. Consequently, many of the advances achieved by Leibniz were recreated by logicians like George Boole
George Boole ( ; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. H ...
and Augustus De Morgan, completely independent of Leibniz.[
Gottlob Frege's ]predicate logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables ove ...
builds upon propositional logic, and has been described as combining "the distinctive features of syllogistic logic and propositional logic."[ Consequently, predicate logic ushered in a new era in logic's history; however, advances in propositional logic were still made after Frege, including natural deduction, truth trees and truth tables. Natural deduction was invented by Gerhard Gentzen and Stanisław Jaśkowski. Truth trees were invented by Evert Willem Beth.][ The invention of truth tables, however, is of uncertain attribution.
Within works by Frege][ and ]Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British philosopher, logician, mathematician, and public intellectual. He had influence on mathematics, logic, set theory, and various areas of analytic ...
,[ are ideas influential to the invention of truth tables. The actual tabular structure (being formatted as a table), itself, is generally credited to either ]Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language.
From 1929 to 1947, Witt ...
or Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
(or both, independently).[ Besides Frege and Russell, others credited with having ideas preceding truth tables include Philo, Boole, ]Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American scientist, mathematician, logician, and philosopher who is sometimes known as "the father of pragmatism". According to philosopher Paul Weiss (philosopher), Paul ...
,[ and Ernst Schröder. Others credited with the tabular structure include ]Jan Łukasiewicz
Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic. His work centred on philosophical logic, mathematical logic and history of logi ...
, Alfred North Whitehead, William Stanley Jevons, John Venn
John Venn, Fellow of the Royal Society, FRS, Fellow of the Society of Antiquaries of London, FSA (4 August 1834 – 4 April 1923) was an English mathematician, logician and philosopher noted for introducing Venn diagrams, which are used in l ...
, and Clarence Irving Lewis.[ Ultimately, some have concluded, like John Shosky, that "It is far from clear that any one person should be given the title of 'inventor' of truth-tables".][
]
Sentences
Propositional logic, as currently studied in universities, is a specification of a standard of logical consequence
Logical consequence (also entailment or logical implication) is a fundamental concept in logic which describes the relationship between statement (logic), statements that hold true when one statement logically ''follows from'' one or more stat ...
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.[
]
Declarative sentences
Propositional logic deals with statements, which are defined as declarative sentences having truth value.[ Examples of statements might include:
* '']Wikipedia
Wikipedia is a free content, free Online content, online encyclopedia that is written and maintained by a community of volunteers, known as Wikipedians, through open collaboration and the wiki software MediaWiki. Founded by Jimmy Wales and La ...
is a free online encyclopedia that anyone can edit.''
* ''London
London is the Capital city, capital and List of urban areas in the United Kingdom, largest city of both England and the United Kingdom, with a population of in . London metropolitan area, Its wider metropolitan area is the largest in Wester ...
is the capital of England
England is a Countries of the United Kingdom, country that is part of the United Kingdom. It is located on the island of Great Britain, of which it covers about 62%, and List of islands of England, more than 100 smaller adjacent islands. It ...
.''
* ''All Wikipedia editors speak at least three language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
s.''
Declarative sentences are contrasted with question
A question is an utterance which serves as a request for information. Questions are sometimes distinguished from interrogatives, which are the grammar, grammatical forms, typically used to express them. Rhetorical questions, for instance, are i ...
s, such as "What is Wikipedia?", and imperative statements, such as "Please add citation
A citation is a reference to a source. More precisely, a citation is an abbreviated alphanumeric expression embedded in the body of an intellectual work that denotes an entry in the bibliographic references section of the work for the purpose o ...
s to support the claims in this article.".[ Such non-declarative sentences have no ]truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
,[ and are only dealt with in nonclassical logics, called erotetic and imperative logics.
]
Compounding sentences with connectives
In propositional logic, a statement can contain one or more other statements as parts.[ ''Compound sentences'' are formed from simpler sentences and express relationships among the constituent sentences.][ This is done by combining them with logical connectives:][ the main types of compound sentences are ]negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
s, conjunctions, disjunctions, implications, and biconditionals,[ which are formed by using the corresponding connectives to connect propositions.][ In English, these connectives are expressed by the words "and" ( conjunction), "or" (]disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
), "not" (negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
), "if" (material conditional
The material conditional (also known as material implication) is a binary operation commonly used in logic. When the conditional symbol \to is interpreted as material implication, a formula P \to Q is true unless P is true and Q is false.
M ...
), and "if and only if" ( biconditional).[ Examples of such compound sentences might include:
* ''Wikipedia is a free online encyclopedia that anyone can edit, and millions already have.'' (conjunction)
* ''It is not true that all Wikipedia editors speak at least three languages.'' (negation)
* ''Either London is the capital of England, or London is the capital of the ]United Kingdom
The United Kingdom of Great Britain and Northern Ireland, commonly known as the United Kingdom (UK) or Britain, is a country in Northwestern Europe, off the coast of European mainland, the continental mainland. It comprises England, Scotlan ...
, or both.'' (disjunction)
If sentences lack any logical connectives, they are called ''simple sentences'',[ or ''atomic sentences'';][ if they contain one or more logical connectives, they are called ''compound sentences'',][ or ''molecular sentences''.][
''Sentential connectives'' are a broader category that includes logical connectives.][ Sentential connectives are any linguistic particles that bind sentences to create a new compound sentence,][ or that inflect a single sentence to create a new sentence.][ A ''logical connective'', or ''propositional connective'', is a kind of sentential connective with the characteristic feature that, when the original sentences it operates on are (or express) ]proposition
A proposition is a statement that can be either true or false. It is a central concept in the philosophy of language, semantics, logic, and related fields. Propositions are the object s denoted by declarative sentences; for example, "The sky ...
s, the new sentence that results from its application also is (or expresses) a proposition
A proposition is a statement that can be either true or false. It is a central concept in the philosophy of language, semantics, logic, and related fields. Propositions are the object s denoted by declarative sentences; for example, "The sky ...
.[ Philosophers disagree about what exactly a proposition is,][ as well as about which sentential connectives in natural languages should be counted as logical connectives.][ Sentential connectives are also called ''sentence-functors'',][ and logical connectives are also called ''truth-functors''.][
]
Arguments
An argument
An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persu ...
is defined as a pair of things, namely a set of sentences, called the premises, and a sentence, called the conclusion.[ The conclusion is claimed to ''follow from'' the premises,][ and the premises are claimed to ''support'' the conclusion.][
]
Example argument
The following is an example of an argument within the scope of propositional logic:
:Premise 1: ''If'' it's raining, ''then'' it's cloudy.
:Premise 2: It's raining.
:Conclusion: It's cloudy.
The logical form of this argument is known as modus ponens,[ which is a classically valid form.][ So, in classical logic, the argument is ''valid'', although it may or may not be '']sound
In physics, sound is a vibration that propagates as an acoustic wave through a transmission medium such as a gas, liquid or solid.
In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by the br ...
'', depending on the meteorological facts in a given context. This example argument will be reused when explaining .
Validity and soundness
An argument is valid if, and only if, it is ''necessary'' that, if all its premises are true, its conclusion is true.[ Alternatively, an argument is valid if, and only if, it is ''impossible'' for all the premises to be true while the conclusion is false.][
Validity is contrasted with ''soundness''.][ An argument is sound if, and only if, it is valid and all its premises are true.][ Otherwise, it is ''unsound''.][
Logic, in general, aims to precisely specify valid arguments.][ This is done by defining a valid argument as one in which its conclusion is a ]logical consequence
Logical consequence (also entailment or logical implication) is a fundamental concept in logic which describes the relationship between statement (logic), statements that hold true when one statement logically ''follows from'' one or more stat ...
of its premises,[ which, when this is understood as ''semantic consequence'', means that there is no ''case'' in which the premises are true but the conclusion is not true][ – see below.
]
Formalization
Propositional logic is typically studied through a formal system in which formulas of a formal language are interpreted to represent propositions. This formal language is the basis for proof systems, which allow a conclusion to be derived from premises if, and only if, it is a logical consequence
Logical consequence (also entailment or logical implication) is a fundamental concept in logic which describes the relationship between statement (logic), statements that hold true when one statement logically ''follows from'' one or more stat ...
of them. This section will show how this works by formalizing the . The formal language for a propositional calculus will be fully specified in , and an overview of proof systems will be given in .
Propositional variables
Since propositional logic is not concerned with the structure of propositions beyond the point where they cannot be decomposed any more by logical connectives,[ it is typically studied by replacing such ''atomic'' (indivisible) statements with letters of the alphabet, which are interpreted as variables representing statements ( ''propositional variables'').][ With propositional variables, the would then be symbolized as follows:
:Premise 1:
:Premise 2:
:Conclusion:
When is interpreted as "It's raining" and as "it's cloudy" these symbolic expressions correspond exactly with the original expression in natural language. Not only that, but they will also correspond with any other inference with the same logical form.
When a formal system is used to represent formal logic, only statement letters (usually capital roman letters such as , and ) are represented directly. The natural language propositions that arise when they're interpreted are outside the scope of the system, and the relation between the formal system and its interpretation is likewise outside the formal system itself.
]
Gentzen notation
If we assume that the validity of modus ponens has been accepted as an axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
, then the same can also be depicted like this:
:
This method of displaying it is Gentzen's notation for natural deduction and sequent calculus.[ The premises are shown above a line, called the inference line,][ separated by a comma, which indicates ''combination'' of premises.][ The conclusion is written below the inference line.][ The inference line represents ''syntactic consequence'',][ sometimes called ''deductive consequence'',][> which is also symbolized with ⊢.][ So the above can also be written in one line as .
Syntactic consequence is contrasted with ''semantic consequence'',][ which is symbolized with ⊧.][ In this case, the conclusion follows ''syntactically'' because the natural deduction inference rule of modus ponens has been assumed. For more on inference rules, see the sections on proof systems below.
]
Language
The language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
(commonly called )[ 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
In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language.
The abbreviation wf ...
'' 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 , 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 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.][
]
Syntax
Given a set of atomic propositional variables , , , ..., and a set of propositional connectives , , , ..., , , , ..., , , , ..., a formula of propositional logic is defined recursively by these definitions:[
:Definition 1: Atomic propositional variables are formulas.
:Definition 2: If is a propositional connective, and A, B, C, … is a sequence of m, possibly but not necessarily atomic, possibly but not necessarily distinct, formulas, then the result of applying to A, B, C, … is a formula.
:Definition 3: Nothing else is a formula.
Writing the result of applying to A, B, C, … in functional notation, as (A, B, C, …), we have the following as examples of well-formed formulas:
*
*
*
*
*
*
*
What was given as ''Definition 2'' above, which is responsible for the composition of formulas, is referred to by Colin Howson as the ''principle of composition''.][ It is this ]recursion
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
in the definition of a language's syntax which justifies the use of the word "atomic" to refer to propositional variables, since all formulas in the language are built up from the atoms as ultimate building blocks.[ Composite formulas (all formulas besides atoms) are called ''molecules'',][ or ''molecular sentences''.][ (This is an imperfect analogy with ]chemistry
Chemistry is the scientific study of the properties and behavior of matter. It is a physical science within the natural sciences that studies the chemical elements that make up matter and chemical compound, compounds made of atoms, molecules a ...
, since a chemical molecule may sometimes have only one atom, as in monatomic gases.)[
The definition that "nothing else is a formula", given above as ''Definition 3'', excludes any formula from the language which is not specifically required by the other definitions in the syntax.][ In particular, it excludes ''infinitely long'' formulas from being well-formed.][ It is sometimes called the ''Closure Clause''.]
CF grammar in BNF
An alternative to the syntax definitions given above is to write a context-free (CF) grammar for the language in Backus-Naur form (BNF).[ This is more common in ]computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
than in philosophy
Philosophy ('love of wisdom' in Ancient Greek) is a systematic study of general and fundamental questions concerning topics like existence, reason, knowledge, Value (ethics and social sciences), value, mind, and language. It is a rational an ...
.[ It can be done in many ways,][ of which a particularly brief one, for the common set of five connectives, is this single clause:][
:
This clause, due to its ]self-referential
Self-reference is a concept that involves referring to oneself or one's own attributes, characteristics, or actions. It can occur in language, logic, mathematics, philosophy, and other fields.
In natural language, natural or formal languages, ...
nature (since is in some branches of the definition of ), also acts as a recursive definition, and therefore specifies the entire language. To expand it to add modal operators, one need only add … to the end of the clause.[
]
Constants and schemata
Mathematicians sometimes distinguish between propositional constants, propositional variables, and schemata. ''Propositional constants'' represent some particular proposition,[ while ''propositional variables'' range over the set of all atomic propositions.][ Schemata, or ''schematic letters'', however, range over all formulas.][ (Schematic letters are also called ''metavariables''.)][ It is common to represent propositional constants by , , and , propositional variables by , , and , and schematic letters are often Greek letters, most often , , and .][
However, some authors recognize only two "propositional constants" in their formal system: the special symbol , called "truth", which always evaluates to ''True'', and the special symbol , called "falsity", which always evaluates to ''False''.][ Other authors also include these symbols, with the same meaning, but consider them to be "zero-place truth-functors",][ or equivalently, "]nullary
In logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the ...
connectives".[
]
Semantics
To serve as a model of the logic of a given natural language, a formal language must be semantically interpreted.[ In ]classical logic
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...
, all propositions evaluate to exactly one of two truth-values: ''True'' or ''False''.[ For example, "]Wikipedia
Wikipedia is a free content, free Online content, online encyclopedia that is written and maintained by a community of volunteers, known as Wikipedians, through open collaboration and the wiki software MediaWiki. Founded by Jimmy Wales and La ...
is a free online encyclopedia
An online encyclopedia, also called an Internet encyclopedia, is a digital encyclopedia accessible through the Internet. Some examples include pre-World Wide Web services that offered the '' Academic American Encyclopedia'' beginning in 1980, Enc ...
that anyone can edit" evaluates to ''True'',[ while "Wikipedia is a ]paper
Paper is a thin sheet material produced by mechanically or chemically processing cellulose fibres derived from wood, Textile, rags, poaceae, grasses, Feces#Other uses, herbivore dung, or other vegetable sources in water. Once the water is dra ...
encyclopedia
An encyclopedia is a reference work or compendium providing summaries of knowledge, either general or special, in a particular field or discipline. Encyclopedias are divided into article (publishing), articles or entries that are arranged Alp ...
" evaluates to ''False''.[
In other respects, the following formal semantics can apply to the language of any propositional logic, but the assumptions that there are only two semantic values ( ''bivalence''), that only one of the two is assigned to each formula in the language ( ''noncontradiction''), and that every formula gets assigned a value ( ''excluded middle''), are distinctive features of classical logic.][ To learn about nonclassical logics with more than two truth-values, and their unique semantics, one may consult the articles on "]Many-valued logic
Many-valued logic (also multi- or multiple-valued logic) is a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's Term logic, logical calculus, there were only two possible values (i.e., "true" and ...
", " Three-valued logic", " Finite-valued logic", and " Infinite-valued logic".
Interpretation (case) and argument
For a given language , an interpretation,[ valuation,][ Boolean valuation,][ or case,][ is an assignment of ''semantic values'' to each formula of .][ For a formal language of classical logic, a case is defined as an ''assignment'', to each formula of , of one or the other, but not both, of the ]truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
s, namely truth
Truth or verity is the Property (philosophy), property of being in accord with fact or reality.Merriam-Webster's Online Dictionarytruth, 2005 In everyday language, it is typically ascribed to things that aim to represent reality or otherwise cor ...
(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 , and whose range is its set of semantic values ,][ or .][
For distinct propositional symbols there are distinct possible interpretations. For any particular symbol , for example, there are possible interpretations: either is assigned T, or is assigned F. And for the pair , there are possible interpretations: either both are assigned T, or both are assigned F, or is assigned T and is assigned F, or is assigned F and is assigned T.][ Since has , that is, denumerably many propositional symbols, there are , and therefore uncountably many distinct possible interpretations of as a whole.][
Where is an interpretation and and represent formulas, the definition of an ''argument'', given in , may then be stated as a pair , where is the set of premises and is the conclusion. The definition of an argument's ''validity'', i.e. its property that , can then be stated as its ''absence of a counterexample'', where a counterexample is defined as a case in which the argument's premises are all true but the conclusion 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.
]
Propositional connective semantics
An interpretation assigns semantic values to atomic formulas directly.[ Molecular formulas are assigned a ''function'' of the value of their constituent atoms, according to the connective used;][ the connectives are defined in such a way that the truth-value of a sentence formed from atoms with connectives depends on the truth-values of the atoms that they're applied to, and ''only'' on those.][ This assumption is referred to by Colin Howson as the assumption of the '' truth-functionality of the connectives''.][
]
Semantics via. truth tables
Since logical connectives are defined semantically only in terms of the truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
s that they take when the propositional variables that they're applied to take either of the two possible truth values,[ the semantic definition of the connectives is usually represented as a ]truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
for each of the connectives,[ as seen below:
This table covers each of the main five logical connectives:][ conjunction (here notated ), ]disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
(), implication (), biconditional () and negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
, (¬''p'', or ¬''q'', as the case may be). It is sufficient for determining the semantics of each of these operators.[ For more truth tables for more different kinds of connectives, see the article "]Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
".
Semantics via assignment expressions
Some authors (viz., all the authors cited in this subsection) write out the connective semantics using a list of statements instead of a table. In this format, where is the interpretation of , the five connectives are defined as:[
* if, and only if,
* if, and only if, and
* if, and only if, or
* if, and only if, it is true that, if , then
* if, and only if, it is true that if, and only if,
Instead of , the interpretation of may be written out as ,][ or, for definitions such as the above, may be written simply as the English sentence " is given the value ".][ Yet other authors][ may prefer to speak of a Tarskian model for the language, so that instead they'll use the notation , which is equivalent to saying , where is the interpretation function for .][
]
Connective definition methods
Some of these connectives may be defined in terms of others: for instance, implication, , may be defined in terms of disjunction and negation, as ;[ and disjunction may be defined in terms of negation and conjunction, as .][ In fact, a '' truth-functionally complete'' system, in the sense that all and only the classical propositional tautologies are theorems, may be derived using only disjunction and negation (as Russell, Whitehead, and ]Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosophy of mathematics, philosopher of mathematics and one of the most influential mathematicians of his time.
Hilbert discovered and developed a broad ...
did), or using only implication and negation (as Frege did), or using only conjunction and negation, or even using only a single connective for "not and" (the Sheffer stroke),[ as Jean Nicod did.][ A ''joint denial'' connective ( logical NOR) will also suffice, by itself, to define all other connectives. Besides NOR and NAND, no other connectives have this property.][
Some authors, namely Howson][ and Cunningham,][ distinguish equivalence from the biconditional. (As to equivalence, Howson calls it "truth-functional equivalence", while Cunningham calls it "logical equivalence".) Equivalence is symbolized with ⇔ and is a metalanguage symbol, while a biconditional is symbolized with ↔ and is a logical connective in the object language . Regardless, an equivalence or biconditional is true if, and only if, the formulas connected by it are assigned the same semantic value under every interpretation. Other authors often do not make this distinction, and may use the word "equivalence",][ and/or the symbol ⇔,][ to denote their object language's biconditional connective.
]
Semantic truth, validity, consequence
Given and as formulas (or sentences) of a language , and as an interpretation (or case) of , then the following definitions apply:[
* Truth-in-a-case:][ A sentence of is ''true under an interpretation'' if assigns the truth value T to .][ If is true under , then is called a ''model'' of .][
* Falsity-in-a-case:][ is ''false under an interpretation'' if, and only if, is true under .][ This is the "truth of negation" definition of falsity-in-a-case.][ Falsity-in-a-case may also be defined by the "complement" definition: is ''false under an interpretation'' if, and only if, is not true under .][ In ]classical logic
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...
, these definitions are equivalent, but in nonclassical logics, they are not.[
* Semantic consequence: A sentence of is a '' semantic consequence'' () of a sentence if there is no interpretation under which is true and is not true.][
* Valid formula (tautology): A sentence of is ''logically valid'' (), or a ''tautology'',][ref name="ms32][ if it is true under every interpretation,][ or ''true in every case.''][
* Consistent sentence: A sentence of is '' consistent'' if it is true under at least one interpretation. It is ''inconsistent'' if it is not consistent.][ An inconsistent formula is also called ''self-contradictory'',][ and said to be a ''self-contradiction'',][ or simply a ''contradiction'',][ although this latter name is sometimes reserved specifically for statements of the form .][
For interpretations (cases) of , these definitions are sometimes given:
* Complete case: A case is ''complete'' if, and only if, either is true-in- or is true-in-, for any in .][
* Consistent case: A case is ''consistent'' if, and only if, there is no in such that both and are true-in-.][
For ]classical logic
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...