SENTENCE LOGIC

Definition 1: By a statement, or a proposition, is meant a sentence which is either true or false, but not both. Statements are generally denoted by the lower case letters p, q, r, ....
For example, the following are statements or propositions:

(1) The numbe 2 is prime. (True)
(2) 5 + 6 = 12 (False)
(3) Sunday is the first day of the week. (True)
(4) Ice is a liquid. (False)

(5) Are you listening? (A question)
(6) Stop what you are doing! (A command)
(7) Wow, what a day! (An exclamation)
(8) The gobblegook spackled the whatach-you-call-it. (Meaningless)

Definition 2: The statement ~p, read "not-p" and called the negation of statement p, and is defined to be the denial of statement p. That is, ~p is false if p is true, and ~p is true if p is false.
Truth tables are used to show all the possible truth values that statements may have.
The following is the truth table for the negation of the proposition p.

p	~p
T	F
F	T

Any proposition symbolized by a single letter is called a simple proposition . Logical relations or connectives are symbols placed between two statements to form a new statement, called compound statements or propositions. Below are the definitions of the four basic logical relations.

Definition 3: The proposition (p V q), read "p or q" and called the disjunction of p and q, is false when both p and q are false and is true otherwise. Disjunction is used logically in the inclusive sence of "and/or" of the Latin word vel. Indeed the symbol V looks like the initial letter of that word. For example, "2 + 2 = 4 or December is a month" is a true disjunction.
The following is the truth table for the disjunction of the propositions p and q.

p	q	p V q
T	T	T
T	F	T
F	T	T
F	F	F

Definition 4: The proposition (p & q), read "p and q" and called the conjunction of p and q, is true when both p and q are true and is false otherwise. Conjunction has the usual meaning given "and," except that the two statements need not be related otherwise.

The following is the truth table for the conjunction of the propositions p and q.

p	q	p & q
T	T	T
T	F	F
F	T	F
F	F	F

Definition 5: The proposition p > q, read "p implies q" or "if p, then q" and called implication or conditional, is false when p is true and q is false, and is true otherwise. The proposition p is called the antecedent and the proposition q is called the consequent. In mathematical theorems of the form of a implication (p > q), p is called the hypothesis and q is called the conclusion, and are so related that the implication can not be false; that is, it is impossible for the hypothesis to be true, and the conclusion to be false. Normally when one says, "If it rains, then I will stay home," the meaning usually includes the inverse statement, "If it does not rain , then I will not stay home." This is not the case for logical implication. As a logical implication, this statement says nothing about the case when it does not rain. This definition of implication allows the following statement to be true, except in the case when the consequent is false and the antecedent is true. "If a figure is a square, then it has four right angles."

The following is the truth table for implication.

p	q	p > q
T	T	T
T	F	F
F	T	T
F	F	T

Mathematicans often use another way of expressing implication. For example, they speak of "a necessary condition that p is true is that q is true." That is, q is necessary for p. Eating is necessary for living. (If one is to live, then one must eat.) Consider the truth table for implication above. Note in the rows where p implies q is true (in third column), q must be true for p to be true; that is, among those rows there is no case in which q is false and p is true. (q is necesary for p.) Mathematican also speak of "a sufficient condition that p be true is that q be true." That is, p is sufficient for q. To speed is sufficient to be arrested. (If one speeds, then one will be arrested.) Consider again the truth table above. In the rows where p implies q is true, q is true if p is true. (p is sufficient for q.) Note also that in those rows where p implies q is true, there is no case in which p is true and q is false; that is, p is true only if q is true. (Only if q, then p).
The following table summarizes this discussion.

p > q	if p, then q	p is sufficient for q
p > q	only if q, then p	q is necessary for p
q > p	only if p, then q	p is necessary for q
q > p	if q, then p	q is sufficient for p
p = q	q if, and only if, p	p is necessary and sufficient for q
p = q	p if, and only if, q	q is necessary and sufficient for p

Entries in the same row are equivalent statements. The first two rows represent the given implication; the third and fourth rows represent its converse; and the fifth and sixth rows represent a biconditional.

Definition 6: The proposition p = q, read "p if, and only if, q" and called biconditional, is true when p and q both are true or both false. A biconditional is false when one of p and q is true and the other is false. Often the abbreviation iff is used for "if, and only if." The biconditional proposition p = q is also read "p is necessary and sufficient for q," or "q is sufficient and necessary for p."

The following is the truth table for the biconditional relation.

p	q	p = q
T	T	T
T	F	F
F	T	F
F	F	T

Note that in a biconditional the two statements need not be related. For example, the statement "2 + 2 = 5 iff July 4 is New Year's Day" is a true biconditional, even though the two statements are unrelated as well as both being false.

The following is the truth table for the negative and the four basic logical relations:

p	q	~p	~q	p & q	p V q	p > q	p = q
T	T	F	F	T	T	T	T
T	F	F	T	F	T	F	F
F	T	T	F	F	T	T	F
F	F	T	T	F	F	T	T

Definition 7: A logical statement that is always true is called a tautology; a proposition that is always false is called an absurdity; one that is sometimes true and sometimes false is called a contingency. For example, (p V ~p) is a tautology and (p & ~p) is an absurdity. But ~(p & ~p), (p > p), and (p > ~~p) are tautologies, as can be seen by the following truth table.

p	~p	p V ~p	p & ~p	~(p & ~p)	p > p	~(~p)	p > ~(~p)
T	F	T	F	T	T	T	T
F	T	T	F	T	T	F	T

Some further examples are [p > (p & q)] is a contingency, while [(p & q) > p] and
[(p & q) = (q & p)] are tautologies, as can be seen by the following truth tables.

p	q	p & q	q & p	p > q	p > (p & q)	(p & q) > p	(p & q) = (q & p)
T	T	T	T	T	T	T	T
T	F	F	F	F	F	T	T
F	T	F	F	T	T	T	T
F	F	F	F	T	T	T	T

Statements with the same truth table are equivalent. The proposition p is said to be equivalent to the proposition q, written (p ≡ q) and read "p is equivalent to q", if, and only if, the biconditional (p = q) is a tautology. Two propositions are equivalents, not because they are identical, but because they have the same truth values. For example in the above, [p > (p & q)] is equivalent to (p > q) and (p & q) is equivalent to (q & p). In any logical argument a statement can be replaced by any equivalent one. The following table shows some important equivalent statememts.

Statements	Equivalent Statements
	Conjunction	Disjunction	Implication
p & q		~(~p V ~q)	~(p > ~q)
p V q	~(~p & ~q)		~p > q
p > q	~(p & ~q)	~p V q

This table shows that each logical relation in the first column can be expressed in terms of the negation and just one of the &, V, or >. The biconditional is not included in this table, since
p = q is equivalent to (p > q) & (q > p) and (~p V q) & (~q V p), containing two logical relations at a time.

Definition 8: If the implication (p > q) is called the given, then the statement (q > p) is called its converse, (~p > ~q) is called its inverse, and (~q > ~p) is called the contrapositive.
The next theorem indicates the logical relation between these four statements in general.

Theorem 1: The given statement and its contrapositive are logically equivalent; the converse and the inverse are logically equivalent.
In symbols, (p > q) = (~q > ~p) and (q > p) = (~p > ~q) are tautologies, but (p > q) and (q > p) are contingencies. The following table shows these relations.

p	q	~p	~q	p > q	~q > ~p	q > p	~p > ~q
T	T	F	F	T	T	T	T
T	F	F	T	F	F	T	T
F	T	T	F	T	T	F	F
F	F	T	T	T	T	T	T

Having defined the negation of a proposition p as the denial of p, that is,~p, this definition must be applied to composite propositions, especially the four basic logical relations. The following table summarizes these negations.

	Given Proposition	Its Negation
Disjunction	p V q	~p & ~q
Conjunction	p & q	~p V ~q
Conditional	p > q	p & ~q
Biconditional	p = q	(p = ~q) or (~p = q)

The negations of disjunction and conjunction are known as the DeMorgan's Laws and are tautologies. DeMorgan's Law for conjunction says, for example, that the negation of a conjunction of the propositions p and q is equivalent to the negation of either p or q.; that is, at least one of the propositions must be false. In symbols,
[~(p & q) ≡ (~p V ~q)]. An application of the negation of implication is the proof of the following mathematical theorem: if x² = y², then x = y. In the proof of this theorem by the indirect method, the negation of this theorem is assumed to be true: (x² = y²) and (x ≠ y). If x ≠ y is true, then
x² = y² is false. Therefore the conjunction is false and the theorem is true.

The following theorem contains a list of some important tautologies.
Theorem 2: The following are tautologies:

(1)	~(p & ~p)	Law of contradiction
(2)	p V ~p	Law of excluded middle
(3)	(p V q) = (q V p)	Commutative Law for disjunction
(4)	(p & q) = (q & p)	Commutative Law for conjuction
(5)	[(p V q) V r] = [p V (q V r)]	Associative Law for disjunction
(6)	[(p & q) & r] = [p & (q & r)]	Associative Law for conjunction
(7)	[p & (q V r)] = [(p & q) V (p & r)]	Distributive Law of conjunction over disjunction
(8)	[p V (q & r)] = [(p V q) & (p V r)]	Distributive Law of disjunction over conjunction
(9)	p = ~~p	Law of double negation
(10)	(p > q) = (~q > ~p)	Law of contrapositive or transposition
(11)	[(p > q) & (q > r)] > (p > r)	Law of syllogism (HS)
(12)	[(p > q) & p] > q	Law of detachment (MP)
(13)	[(p > q) & ~q] > ~p	Law of contraposition (MT)
(14)	(p > q) = [p > (p & q)]	Law of absorption (Abs)
(15)	[(p & q) > r] = [p > (q & r)]	Law of exportation
(16)	(p & q) > p	Law of simplification (Simp)
(17)	[(p V q) & ~p] > q	Law of disjunction (DS)
(18)	(p V p) = p	Idempotent Law or tautology for disjunction
(19)	(p & p) = p	Idempotent Law or tautology for conjunction
(20)	~(p V q) = (~p & ~q)	DeMorgan's Law for disjunction
(21)	~(p & q) = (~p V ~q)	DeMorgan's Law for conjunction
(22)	(p > q) = (~p V q)	Conditional or Material Implication
(23)	(p > q) = ~(p & ~q)	Conditional or Material Implication
(24)	(p = q) = [(p > q) & (q > p)]	Biconditional or Material Equivalence
(25)	(p = q) = [(p & q) V (~p & ~q)]	Biconditional or Material Equivalence

An argument is a set of statements in which the final statement (called the conclusion) is said to follow from an initial statement or set of statements (called the premises). If, whenever the premises are true, it follows that the conclusion must be true, the argument is a valid argument. But if the premises is true and the conclusion is false, the argument cannot be valid. Note that an argument may be valid without implying the conclusion or premises are true statements. In fact, the truth of the conclusion is not a necessary and sufficient condition for the validity of the argument. Consider the following argument.

Premise:	All musicians have long hair
Premise:	Louis Armstrong is a musician.
Conclusion:	Louis Armstrong has long hair.

In this example, the argument is valid; however, the conclusion is false. This is only possible if at least one premise is false. In this example the first premise is false and the second is true. Consider another argument.

Premise:	All New Englanders are Americans.
Premise:	All Bostonians are Americans.
Conclusion:	All Bostonians are New Englanders.

In this example, both premises and conclusion are true; however, the argument is invalid. The conclusion, while true, does not follow from the premises.

A valid argument is called a proof. And a sentence that may be proved true is called a theorem. The proof of a mathematical theorem is a valid argument that leads from the premises, which are the axioms of the mathematical system together with the hypothesis of the theorem, to the conclusion of the theorem. Logic provides rules of inference to be used in making proofs.

1. One of the principle rule is the Rule of Detachment, also called the rule of modus ponens (MP), and may be stated as follows: If the statement (p > q) is true and the statement p is true, then the statement q is true. In symbols, [(p > q) & p] > q. This rule is based on the definition of implication as shown in its truth table. The statements p and (p > q) are both true in only the first row of the table; in that same row q is also true. The truth of q can be "detached" from the truth of (p > q), when p is also true. Note that the truth of q cannot be concluded merely on the basis that (p > q) is true. (See row three of the truth table.) This rule is a tautology according to Theorem 2 (12) above. This rule affirms the antecedent of the conditional premise and the conclusion affirms the consequent. Any argument of this form is valid and is said to be the affirmative mode or modus ponens (from the Latin ponere, meaning "to affirm"). A fallacy that often occurs with this rule is called affirmimg the consequent where the premise affirms the consequent of the conditional premise. And it has the following form: [(p > q) & q] > p..This form is invaild, as can be seen from a truth table.

2. Another rule of inference is the Law of Contraposition, also called the rule of modus tollens (MT): If the statement (p q) is true and the statement ~q is true, then the statement ~p is true. In symbols, [(p > q) & ~q] & ~p. This rule is based on the definition of implication as shown in its truth table. The statement (p > q) is true and q is false (~q is true) in the fourth row of the table; in that same row p is false (~p is true). This rule is a tautology according to Theorem 2 (13) above. This rule denies the the consequent of the conditional premise and the conclusion denies the antecedent . Any argument of this form is valid and is said to be in the denying mode or modus tollens (from the Latin tollere, meaning "to deny"). A fallacy that often occurs with this rule is called the denying the antecedent where the premise denies the antecedent of the conditional premise. And it has the following form: [(p > q) & ~p] > ~q. This form is invalid, as can be seen from a truth table.

3. Another rule of inference is the Law of the Syllogism, also called hypothetical syllogism (HS). This asserts that if (p > q) and (q > r), then (p > r). In symbols,
   [(p > q) & (q > r)] > (p > r). This rule is also a tautology according to Theorem 2 (11) above.

4. A fourth rule that is used in mathematical proofs is the Replacement Rule which allows any statement in a proof to be replaced by a logically equivalent statement.

There are two methods of proof of theorems in mathematics: direct and indirect proof.

1. In a direct proof, in whch the theorem is stated in the form of a conditional statement, the hypothesis is assumed to be true and conclusion is deduced by a chain of statements that known to be true. These are known to be true on the basis of definitions, axioms, rules of inference, previous steps in the proof, and previously proven theorems. Note that in direct proof the conclusion is shown to be true under the assumption that the hypothesis is true. Hence the proof merely shows that if the hypothesis is accepted as true, then the conclusion must also be true. As an example of direct proof, consider the following.

   If p and q are true and (p V q) > r, then r is true.
   

   		STATEMENT	REASON
   Proof:	1.	p and q are true	by hypothesis
   	2.	p V q is true	by rule of Addition
   	3.	(p V q) > r	by hypothesis
   	4.	r is true.	by 2, 3 and Modus Ponens QED

2. There are several methods of indirect proof.
   1. One of these methods, using (P > Q) = (~Q > ~P), attempts to show that (~Q > ~P) is true, thus proving the theorem (P > Q). Since (~Q > ~P) is called the contrapositive, this method of indirect proof is called proof by contrapositive. As an example of this method of proof, the following theorem for whole numbers will be proved by this method: If n² is even, then n is even. The contrapositive of this theorem is: If n is not even, then n² is not even. This is the same as saying if n is odd, then n² is odd. (Note: a whole number is even if divisible by 2; an odd number is not divisible by 2 and when an odd number is divided by 2 its quotient is m and its remainder is 1.)
      

      	STATEMENT	REASON
      1.	n = 2m + 1	Definition of odd natural number.
      2.	n² = (2m + 1)²	Properties of equality.
      3.	n² = 4m² + 4m + 1	Product of binomial.
      4.	n² = 2(2m² + 2m) + 1	Factoring common factor of 2.
      5.	n² = 2M + 1	Let 2m² + 2m = 2(m² + m) = M.
      6.	n² is odd	Step 5 and the definition of odd natural number.

      Having proved (~Q > ~P), which is equivalent to (P & Q), the original theorem is proved. QED

   2. A second method of indirect proof is called reducio absurdum, or "proof by contradiction." In this method the mathematican attempts to show that the theorem (P > Q) is true by showing that its negation, ~(P > Q), is false. That is, if ~(P > Q) is false, then (P > Q) is true. And since ~(P > Q) = (P & ~Q), the negation of the (P > Q) is put into the form (P & ~Q). Hence to prove (P > Q), one must show that (P & ~Q) is false by showing that it leads to a contradiction. Thus the proof of the theorem (P > Q) by contradiction consists essentially of assuming that (P & ~Q), which is the conjunction of the hypothesis and the negation of the conclusion, is true and deriving a contradiction (S & ~S), that is, by proving that
      (P & ~Q) > (S & ~S). Since (S & ~S) is always logically false (by the Law of Contradiction), (P & ~Q) > (S & ~S) can hold only if (P & ~Q) is false (See the last row of implication truth table). And if (P & ~Q) is false, then (P > Q) is true. Thus the desired conclusion follows logically from the given hypothesis. This logical justification usually remains in the background of more informal proofs, but is always available to justify the steps of the proof. In the proofs of later mathematical theorems, the details of this method of proof will be elaborated.

      As example of this method of indirect proof by contradiction, consider the following.
      If p and q are true and (p V q) > r, then r is true.
      

      	STATEMENT	REASON
      1.	Assume r is false, or that ~r is true,	using the method of Indirect Proof.
      2.	~r > ~(p V q)	Counterpositive of (p V q) > r
      3.	~(p V q) is true	By 1, 2 and the rule of detachment or Modus Ponens
      4.	~p & ~q	By 3 and DeMorgan's Law for disjunction
      5.	~p is true and ~q is true	By 4 and the rule of Simplification
      6.	~p & p and ~q & q	By 5, hypothesis and the rule of Conjunction
      7.	p V r and q V r	By hypothesis and the rule of Addition
      8.	r is true.	By 7, 5 and the rule of Disjunctive Syllogism. QED

   3. A third method of indirect proof is called proof by counterexample. This method attempts to prove that a theorem is false by citing an example of the theorem that contradicts the theorem. While it is not strictly a proof of a theorem, it is useful to know when a proposed theorem is false, so time is not wasted in the attempt to prove what is not possible to prove. As an example of this method consider the following proposition: All similar triangles are congruent. (Two triamgles are called similar if the angles and ratio of the corresponding sides of one triangle are equal to those of the other. Two triangles are called congruent if they are identical in size and shape.) To prove this false, write its negation: Some similar triangles are not congruent. To prove this, one specific example of two similar, but not congruent, triangles must be exhibited. Since this is easily done, the falsehood of the given proposition is proved. Thus a proposition, which is supposed to be true for all x, is false if there can be found one x for which it is false. Such an x is called a counterexample.