|
|
Propositional Logic is the most basic branch of Mathematical Logic. It is also called Propositional Calculus (PC). In Latin, calculus means a stone used in counting. In PC, the truth or falsity of a "proposition" can be "counted" - determined - using "Truth Tables."
PC can be described as consisting of a collection of Primitive symbols (or primitives), Definitions, and rules called Formation Rules.
Primitives:
Variable symbols: such as p, q, r. They are infinite in number.
A monadic (or unary) operator ~
Four dyadic (or binary) operators ∧, ∨, ⇒, and ⇔
Two parentheses: ( and )
Formation Rules:
When we string together the variables, operators, and parentheses, we get a string of those; any such string is called a "formula." The Formation Rules describe how to produce a Well Formed Formula (wff). Well-formed formulas will be called "wffs".
Rule (1) A variable standing alone is a wff.
Rule (2) If p is a wff, so is ~p.
Rule (3) If p and q are wffs, (p∧q), (p∨q), (pÉq), and (p⇔q) are wffs.
Example:
This is a wff: p∧(q∨r).
This is not a wff: p~
This is not a wff: p~q
This is not a wff: pq
This is not a wff: p∨⇒q
So there are an infinite number of formulas that are not wffs, just as there are an infinite number that are wffs.
Definitions:
Let p and q be variables.
(0) Each of the variables can take one of two values: T (true) or F (false). These are the truth values.
(1) ~p means "not p" and is false when p is true and true when p is false. We say ~p is the negation of p.
(2) p∧q means "p and q" which is to count as true when p and q are both true and as false in all other cases. p∧q is said to be the conjunction of p and q; p and q are called the conjuncts. The symbol "." is often used in place of "∧." Thus p∧q and p.q are the same. It is also the convention to write the conjunction of p and q as pq.
(3) p∨q means "p or q" which is to count as false when p and q are both false and true in all other cases; thus it represents the assertion that at least one of p and q is true. p∨q is called the disjunction of p and q; p and q are known as disjuncts.
(4) p ⇒ q means "if p then q" or " p implies q" which is to count as false when p is true and q is false, and true in all other cases.
⇒ is the implication sign. In p ⇒ q, p is known as the antecedent and q as the consequent. q ⇒ p is called the converse of p ⇒ q.
(5) Last, p ⇔ q means "p is equivalent to q" or "p if and only if q" which is to count as true when p and q have the same truth value (that is, when both are true or when both are false), and false when thay have different truth values.
Valid wffs
PC is a two-valued logic. That is, the variables can take on exactly one of two values: T or F.
(There are logics, where the variables can take on more than two values, such as, say, 1, 1/2, 0.)
An important property of a wff in PC is that when its variables are assigned truth values, the wff as a whole yields either a T or a F. In fact, this is how we decide if a formula in PC is a wff.
The infinitude of wffs can be grouped under three types:
Valid wff: Yields T for all truth value assignments to the variables. Valid wff are called 'tautologies'.
Unsatisfiable or inconsistent: Yields F for all truth value assignments to the variables. These are called 'contradictions'.
Contingent: Yields T for some truth value assignments and F for some other assignments. These are called 'contingencies'.
Since the negation of an inconsistent wff is a valid wff and valid wffs are the ones relevant to the theorems (see below) of mathematics, let us pursue valid wffs.
Here are some of the more important valid wffs of PC. We use "." for ∧. And we use the square brackets in some places for readability. But the square brackets are not in our parenthesis symbols. They just stand for the round brackets.
Some valid wffs of PC
| Law | wff |
| Law of Identity | p ⇔ p |
| Law of Double Negation | p ⇔ ~~p |
| Law of Excluded Middle | p ∨ ~p |
| Law of Noncontradiction | ~(p.~p) |
| De Morgan Laws | (p.q) ⇔ ~(~p ∨ ~q) |
| (p∨q) ⇔ ~(~p.~q) |
| Commutative Laws | (p∨q) ⇔ (q∨p) |
| (p.q) ⇔ (q.p) |
| Associative Laws | [(p∨q)∨r] ⇔ [p∨(q∨r)] |
| [(p.q).r] ⇔ [p.(q.r)] |
| Law of Transposition | (p⇒q) ⇔ (~q ⇒ ~p) |
| Distributive Laws | [p.(q∨r)] ⇔ [(p.q)∨(p.r)] |
| [p∨(q.r)] ⇔ [(p∨q).(p∨r)] |
| Law of Permutation | [p⇒(q⇒r)] ⇔ [q⇒(p⇒r)] |
| Law of Syllogism | (p⇒q) ⇒ [(q⇒r
)⇒(p⇒r)] |
| Law of Exportation | [(p.q)⇒r] ⇔ [(p⇒(q⇒r)] |
We can easily prove that each of these formulas is a valid wff by assigning T and F values to the variables. If there are n variables in a formula, this would result in 2n truth value assignments and in each case the formula will evaluate as T if the formula is a valid wff. For instance, in a formula containing p and q, we could assign T for p and T for q and evaluate the formula; then assign T for p and F for q and evaluate the formula, then assign F for p and T for q, and finally F for p and F for q, resulting in 22 truth value assignments, with the wff evaluating as T in each instance. In PC, there are also other decision procedures for certifying wff as valid wff, but the simplest is the method of truth value assignments which is done easily in a table format called truth table.
In PC, the variables represent "propositions" and, hence, are known as propositional variables. So a wff is a compound proposition.
An instance of a wff is the result of substituting a declarative sentence for each variable in the wff. The declarative sentence must be the type that is either true or false, according to the context. Here is a declarative sentence that does not qualify: "this sentence is false." It is declarative, but neither true nor false. Here is another: "the king of America is wise."
Now consider the wff p É q. Substitute the declarative sentence "it is raining" for p and 'water drops fall on the ground' for q. We get 'If it is raining, water drops fall on the ground'. This is an instance of a (compound) proposition which happens to be a sentence that is true. But suppose we substitute 'water drops do not fall on the ground' for q. Then we have "if it is raining, water drops do not fall on the ground' which is also an instance of a proposition since it also has a truth value, namely F.
The relationship of a proposition (wff) in PC to an instance of the proposition may be likened to that of a statement such as x + y = z in algebra to statements such as 2 + 3 = 6, 2 + 3 = 5, etc., which may be true or false.
What is a Theorem?
A theorem in PC is precisely a tautology (valid wff). Consider the Law of Identity: p ⇔ p. Substitute T for p. We get: T ⇔ T, which according to Definition (5) is true. Now substitute F for p. We get: F ⇔ F, which is again true by Definition (5). So p ⇔ p, yields T for all assignment of truth values and so is a valid wff or tautology. Hence p ⇔ p is a theorem. We can verify similarly that the valid wffs we presented in the list above are all theorems.
A theorem in mathematics is an instance of a tautology in PC. Unfortunately, mathematicians also use the name 'proposition' for theorem. And many use 'theorem' to denote propositions of wide import. In longer proofs, sometimes a whole theorem may need to be proved as part of the argument in the proof. Mathematicians call such a sub-theorem a 'lemma'. For the logician, those too are theorems.
At this point, the beginner may ask: 'Why do we need theorems?' You see, mathematics consists of a collection of theories. Naive Set Theory (NST) is one of them.
A theory, say NST, is constructed starting with some primitive objects such as "set", fundamental assumptions
called axioms such as 'there exists a set', 'Two sets are equal if and only if each is a subset of the other,' and the like, which in turn
causes introduction of new concepts and establishment of their properties and relationships through "theorems."
We singled out NST among all theories because every theory or branch of mathematics - for instance, Plane Euclidean Geometry - is just a specific interpretation of NST.
(A less convenient theory, but one that avoids certain problems that NST has with the infinite, is the ZFC Set Theory.) The point is, mathematics needs theorems, for theorems describe properties of the mathematical objects! And without proof a theorem is not a theorem!
We have given a description of PC in terms of some primitive symbols, definitions, and rules. A more precise approach would be to construct PC itself as an axiom system, starting with primitives ( it would be found that only the negation sign and any one of the three operator primitives ∧, ∨, and ⇒ is necessary, but keeping them all would make the meanings of individual wffs more clear), definitions, formation rules, a list of selected wffs as axioms, and a set of transformation rules for performing specified operations on axioms or theorems.
We have not discussed the transformation rules. Yet it will profit us to be familiar with them, for the inference rules used in mathematics proofs are the transformation rules of PC.
Inference Rules used in Proof
G.R.T.
MathPath - "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright Ó 2001- MathPath
Last updated - January 20, 2007
|
