Formal Logic/Print version
This is the print version of Formal Logic You won't see this message or any elements not part of the book's content when you print or preview this page. 
Contents
 1 Sets
 2 Goals
 3 The Sentential Language
 4 Formal Syntax
 5 Informal Conventions
 6 Formal Semantics
 7 Truth Tables
 8 Expressibility
 9 Properties of Sentential Connectives
 10 Substitution and Interchange
 11 Translations
 12 Derivations
 13 Inference Rules
 14 Constructing a Simple Derivation
 15 Subderivations and Discharge Rules
 16 Constructing a Complex Derivation
 17 Theorems
 18 Derived Inference Rules
 19 Disjunctions in Derivations
 20 Goals
 21 The Predicate Language
 22 Formal Syntax
 23 Free and Bound Variables
 24 Models
 25 Satisfaction
 26 Truth
SetsEdit
Presentations of logic vary in how much set theory they use. Some are heavily laden with set theory. Though most are not, it is nearly impossible to avoid it completely. It will not be a very important focal point for this book, but we will use a little set theory vocabulary here and there. This section introduces the vocabulary and notation used.
Sets and elementsEdit
Mathematicians use 'set' as an undefined primitive term. Some authors resort to quasisynonyms such as 'collection'.
A set has elements. 'Element' is also undefined in set theory. We say that an element is a member of a set, also an undefined expression. The following are all used synonymously:
 x is a member of y
 x is contained in y
 x is included in y
 y contains x
 y includes x
NotationEdit
A set can be specified by enclosing its members within curly braces.
is the set containing 1, 2, and 3 as members. The curly brace notation can be extended to specify a set using a rule for membership.
 (The set of all x such that x = 1 or x = 2 or x = 3)
is again the set containing 1, 2, and 3 as members.
 , and
both specify the set containing 1, 2, 3, and onwards.
A modified epsilon is used to denote set membership. Thus
indicates that "x is a member of y". We can also say that "x is not a member of y" in this way:
Characteristics of setsEdit
A set is uniquely identified by its members. The expressions
all specify the same set even though the concept of an even prime is different from the concept of a positive square root. Repetition of members is inconsequential in specifying a set. The expressions
all specify the same set.
Sets are unordered. The expressions
all specify the same set.
Sets can have other sets as members. There is, for example, the set
Some special setsEdit
As stated above, sets are defined by their members. Some sets, however, are given names to ease referencing them.
The set with no members is the empty set. The expressions
all specify the empty set. Empty sets can also express oxymora ("foursided triangles" or "birds with radial symmetry") and factual nonexistence ("the King of Czechoslovakia in 1994").
A set with exactly one member is called a singleton. A set with exactly two members is called a pair. Thus {1} is a singleton and {1, 2} is a pair.
ω is the set of natural numbers, {0, 1, 2, ...}.
Subsets, power sets, set operationsEdit
SubsetsEdit
A set s is a subset of set a if every member of s is a member of a. We use the horseshoe notation to indicate subsets. The expression
says that {1, 2} is a subset of {1, 2, 3}. The empty set is a subset of every set. Every set is a subset of itself. A proper subset of a is a subset of a that is not identical to a. The expression
says that {1, 2} is a proper subset of {1, 2, 3}.
Power setsEdit
A power set of a set is the set of all its subsets. A script 'P' is used for the power set.
UnionEdit
The union of two sets a and b, written a ∪ b, is the set that contains all the members of a and all the members of b (and nothing else). That is,
As an example,
IntersectionEdit
The intersection of two sets a and b, written a ∩ b, is the set that contains everything that is a member of both a and b (and nothing else). That is,
As an example,
Relative complementEdit
The relative complement of a in b, written b \ a (or b − a) is the set containing all the members of b that are not members of a. That is,
As an example,
Ordered sets, relations, and functionsEdit
The intuitive notions of ordered set, relation, and function will be used from time to time. For our purposes, the intuitive mathematical notion is the most important. However, these intuitive notions can be defined in terms of sets.
Ordered setsEdit
First, we look at ordered sets. We said that sets are unordered:
But we can define ordered sets, starting with ordered pairs. The angle bracket notation is used for this:
Indeed,
Any set theoretic definition giving 〈a, b〉 this last property will work. The standard definition of the ordered pair 〈a, b〉 runs:
This means that we can use the latter notation when doing operations on an ordered pair.
There are also bigger ordered sets. The ordered triple 〈a, b, c〉 is the ordered pair 〈〈a, b〉, c〉. The ordered quadruple 〈a, b, c, d〉 is the ordered pair 〈〈a, b, c〉, d〉. This, in turn, is the ordered triple 〈〈〈a, b〉, c〉, d〉. In general, an ordered ntuple 〈a_{1}, a_{2}, ..., a_{n}〉 where n greater than 1 is the ordered pair 〈〈a_{1}, a_{2}, ..., a_{n1}〉, a_{n}〉.
It can be useful to define an ordered 1tuple as well: 〈a〉 = a.
These definitions are somewhat arbitrary, but it is nonetheless convenient for an ntuple, n 〉 2, to be an n1 tuple and indeed an ordered pair. The important property that makes them serve as ordered sets is:
RelationsEdit
We now turn to relations. Intuitively, the following are relations:
 x < y
 x is a square root of y
 x is a brother of y
 x is between y and z
The first three are binary or 2place relations; the fourth is a ternary or 3place relation. In general, we talk about nary relations or nplace relations.
First consider binary relations. A binary relation is a set of ordered pairs. The less than relation would have among its members 〈1, 2〉, 〈1, 3〉, 〈16, 127〉, etc. Indeed, the less than relation defined on the natural numbers ω is:
Intuitively, 〈x, y〉 is a member of the less than relation if x < y. In set theory, we do not worry about whether a relation matches an intuitive concept such as less than. Rather, any set of ordered pairs is a binary relation.
We can also define a 3place relation as a set of 3tuples, a 4place relation as a set of 4tuples, etc. We only define nplace relations for n ≥ 2. An nplace relation is said to have an arity of n. The following example is a 3place relation.
Because all ntuples where n > 1 are also ordered pairs, all nplace relations are also binary relations.
FunctionsEdit
Finally, we turn to functions. Intuitively, a function is an assignment of values to arguments such that each argument is assigned at most one value. Thus the + 2 function assigns a numerical argument x the value x + 2. Calling this function f, we say f(x) = x + 2. The following define specific functions.
Note that f_{3} is undefined when x = 0. According to biblical tradition, f_{4} is undefined when x = Adam or x = Eve. The following do not define functions.
Neither of these assigns unique values to arguments. For every positive x, there are two square roots, one positive and one negative, so f_{5} is not a function. For many x, x will have multiple sons, so f_{6} is not a function. If f_{6} is assigned the value the son of x then a unique value is implied by the rules of language, therefore f_{6} will be a function.
A function f is a binary relation where, if 〈x, y〉 and 〈x, z〉 are both members of f, then y = z.
We can define many place functions. Intuitively, the following are definitions of specific many place functions.
Thus 〈4, 7, 11〉 is a member of the 2place function f_{7}. 〈3, 4, 5, 35〉 is a member of the 3 place function f_{8}
The fact that all ntuples, n ≥ 2, are ordered pairs (and hence that all nary relations are binary relations) becomes convenient here. For n ≥ 1, an nplace function is an n+1 place relation that is a 1place function. Thus, for a 2place function f,
GoalsEdit
Sentential logicEdit
Sentential logic attempts to capture certain logical features of natural languages. In particular, it covers truthfunctional connections for sentences. Its formal language specifically recognizes the sentential connections
 It is not the case that _____
 _____ and _____
 Either _____ or _____
 _____ or _____ (or both)
 if _____, then _____
 _____ if and only if _____
The blanks are to be filled with statements that can be true or false. For example, "it is raining today" or "it will snow tomorrow". Whether the final sentence is true or false is entirely determined on whether the filled statements are true or false. For example, if it is raining today, but it will not snow tomorrow, then it is true to say that "Either it is raining today or it will snow tomorrow". On the other hand, it is false to say "it is raining today and it will snow tomorrow", since it won't snow tomorrow.
"Whether a statement is true or false" is called the truth value in logician slang. Thus "Either it is raining today or it is not raining today" has a truth value of true and "it is raining today and it is not raining today" has truth value of false.
Note that the above listed sentential connections do not include all possible truth value combinations. For example, there is no connection that is true when both substatements are true, both substatements are false or the first substatement is true while the other is false, and that is false else. However, you can combine the above connections together to build any truth combination of any number of substatements.
IssuesEdit
Already we have tacitly taken a position in ongoing controversy. Some questions already raised by the seemingly innocuous beginning above are listed.
 Should we admit into our logic only sentences that are true or false? Multivalued logics admit a greater range of sentences.
 Are the connections listed above truly truth functional? Should we admit connections that are not truth functional sentences into our logic?
 What should logic take as its truthbearers (objects that are true or false)? The two leading contenders today are sentences and propositions.
 Sentences. These consist of a string of words and perhaps punctuation. The sentence 'The cat is on the mat' consists of six elements: 'the', 'cat', 'is', 'on', another 'the', and 'mat'.
 Propositions. These are the meanings of sentences. They are what is expressed by a sentence or what someone says when he utters a sentence. The proposition that the cat is on the mat consists of three elements: a cat, a mat, and the onness relation.
 Elsewhere in Wikibooks and Wikipedia, you will see the name 'Propositional Logic' (or rather 'Propositional Calculus', see below) and the treatment of propositions much more often than you will see the name 'Sentential Logic' and the treatment of sentences. Our choice here represents the contributor's view as to which position is more popular among current logicians and what you are most likely to see in standard textbooks on the subject. Considerations as to whether the popular view is actually correct are not taken up here.
 Some authors will use talk about statements instead of sentences. Most (but not all) such authors you are likely to encounter take statements to be a subset of sentences, namely those sentences that are either true or false. This use of 'statement' does not represent a third position in the controversy, but rather places such authors in the sentences camp. (However, other—particularly older—uses of 'statement' may well place its authors in a third camp.)
Sometimes you will see 'calculus' rather than 'logic' such as in 'Sentential Calculus' or 'Propositional Calculus' as opposed to 'Sentential Logic' or 'Propositional Logic'. While the choice between 'sentential' and 'propositional' is substantive and philosophical, the choice between 'logic' and 'calculus' is merely stylistic.
The Sentential LanguageEdit
This page informally describes our sentential language which we name . A more formal description will be given in Formal Syntax and Formal Semantics
Language componentsEdit
Sentence lettersEdit
The sentence letters are single letters such as
Some texts restrict this to lower case letters, and others restrict them to capital letters. We will use capital letters.
Intuitively, we can think of sentence letters as translating English sentences that are either true or false. Thus, can translate 'The Earth is a planet' (which is true) or 'The moon is made of green cheese' (which is false). But can not translate 'Great ideas sleep furiously' because it is neither true nor false. Translations between English and work best if we restrict ourselves to timelessly true or false present tense sentences in the indicative mood. You will see from the translation section below that we do not always follow that advice. The truth or falsity of those sentences is not timeless.
Sentential connectivesEdit
Sentential connectives are special symbols in Sentential Logic that represent truth functional relations. They are used to build larger sentences from smaller sentences. The truth or falsity of the larger sentence can then be computed from the truth or falsity of the smaller ones.
 Translates to English as 'and'.
 is called a conjunction and and are its conjuncts.
 is true if both and are true—and is false otherwise.
 Some authors use an & (ampersand), • (heavy dot) or juxtaposition. In the last case, an author would write
 instead of our
 Translates to English as 'or'.
 is called a disjunction and and are its disjuncts.
 is true if at least one of and are true—is false otherwise.
 Some authors may use a vertical stroke: . However, this comes from computer languages rather than logicians' usage. Logicians normally reserve the vertical stroke for nand (alternative denial). When used as nand, it is called the Sheffer stroke.
 Translates to English as 'it is not the case that' but is normally read 'not'.
 is called a negation.
 is true if is false—and is false otherwise.
 Some authors use ~ (tilde) or −. Some authors use an overline, for example writing
 instead of
 Translates to English as 'if...then' but is often read 'arrow'.
 is called a conditional. Its antecedent is and its consequent is .
 is false if is true and is false—and true otherwise.
 By that definition, is equivalent to
 Some authors use ⊃ (hook).
 Translates to English as 'if and only if'
 is called a biconditional.
 is true if and both are true or both are false—and false otherwise.
 By that definition, is equivalent to the more verbose . It is also equivalent to , the conjunction of two conditionals where in the second conditional the antecedent and consequent are reversed from the first.
 Some authors use ≡.
GroupingEdit
Parentheses and are used for grouping. Thus
are two different and distinct sentences. Each negation, conjunction, disjunction, conditional, and biconditionals gets a single pair or parentheses.
NotesEdit
(1) An atomic sentence is a sentence consisting of just a single sentence letter. A molecular sentence is a sentence with at least one sentential connective. The main connective of a molecular formula is the connective that governs the entire sentence. Atomic sentences, of course, do not have a main connective.
(2) The ⊃ and ≡ signs for conditional and biconditional are historically older, perhaps a bit more traditional, and definitely occur more commonly in WikiBooks and Wikipedia than our arrow and double arrow. They originate with Alfred North Whitehead and Bertrand Russell in Principia Mathematica. Our arrow and double arrow appear to originate with Alfred Tarski, and may be a bit more popular today than the Whitehead and Russell's ⊃ and ≡.
(3) Sometimes you will see people reading our arrow as implies. This is fairly common in WikiBooks and Wikipedia. However, most logicians prefer to reserve 'implies' for metalinguistic use. They will say:
 If P then Q
or even
 P arrow Q
They approve of:
 'P' implies 'Q'
but will frown on:
 P implies Q
TranslationEdit
Consider the following English sentences:
 If it is raining and Jones is out walking, then Jones has an umbrella.
 If it is Tuesday or it is Wednesday, then Jones is out walking.
To render these in , we first specify an appropriate English translation for some sentence letters.
 It is raining.
 Jones is out walking.
 Jones has an umbrella.
 It is Tuesday.
 It is Wednesday.
We can now partially translate our examples as:
Then finish the translation by adding the sentential connectives and parentheses:
Quoting conventionEdit
For English expressions, we follow the logical tradition of using single quotes. This allows us to use ' 'It is raining' ' as a quotation of 'It is raining'.
For expressions in , it is easier to treat them as selfquoting so that the quotation marks are implicit. Thus we say that the above example translates (note the lack of quotes) as 'If it is Tuesday, then It is raining'.
Formal SyntaxEdit
In The Sentential Language, we informally described our sentential language. Here we give its formal syntax or grammar. We will call our language .
VocabularyEdit
 Sentence letters: Capital letters 'A' – 'Z', each with (1) a superscript '0' and (2) a natural number subscript. (The natural numbers are the set of positive integers and zero.) Thus the sentence letters are:
 Sentential connectives:
 Grouping symbols:
The superscripts on sentence letters are not important until we get to the predicate logic, so we won't really worry about those here. The subscripts on sentence letters are to ensure an infinite supply of sentence letters. On the next page, we will abbreviate away most superscripts and subscripts.
ExpressionsEdit
Any string of characters from the vocabulary is an expression of . Some expressions are grammatically correct. Some are as incorrect in as 'Over talks David Mary the' is in English. Still other expressions are as hopelessly illformed in as 'jmr.ovn asgj as;lnre' is in English.
We call a grammatically correct expression of a wellformed formula. When we get to Predicate Logic, we will find that only some well formed formulas are sentences. For now though, we consider every well formed formula to be a sentence.
Formation rulesEdit
An expression of is a wellformed formula of if and only if it is constructed according to the following rules.
 i. A sentence letter is a wellformed formula.
 ii. If and are wellformed formulae, then so are each of:
In general, we will use 'formula' as shorthand for 'wellformed formula'. Since all formulae in are sentences, we will use 'formula' and 'sentence' interchangeably.
Quoting conventionEdit
We will take expressions of to be selfquoting and so regard
to include implicit quotation marks. However, something like
requires special consideration. It is not itself an expression of since and are not in the vocabulary of . Rather they are used as variables in English which range over expressions of . Such a variable is called a metavariable, and an expression using a mix of vocabulary from and metavariables is called a metalogical expression. Suppose we let be and be Then (1) becomes
 '' '' ''
which is not what we want. Instead we take (1) to mean (using explicit quotes):
 the expression consisting of '' followed by followed by '' followed by followed by '' .
Explicit quotes following this convention are called Quine quotes or corner quotes. Our corner quotes will be implicit.
Additional terminologyEdit
We introduce (or, in some cases, repeat) some useful syntactic terminology.
 We distinguish between an expression (or a formula) and an occurrence of an expression (or formula). The formula
is the same formula no matter how many times it is written. However, it contains three occurrences of the sentence letter and two occurrences of the sentential connective .
 is a subformula of if and only if and are both formulae and contains an occurrence of . is a proper subformula of if and only if (i) is a subformula of and (ii) is not the same formula as .
 An atomic formula or atomic sentence is one consisting solely of a sentence letter. Or put the other way around, it is a formula with no sentential connectives. A molecular formula or molecular sentence is one which contains at least one occurrence of a sentential connective.
 The main connective of a molecular formula is the last occurrence of a connective added when the formula was constructed according to the rules above.
 A negation is a formula of the form where is a formula.
 A conjunction is a formula of the form where and are both formulae. In this case, and are both conjuncts.
 A disjunction is a formula of the form where and are both formulae. In this case, and are both disjuncts.
 A conditional is a formula of the form where and are both formulae. In this case, is the antecedent, and is the consequent. The converse of is . The contrapositive of is .
 A biconditional is a formula of the form where and are both formulae.
ExamplesEdit
By rule (i), all sentence letters, including
are formulae. By rule (iia), then, the negation
is also a formula. Then by rules (iic) and (iib), we get the disjunction and conjunction
as formulae. Applying rule (iia) again, we get the negation
as a formula. Finally, rule (iic) generates the conditional of (1), so it too is a formula.
This appears to be generated by rule (iic) from
The second of these is a formula by rule (i). But what about the first? It would have to be generated by rule (iib) from
But
cannot be generated by rule (iia). So (2) is not a formula.
Informal ConventionsEdit
In The Sentential Language, we gave an informal description of a sentential language, namely . We have also given a Formal Syntax for . Our official grammar generates a large number of parentheses. This makes formal definitions and other specifications easier to write, but it makes the language rather cumbersome to use. In addition, all the subscripts and superscripts quickly get to be unnecessarily tedious. The end result is an ugly and difficult to read language.
We will continue to use official grammar for specifying formalities. However, we will informally use a less cumbersome variant for other purposes. The transformation rules below convert official formulae of into our informal variant.
Transformation rulesEdit
We create informal variants of official formulae as follows. The examples are cumulative.
 The official grammar required sentence letters to have the superscript '0'. Superscripts aren't necessary or even useful until we get to the predicate logic, so we will always omit them in our informal variant. We will write, for example, instead of .
 We will omit the subscript if it is '0'. Thus we will write instead of . However, we cannot omit all subscripts; we still need to write, for example, .
 We will omit outermost parentheses. For example, we will write
 instead of
 We will let a series of the same binary connective associate on the right. For example, we can transform the official
 into the informal
 However, the best we can do with
 is
 We will use precedence rankings to omit internal parentheses when possible. For example, we will regard as having lower precedence (wider scope) than . This allows us to write
 instead of
 However, we cannot remove the internal parentheses from
 Our informal variant of this latter formula is
 Full precedence rankings are given below.
Precedence and scopeEdit
Precedence rankings indicate the order that we evaluate the sentential connectives. has a higher precedence than . Thus, in calculating the truth value of
we start by evaluating the truth value of
first. Scope is the length of expression that is governed by the connective. The occurrence of in (1) has a wider scope than the occurrence of . Thus the occurrence of in (1) governs the whole sentence while the occurrence of in (1) governs only the occurrence of (2) in (1).
The full ranking from highest precedence (narrowest scope) to lowest precedence (widest scope) is:
highest precedence (narrowest scope)  
lowest precedence (widest scope) 
ExamplesEdit
Let's look at some examples. First,
can be written informally as
Second,
can be written informally as
Some unnecessary parentheses may prove helpful. In the two examples above, the informal variants may be easier to read as
and
Note that the informal formula
is restored to its official form as
By contrast, the informal formula
is restored to its official form as
Formal SemanticsEdit
English syntax for 'Dogs bark' specifies that it consists of a plural noun followed by an intransitive verb. English semantics for 'Dogs bark' specify its meaning, namely that dogs bark.
In The Sentential Language, we gave an informal description of . We also gave a Formal Syntax. However, at this point our language is just a toy, a collection of symbols we can string together like beads on a necklace. We do have rules for how those symbols are to be ordered. But at this point those might as well be aesthetic rules. The difference between wellformed formulae and illformed expressions is not yet any more significant than the difference between pretty and ugly necklaces. In order for our language to have any meaning, to be usable in saying things, we need a formal semantics.
Any given formal language can be paired with any of a number of competing semantic rule sets. The semantics we define here is the usual one for modern logic. However, alternative semantic rulesets have been proposed. Alternative semantic rulesets of have included (but are certainly not limited to) intuitionistic logics, relevance logics, nonmonotonic logics, and multivalued logics.
Formal semanticsEdit
The formal semantics for a formal language such as goes in two parts.
 Rules for specifying an interpretation. An interpretation assigns semantic values to the nonlogical symbols of a formal syntax. The semantics for a formal language will specify what range of values can be assigned to which class of nonlogical symbols. has only one class of nonlogical symbols, so the rule here is particularly simple. An interpretation for a sentential language is a valuation, namely an assignment of truth values to sentence letters. In predicate logic, we will encounter interpretations that include other elements in addition to a valuation.
 Rules for assigning semantic values to larger expressions of the language. For sentential logic, these rules assign a truth value to larger formulae based on truth values assigned to smaller formulae. For more complex syntaxes (such as for predicate logic), values are assigned in a more complex fashion.
An extended valuation assigns truth values to the molecular formulae of (or similar sentential language) based on a valuation. A valuation for sentence letters is extended by a set of rules to cover all formulae.
ValuationsEdit
We can give a (partial) valuation as:
(Remember that we are abbreviating our sentence letters by omitting superscripts.)
Usually, we are only interested in the truth values of a few sentence letters. The truth values assigned to other sentence letters can be random.
Given this valuation, we say:
Indeed, we can define a valuation as a function taking sentence letters as its arguments and truth values as its values (hence the name 'truth value'). Note that does not have a fixed interpretation or valuation for sentence letters. Rather, we specify interpretations for temporary use.
Extended valuationsEdit
An extended interpretation generates the truth values of longer sentences given an interpretation. For sentential logic, an interpretation is a valuation, so an extended interpretation is an extended valuation. We define an extension of valuation as follows.
ExampleEdit
We will determine the truth value of this example sentence given two valuations.
First, consider the following valuation:
(2) By clause (i):
(3) By (1) and clause (iii),
(4) By (1) and clause (iv),
(5) By (4) and clause (v),
(6) By (3), (5) and clause (v),
Thus (1) is false in our interpretation.
Next, try the valuation:
(7) By clause (i):
(8) By (7) and clause (iii),
(9) By (7) and clause (iv),
(10) By (9) and clause (v),
(11) By (8), (10) and clause (v),
Thus (1) is true in this second interpretation. Note that we did a bit more work this time than necessary. By clause (v), (8) is sufficient for the truth of (1).
Truth TablesEdit
In the Formal Syntax, we earlier gave a formal semantics for sentential logic. A truth table is a device for using this form syntax in calculating the truth value of a larger formula given an interpretation (an assignment of truth values to sentence letters). Truth tables may also help clarify the material from the Formal Syntax.
Basic tablesEdit
NegationEdit
We begin with the truth table for negation. It corresponds to clause (ii) of our definition for extended valuations.

T and F represent True and False respectively. Each row represents an interpretation. The first column shows what truth value the interpretation assigns to the sentence letter . In the first row, the interpretation assigns the value True. In the second row, the interpretation assigns the value False.
The second column shows the value receives under a given row's interpretation. Under the interpretation of the first row, has the value False. Under the interpretation of the second row, has the value True.
We can put this more formally. The first row of the truth table above shows that when = True, = False. The second row shows that when = False, = True. We can also put things more simply: a negation has the opposite truth value than that which is negated.
ConjunctionEdit
The truth table for conjunction corresponds to clause (iii) of our definition for extended valuations.

Here we have two sentence letters and so four possible interpretations, each represented by a single row. The first two columns show what the four interpretations assign to and . The interpretation represented by the first row assigns both sentence letters the value True, and so on. The last column shows the value assigned to . You can see that the conjunction is true when both conjuncts are true—and the conjunction is false otherwise, namely when at least one conjunct is false.
DisjunctionEdit
The truth table for disjunction corresponds to clause (iv) of our definition for extended valuations.

Here we see that a disjunction is true when at least one of the disjuncts is true—and the disjunction is false otherwise, namely when both disjuncts are false.
ConditionalEdit
The truth table for conditional corresponds to clause (v) of our definition for extended valuations.

A conditional is true when either its antecedent is false or its consequent is true (or both). It is false otherwise, namely when the antecedent is true and the consequent is false.
BiconditionalEdit
The truth table for biconditional corresponds to clause (vi) of our definition for extended valuations.

A biconditional is true when both parts have the same truth value. It is false when the two parts have opposite truth values.
ExampleEdit
We will use the same example sentence from Formal Semantics:
We construct its truth table as follows:

With three sentence letters, we need eight valuations (and so lines of the truth table) to cover all cases. The table builds the example sentence in parts. The column was based on the and columns. The column was based on the and columns. This in turn was the basis for its negation in the next column. Finally, the last column was based on the and columns.
We see from this truth table that the example sentence is false when both and are true, and it is true otherwise.
This table can be written in a more compressed format as follows.

The numbers above the connectives are not part of the truth table but rather show what order the columns were filled in.
Satisfaction and validity of formulaeEdit
SatisfactionEdit
In sentential logic, an interpretation under which a formula is true is said to satisfy that formula. In predicate logic, the notion of satisfaction is a bit more complex. A formula is satisfiable if and only if it is true under at least one interpretation (that is, if and only if at least one interpretation satisfies the formula). The example truth table of Truth Tables showed that the following sentence is satisfiable.
For a simpler example, the formula is satisfiable because it is true under any interpretation that assigns the value False.
We can use the following convenient notation to say that the interpretation satisfies (or does not satisfy) .
We can extend the notion of satisfaction to sets of formulae. A set of formulae is satisfiable if and only if there is an interpretation under which every formula of the set is true (that is, the interpretation satisfies every formula of the set).
A formula is unsatisfiable if and only if there is no interpretation under which it is true. A trivial example is
You can easily confirm by doing a truth table that the formula is false no matter what truth value an interpretation assigns to . We say that an unsatisfiable formula is logically false. One can say that an unsatisfiable formula of sentential logic (but not one of predicate logic) is tautologically false.
ValidityEdit
A formula is valid if and only if it is satisfied under every interpretation. For example,
is valid. You can easily confirm by a truth table that it is true no matter what the interpretation assigns to . We say that a vaild sentence is logically true. We call a valid formula of sentential logic—but not one of predicate logic—a tautology.
We can use the following convenient notation to say that is (or is not) valid.
EquivalenceEdit
Two formulae are equivalent if and only if they are true under exactly the same interpretations. You can easily confirm by truth table that any interpretation that satisfies also satisfies . In addition, any interpretation that satisfies also satisfies . Thus they are equivalent.
We can use the following convenient notation to say that and are equivalent.
which is true if and only if
Validity of argumentsEdit
An argument is a set of formulae designated as premises together with a single sentence designated as the conclusion. Intuitively, we want the premises jointly to constitute a reason to believe the conclusion. For our purposes an argument is any set of premises together with any conclusion. That can be a bit artificial for some particularly silly arguments, but the logical properties of an argument do not depend on whether it is silly or whether anyone actually does or might consider the premises to be a reason to believe the conclusion. We consider arguments as if one does or might consider the premises to be a reason for the conclusion independently of whether anyone actually does or might do so. Even an empty set of premises together with a conclusion counts as an argument.
The following examples show the same argument using several notations.
 Example 1
 Therefore
 Example 2
 ∴
 Example 3
 Example 4
 ∴
An argument is valid if and only if every interpretation that satisfies all the premises also satisfies the conclusion. A conclusion of a valid argument is a logical consequence of its premises. We can express the validity (or invalidity) of the argument with as its set of premises and as its conclusion using the following notation.
 (1)
 (2)
For example, we have
Validity for arguments, or logical consequence, is the central notion driving the intuitions on which we build a logic. We want to know whether our arguments are good arguments, that is, whether they represent good reasoning. We want to know whether the premises of an argument constitute good reason to believe the conclusion. Validity is one essential feature of a good argument. It is not the only essential feature. A valid argument with at least one false premise is useless. Validity is the truthpreserving feature. It does not tell us that the conclusion is true, only that the logical features of the argument are such that, if the premises are true, then the conclusion is. A valid argument with true premises is sound.
There are other less formal features that a good argument needs. Just because the premises are true does not mean that they are believed, that we have any reason to believe them, or that we could collect evidence for them. It should also be noted that validity only applies to certain types of arguments, particularly deductive arguments. Deductive arguments are intended to be valid. The archetypical example for a deductive argument is a mathematical proof. Inductive arguments, of which scientific arguments provide the archetypical example, are not intended to be valid. The truth of the premises are not intended to guarantee that the conclusion is true. Rather, the truth of the premises are intended to make the truth of the conclusion highly probably or likely. In science, we do not intend to offer mathematical proofs. Rather, we gather evidence.
Formulae and argumentsEdit
For every valid formula, there is a corresponding valid argument having the valid formula as its conclusion and the empty set as its set of premises. Thus
if and only if
For every valid argument with finitely many premises, there is a corresponding valid formula. Consider a valid argument with as the conclusion and having as its premises . Then
There is then the corresponding valid formula
There corresponds to the valid argument
 ∴
the following valid formula:
ImplicationEdit
You may see some text reading our arrow as 'implies' and using 'implications' as an alternative for 'conditional'. This is generally decried as a usemention error. In ordinary English, the following are considered grammatically correct:
 (3) 'That there is smoke implies that there is fire'.
 (4) 'There is smoke' implies 'there is fire'.
In (3), we have one fact or proposition or whatever (the current favorite among philosophers appears to be proposition) implying another of the same species. In (4), we have one sentence implying another.
But the following is considered incorrect:
 There is smoke implies there is fire.
Here, in contrast to (3), there are no quotation marks. Nothing is the subject doing the implying and nothing is the object implied. Rather, we are composing a larger sentence out of smaller ones as if 'implies' were a grammatical conjunction such as 'only if'.
Thus logicians tend to avoid using 'implication' to mean conditional. Rather, they use 'implies' to mean has as a logical consequence and 'implication' to mean valid argument. In doing this, they are following the model of (4) rather than (3). In particular, they read (1) and (2) as ' implies (or does not imply) .
ExpressibilityEdit
Truth functionsEdit
A formula with n sentence letters requires lines in its truth table. And there are possible truth functions having a truth table of m lines. Thus there are possible truth functions of n sentence letters. There are 4 possible truth functions of one sentence letter (requiring a 2 line truth table) and 16 possible truth functions of two sentence letters (requiring a 4 line truth table). We illustrate this with the following tables. The numbered columns represent the different possibilities for the column of a main connective.

You will recognize column (iii) as the negation truth function.

Column (ii) represents the truth function for disjunction, column (v) represents conditional, column (vii) represents biconditional, and column (viii) represents conjunction.
Expressing arbitrary truth functionsEdit
The question arises whether we have enough connectives to represent all the truth functions of any number of sentence letters. Remember that each row represents one valuation. We can express that valuation by conjoining sentence letters assigned True under that valuation and negations of sentence letters assigned false under that valuation. The four valuations of the second table above can be expressed as
Now we can express an arbitrary truth function by disjoining the valuations under which the truth function has the value true. For example, we can express column (x) with:
 (1)
You can confirm by completing the truth table that this produces the desired result. The formula is true when either (a) is true and is false or (b) is false and is true. There is an easier way to express this same truth function: . Coming up with a simple way to express an arbitrary truth function may require insight, but at least we have an automatic mechanism for finding some way to express it.
Now consider a second example. We want to express a truth function of , , and , and we want this to be true under (and only under) the following three valuations.
(i)  (ii)  (iii)  
True  False  False  
True  True  False  
False  False  True 
We can express the three conditions which yield true as
Now we need to say that either the first condition holds or that the second condition holds or that the third condition holds:
 (2)
You can verify by a truth table that it yields the desired result, that the formula is true in just the interpretation above.
This technique for expressing arbitrary truth functions does not work for truth functions evaluating to False in every interpretation. We need at least one interpretation yielding True in order to get the formula started. However, we can use any tautologically false formula to express such truth functions. will suffice.
Normal formsEdit
A normal form provides a standardized rule of expression where any formula is equivalent to one which conforms to the rule. It will be useful in the following to define a literal as a sentence letter or its negation.
The technique for expressing arbitrary truth functions used formulae in disjunctive normal form. A formula in disjunctive normal form is a disjunction of conjunctions of literals. For the purposes of this definition, we countenance manyplace disjunctions and conjunctions such as or . Also for the purpose of this definition we countenance degenerate disjunctions and conjunctions of only one disjunct or conjunct. Thus we count as being in disjunctive normal form. It is a degenerate (oneplace) disjunction of a degenerate (oneplace) conjunction. We could make it less degenerate (but more debauched) by converting it to the equivalent formula .
There is another common normal form in sentential logic, conjunctive normal form. Conjunctive normal form is a conjunction of disjunctions of literals. We can express arbitrary truth functions in conjunctive normal form. First, take the valuations for which the truth function evaluates to False. For each such valuation, form a disjunction of sentence letters the valuation assigns False together with the negations of sentence letters the valuation assign true. For the valuation
 : False
 : True
 : False
we form the disjunction
The conjunctive normal form expression of an arbitrary truth function is the conjunction of all such disjunctions matching the interpretations for which the truth function evaluates to false. The conjunctive normal form equivalent of (1) above is
The conjunctive normal form equivalent of (2) above is
Interdefinability of connectivesEdit
Negation and conjunction are sufficient to express the other three connectives and indeed any arbitrary truth function.
Negation and disjunction are sufficient to express the other three connectives and indeed any arbitrary truth function.
Negation and conditional are sufficient to express the other three connectives and indeed any arbitrary truth function.
Negation and biconditional are not sufficient to express the other three connectives.
Joint and alternative denialsEdit
We have seen that three pairs of connectives are each jointly sufficient to express any arbitrary truth function. The question arises, is it possible to express any arbitrary truth function with just one connective? The answer is yes, but not with any of our connectives. There are two possible binary connectives each of which, if added to , would be sufficient.
Alternative denialEdit
Alternative denial, sometimes called NAND. The usual symbol for this is called the Sheffer stroke. Temporarily add the symbol to and let be True when at least one of or is false. It has the truth table :

We now have the following equivalences.
Joint denialEdit
Joint denial, sometimes called NOR. Temporarily add the symbol to and let be True when both and are false. It has the truth table :

We now have the following equivalences.
Properties of Sentential ConnectivesEdit
Here we list some of the more famous, historically important, or otherwise useful equivalences and tautologies. They can be added to the ones listed in Interdefinability of connectives. We can go on at quite some length here, but will try to keep the list somewhat restrained. Remember that for every equivalence of and , there is a related tautology .
BivalenceEdit
Every formula has exactly one of two truth values.
 Law of Excluded Middle
 Law of NonContradiction
Analogues to arithmetic lawsEdit
Some familiar laws from arithmetic have analogues in sentential logic.
ReflexivityEdit
Conditional and biconditional (but not conjunction and disjunction) are reflexive.
CommutativityEdit
Conjunction, disjunction, and biconditional (but not conditional) are commutative.
AssociativityEdit
Conjunction, disjunction, and biconditional (but not conditional) are associative.
DistributionEdit
We list ten distribution laws. Of these, probably the most important are that conjunction and disjunction distribute over each other and that conditional distributes over itself.
TransitivityEdit
Conjunction, conditional, and biconditional (but not disjunction) are transitive.
Other tautologies and equivalencesEdit
ConditionalsEdit
These tautologies and equivalences are mostly about conditionals.
BiconditionalsEdit
These tautologies and equivalences are mostly about biconditionals.
MiscellaneousEdit
We repeat DeMorgan's Laws from the Interdefinability of connectives section of Expressibility and add two additional forms. We also list some additional tautologies and equivalences.
 Idempotence for conjunction
 Idempotence for disjunction
 Disjunctive addition
 Disjunctive addition
 Demorgan's Laws
 Demorgan's Laws
 Demorgan's Laws
 Demorgan's Laws
 Double Negation
Deduction and reduction principlesEdit
The following two principles will be used in constructing our derivation system on a later page. They can easily be proven, but—since they are neither tautologies nor equivalences—it takes more than a mere truth table to do so. We will not attempt the proof here.
Deduction principleEdit
Let and both be formulae, and let be a set of formulae.
Reduction principleEdit
Let and both be formulae, and let be a set of formulae.
Substitution and InterchangeEdit
This page will use the notions of occurrence and subformula introduced at the Additional terminology section of Formal Syntax. These notions have been little used if at all since then, so you might want to review them.
SubstitutionEdit
Tautological formsEdit
We have introduced a number of tautologies, one example being
 (1)
This has the (informally written) form
 (2)
As it turns out, any formula matching this form is a tautology. Thus, for example,
 (3)
is a tautology. This process is general. Take any tautology. Find its most fully explicitly form by uniformly replacing distinct sentence letters with distinct Greek letters. We can call this a tautological form, which will not be a formula but rather a metalogical expression. Any instance of this tautological form is a tautology.
Substitution instancesEdit
The preceding illustrated how we can generate new tautologies from old ones via tautological forms. Here, we will show how to generate tautologies without resort to tautological forms. To do this, we will define a substitution instance of a formula. Any substitution instance of a tautology is also a tautology.
First, we define the simple substitution instance of a formula for a sentence letter. Let and be formulae and be a sentence letter. The simple substitution instance is the result of replacing every occurrence of in with an occurrence of . A substitution instance of formulae for a sentence letters is the result of a chain of simple substitution instances. In particular, a chain of zero simple substitutions instances starting from is a substitution instance and indeed is just itself. Thus, any formula is a substitution instance of itself.
It turns out that if is a tautology, then so is any simple substitution instance . If we start with a tautology and generate a chain of simple substitution instances, then every formula in the chain is also a tautology. Thus any (not necessarily simple) substitution instance of a tautology is also a tautology.
Substitution examplesEdit
Consider (1) again. We substitute for every occurrence of in (1). This gives us the following simple substitution instance of (1):
 (4)
In this, we substitute for . That gives us (3) as a simple substitution instance of (4). Since (3) is the result of a chain of two simple substitution instances, it is a (nonsimple) substitution instance of (1) Since (1) is a tautology, so is (3). We can express the chain of substitutions as
Take another example, also starting from (1). We want to obtain
 (5)
Our first attempt won't work. First we substitute for obtaining
Next we substitute for obtaining
 (6)
This is indeed a tautology, but it is not the one we wanted. Let's try again. In (1), we substitute for obtaining
Now substitute for obtaining
Finally, substituting for gets us the result we wanted, namely (5). Since (1) is a tautology, so is (5). We can express the chain of substitutions as
Simultaneous substitutionsEdit
We can compress a chain of simple substitutions into a single complex substitution. Let , , , ... be formulae; let , , ... be sentence letters. We define a simultaneous substitution instance of formulas for sentence letters be the result of starting with and simultaneously replacing with , with , .... We can regenerate our examples.
The previously generated formula (3) is
Similarly, (5) is
Finally (6) is
When we get to predicate logic, simultaneous substitution instances will not be available. That is why we defined substitution instance by reference to a chain of simple substitution instances rather than as a simultaneous substitution instance.
InterchangeEdit
Interchange of equivalent subformulaeEdit
We previously saw the following equivalence at Properties of Sentential Connectives:
You then might expect the following equivalence:
This expectation is correct; the two formulae are equivalent. Let and be equivalent formulae. Let be a formula in which occurs as a subformula. Finally, let be the result of replacing in at least one (not necessarily all) occurrences of with . Then and are equivalent. This replacement is called an interchange.
For a second example, suppose we want to generate the equivalence
We note the following equivalence:
These two formulae can be confirmed to be equivalent either by truth table or, more easily, by substituting for in both formulae of (7).
This substitution does indeed establish (9) as an equivalence. We already noted that and are equivalent if and only if is a tautology. Based on (7), we get the tautology
Our substitution then yields
which is also a tautology. The corresponding equivalence is then (9).
Based on (9), we can now replace the consequent of with its equivalent. This generates the desired equivalence, namely (8).
Every formula equivalent to a tautology is also a tautology. Thus an interchange of equivalent subformulae within a tautology results in a tautology. For example, we can use the substitution instance of (7):
together with the tautology previously seen at Properties of Sentential Connectives:
to obtain
as a new tautology.
Interchange exampleEdit
As an example, we will use the interdefinability of connectives to express
 (10)
using only conditionals and negations.
Based on
we get the substitution instance
which in turn allows us to replace the appropriate subformula in (10) to get:
 (11)