[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] aSiteMap.html>Site map
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] aDirectory.html>Directory
Search this site

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] index.html>Home

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] About/aboutToc.html>1: About
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Synopsis/aSynopsisToc.html>2: Synopsis
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Development/aDevToc.html>3: Development

Next: [Macro error: Can't evaluate the expression because the name "nextURL" hasn't been defined.] >[Macro error: Can't evaluate the expression because the name "nextText" hasn't been defined.]
Previous: [Macro error: Can't evaluate the expression because the name "previousURL" hasn't been defined.] >[Macro error: Can't evaluate the expression because the name "previousText" hasn't been defined.]

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Glossary/aGlossaryToc.html>4: Glossary
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Questions/aQuestionsToc.html>5: Questions

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Essays/aEssaysToc.html>6: Essays
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Notes/aNotesToc.html>7: Notes
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] History/aHistoryToc.html>8: History

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Persons/aPersonsToc.html>9: Persons

[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Supplementary/aSupplementaryToc.html>10: Supplementary
[Macro error: Can't evaluate the expression because the name "topPath" hasn't been defined.] Policy/aPolicyToc.html>11: Policy

... to restore theology to the mainstream of science 

  -This file created 16/5/98 13:58 by Claris Home Page version 2.0

Toward natural religion project

Current development/technical pages

Propositional calculus

Introduction

I introduce propositional caluculus by providing you with a local copy of

The Propositional Calculus

Robert G. Muncaster

[After this introduction is a section on the axiomatisation of propositional calculus]

Basic Components

The propositional calculus is a methodology for modeling logical operations. It's elementary objects are called "atomic propositions", often denoted by letters p, q, r, a, b, etc., and we interpret these to be statements to which we are willing to assign a value of either T (for True) or F (for False).

The Elementary Connectives

The other important element in the propositional calculus is a small collection of operators that take propositions and form from them other propositions (this time no longer atomic). The most elementary of these is the "not" operator. We define the not operator by giving its truth value, i.e. the truth value of not p given all possible truth values for the proposition p. We do this using a "truth table" of the form

The letters in italics below p denote the possible truth values of p. The letters in plain type below 'not' indicate the truth value of 'not p' for each choice of the truth value of p. Thus not p is False if p is True and True if p is False.

Four other connectives are conventionally introduced: and, or, implies, and iff (if and only if, or also known as equivalence). These are "binary" operators, each forming a new proposition out of two others. To define one of these, say "and", we need to give the truth value of "p and q" for every possible truth value of both p and q. We do this in another table:

Again the letters in italics are set down to start. Then the letters in plain type define the 'corresponding' truth value of the proposition 'p and q'. This definition shows that 'p and q' is True if both p and q are True and is otherwise False. This certainly corresponds to our intuition about the logical meaning of the word 'and.' The other three connectives are defined by the tables

We can summarize these as follows:

• p or q is True whenever one or both of p and q are True, otherwise it is False
• p implies q is False if p is False while q is True (since then we would not expect the truth of p to imply the truth of q), but otherwise is True (it is assumed that if p is False then we can infer nothing about the truth of q, and in the absence of a contradictory conclusion we accept the value True)
• p iff q is True whenever p and q are the same and False if they are different

The Inferred Rules of the Propositional Calculus

From these basic building blocks we begin to draw conclusions about more complicated combinations of operators and propositions. These conclusions come in two forms, namely, "rules" and "equivalences". A "rule" is an implication while an equivalence is an iff (i.e. a two way implies). An example of a rule, one referred to a Modus Ponens, is : if p is true, and if p implies q, then q is true. We should think of this as a "Theorem", a statement that requires a proof, but once proven is free for us to use in drawing conclusions about the truth of new propositions (here q) given othe propositions (here 'p' and 'p implies q'). We prove this theorem (rule) using a table as above, but this time the table contains a proof rather than characterizing a definition. What is it that we want to prove? We can summarize the Modus Ponens rule as the proposition: (p and (p implies q)) implies q. Here is the table that contains the "proof".

Step 1: The italic letters are the beginning. Step 2: Then we form the plain letters under the first 'implies' using the definition of implies. Step 3: Next we form the bold letters under the 'and' using the definition of the truth value of 'and and columns 1 and4. Step 4: Finally we use columns 2 and 7 and the definition of the truth value of 'implies' to form the bold italic letters in column 6. Since these are all T, the proposition is always True. This is the proof of Modus Ponens.

There are several other rules that are common in the propositional calculus and we will use them in our work. They are (you should construct a table for each to establish its truth as we did above for Modus Ponens):

• Modus Ponens: if (p) and if (p imples q) then (q)
• Modus Tollens: if (not q) and if (p implies q) then (not p)
• Hypothetical Syllogism: if (p implies q) and (q implies r) then (p implies r)
• Disjunctive Syllogism: if (not p) and if (p or q) then (q)
• Conjunctive Dilemma: if (p implies q) and if (r implies s) and if (p or r) then (q or s)
• Conjunction: if (p) and if (q) then (p and q)
• Addition: if (p) then (p or r)

Inferred Equivalences

An obvious equivalence is the statement that 'not (not p)' is the same as p, i.e. if p is True then not p is False and so not (not p) is True. To 'prove' this we construct a table for the statement 'not (not p) iff p' which characterizes the equivalence. Here is the table:

Step 1: Begin with the columns for p in italics. Step 2: Then we form column 2 in plain type using the definition of not. Step 3: Next we form column 1 in bold using column 2 and the definition of not. Step 4: Finally we form the bold italic letters in column 4 using columns 1 and 5 and the definition of iff. Since this column contains only True, we conclude that the equivalence is always true.

A second example is instructive. The equivalence called Material Implication states that 'p implies q' is equivalent to 'not p or q'. This is an unusual conclusion since it gives us a way to go back and forth between implies connectives and or conectives. Here is the 'proof':

Step 1: Begin with the italic values under p and q. Step 2: Next we infer the plain characters in columns 2 and 5. Step 3: Thereafter we infer the bold characters in column 7. Step 4: Finally we infer the truth values in bold italic in column 4. Since these are all true, the equivalence is proved.

Here is a list of the full set of equivalences commonly considered in the propositional calculus (you should verify each using a table as above):

• Demorgan's Law: not (p or q) is equivalent to ((not p) and (not q))
• Demorgan's Law: not (p and q) is equivalent to ((not p) or (not q))
• Double Negation: not (not p) is equivalent to (p)
• Transposition: (p implies q) is equivalent to ((not q) implies (not p))
• Distribution: (p and (q or r)) is equivalent to ((p and q) or (p and r))
• Distribution: (p or (q and r)) is equivalent to ((p or q) and (p or r))
• Material Implication: (p implies q) is equivalent to ((not p) or q)

Drawing Conclusions Using Rules and Equivalences

In general we will be interested in drawing conclusions from a given set of basic (or perhaps subsequently derived) propositions. When we find a conclusion that we feel follows from our hypotheses, we could "prove" our conclusion is true using tables as we have done above. Fortunately this is rarely necessary. Instead we "prove" things now by showing that they follow from the set of rules and equivalences that have already been proved. Here is an example:

Given that (p) is true, that (p implies q), and that ((not q) or r), then we can conclude (r) is true.

Here is the proof:

Step 1: ((not q) or r) [Given] is equivalent to (q implies r) by Material Implication Step 2: since (p implies q) [Given] and (q implies r) [Step 1], we know (p implies r) by Hypothetical Syllogism Step 3: since (p) [Given] and (p implies r) [Step 2], we conclude (r) by Modus Ponens

The proof is complete.

The axioms of propositional calculus

The truth table approach to propositional calculus is an effective procedure for dealing with small systems of propositions, but there are systems too complex to handle with truth tables. What is required instead is a formal theory of propositional calculus which enables us to talk about these more complex systems.

The meaning of propositional calculus

The propositional calculus takes a very abstract view of propositions. It concerns itself simply with a name and a truth value, true or false, for each proposition. The actual meaning of a proposition is irrelevant to the working of propositional calculus. ,

Uploaded Easter Sunday, 12 April 1998

Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items

Related sites: