Propositional Logic: Logic of
statements, i.e. rules of reasoning or axioms about the connectives that produce
statements from statements, such as not, and, or, ifthen,
and if and only if. This is in many ways the basis of logic, and
it is an interesting fact that Propositional Logic or PL was isolated as a
specific logical subject only in the 1920ies. As such, it is the foundation of
First Order Logic, which not only considers statements, but also terms
and quantifiers. There are at present very many published systems of PL, also
of various kinds (Modal Logic, Natural Deduction Systems, Axiomatic Systems
etc.) and with various enrichments or complications (Multivalued Logic etc.)
and the same holds for First Order Logic. The reason to speak of
"Propositional Logic" rather than "Logic of Statements", though that name is
also used for the subject, is that this is the historically most used term for
the subject in English, and the notion of
proposition rather than statement is useful
 if the distinction is kept clear  in that it concerns statements in any
natural language rather than a specific one. Below there is an explanation of
Classical Propositional Logic or CPL, followed by a briefer
explanation of how this can be changed to several other wellknown systems of
propositional logic. A. Classical Propositional Logic
1. Introduction
1.1 Basic concepts
1.2 Basic grammar
1.3 Basic assumptions
1.4 Truthtables
1.5 Tautologies, contradictions and contingencies
1.6 Assorted tautologies
1.7 What one can do with CPL
1.8 Questions about CPL for those new to logic
2. Fundamental definitions
3. Rules of inference and axioms
4. Proofs in CPL
5. Truths about CPL
6. Limitations of CPL 1.1 Basic concepts: Propositional
logic is concerned with
connectives that produce statements from statements, such as not, and, or, ifthen,
and if and only if. These also are the most important and most common in
CPL, if only because other connectives are definable in terms of the given ones,
as will be illustrated below. CPL is a formal logic, which may be
described as arising from a natural language if this is extended with variables.
A variable is a term that does not occur among the nonvariables of the language and that
may replace terms of a certain kind. In PL, the only variables
are variables for propositions.
A proposition in which some terms have been replaced by variables of
appropriate kinds is called a formula, and the variables in a formula may be
uniformally substituted by any
term of the kind it substitutes for. A term replaces another term uniformally in
a formula (or series thereof) if whenever any one term in the formula (or
series) that is replaced by that term, then any other occurrence of the one term
in the formula is also replaced by an occurence of that term.
Indeed, the same can be put clearer by using variables x and y for terms: A
term x replaces another term y uniformally in a formula (or series thereof) if
whenever any one term x in the formula (or
series) that is replaced by that term y, then any other occurrence of the one term
x in the formula is also replaced by an occurence of that term y.
Thus, if "p" and "q" are variables for propositions, "if p and q, then p" is
a formula, and uniformally substituting "it rains" for "p" and "it is cold" for
"q" produces "if it rains and it is cold, then it rains". In this way, having
variables for propositions, a formula may represent a wide class of those
statements that can be obtained from it by uniform substitution.
1.2 Basic grammar: Also, having propositional variables allows one to write a succinct grammar
for fomulas of CPL, namely as follows·
Basic grammar for CPL (first form):
G1. If 'p' is a propositional variable, then 'p' is a formula of CPL.
G2. If 'p' is a formula of CPL, then 'not p' is a formula of CPL.
G3. If 'p' and 'q' are formulas of CPL, then 'p and q' is a formula of CPL.
G4. If 'p' and 'q' are formulas of CPL, then 'p or q' is a formula of CPL.
In the given grammar two simplifications have been made that will be later
undone. First, the logical connectives 'not', 'and' and 'or' have not been
replaced by briefer onecharacter notations; and second, the connectives
'if..then' and 'if and only if' have not been provided for. This motivates the
expression "(first form)".
1.3 Basic assumptions: Next, we can now articulate the basic assumptions for CPL, namely those which
lay down the usages of the terms 'true' and 'false' with formulas of CPL.
Basic assumptions for CPL (first form):
If p and q are formulas of CPL then the following is assumed:
A1. It is true that p or it is false that p.
A2. If it is true that not p, then it is false that p.
A3. If it is false that not p, then is true that p.
A4. If it is true that p and q, then it is true that p and it is true that q.
A5. If it is false that p and q, then it is false that p or it is false that q.
A6. If it is true that p or q, then it is true that p or it is true that q.
A7. If it is false that p or q, then it is false that p and it is false that q.
These may be taken as assumptions about 'and', 'or', 'not', 'true' and
'false', and then fairly natural and obvious ones, for quite a lot of reasoning
with propositions in English and other natural languages conforms to the stated
assumptions (possibly with suitable translations), or they may be taken as
conventions, in the sense that one declares something to the effect 'I will use
these expressions 'and', 'or', 'not', 'true' and 'false' conforming those
conditions.
Note that the basic assumptions for CPL consist of one first assumption about
any formula, to the effect that any formula is true or is false, and three pairs
of assumptions that regulate what is the case if a propositions involving a
connective is true, and what is the case if a propositions involving a
connective is false.
If there is a criticism of these assumptions, it will tend to concern A1,
since it is involved in all the other assumptions. It and its equivalents are
often called 'The Law of Bivalence' or also 'Tertium non datur', which is Latin
for 'there is no third' truthvalue besides
'true' and 'false'.
1.4 Truthtables: Using these basic assumptions, we can introduce truthtables, that are an
alternative way of stating what A1A7 state. To state these, we shall also
replace 'and', 'or', and 'not' by onecharacter abbreviations for them, namely
respectively '&', 'V' and '~'. The main reason to introduce these abbreviations
is that they make especially longer formulas much more perspicuous.
A truthtable is a tabular form made up of rows and columns that lists on the
left side in the first column all possible distinct combinations of variables
that occur in the formulas on the first row that are to be evaluated. Here is
the table for '~' with two consequences:
(0) 
p 
(~p) 
(pV~p) 
(p&~p) 
(1) 
T 
F 
T 
F 
(2) 
F 
T 
T 
F 
The rows are numbered in a special leftmost column, and row (0) lists the
variables in the formulas and the formulas to be evaluated, in this case the
three that make up the top of the last three columns.
Now by A1 any formula is true or false, and accordingly there are for just p
two possibilities, on rows (1) and (2). Now the rows (1) and (2) under the
formula (~p) both follow directly by A2 and A3 respectively. The formula (pV~p)
must be true in any case by A1 and A6 and A7, while that the formula (p&~p) is
never true i.e. always false follows from A1 and A4 and A5.
A formula that is true in any possible case is called a tautology, and
a formula that is true in no possible case is called a contradiction, and
accordingly (pV~p) is a tautology and (p&~p) a contradiction, while the reader
may reason out why the formula ~(p&~p) again is a tautology.
In case of (p&q) and (pVq), which we saw to be formulas by the basic grammar
for CPL, when 'and' is replaced by '&' and 'or' by 'V' the following can be
derived from the basic assumptions:
(0) 
p 
q 
(p&q) 
(pVq) 
(1) 
T 
T 
T 
T 
(2) 
T 
F 
F 
T 
(3) 
F 
T 
F 
T 
(4) 
F 
F 
F 
F 
Note that truthtables are just a device to clearly outline all
possibilities.
It was mentioned above that no proviso had been made for 'if..then' or
'implies' (since that often gives slightly more readable expressions) and 'if
and only if'. One reason not to do so is that both are definable in terms of
what we have already, namely like so: 'p implies q' abbreviates 'not p or q'
while 'p if and only if q' abbreviates 'p implies q and q implies p'.
Introducing abbreviations for these connectives, namely '>' for 'implies' and
'iff' for 'if and only if', it follows the truthtables for them should conform
to this:
(0) 
p 
q 
(p>q) 
(p iff q) 
(1) 
T 
T 
T 
T 
(2) 
T 
F 
F 
F 
(3) 
F 
T 
T 
F 
(4) 
F 
F 
T 
T 
Also, as regards terminology, (p>q) is
called an implication, and (p iff q) an equivalence, the last
because  as the reader can see  p and q are both true or both false. And the
name for (p&q) is a conjunction, and for (pVq) a disjunction.
1.5 Tautologies, contradictions and contingenies: At this point we can use the device of truthtables to illustrate a very
important feature of CPL, namely that on the given assumptions quite a lot of
formulas in several variables turn out to be tautologies, and others
contradictions, and yet others neither, in which case they are said to be
contingent.
Here is an example for the basic formulas ((p and q) implies p) and (p
implies (pVq)) using the abbreviations introduced and with some help to justify
all entries
(0) 
p 
q 
(p&q) 
(pVq) 
(p>q) 
((p&q)>q) 
(p>(pVq)) 
(1) 
T 
T 
T 
T 
T 
T
T T 
T T
T 
(2) 
T 
F 
F 
F 
F 
F
T F 
T T
T 
(3) 
F 
T 
T 
F 
T 
F
T T 
F T
T 
(4) 
F 
F 
T 
T 
T 
F
T F 
F T
F 
If you are not familiar with this reasoning, it makes sense to convince
yourself that you understand all entries in the last two columns. The basic
principles that are involved are that (1) a formula with an implication,
like (A>C), supposing A and C to be formulas, is true whenever A is not true,
by the definition of (A>C) and (2) the component propositions, like '(p&q)'
and '(pVq)' are evaluated inside out, as it were.
Of course, one can reason the stated formulas out much faster than by setting
up a truthtable. Thus, ((p&q)>q) is a tautology
because an implication is true whenever its antecedent is not true, which is the
case whenever ~(p&q), which covers line (2)(4) in the above table and column.
Finally, in case (p&q) is true, (q) must be true since whenever (p&q) both (p)
and (q) are true. Hence it is true in any case. Therefore it is a
tautology.
Also, in a formula with an implication like '(A>C)' 'A' is called the
antecedent and 'C' the consequent (or sometimes also respectively:
the ifclause and the thenclause). In these terms,
'(p>(pVq))' is a tautology because the only cases where the antecedent
are true are cases where the consequent is true. So it never can be false. Hence
it is true in any case. (By A1). Therefore it is a tautology.
1.6 Assorted tautologies: Now here follows a list with assorted
tautologies of CPL, which the reader can all verify with the help of truthtables or by
other means involving the above basic assumptions, followed by a few comments.
Some tautologies are given a common name for those tautologies.
Assorted tautologies of
CPL

For
a single proposition 

pV~p 

~(p&~p) 

p>p 

p iff p 

~~p iff
p
Double negation elimination 

pV~p iff ~(p&~p) 
For
and 

p&q > p 

p&q > q 

p&q
>
q&p
Symmetry of & 

p&(q&r)
iff
(p&q)&r
Associativity of & 
For
or 

p > pVq 

q > qVp 

pVq
>
qVp
Symmetry of V 

pV(qVr)
iff
(pVq)Vr
Associativity of V 
De
Morgan's laws 

~(pVq) iff ~p &
~q 

~(p&q) iff ~p V
~q 
Distributive laws 

p & (qVr) iff
p&q V p&r 

p V (q&r) iff
pVq & pVr 
Equivalents of implications 

p>q iff (p iff
p&q) 

p>q iff
~q>~p 

p>q iff
~(p&~q) 
Inferential principles 

(p
& p>q) >
q
Modus Ponens 

(~q
& p>q) >
~p
Modus Tollens 

(p>(q&~q))
>
~p
Reductio ad absurdum 
For
implies 

(p>(q>r))
> ((q>(p>r)) 

(p>(q>r))
> (p&q >r)) 

((p>q) >
((q>r) > (p>r)) Transitivity of > 
For
if and only if 

(p iff
q) iff (q
iff
p)
Symmetry of iff 

((p iff q) iff
r) iff (p iff (q iff r))
Associativity of iff 

(p iff q) iff
(~p iff ~q) 

~(p iff q) iff
(p iff ~q) 

((p iff q) >
((q iff r)) > (p iff r)) Transitivity of iff 
Here are some comments on the above list of assorted tautologies of CPL. I
follow the headings provided in the list.
For
a single proposition: The reader will probably find that most of these
are quite intuitively true  and indeed one of the pleasant things about CPL and
about truthtables is that these provide means to verify (or falsify) one's
logical intuitions about formulas.
The last two formulas under the heading require some comments.
First, the law of double negation elimination:
~~p iff p. It is easy to verify this is a tautology in CPL, but it should be
noted some people  notably those who believe in intuitionist logic  object to
the validity of (~~p > p), which In CPL follows from the double negation law.
Normally, such people also reject the law of bivalence, and then rightly
so, because given the law of bivalence (~~p > p) is a tautology unless one
also revises other rules. I will have more to say about this later, but at this
stage merely repeat that ~~p iff p is easily verified by a truthtable and
follows from the basic assumptions. Hence, those who wish to reject it must
reject some of the basic assumptions.
Second, the tautology pV~p iff ~(p&~p) is
an example of an equivalence with a tatuology on both sides. Since a tautology
is true in any case and false in none, this holds in fact in CPL for all
tautologies: If t1 and t2 are a tautologies of CPL, then t1 iff t2 is also a
tautology.
For
and: I take it the laws listed here are all intuitive, and only remark
upon the law of associativity: p&(q&r) iff (p&q)&r. The impact of this is that
ordering does not matter to the value of a conjunction, and therefore that one
is free to reorder the terms in a long conjunction. A similar thing holds for
the other laws that are called associative, and it is noteworthy that of &, V,
> and iff only > is not associative, as the reader may verify by setting up
a truthtable.
For or: Again I take it the laws listed under this heading are all
intuitive, and remark only that the first two laws listed for and and the
first two listed for or are a sort of mirrorimage and entail that ((p&q)
> (pVq)).
De Morgan's laws are named after the English 19th Century
mathematician and logician Augustus de Morgan, though the properties of ~, & and
V they state were already known in Antiquity, and discussed by Stoic logicians.
The distributive laws: The reader probably knows a similar sort of
distributive law from elementary algebra: x*(y+z) = x*y + x*z. He also probably
regards the first as intuitively valid, but may have doubts about the second 
and indeed in algebra x+(y*z) ≠ x+y * x+z for most
values of the variables. (Try x=2, y=3, z=3). Even so, in CPL (p V (q&r)) iff
(pVq & pVr) is a tautology, as the reader may verify.
Equivalents of implications: These are based on the definition of
implication in CPL, about which more will be said later. (p>q) iff (p iff
p&q) lists a tautology that is often convenient in arguments, and the
same holds even more for p>q iff
~q>~p, which should be compared with Modus Tollens in the next group. p>q iff
~(p&~q) is an often useful version of implication, and explains its use in
CPL.
Inferential principles: Each of the laws listed as inferential
principles indeed are important and quite common principles of inference. The
first two show that given that an implication is true, the consequent is true if
the antecedent is true, and the antecedent is false if the consequent is false.
Both are what most people expect about "if..then..), which is one reason that
> as defined in CPL meets many intuitions about "if..then..".
Reductio ad absurdum i.e.
(p>(q&~q)) > ~p also is important, since it provides a means to show that a
a proposition is not true: Show that it implies a contradiction.
For implies: The main point of the first two formulas listed under
this heading is that in effect one can gather the antecedents in a series of
implications into a conjunction, and also reorder the antecedents in any
convenient order. And the transitivity of implication, i.e.
((p>q) > ((q>r) > (p>r)), is one that everyone uses intuitively, along
lines like "if q implies r and if p implies q, then also p implies r".
For
if and only if: Again I take it the reader will consider most of these
intuitively true, probably except for associativity of iff: ((p iff q) iff r)
iff (p iff (q iff r)), which he might verify by a truthtable.
1.7 What one can do with CPL: Now let's reflect a moment on what we may have learned so far.
One basic lesson comes to this: Given the assumptions of CPL and the device
of truthtables that may be based on these assumptions, one has a means to test
any formula of CPL, and establish by a truthtable whether it is tautologous,
contradictory or contingent. And this helps testing any argument in English or
any other natural language that can be translated into CPL.
This is important, if only for the reason that it provides a way to test
logical intuitions  which everybody has who speaks a natural language, for all
contain logical connectives 'and', 'or' and 'not', and also
"if.. then" and others that may be defined  in CPL  in terms of the
first three.
Another basic lesson comes to this: Although mathematically speaking, CPL is
neither intricate nor complex, it still shows that a lot of apparent complexity
can be handled by and reduced to a few simple basic assumptions.
One example, amongst very many that might be given, is the formula ((p>(q
> r)) > ((p>q) > (p>r)), which firstly abbreviates a statement
involving six implications that may sound quite formidable and covers any
formula of that form; and secondly concerns a principle of reasoning everybody
relies upon sometimes; and thirdly is easily shown to be a tautology in CPL.
More generally, one can do this for any argument of natural language in so
far as the argument only depends on propositions and connectives and not also on
the terms inside the propositions: One can can translate the argument into CPL
and test whether it is a tautology, contradiction, or contingency of CPL, and
accordingly whether it is respectively valid, invalid, or only valid given
further assumptions.
A third lesson is that to the extent one accepts the basic assumptions of CPL
one has a precise explanation why certain formulas are always true, others never
true, and yet others true in some circumstances and false in others. And note
here that this does not involve an explanation of what "true" is or means, but
only how it is used to evaluate negations, conjunctions and disjunctions,
supposing the axiom of bivalence A1.
1.8 Questions about CPL for those new to logic: The reader who is new to formal logic may at this point inquire what is the
use of tautologies, perhaps motivated by the notion that in natural language
stating a tautology in fact tells the listener or reader nothing he didn't know
already ("If I go, I go! Really!").
That is a good question, and the answer comes by considering  for example 
implications. Suppose that you know or assume that (p>q)  whatever your
reasons for doing so. Now you know that if p is true, q must be true in
any case, supposing CPL i.e. the assumptions that went into it  and thus you
know that if you find that in fact ~q is true, it must follow that either p
is not true or (p>q) is not true, in spite of what you believed you knew or
assumed. Similarly, still supposing CPL i.e. the assumptions that went into it,
given the same implication, you know that if you learn that ~q that then
~p must be true, or else the implication you started with is not true.
And so on. In short, the use of tautologies is that they embody valid
inferences, and one can use them to make inferences from the parts of
tautologies one either knows or assumes.
Another question the logically naive reader may ask is whether learning
formal logic will help him to reason better, perhaps motivated by the notion
that it looks mathematical and he doesn't like mathematics, and besides it is no
use to study a subject if it doesn't help one with something one likes doing.
This is also a good question, and the answers are as follows.
First, about reasoning. Knowing formal logic may not improve one's capacity
to reason logically much, since this seems to be in part native and in part a
matter of long training with reasoning in natural language, but it will
certainly help one to prevent mistakes in reasoning; it will make it
easier to recognize mistakes and explain why they are mistakes;
and it will help pinpoint one's attention to those parts of arguments that are
critical and to recognize those that are trivial.
Hence, knowing formal logic is helpful in that it sharpens such logical
intuitions as one has, and gives one the tools with which to criticize or
investigate all manner of arguments, and explain such intuitions as one has.
Second, about the mathematical look of it. The short of it is that it cannot
be helped and that the notation is there for a very good reason: In principle it
is quite possible to do formal logic merely with variables and English (or any
other natural language), perhaps somewhat regimented by special grammatical
rules as were adopted above for propositions of CPL. The problem is that this
very easily would make one's formulas formidably long, unwieldy, and much harder
to get than with a good notation. (Thus, the above used formula ((p>(q > r))
> ((p>q) > (p>r)) transliterates into English as "If r if q if p, then
if q if p then r if p". This may be shorter than the notation used, but is less
perspicuous.)
Besides, while the subject of formal logic when presented in a modern way
looks like mathematics for the reason just explained, in fact it concerns
reasoning and only uses strict reasoning according to clearly formulated
rules. The notation, that indeed looks mathematical, is there only to help. And
in this sense, logic being about reasoning, the subject of logic is more general
and less complex than what is normally taken to be the subject of mathematics
(numbers, lines, triangles, differentials etc., which at the very least involve
more assumptions than mere logic).
