Maarten Maartensz:    Philosophical Dictionary | Filosofisch Woordenboek                      

 L - Logic - Propositional


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, if-then, 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 1920-ies. 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 (Multi-valued 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 well-known systems of propositional logic.

A. Classical Propositional Logic

1. Introduction

1.1 Basic concepts
1.2 Basic grammar
1.3 Basic assumptions
1.4 Truth-tables

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, if-then, 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 non-variables 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 one-character 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' truth-value besides 'true' and 'false'. 

1.4 Truth-tables: Using these basic assumptions, we can introduce truth-tables, that are an alternative way of stating what A1-A7 state. To state these, we shall also replace 'and', 'or', and 'not' by one-character 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 truth-table 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 truth-tables 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 truth-tables 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 truth-tables 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 truth-table. 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 if-clause and the then-clause). 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 truth-tables 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
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 truth-tables 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 truth-table 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 re-order 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 truth-table.

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 mirror-image 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 truth-table.

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 truth-tables that may be based on these assumptions, one has a means to test any formula of CPL, and establish by a truth-table 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).


See also: Basic Logic, Natural Logic


Carnap, Cartwright,

 Original: Sep 16, 2004                                                Last edited: 10 October 2007.   Top