Chapter 1

An

Introduction

to

Logic

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1.1             STATEMENTS, NEGATIONS, CONJUNCTIONS,

DISJUNCTIONS,  AND TRUTH TABLES.

 

The theory of logic was developed by many different mathematicians, its roots were laid by  Aristotle, but reached a rigorous level by the nineteenth and early twentieth centuries through the work of Boole, Frege, Whitehead, Russell, Gödel, DeMorgan, etc.  It is the one of the basic building blocks and a foundation of higher level mathematics and gives the mathematician the power to communicate reasoned ideas and thoughts succinctly, clearly, and in an organised manner.

Logic is a formal study to analyze the process of arriving at conclusions based on a given set of premises. Statements are declaratives that are either true or false, but can not be both true and false simultaneously. A simple statements (or prime statement or atom) is a declarative that is either true or false, but not both and cannot be decomposed into any shorter group of statements that would still constitute a meaningful sentence.

Examples of statements are: “The box is blue.” “If you go to the market, then I will go to the sea.”  Whereas, "go to the store!" is not a statement, but a command.  Indeed the first statement, “the box is blue,” is a simple statement; whereas, the second statement ”if you go to the market, then I will go to the sea,” is not since it is composed of a simple statement, “you go to the market,” the simple statement, “I will go to the sea,” and is connected by the connective, “if ð , then à.”

       An argument is a collection of statements called premises followed by a conclusion. The premises are statements which are assumed true, whilst the conclusion is a statement that may or may not follow from the given set of premises (more on this later). So stated differently, the study of logic is a formal study to determine if we assume all the premises to be true, does the necessarily follow from the premises? 

       When a person states something to you, do you agree that it is correct?  Or do you question it and attempt to determine if it is true or not?

       For example, if one person says, "it is raining," it is quite easy to check to see if it is true or not; yet, it is more difficult to check to see if the following is true or not, "If you make a 'A' on the next test, then I will give you $10.00."  The statements are obvious, but will the promise be fulfilled?  We will attempt to answer that question by the end of this section.

       We must first understand the construct of an argument, and it should be noted that it can take on many different forms.  Let us begin our discussion with some basic definitions for compound statements and connectives. Once we  understand compound statements we can then consider arguments.

For example, suppose we have the following:  Khalil has a red corvette.  The opposite of this statement is Khalil does not have a red corvette.  The logical opposite of a statement is called its negation. If "Khalil has a red corvette" is symbolised by a "K,"  then the negation, "Khalil does not have a red corvette," is symbolised by “Ø K.”[1] There are other ways to symbolise not K; for example, ~ K, - K, K¢,`K, KC are all used in different contexts to mean not K.  We shall adopt as a convention the symbol Ø K, but interspersed in the text and exercises shall be the congruent symbols.   

Also, two statements can be joined by a connective called the conjunction, "and."  Bob is tall and Mary is blonde.  Let us symbolise the first statement, "Bob is tall," as "B" and the second statement, "Mary is blonde," as "M."  So, we have the statement B and M, which shall be symbolised as   B Ù M. 

Suppose, however, we had the following two statements joined by the connective called the disjunction, "or."  Raul is a New Yorker or Sonya is saddened at the loss of her aunt.  Let us symbolise the first statement, "Raul is a New Yorker," as "R," and the second, "Sonya is saddened at the loss of her aunt," as "S." So, we have the statement R or S, which shall be symbolised as R  Ú  S. 

Now, let us consider the validity of compound statements. A compound statement is a statement such that it decomposes into simple statements and connectives.  Thus, the shortest compound statement would be of the form not X where X is a simple statement since one cannot have connectives without statements or two simple statements without a connective. 

Let us begin with Khalil.  Suppose he has a red corvette. So, the statement, "Khalil has a red corvette," is, of course, true,; whereas, the statement, "Khalil does not have a red corvette," is false. Similarly, if he does not have a red corvette, the statement, "Khalil has a red corvette," is, of course, false, whereas, the statement, "Khalil does not have a red corvette," is true.

We can represent this in the following manner using a truth table (a table constructed by listing all possible combinations of true and false for the two separate statements followed by the result of the combination of the two statements by the connective):

 

Truth Table 1.1.1       

K

ØK

T

F

F

T

 

So, a truth table is simply a diagramme that lists all possible truth values for the simple statements and then the corresponding truth values for a compound statement.

Suppose Bob is tall, and further Mary is blonde.  Then, is the statement, "Bob is tall

and Mary is blonde," true? Of course.  However, suppose Bob is tall, but Mary is not blonde.  Then is the statement, "Bob is tall and Mary is blonde," true?  No, because the statement, "Mary is blonde," is false.  Suppose Bob is not tall, but Mary is blonde.  The statement, "Bob is tall and Mary is blonde," is also false for the same reason as before: one of the two conditions was false.  Last, suppose Bob is not tall, while Mary is not blonde.  The statement, "Bob is tall and Mary is blonde," is false because both statements are false.  We can represent this in the following manner using a truth table:

 

Truth Table 1.1.2       

B

M

B Ù M

T

T

T

T

F

F

F

T

F

F

F

F

Now, let us consider Raul and Sonya.  Suppose Raul is a New Yorker and Sonya is saddened at the death of her aunt. Is the statement, "Raul is a New Yorker or Sonya is saddened at the death of her aunt," true?  Of course, since both are true.  Consider the situation if Raul is a New Yorker, but Sonya is not saddened at the death of her aunt. Is the statement, "Raul is a New Yorker or Sonya is saddened at the death of her aunt," true? Yes, because one of the two statements was true. Continuing, consider the situation if Raul is not a New Yorker, but Sonya is saddened at the death of her aunt. Is the statement, "Raul is a New Yorker or Sonya is saddened at the death of her aunt," true? Yes, because one of the two statements was true. Finally, consider the situation if Raul is a not New Yorker, while Sonya is not saddened at the death of her aunt. Is the statement, "Raul is a New Yorker or Sonya is saddened at the death of her aunt," true? No, for both conditions are false, therefore, the disjunction is false.

We can represent this in the following manner using a truth table:

 

Truth Table 1.1.3       

R

S

R Ú S

T

T

T

T

F

T

F

T

T

F

F

F

 

Normally, the first statement is symbolised by a p and the second statement is symbolised by a q, and lower case letters are oft used; but, as you can see, this is not important.  The important part is considering all the possible combinations of true and false and then determining if the conjunction, disjunction, or negation is true or false.

Now let us combine two statements with more than one connective.  For example consider the statement, it is not the case that Paul is perfect or Michael is creative.  When we use the phrase, it is not the case that , we mean that we are negating the entire statement .  Therefore, letting P be “Paul is perfect” and letting M be “Michael is creative” we find that Paul is perfect or Michael is creative is symbolised as P Ú M.  To negate this requires us to use parentheses, so the statement, “it is not the case that Paul is perfect or Michael is creative,” is symbolised as Ø (P Ú M).

       A rule to establish order of operations is necessary at this stage of the discussion; thus, note the following (it will be expanded later):

 

Highest precedence              parentheses

not

or/and and/or (from left to right only)   Lowest precedence

 

Thus, we can represent “it is not the case that Paul is perfect or Michael is creative,”  Ø (P Ú M), in the following manner using a truth table:

 

 

 

 

 

Truth Table 1.1.4       

P

M

P Ú M

Ø(P Ú M)

T

T

T

F

T

F

T

F

F

T

T

F

F

F

F

T

 

Note that the order of operation is illustrated by the columns of the truth table.  Therefore, in the construction of a truth table we should follow the order of operations.

Now let us combine more than two statements with more than one connective.  For example consider the statement, Paul is not perfect or Michael is creative and Lisa is lonely.  Letting P be “Paul is perfect,” M be “Michael is creative,” and L be “Lisa is lonely,” we find that Paul is perfect or Michael is creative and Lisa is lonely is symbolised as P Ú M  Ù L.  Nonetheless, note that the order of operation requires the conjunction and disjunction to be of the same precedence and we order from left to right. Therefore, Paul is perfect or Michael is creative and Lisa is lonely is symbolised as (P Ú M)  Ù L. 

Also, note that four rows for the truth table is not sufficient.  There are eight ways to combine true and false in order to represent all the possibilities for the truth of each simple statement

 

Truth Table 1.1.5       

P

M

L

P Ú M

(P Ú M) Ù L

T

T

T

T

T

T

T

F

T

F

T

F

T

T

T

T

F

F

T

F

F

T

T

T

T

F

T

F

T

F

F

F

T

F

F

F

F

F

F

F

 

       Note that the statement did not properly use punctuation. The statement, Paul is not perfect or Michael is creative and Lisa is lonely is properly punctuated as, “, Paul is not perfect or Michael is creative, and Lisa is lonely.”  We cannot allow for ambiguity, thus, if the statement is not properly punctuated, we adopt the convention that punctuation follows the order of precedence.

Let us consider a different statement, Paul is not perfect, or Michael is creative and Lisa is lonely. Noting connectives, punctuation, and letting P be “Paul is perfect,” M be “Michael is creative,” and L be “Lisa is lonely,” we find that Paul is perfect, or Michael is creative and Lisa is lonely is symbolised as P Ú (M  Ù L). 

The truth table is therefore:

 

 

 

 

 

Truth Table 1.1.6       

P

M

L

M Ù L

P Ú (M Ù L)

T

T

T

T

T

T

T

F

F

T

T

F

T

F

T

T

F

F

F

T

F

T

T

T

T

F

T

F

F

F

F

F

T

F

F

F

F

F

F

F

 

Note the truth values obtained for the statement in table 6 are different than in table 5.

Two statements are said to be equivalent (or synonymous, the same, or logically equivalent) only in the instance where the final column of the compleat truth tables are the same where the prime statements were assigned truth values in the exact same order.  Suppose the statement X is equivalent to Y, we symbolise this as X º Y. Two statements are said to non- equivalent in the instance where they are not equivalent (duh). Suppose the statement X is not equivalent to Y, we symbolise this as X  Y.  Finally two statements, X and Y, are said to be logical opposites in the instance where X  º ØY (and Y  º ØX).

       As with any convention, when we wish to symbolise not a particular property in symbol form, we slash through the symbol to represent such a scenario.

Note, that the negation of the conjunction Ø (p  Ù  q) is equivalent to the disjunction

 Øp  Ú  Øq (it is left as an exercise to verify). Also note, the parentheses are necessary, for the statement Ø (p  Ù  q)   is not the same as  Ø p  Ù  q (see truth tables 1.7 and 1.8)!  This is problematic for some people for they might erroneously think the two are the same.  For colloquial statements in English, this can be a problem, but for proper statements in logic it is not.  Let us assign to the symbol p the simple statement “it is pouring” and assign to the symbol q the simple statement Natasha is quick.  Now, the statement, it is not pouring and Natasha is quick is Ø p  Ù  q; whereas, the statement, it is not the case that it is pouring and Natasha is quick is, Ø (p  Ù  q).  Since Ø (p  Ù  q) is equivalent to  Øp  Ú  Øq, for many it would be clearer if one simply said, “it is not pouring or Natasha is not quick.”

 

Truth Table 1.1.7       

P

Q

P Ú Q

Ø(P Ú Q)

T

T

T

F

T

F

T

F

F

T

T

F

F

F

F

T

 

Truth Table 1.1.8       

P

Q

ØP

ØP Ú Q

T

T

F

T

T

F

F

F

F

T

T

T

F

F

T

T

§ 1.1   EXERCISES.

 

1. Construct a compleat truth table for the following statements, identify which statements are logically equivalent, which statements are logical opposites, and which are neither:

 

A.   Øp  Ù  q                                                            B.   p  Ù  ~q

C.   p  Ù  ~q                                                                   D.   p  Ù  q

E.   Øq  Ú  p                                                            F.   Øp  Ú  q

G.   p  Ù  ~p                                                                   H.   ~ (p Ú q)

I.    ~ (p Ù q)                                                           J.    p Ú Øp

 

 

2. Construct a compleat truth table for the following statements:

 

A.   p  Ù  q  Ú  p   Ù  r                                             B.   p  Ù  (q  Ú  p)   Ù  r

C.   p  Ù  q  Ú  (p   Ù  r)                                          D.   (p  Ù  q)  Ú  (p   Ù  r)

E.   Øp  Ù  q  Ú  p   Ù  r                                          F.   p  Ù  ~(q  Ú  p)   Ù  r

G.   p  Ù  q  Ú                                            H.   (p  Ù  Øq)  Ú  (p   Ù  r)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1.2   CONDITIONAL AND BICONDITIONAL STATEMENTS

 

Now, let us investigate the statement, "If you make a 'A' on the next test, then I will give you $10.00."

Let us symbolise "if you make an 'A' on the next test as, p, and the statement "I will give you $10.00," as q. So, we have: if p, then q.  This statement is called the conditional, and is symbolised by : p  Þ  q . It is also symbolised by p ® q, q Ü p, p \ q,  and q ¬ p.  The statement p is called the hypothesis or antecedent and the statement q is called the consequent or conclusion. 

       Now, on to the argument. Suppose you make an 'A' on the next test and I give you $10.00.  Is the statement, "if you make a 'A' on the next test, then I will give you $10.00," true? Yes, because I kept my promise.  However, suppose you make an 'A' on the next test and I do not give you $10.00.  Is the statement, "if you make a 'A' on the next test, then I will give you $10.00," true? No, I have broken my promise to you. Next, suppose you do not make an 'A' on the next test, but I do give you $10.00.  Is the statement, "if you make a 'A' on the next test, then I will give you $10.00," true? Yes.  You have not made the 'A,' but out of the generosity of my heart, I still provide you with the $10.00.  Last, suppose you do not make an 'A' on the next test and I do not give you $10.00.  Is the statement, "if you make a 'A' on the next test, then I will give you $10.00," true? Yes.  You have not made the 'A,' and I do not provide you with the $10.00. The promise still held, because you did not fulfill your part of the bargain.  So, notice if the first part of the conditional is false, it does not matter what happens in the second part- the conditional (the promise) is true. The point of this discussion is that burden of following through on the promise (thus, the conditional) is on me (q; the consequent).  There is no such burden on you (p; the antecedent) since no promise was made by you. We can represent this in the following manner using a truth table:

 

Truth Table 1.2.1       

p

q

p Þ q

T

T

T

T

F

F

F

T

T

F

F

T

 

       The last two rows of the truth table illustrate a condition called the condition of vacuous truth for a conditional.  It illustrates that when the antecedent is false the conditional is always true. For example, “if donkeys fly, [fill in the blank],” for donkeys do not fly so you can say whatever you wish and the conditional is true no matter what is filled in for the blank.  Note that this is the case since the conditional cannot be shown to be false when the antecedent is false.   Note also that the first and third rows of the truth table illustrate that when the consequent is true the conditional is always true.   Hence, of prime importance is the second row.  Focus on that row for it is the row where the conditional is false.  There should never be a case where one argues with a true antecedent implying a false consequent (though the world is rife with examples of just such argument forms). 

Recall truth table 1.1.8.  Compare truth table 1.1.8 and 1.2.1.  Note that these demonstrate that p Þ q  º  Øp Ú q. 

There are many variations of the wording for the conditional.  You must learn these so that you become adept at reading and listening to mathematics. 

The conditional     P Þ Q  ,   P ® Q ,  Q Ü P  , or   Q ¬ P   translates to:

               (1)          If P, then Q.

               (2)          Q, if P

               (3)          P hence Q

               (4)          Q whence P

               (5)          P is a sufficient condition for Q

               (6)          Q is a necessary condition for P

               (7)         P only if Q

               (8)          If not Q, then not P

               (9)          P implies Q

               (10)        Not P, or Q

               (11)        Q whenever P.

So, consider the conditional, “if Alexis is running, then Blake is driving;” stated as a conditional version (1) from above would be (in alternate wording from above):

(2) Blake drives if Alexis runs.

(3) Alexis runs hence Blake drives.

(4) Blake runs whence Alexis drives.

(5) Alexis to be running is a sufficient condition for Blake to be driving.

(6) It is necessary that Blake drive for Alexis to be running.

(7) Alexis runs, only if Blake drives.

(8) If Blake doesn’t drive, then Alexis does not run.

(9) Alexis driving implies Blake runs.

(10) Alexis doesn’t run or Blake is driving.

(11) Blake drives whenever Alexis runs.

       When at least one of the prime statements in the conditional represents a group, then the translation can be slightly different. The conditional P Þ Q translates to:

(12) All Ps are Qs.

(13) No Ps are not Qs.

(14) All of the Ps have the property of Q.

(15) None of the Ps are not Qs.  

For example, consider the conditional, “if that thing is a bird, then it is an animal;” would be:

(12) All birds are animals.

(13) No birds are not animals.

(14) All of the birds have the property of being animals.

(15) None of the birds are not animals.      

       Thus, there are at least fifteen different ways to state a conditional in idiomatic English. The student should learn the different ways to state the conditional; understand the uses (when using plural versus singular concepts); and, be comfortable translating from English to symbols, symbols to English, symbol form to alternate symbol form, and from English form to synonymous English form.

       The biconditional is a compound of two conditionals, if p, then q and if q, then p. Take, for example, p: I am happy, and q: you are gardening.  We would for the biconditional have, "if I am happy, then you are gardening," AND, "if you are gardening, then I am happy."  This is very cumbersome, so we have an easier way to state the biconditional: "I am happy if and only if you are gardening."  One can see that by checking each individual conditional the p  Þ  q  is false only when p is true, and q is false, and the q   Þ  p is false only when q is true and p is false, then combining the two conditionals with a conjunction yields the following:

 

Truth Table 1.2.2       

p

q

p Þ q

q Þ p

(p Þ q) Ù (q Þ p)

T

T

T

T

T

T

F

F

T

F

F

T

T

F

F

F

F

T

T

T

 

Which can be simplified to:

 

Truth Table 1.2.3       

p

q

p Û q

T

T

T

T

F

F

F

T

F

F

F

T

by replacing (p Þ q) Ù (q Þ p) with the more parsimonious symbol p Û q.

 

The biconditional            P Û Q  or   P « Q    translates to:

               (1)   P if and only if Q.

               (2)   P iff Q (this is just a shorthand for version 1).

               (3)   P is necessary and sufficient for Q.

               (4)   P and Q are logically equivalent.

               (5)   If P then Q and if Q then P.

Condition (4) establishes that two statements, P and Q, are logically equivalent in the instance where P Û Q is true for note the only time when P Û Q is true is when both P and Q are true or when both P and Q are false.

Since we have two more symbols we must add them to our order of precedence

Highest precedence              parentheses   ( )

not  ~,  Ø, or ___

and/or (from left to right)       Ù  Ú             

                                            conditional Þ  ®

                                            biconditional     Û  «                        Lowest precedence

Note when two symbols of equal precedence are connecting, then precedence is from left to right (e.g.: P Þ Q Þ R means (P Þ Q) Þ R); but non-equal precedence does not follow left to right but by order of precedence (e.g.: P Þ Q Ù R means P Þ (Q Ù R) and P Ù Q Þ  R means (P Ù Q) Þ  R).

Various types of statements are of interest to mathematicians. A compound statement is a tautology when the compound statement is true for every true-false combination. A statement is a fallacy when the statement is true for at least one true-false combination and is false for at least one true-false combination.  A contradiction is a compound statement that is false for every true-false combination for the prime statements.

       We are interested in discerning what statement forms are tautologies, fallacies, or contradictions so that when we begin investigating argument forms, we can use tautologies or contradictions and avoid fallacies.  A tautological argument is that which we attempt to construct when we prove an assertion.

       Finally there is one other type of disjunction, the exclusive disjunction, which is symbolised as  P  Q.  We reference this because there are times in mathematics when we do not want to have the possibility of both conditions being satisfied but wish to have one or the other exclusively satisfied. 

P or Q, but not both.

P exclusive or Q.

                                    P exor Q.

 

Truth Table 1.2.4       

p

q

p  q

T

T

F

T

F

T

F

T

T

F

F

F

 

Note that P  Q is the logical opposite of  P Û Q.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1.2   EXERCISES.

 

1. Construct a compleat truth table for the following statements, identify which statements are logically equivalent, and which statements are logical opposites:

A.   Øp  Ù  q                                             B.   p Þ q

C.   Øp ® Øq                                           D.   p Ü q

E.   p  Ù  ~q                                              F.    p Û Øq

G.   p  Ù  q                                                H.   Øq  Ú  p

I.   Øp  Ú  q                                               J.   Øp  ®  q

K.   Øq  ®  Øp                                         L.   q  ®  p

M.   Øq  Þ  q                                           N.   p  Ù  ~p 

O.   p Þ p                                                P.   ~ (p Ú q)

Q.  ~ (p Ù q)                                             R.  p  ®  p

 

2. Construct a compleat truth table for the following statements:

A.   (p  Ù  Øq)  Ú  (p   Ù  r)                                            B.   p  Þ  q  Ú  p   Ù  r

C.   p  Ù  (q  ®  p)   Ù  r                                                D.    p  ®  q  Ú  (p   Ù  r)

E.   (p  Ù  q)  Þ  (p   Ù  r)                                              F.   (p  Ù  q)  Þ  p  

G.   (p  Ù  q)  Þ   q                                                        H.   (p  Ú  q)  Þ  p  

I.   (p  Ú  q)  Þ   q                                                          J.   p  Þ   p  Ú  q 

K.   q    Þ  p  Ú  q                                                         L.   q  Þ   p  Ú  q  Ú r

 

3. Let p be "it is foggy" and q be "it is cold."

Translate each of the following into symbolic logic.

A. It is foggy or it is cold.

B. It is not foggy and it is not cold.

C. If it is foggy, then it is warm or hot.

D. The day being foggy is a necessary and sufficient condition for it to be cold.

E. It is false that it is both cold and foggy.

 

4. Write the negation of the following in standard colloquial written English:

A. Either we will buy ice cream or we will rent a movie.

B. Cynthia is charming and Paul is well-mannered.

C. It is false that Rameses is happy and Colette is sad.

D. Ashton is not wealthy.

 

5. Translate the following into symbolic form (do not forget to define symbols representing prime statements):

A.    If this is Tuesday, we must be in Belgium.

B.    It is a bird, if it is an eagle.

C.    All people have heads.

D.    She has no cash or she has a charge plate.

E.    p2 ¹ 25,  p = 5,  or p = -5.

F.    | y + 6 | ¹ 8 and y = 2 or y = -14.

G.    If x + 3 = 5, then x = 1 or x = 2.

H.    If z = 1 and z = 5, then z2 + 2z + 1 = 0.

I.     It is snowing implies it is below 32° F.

J.     It is not snowing or it is below 32° F.

K.   It is necessary that x < 2 for x + 1 < 3.

L.    If the Mets win every game left in the season, then they will win the N. L. East.

M.   Tom always buys an Oldsmobile.

N.   Sarah buys a Toy when she is in New York.

O.   No chicken are teetotalers.

P.    I love New York.

Q.   Nobody is alone who cares for a pet.

R.    Watering grass is sufficient for grass to grow.

S.    If the butler did it, then the maid didn’t.  The butler or the maid did it.  If the maid did it, then the butler did it.

T.    If math was interesting, then I would earn an ‘A.”  Math isn’t interesting. Thus, I am not earning an “A.”

U.    No alterations, redecorating, tacks, or nails shall be made in the building, unless written permission is obtained.  

V.    Babies are illogical.  Nobody is despised who can manage a crocodile.  Illogical people are despised.

W.   If the population increases rapidly and production remains constant, then prices rise.   If prices rise then the government will control prices.  I am rich then I do not care about increases in prices.  It is not true that I am not rich. Either the government does not control prices or I do not care about increases in prices. Therefore, it is not the case that the population increases rapidly and production remains constant.

X.    Dean praises me only if I can be proud of myself.  Either I do well in classes or I cannot be proud of myself.  If I do my best in sports, then I cannot be proud of myself.  Therefore, if Dean praises me, then I do my best in sports.

Y.    If Winston or Halbert wins then Luke and Susan cry.  Susan does not cry.  Thus, Halbert does not win.

Z.    If I enroll in the course and study hard, then I will earn acceptable grades. If I make satisfactory grades, then I am content.  I am not content. Hence, either I did not enroll in this course or I did not study hard.

AA.        If he goes to the party, he does not fail to brush his hair.   To look fascinated is necessary to be tidy.  If he is a sushi eater, then he has no self-command.   If he brushes his hair, he looks fascinated. He wears white gloves only if he goes to the party.  Having no self-command is sufficient to make one look untidy.  Therefore, sushi eaters do not wear white gloves.

BB.         No ducks waltz. No officer ever declined to waltz.  All my poultry are ducks.  Thus, None of my poultry are officers.

CC.        Everyone who is sane can do logic.  None of your sons can do logic. No lunatics are fit to serve on the jury.  Therefore, if he is your son, then he is not on the jury.

DD.        The sum of an irrational number and a rational number is an irrational number.

EE. The product of two negative numbers is a positive number.

FF. The square root of a positive number is a positive number.

GG.         only if .

HH.        If   then .

II.    The square of a negative number is a positive number.

JJ (dyn-o-mite!). a3 = 8, b = 3, and c = 1.  

KK. 7 < 3 and 5 > 4, or 2 = 1.

LL. a2 + b2 = g2 whence a = 3, b = 4, and g = 5.

MM. All of the dated letters in this room are written on blue paper. None of them are in black ink, except those that are written in the third person. I have not filed any of those I have not read. None of those that are written on one sheet are undated. All of those that are not crossed out are written in black ink. All of those that are written by Mr. Brown begin with “Dear Sir.” All of those that are written on blue paper are filed. None of those that are written on more than one sheet are crossed out.  None of those that begin with “Dear Sir” are written in the third person. Hence, I cannot read any of Mr. Brown’s letters.

 

6. Translate the following into symbolic form (do not forget to define symbols representing prime statements) and supply a valid conclusion:

A.    No kitten that loves fish is uneducable.  No kitten without a tail will play with a gorilla.  Kittens with whiskers always love fish.  No educable kitten has green eyes. No kittens have tails unless they have whiskers.

B.    Promise-breakers are untrustworthy. Alcohol drinkers are very verbose. A person who keeps a promise is honest. No teetotalers are pawnbrokers. One can trust a very loquacious person.  

C.    All the dated letters in this room are written on embossed paper.  None of them are in black ink, except those that are written in the third person.  I have not filed any of them that I can read.  None of them that are written on one sheet are undated.  All of them that are not crossed are in black ink.  All of them written by Thomas Brown, Esq. Begin with “Dear Sir.” All of them written on embossed paper are filed.  None of them written on more than one sheet are crossed. None of them that begin with “Dear Sir” are written in the third person.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1.3   THE LAWS OF LOGIC

 

       In mathematics oft times there are concepts that are intuitive or practical that are allowed such that there is general agreement to allow for the claim that such may be assumed.  These  claims are called axioms or postulates and are the basic ideas that underlie a particular area of mathematics.

       Further, there is oft a need to introduce other concepts, notation, symbols, etc.  These are called definitions for they describe a class of objects, a symbol, or other such fundamentals.  The purpose of a definition is to avoid ambiguity, so that clarity, objectivity, and rigor is maintained.  Many definitions are no doubt familiar to you, the reader, for example the definition of the symbol “=, ” or the definition of a natural number. 

However, the definition of a concept may differ depending on context, author, subject, class, etc.   Some authors define the natural numbers to be the collection of numbers 0, 1, 2, 3, 4, 5,  ¼; whilst others define the natural numbers to be the collection of numbers 1, 2, 3, 4, 5, ¼ .  Now clearly these are not logically the same collections[2] but it doesn’t really matter in the long run.[3]  What does matter is that an author, an instructor, etc. must define the meaning of the term natural numbers before proceeding with a discussion of the natural numbers or use of them.

Some definitions will be completely new to you, the student, and thus will have to be learnt without prior exposure.  For example, suppose the author defines a “brent” to be any rational number such that when expressed in reduced fraction form the denominator is 3.   So, a student can easily see that .5 is not a brent, .3 is not a brent, but  is a brent, 1 is not a brent, p is not a brent, .67 is not a brent, but is a brent.

       Furthermore, the definition must completely specify the concept and cannot allow for something to be both the concept and not the concept for that would be self-contradictory; hence, useless (and see the law of double negation below).

We want a definition to be of use and not self-contradictory;  for example, in everyday life the concept of tall is not well defined since it is ambiguous, contextual, and subjective. 

 

Axiom 1:

All prime statements P, Q, R, etc. are statements.

If P is a statement, then  Ø P is a statement.

If P and Q are statements, then P Ú Q is a statement.

If P and Q are statements, then P Ù Q is a statement.

If P and Q are statements, then P Þ Q is a statement.

If P and Q are statements, then P Û Q is a statement.

 

 

Given the previous, then we can deduce that there are tautological statements that are of use to us. 

 

Idempotent Law (1)           P Ú P º P

Idempotent Law (2)           P Ù P º P

 

Truth Table 1.3.1       

P

P Ú P

T

T

F

F

 

Truth Table 1.3.2       

P

P Ù P

T

T

F

F

 

Law of Double Negation          Ø (Ø P)     P   [ same as    Ø (Ø P)  Û  P ]

 

Truth Table 1.3.2       

P

ØP

Ø(Ø P)

T

F

T

F

T

F

 

Law of the Excluded Middle (1)             P  Ú  ØP   is always true[4]

 

Law of the Excluded Middle (2)             P  Ù  ØP   is always false [5]

(Law of Contradiction)

 

Please note that these laws are central to basic (dichotomous) logic.  Therefore, we note the following truth tables as support for the assertion.

 

Truth Table 1.3.3       

P

Ø P

P Ú ØP

T

F

T

F

T

T

 

Truth Table 1.3.4       

P

Ø P

P Ù ØP

T

F

F

F

T

F

Material Implication                               P Þ  Q      Ø P  Ú  Q

(The Or Form of the Implication)

(note: when changing from implication to or form reference or form; when changing from or form to implication reference implication form; or, just reference material implication)                  

 

Truth Table 1.3.5       

P

Q

P Þ Q

ØP

Ø P Ú Q

T

T

T

F

T

T

F

F

F

F

F

T

T

T

T

F

F

T

T

T

 

Table 1.3.5 illustrates the use of one truth table to demonstrate the logical equivalence of two statements.  It is most useful when typing since the letter denoting true or false for the claim can be highlighted using the bold function in a word processing function of a computer. However, when writing a justification of the logical equivalence of two statements it is best to do two separate tables.  

 

Contrapositive Form of the Implication                P Þ  Q      Ø Q  Þ  Ø P

(Transposition)

 

Truth Table 1.3.6       

P

Q

P Þ Q

T

T

T

T

F

F

F

T

T

F

F

T

 

Truth Table 1.3.7       

P

Q

ØQ

ØP

ØQ Þ ØP

T

T

F

F

T

T

F

T

F

F

F

T

F

T

T

F

F

T

T

T

 

De Morgan’s Law (1)                             Ø P  Ú  ØQ    Ø (P  Ù   Q)

De Morgan’s Law (2)                             Ø P  Ù  ØQ    Ø (P  Ú   Q)

 

Truth Tables (exercises  1A and 1B)

 

Exportation                                P  Ù  R  Þ  Q  (P  Þ  (R  Þ  Q))

(Direct Proof Law)    

Truth Table (exercise 1C) 

 

Indirect Proof  Law                            P  Ù  ØQ Þ  always false   P Þ  Q

 

Truth Table (exercise 1D) 

 

Commutative Law  of  “or”  (1)              P  Ú  Q    Q  Ú  P

Commutative Law  of  “and” (2)            P  Ù Q    Q  Ù  P

 

Truth Tables (exercises 1E and 1F) 

 

Associative Law  of  “or”  (1) P  Ú  (Q  Ú  R)  (P  Ú  Q)  Ú  R   P  Ú  Q  Ú  R

Associative Law  of  “and” (2)        P  Ù  (Q  Ù  R)  (P  Ù  Q) Ù  R   P  Ù  Q  Ù  R

 

Truth Tables (exercises 1G and 1H)

 

Distributive Law of “and over or” (1)    P  Ù  (Q  Ú  R)  (P  Ù  Q)  Ú  (P Ù R)

Distributive Law of “or over and” (2)    P  Ú  (Q  Ù  R)  (P  Ú  Q)  Ù  (P Ú R)

 

Truth Tables (exercises 1I and 1J)   

 

Law of Disjunctive Addition (Law of Addition)                   P  Þ P Ú  Q

 

Truth Table 1.3.8       

P

Q

P Ú Q

P Þ P Ú Q

T

T

T

T

T

F

T

T

F

T

T

T

F

F

F

T

 

Law of Conjunctive Simplification (Law of Simplification)               P Ù  Q Þ P

 

Truth Table 1.3.9       

P

Q

P Ù Q

P Ù Q Þ P

T

T

T

T

T

F

F

T

F

T

F

T

F

F

F

T

 

       Of course, P Ù Q also implies Q, but this is not stated as a law since one can argue that P Ù Q is logically equivalent to Q Ù P (by the commutative law); then applying the law of simplification, it is the case that we have Q.

       Also, note that oft times students confuse the law of addition and the law of simplification. You must remember that “or does not reduce - - it adds” whilst “and reduces it never adds.”  If these are confused, then many “proofs” that students produce are not worth the paper on which the “proofs” were written.

Modus Ponens                          [(P Þ Q) Ù  P ] Þ Q

 

Truth Table (exercise 1K) 

 

Modus Tollens                          [(P Þ Q) Ù  ØQ] Þ ØP

 

Truth Table (exercise 1L)  

 

Disjunctive Syllogism                      [(P Ú  Q) Ù  ØQ] Þ  P

 

Truth Table (exercise 1M)        

 

Hypothetical Syllogism                    [ (P Þ Q) Ù  (Q Þ R)]  Þ   [P Þ R ]

(Transitivity)

 

Truth Table (exercise 1N) 

 

Assume the hypothesis of the conclusion      (P  Þ  (R  Þ  Q)) Þ  (P  Ù  R)  Þ  Q

 

Truth Table (exercise 1O) 

 

Constructive Dilemma                     [ (P Þ Q) Ù (R Þ S) Ù (P Ú R)]  Þ   [Q Ú S ]

 

Truth Table (exercise 1P)  

 

Destructive Dilemma               [ (P Þ Q) Ù (R Þ S) Ù (ØQ Ú ØS)]  Þ   [ØP Ú ØR]

 

Truth Table (exercise 1Q) 

 

       Whilst most texts note the laws of logic and the rules of inference, it is not sufficient in my opinion; stating the laws is all well and good but it is also helpful to note the fallacies to avoid.  Therefore, we shall also discuss some fallacies of logic and rhetoric.

       One of the most pernicious mistakes students make is asserting the conclusion.  They are often taught this is a valid method of reasoning in high school (by teachers who have no business teaching, I might add) or induce that it is a reasoning pattern that is valid from typical high school mathematics problems such as:

(1) Let the universe be the real numbers. Consider the equation x2 + x - 5 = 0.  Solve for x.  Solution:  x = -3 or x = 2.

(2) Let the universe be the real numbers. Reduce (16)(64)-1.  Solution: .25.

       Note that the assumption was made in the statement of the first problem that the equality held. So, a student can by trial and error reach the solution without knowledge of factoring, completion of the square, or the quadratic equation. Note that the assumption was made in the statement of the second problem that it could be reduced. Then a non-mathematical solution would be to plug it into a calculator or reduce it incorrectly. So, a student can reach the solution without knowledge of factorisation and proper methods of cancellation.

       However, assuming a conclusion and then “filling in the details” is fraught with problems. Let us illustrate this with the second problem noted above.   Consider four students A, B, C, and D. 

Student A considers the problem. Let the universe be the real numbers. Reduce (16)(64)-1.

He reaches for his TI - 89 and punches 16, 64, yx, -1, and =.  He sees .25 in the screen and writes down the answer.  What does he really know?

Student B considers the problem. Let the universe be the real numbers. Reduce (16)(64)-1.

She reaches for her Casio 4 and punches 16, 64, ¸, and =.  She sees .25 in the screen and writes down the answer.  What does she really know?

Student C considers the problem. Let the universe be the real numbers. Reduce (16)(64)-1.

He writes 16 . 64-1 =  =  =. We know he has incorrectly applied the real variable law of cancellation.

Student D considers the problem. Let the universe be the real numbers. Reduce (16)(64)-1.

He writes 16 . 64-1 = = =  =   =.  We know he has correctly applied real variable cancellation and knows what he is doing.

       When asserting a conclusion to a claim, one is already done.  Let us illustrate this point by noting the following.  Suppose all boys are rugged.  All rugged things are tall. Suppose from this we wish to say, “all boys are two-footed.” 

Now, to begin let us assume all boys are two-footed. 

So?  What’s our point?  We are already at the conclusion.  Did this mean that the first two sentences in the claim necessarily imply the conclusion? Of course not, we are making one of the oldest mistakes in reasoning: asserting the conclusion. Perhaps (I believe it is the case) this was not the best example; but it shows how asserting the conclusion really is quite the mistake.

 

The Fallacy of Asserting the Conclusion                     [(P Þ Q) Ù  Q] Þ P  

( assuming the conclusion)  (fallacy of the converse)

 

Truth Table 1.3.10     

P

Q

P Þ Q

(P Þ Q) Ù Q

[(P Þ Q) Ù Q] Þ P

T

T

T

T

T

T

F

F

F

T

F

T

T

T

F

F

F

T

F

T

 

It is actually the case that  necessarily!

 

 

 

 

The Fallacy of Asserting the Premise                  (P Þ Q) Þ P      

( assuming the hypothesis of an implication must always be true)

 

Truth Table 1.3.11     

P

Q

P Þ Q

(P Þ Q) Þ P

T

T

T

T

T

F

F

T

F

T

T

F

F

F

T

F

 

It is actually the case that  necessarily! Also note that since there are two false entries in the last column of the truth table versus one false entry in the last column of truth table 1.3.10 does not make the fallacy of asserting the conclusion “better” than the fallacy of asserting the premise.  A fallacy is a fallacy - - no more, no less. Arguing on the basis of a fallacy, fallacious reasoning, over-generalising, etc. are all wrong and should be avoided.

 

The Fallacy of Denial of the Hypothesis of a Conditional [(P Þ Q) Ù ØP] Þ ØQ     

(fallacy of the inverse)

 

Truth Table 1.3.12     

P

Q

P Þ Q

ØP

(P Þ Q) Ù ØP

ØQ

[(P Þ Q) Ù ØP]Þ ØQ

T

T

T

F

F

F

T

T

F

F

F

F

T

T

F

T

T

T

T

F

F

F

F

T

T

T

T

T

 

It is actually the case that necessarily!

 

The Fallacy of Reduction of Or                                    P  Ú  Q Þ P

(incorrectly reversing the law of addition)

 

Truth Table (exercise 2A) 

 

The Fallacy of Construction of And                                    P Þ P Ù  Q

(incorrectly reversing the law of simplification)

 

Truth Table (exercise 2B)  

 

There are MANY more fallacies we could list; but these are the most common I have come across in grading proofs.  Avoid them!

 

 

 

 

 

§ 1.3   EXERCISES.

 

1. Construct a compleat truth table for the following laws.  Note why such is a law.

 

A.    De Morgan Law (1)                   

B.    De Morgan Law (2)                   

C.    Exportation                                

D.    Indirect Proof  Law             

E.    Commutative Law  of  “or”  (1)  

F.    Commutative Law  of  “and” (2)

G.    Associative Law  of  “or”  (1)     

H.    Associative Law  of  “and” (2)    

I.     Distributive Law of “and over or” (1)  

J.     Distributive Law of “or over and” (2)  

K.   Modus Ponens                    

L.    Modus Tollens                           

M.   Disjunctive Syllogism                  

N.   Hypothetical Syllogism                

O.   Assume the hypothesis of the conclusion    

P.    Constructive Dilemma                 

Q.   Destructive Dilemma                   

 

2. Construct a compleat truth table for the following fallacies.  Note why such is a fallacy.

 

A.    The Fallacy of Reduction of Or                   

B.    The Fallacy of Construction of And

C.  (P Þ Q)  º  (Q Þ P)

D.  (P Þ Q)  º  (ØP Þ ØQ)

                                   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§ 1.4         ARGUMENTS, ARGUMENT FORMS, PROOFS, AND

COUNTEREXAMPLES.

      

       Suppose we have a set of propositions and we wish to determine if there is some statement that can be drawn from the propositions.  An argument may be defined as any group of propositions of which one is claimed to follow from the others, which are regarded as supplying evidence for the truth of that one.  All the propositions that are pre-supposed are called premises, and the one that is claimed to follow from the others is called the conclusion. Premises are connected by an implied and, while the premises are all group together, then the conclusion is connected to the premises by a conditional.

       Typical examples of premise indicators are: for, since, because, given, given that, whence, assuming that, seeing that, granted that, this is true because, the reason for, for the reason that, by the fact that, inasmuch as, etc.  Typical examples of conclusion indicators are: thus, therefore, hence, so, consequently, accordingly, ergo, thereupon, it follows that, which shows that, as a result, in conclusion, finally, en fin, etc.  Neither of these lists is exhaustive (I am not a linguist); but, hopefully the lists will assist the student in detecting the premises and conclusion.   The conclusion typically ends the argument but does not have to.  For example the argument (albeit simple), “Annie goes to the store, if Mickey want milk,” has the conclusion preceding the premise.

       Let us consider another argument:

“If I enroll in the course and study hard, then I will earn acceptable grades. If I

make satisfactory grades, then I am content.  I am not content. Hence, either I

did not enroll in this course or I did not study hard.”

“If I enroll in the course and study hard, then I will earn acceptable grades” is premise one.

“If I make satisfactory grades, then I am content” is premise two.

“I am not content” is premise 3.

“Either I did not enroll in this course or I did not study hard” is the conclusion.

Note that the conclusion concludes the argument (duh) and it is typically (but not always) separated from the premises by the transitional word hence.

       Now symbolising the argument, let E denote “I enroll in the course,” S denote “I study hard,” G denote “I earn acceptable (satisfactory) grades,” and C denote “I am content.” Thus the argument is

[(E Ù S ®G) Ù (G ® C) Ù (ØC)] Þ [ØE Ú ØS].

Note by order of operations, premise one is represented as (E Ù S) ®G (with parentheses which for clarity is quite helpful).  Referring to truth table 1.5.1, note only row 8, row 12, and row 16 result in the conjunction of the three premises being true.  Thus, for row 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, and 15 we get a final true for the argument since false implies anything is true! [6]  When one completes the truth table, he will get for the statement ØE Ú ØS true in rows 8, 12, and 16.  Thus, the argument is always true.

       An argument, which is always true, is said to be valid; an argument where there exists at least one combination of truth-values for the premises and conclusion such that the argument is false is said to be invalid. Thus, note only tautological arguments are valid; whereas both arguments that are fallacies and contradictions are invalid.[7] 

 

Truth Table 1.4.1 (incompleat; compleat in exercise 1)

 

E

(1)

S

(2)

G

(3)

C

(4)

E Ù S

(5)

E Ù S ® G

(6)

G ® C

(7)

ØC

(8)

6 Ù 7 Ù 8

(9)

T

T

T

T

T

T

T

F

F

T

T

T

F

T

T

F

T

F

T

T

F

T

T

F

T

F

F

T

T

F

F

T

F

T

T

F

T

F

T

T

F

T

T

F

F

T

F

T

F

F

T

F

T

F

T

F

F

T

F

T

T

F

F

T

F

F

F

F

T

T

T

T

F

T

T

T

F

T

T

F

F

F

T

T

F

F

T

F

T

F

F

T

F

T

F

T

T

F

F

F

T

F

F

F

T

T

T

T

F

F

T

T

F

T

T

F

F

F

F

T

F

F

T

F

T

F

F

F

F

T

F

T

T

F

F

F

F

F

F

F

T

T

T

T

 

       Perhaps one of the simplest and most useful argument forms is modus ponens.  Consider the premises p ® q; p; thus, q.  This is a simple argument consisting of two premises; namely, if p, then q and p. It has a conclusion, q.  Let us let p be “you understand logic” and q be “you pass the test” (you can put any simple sentence in for p and any other simple sentence in for q).  So, the argument is: If you understand logic, then you will pass the test.  You understand logic.  Thus, you pass the test.

 

Truth Table 1.4.2       

P

Q

P ® Q

(P ® Q) Ù P

(P ® Q) Ù P Þ Q

T

T

T

T

T

T

F

F

F

T

F

T

T

F

T

F

F

T

F

T

 

Thus, in the construction of arguments we may use this as a valid argument form for justification of an argument.

       Fundamental primitive true[8] statements in a system are called axioms. Such statements are agreed upon to be true.  Further statements derived from the axioms are called lemmas, theorems, or corollaries.   A theorem is a further statement proven from the axioms.  If the theorem is of a “sufficiently” small scale and is used to prove a larger claim, then it is called a lemma (consider it a ‘helper’ theorem). If a theorem follows so clearly and obviously from another theorem, then it is called a corollary.

       A proof or mathematical argument is an argument such that it consists of a finite sequence of statements, each of which is either a premise, an axiom, or a previously proven lemmas, theorems, or corollaries, or follows from the premises, axioms, or previously proven theorems by application of correct modes of inference (logic).  The last statement is the conclusion that follows from the given set of premises.  A proof is announced by writing Proof before the argument and is closed by writing QED (which means quod erat demonstratum) at the end.  The application of the correct modes of inference is the “map” of the proof and the proof and QED the frame to announce to a reader where the proof begins and where it ends.  Furthermore, the claim being proven should be succinctly stated (otherwise oft one will be left with a very confused audience).

       A proof is to be clear, hopefully concise, and correct.  A proof is not to be some sort of magic trick where slight of hand, misdirection, etc. are employed.  A proof should understandable (assuming the reader has the requisite background).  A magician pulls a rabbit out of a hat because of a concealed compartment, a gambler win a hand of poker because of an ace up his sleeve, a businessman gets a contract because of “connections.” None of these are reasonable concepts for the mathematician.  The mathematician objectively seeks the truth.  The mathematician justifies his inferences.  The mathematician explains his work.  And the way the mathematician does these things is by constructing sound proofs or counter-arguments.

       You may assume any of the laws of logic from section 1.3.  Those are premises that are not stated.  Therefore, even in the most simple of claims there are many premises besides the stated ones; but they are agreed true statements that are being assumed.  Note we do not assume that the fallacy of assuming the conclusion, etc. may be used.  That which is assumed must be an axiom, previously proven theorem, a stated premise, or a law of logic.

       Let us look at an example of a claim and a proof of the veracity of the claim.

 

Example 1.4.1

 

Claim: If I am spent, then I shall rest. I am not resting. Therefore, I am not spent.

Let S denote “I am spent,” and R denote “I rest.”  Thus, the claim is

S ® R. ØR. \ ØS.  

Proof:

1.    S ® R                                 1. Premise.

2.    ØR                                      2. Premise.

3.    ØR  ®   ØS                        3. Contrapositive form of line 1.

4.    ØS                                       4. Modus Ponens (line 2 and line 3).

QED

Note that the proof was done in a “vertical” form such that each statement is justified.  Further note the claim was really an application of modus tollens (and was valid by modus tollens).  This should demonstrate that there is no one mode of reasoning that is right.  There are many but they must be correct (not fallacious).  In mathematics, an elegant proof is considered one which is the shortest most compleat argument such that if one word, one letter (perhaps) were deleted the proof would tumble and no longer be valid.  It is not the object of this class (or any other that I ever teach) to instruct a student on elegance.  A proof is valid so long as it contains all that is required.  If it is longer that another - - so be it.   Therefore, no one will be encouraged to attempt elegance; you will be encouraged simply to be right (and that is quite enough, I guarantee it [quote Justin Wilson]).

       Now, let’s consider a more challenging claim.

 

Example 1.4.2

 

Claim:  Given the premises  ØA Ù C,  B Þ D, and Ø(D Ù ØA).   The conclusion ØB follows.

Proof:

1.    ØA Ù C                               1. Premise.

2.    ØA                                      2. Law of Simplification (line1)

3.    Ø(D Ù ØA)                         3. Premise.

4.    ØD Ú Ø(ØA)                       4. DeMorgan’s Law (line 3).

5.    ØD Ú A                               5. Law of Double Negation (line 4).

6.    ØD                                      6. Disjunctive Syllogism (lines 2 and 5).

7.    B Þ D                                7. Premise.

8.    ØB                                      8. Modus Tollens (lines 6 and 7).

QED

       Let us consider the use of this form of proof.  There are other forms (most often referred to as horizontal form proofs since they are written more in the style of everyday Western writing. Let us look at the following claim and compare and contrast the techniques of writing a proof.

 

Example 1.4.3

 

Claim:  Given the premises  P Ú Q, ØS,  P Þ ØR, and R Ú S.   The conclusion Q follows.

Proof (1): Consider R Ú S. Let us assume ØS.  So, R. Assume P Þ ØR. So, ØP. Assume P Ú Q.  Thus, Q.  QED.

Proof (2): Consider R Ú S (it can be assumed since it is a premise). Let us assume ØS since it too is a premise.  So, R must follow by the disjunctive syllogism. Assume P Þ ØR since it is a premise. So, ØP must follow by modus tollens. Assume P Ú Q since it is a premise.  Thus, Q follows by the disjunctive syllogism.  Hence, the conclusion follows from the premises.  QED.

 

Proof (3):

1.    R Ú S                                  1. Premise.

2.    ØS                                       2. Premise.

3.    R                                         3. Disjunctive Syllogism (1,2).

4.    P Þ ØR                              4. Premise.

5.    Ø(ØR)                                 5. Law of Double Negation (3).

6.    ØP                                       6. Modus Tollens (4, 5).

7.    P Ú Q                                  7. Premise.

8.    Q                                         8. Disjunctive Syllogism (6, 7).

QED

       Note that proof (1) is correct.  However, the deletion of the justification leaves the reader to recall the reasons why the statements follow.  Note proof (2) is correct, but with the added loquacious manner, it is not the best technique to follow when one is trying to establish a comfort with method of proof.  Hence, proof (3) is the most satiating since it combines parsimony with detail. So, for now we will follow technique (3).  In time (Math 255), the student will begin to use proof technique (2); and, eventually, he will be comfortable enough to use technique (1) [with regard to logic - - the particular justification in a mathematical area will oft be required by professors so that clarity is maintained].

       One might reasonably ask must every proof begin with the premises and end with the conclusion.  The answer is, “no.”  So far we have consider claims such that it is facile to assume the premises and derive the conclusion.   However, we must keep in mind that not all claims are true (so we will be discussing the methods of disproof - - counterexample) and even if a claim is true, it may not be so easy to prove in a direct manner such as we have seen to this point. 

The straight-forward method employed so far is:

Direct Proof (1): To prove the conclusion C from a set of premises {say P1, P2, P3,  . . ., Pk} show that C is provable as a consequent of the set of premises (hypotheses) P1, P2, P3,  . . ., Pk.

The practical meaning is:

I want to prove ASSUMING  the  premises P1, P2, P3,  . . ., Pk that  C follows from them; so,  I assume P1, P2, P3,  . . ., Pk  are true and prove that C follows from these premises.

       Nonetheless, suppose the conclusion is an implication. In this case we may employ a different method of proof that is still direct.

Direct Proof (2): To prove the implication A Þ B from a set of premises {say P1, P2, P3,  . . ., Pk} it is sufficient to include A in the set of premises {e.g.: A, P1, P2, P3,  . . ., Pk} and show that B is provable as a consequent of the augmented set of premises (hypotheses).

The practical meaning is:

I want to prove ASSUMING  the  premises P1, P2, P3,  . . ., Pk that A Þ B follows from them, 

so,  it is equivalent to:    Assume A, P1, P2, P3,  . . ., Pk are the premises and prove that (B) follows from these.  This can be done since the law of logic assume the hypothesis of the conclusion,  (P  Þ  (R  Þ  Q)) Þ  (P  Ù  R)  Þ  Q,  is true.

Let us consider a claim that can be proven using the direct proof (2) method (it does not have to be proven in this manner, it is just convenient to do so).

 

Example 1.4.4

 

Claim:   Given the premises A Þ B,  C Þ D,  (B Ù D) Þ  ØE, and E it is the case that

A Þ  ØC follows as a conclusion.

Proof :

1.    A                                         1. Hypothesis of the conclusion.

2.    A Þ B                                2. Premise.

3.    B                                         3. Modus Ponens (1,2).

4.    E                                         4. Premise.

5.    (B Ù D) Þ  ØE                   5. Premise.

6.    Ø(B Ù D)                            6. Modus Tollens (4, 5).

7.    ØB Ú ØD                            7. DeMorgan’s Law (6).

8.    ØD                                      8. Disjunctive Syllogism (3, 7).

9.    C Þ D                                9. Premise.

10. ØC                                      10. Modus Tollens (8, 9).

QED

       Nonetheless, claims are not true every time they are posed.  Thus, a need to discuss proper techniques for demonstrating that a claim is false is also a matter that must be discussed.  A counter-argument that demonstrates a claim is false is known as a counterexample.  It is constructed in a similar, but not identical, manner as a proof.   Recall that the form of a proof is 1) the announcement of the proof by writing, “proof,” followed by the argument, followed by the announcement that is is done, “QED.”  Similarly, the form for a counterexample begins with a declaration that a counterexample is being proposed; thus, announced by writing, “counterexample,” then the counterexample is declared which is an assignment of truth values for all the prime statements, then the writer demonstrates that it is indeed a counterexample by noting the argument is false with the assigned truth values, and, finally the counterexample is declared finished by writing “EEF,” which means exemplum est factum.

       Consider the following claim: Given the premises A Þ B,  C Þ D,  (B Ù D) Þ  ØE, and E it is the case that ØC follows as a conclusion.  Note that it is similar to the previous claim (which does not mean that it is false necessarily – more than one conclusion may be derived from a given set of premises (see the exercise set at the end of this section). Nonetheless, this is a false claim.  One can discern the lack of veracity by doing a compleat truth table (which is a fine method, but then one need to present the truth table in the compleat counterexample form, thus exhausting much time). One can discern that it is false by considering that argument forms follow the strict pattern of an inferred “and” between each premise, and an inferred conditional connecting the premises to the conclusion, for what we are saying is that if the premises are true, does it the conclusion logically follow? Note, that it does not matter how silly the hypotheses are- it is the argument that we are considering and the implication of premises to conclusion.  Thus, each of the premises must be true and the conclusion false. 

Therefore, let ØC be false which necessarily implies that C is true by the law of the excluded middle.  Since C is true and one of the premises is C Þ D, since the hypothesis of this conditional is true, the consequent must also be true.  So, D is true. Note that there is a unique E as a premise.  It must be true.  So, now considering the premise (B Ù D) Þ  ØE, we have ØE is false and when the consequent is false the only way for the implication to be true is if the antecedent is also false.  We already have D is true, so the only way to make this whole premise true is if we assign a false for B.  So, B is false.  Now, let us turn our attention to the last premise (which was the first in the list [note: order does not matter, what matters is getting it right]) A Þ B, we already said B is false which forces A to be false also to make sure the premise is true. All of the aforementioned analysis is conducted by a student either in his head (if he has an excellent memory) or on scratch paper.  Now we are ready for the counterexample. 

 

 

 

 

 

 

 

Example 1.4.5

 

Claim:   Given the premises A Þ B,  C Þ D,  (B Ù D) Þ  ØE, and E it is the case that ØC follows as a conclusion.

Counterexample :

Let A be false, B be false, C be true, D be true, and E be true. 

Consider the claim        [ (A Þ B) Ù (C Þ D) Ù (B Ù D) Þ  ØE) Ù (E) ] Þ  ØC

Which is                       [ (F Þ F) Ù (T Þ T) Ù (F Ù T) Þ  ØT) Ù (T) ] Þ  ØT

So,                               [ (   T     ) Ù (    T    ) Ù (  F       Þ   F  ) Ù (T) ] Þ  F

Thus,                            [ (   T     ) Ù (    T    ) Ù (        T           ) Ù (T) ] Þ  F

Hence, So,                                               T                                           Þ  F

Which is false.

EEF.

       Note the first line is the counterexample (in actuality that is it).  However, demonstrating that it is indeed a counterexample does two things: first, it helps the student realise he is right (or wrong and must propose a different counterexample); and, second, it helps the reader follow the logic of the counterexample (especially when there is a complex claim).

       Now, let us consider another claim:

Claim:   Given the premises A Þ ØB, ØA Þ ØC, C, D Þ B, it is the case that ØD follows as a conclusion.

       Suppose the conclusion seems to follow from the premises, but it is not easily seen directly. In this case we may employ a different method of proof called indirect.

Indirect Proof (1):  For the above claim let us use reducto ad absurdum (reduce to the absurd), also called proof by contradiction.[9] To prove Q follows from a set of premises {say P1, P2, P3,  . . ., Pk }it is sufficient to consider ØQ  as an additional premise {say ØQ, P1, P2, P3,  . . ., Pk } and prove a statement of the form ØR Ù R, where R is any statement following from the premises and the negation of the conclusion.  The practical meaning of this is that when one wants to prove ASSUMING  the  premises P1, P2, P3,  . . ., Pk that Q follows from them, it is equivalent to assuming ØQ, P1, P2, P3,  . . ., Pk are the premises and prove that () follows from these where can be any statement and its negation that follows (which is the contradiction - - because it is nonsensical to claim that R and not R can be true at the same time because it is a violation of the law of the excluded middle).  With that being the case, then the addition of not Q to the hypotheses must have been in error!  So, since all the hypotheses P1, P2, P3,  . . ., Pk  were assumed true and  ØQ, P1, P2, P3,  . . ., Pk is false, then ØQ must be false as a consequent to P1, P2, P3,  . . ., Pk, ergo Q must follow (since there were only two possibilities, Q and ØQ)!

       Moreover, an important principle of proof must also be noted before attacking the claim.  That is there is another technique we must mention, adjunction. If P is provable from the set of premises {say P1, P2, P3,  . . ., Pk } and Q is provable from the same set of premises, then P Ù Q is provable from that set of premises.   The practical meaning of this is let us suppose you are doing a proof (any method)  that P is provable from the set of premises (P1, P2, P3,  . . ., Pk),

later you do a proof Q is provable from the same set of premises logic ‘tells’ us that P Ù Q is a result of P1, P2, P3,  . . ., Pk.  In ordinary circumstances such has already been deduced, but when doing a proof there are times one needs a statement of the form P Ù Q and one already has shown P follows from the premises and Q follows from the premises.  Thus, we use the justification of adjunction to note that we have P Ù Q.  It will become clear in the next proof (note lines 8, 9, and 10).

       Let us now return to the claim and a proof of the veracity of the claim using reducto ad absurdum:

 

Example 1.4.6

 

Claim:   Given the premises A Þ ØB, ØA Þ ØC, C, D Þ B, it is the case that ØD follows as a conclusion.

Proof :

1.    Ø(ØD)                                 1. Negation of the conclusion.

2.    D                                         2. Law of Double Negation (1).

3.    D Þ B                                3. Premise.

4.    B                                         4. Modus Ponens (2, 3).

5.    A  Þ ØB                             5. Premise.

6.    ØA                                      6. Modus Tollens (4, 5).

7.    ØA Þ ØC                           7. Premise.

8.    ØC                                      8. Modus Ponens (6, 7).

9.    C                                         9. Premise

10. ØC Ù C                               10. Adjunction (8, 9).

11. ØD                                       11. Contradiction (1, 10).

QED

Normally, many mathematicians skip the illustration of the law of double negation.  I have included it in this example for the sake of clarity. 

       I cannot underrate the importance of this method of proof.  Oft times I have found myself with nary a hope of proving a claim, but then when I attacked the claim indirectly, it became facile.  Further, there are some claims that cannot be proven directly (that I know of); for example, it is the case considering the real numbers that  is irrational.[10]  Given the nature of the irrationals (the name alone conjures up an image of something that is not very ‘nice’) one can see that properties of the rationals are such that they are ‘nice,’ so assuming is rational will lead us to a contradiction (we will prove this to be the case in Set Theory or Advanced Calculus I).

       Let us consider another important principle of proof.  There is another technique we must mention, substitution.[11]  Suppose you have a set of premises (say P1, P2, P3,  . . ., Pk ) and hold Pa (one of the premises) is obtainable from another say, Pb, by substituting a statement R for any occurrence of a statement S in Pa.    Then we can derive Pb from S Û R and Pa. The practical meaning of this is when you have a set of premises  (say P1, P2, P3,  . . ., Pk ) and you want to show a particular one of the premises is derivable from another one of the premises the equivalence statement S Û R means S can replace any occurrence of R or visa versa by substituting in any part of the proof. In ordinary circumstances such has already been deduced or given (the equivalence of some statement S and R e.g.: D º ØØD by the law of double negation), but when doing a proof there are times one needs a statement of the form R and one already has shown S follows from the premises.  Thus, we use the justification of substitution to note that we have R.  It will become clear in the next proof (note lines 8, 9, and 10).

 

Example 1.4.7

 

Claim:   Given the premises A Ú B, ØA , C Þ E, C Û B, it is the case that E follows as a conclusion.

Proof :

1.    ØA                                      1. Premise.

2.    A Ú B                                  2. Premise.

3.    B                                         3. Disjunctive Syllogism (1, 2).

4.    C  Þ E                                4. Premise.

5.    C Û B                                5. Premise.

6.    C                                         6. Substitution (3, 5)

7.    E                                          7. Modus Ponens (6, 4).

QED

       Oft times substitution comes in some interesting forms; for example, in reduction of fractions in arithmetic, polynomial expressions in algebra, etc.  You will find it a useful technique; but be careful for it is only allowable such that there is a logical equivalence, not in a simple implication form.   For example because C Û B, we could substitute C for B, but if we had C Þ B we could not.  Some of the ‘trickiest’ cases with the erroneous use of substitution occurs in real analysis.  Consider the real numbers and the function f (x) = x + 1 where f (x) goes from the reals to the reals.  Note it is a line.  Is g(x) =  the same? Can we substitute g (x) for f (x)?   The answer is, “no.”  Note (from your understanding of functions from high school) that f (1) exists, but g (1) does not.  Therefore, the two could not be the same (we will explore this in more depth throughout your mathematical studies).   Suffice it to say that some things look deceptively true when indeed they are false. 

       Also, let us note that in the preceding discussion we had premises that were consistent.  A set of premises is consistent if contradiction does not follow from them.  A set of premises is inconsistent if a contradiction (a statement of the form R Ù ØR) necessarily follows from them.

Note, therefore, we use the inconsistency of adjoining the negation of the conclusion to a given set of premises to arrive at a contradiction when we use the technique of reducto ad absurdum. 

       Some times a given set of premises is incompleat, which is to say if there was just one or more conditions added to the list of premises, then we could prove a particular conclusion.  Researchers find this to be the case often (where they have to strengthen hypotheses). 

Consider we assume A Þ (B Þ C) is true and we wish to deduce ØA.  We cannot!  However, if we could argue that B Ù ØC are true; then we could prove this along with A Þ (B Þ C) forces ØA.   Much in science explicitly or implicitly relates to this type of scenario.   However, it is beyond the scope of the course and lays groundwork which I feel is harmful.  This is because oft times students add hypotheses to problems that are not stated nor implied!

For example, consider the problem of solving = 0 for the real numbers.   Note (from your understanding of functions from high school) that = 0  Þ x =   Ú x = -.  Many students would say the answer does not exist (they are thinking only of rational numbers) which is wrong.   Many students would write the solution as  thinking that means x =   Ù x = -which is wrong.  Many students would write x = 2.2360679775 or

x = - 2.2360679775 (which are approximations on a calculator) which is wrong.  Consider the claim that many high school students allow:   for the real numbers which is false (suppose x = 0). Indeed consider one of my favourites: Reduce completely .   Many students claim this is equal to x - y; it is not (solve it yourself). 

I could drone on, but suffice it to say that some things look deceptively right when indeed they are wrong. So incumbent on you, the student, is the responsibility to learn how to properly, correctly, and precisely reason and to ‘toss off’ the shackles of answers gained by external methods (calculators), added hypotheses which are not correct, etc. 

       Let us direct our attention to a given set of premises and let us deduce a conclusion that follows form the given set of premises. For example, consider ØA Þ ØB, B, A Þ C what necessarily follows from these premises?  Since B is given note by modus tollens that A follows. However, that is not very satiating since we have not used all the premises (but it is not wrong since there is no method of proof that states all premises must be used; if all the premises are not used, then the premises not used are called unnecessary premises or superfluous premises and in research would be discarded before a final presentation [if the researcher realised that it was not used]). Since B is given note by modus tollens that A follows and that since A ÞC is given it therefore follows that C is a conclusion that follows.  Note that ØC could not follow!   However, Ø(ØC) follows as does Ø(Ø(Ø(ØC))), etc. So, may logically equivalent statements follow from a given set of premises.  Could it be the case that two different conclusions can follow?  The answer is, “yes,” when we allow for unnecessary premises.

       Consider the premises to be K Þ L, M Þ N, O Þ N, P Þ L, ØN Ú ØL, ØM Ú ØO. Note that ØN Ú ØL º N Þ ØL; thus, since M Þ N is a premise it follows we have M Þ ØL. But, M Þ ØL º L Þ ØM; thus, since P Þ L is a premise we can derive P Þ ØM by the hypothetical syllogism.  However, note since we have ØN Ú ØL º ØL Ú ØN º L Þ ØN; thus, since K Þ L is a premise, we get K Þ ØN.  But, M Þ N is a premise, so M Þ N º ØN Þ ØM; thus, K Þ ØM. On the other hand, ØM Ú ØO º ØO Ú ØM º O Þ ØM which leads nowhere.  So, there are different conclusions that can be drawn from the premises.   One might say the best was a conclusion that uses the most premises; and one should always seek such conclusions.  I am not in that school.  What I advocate (profess) is that it is important for a student of mathematics to be right, to know why he is right (therefore, he justifies himself), and to communicate that to others (communicate - - not condescend).  The last comment is, perhaps, the most important for it is not the case that we wish to ‘keep the secrets’ of mathematics to ourselves, but to share our understanding with others.  However, it is not the case that this profession is predicated on the principle of doing it for others.  A professor of mine (now deceased) at Georgia State used to have on his office door the saying (I am paraphrasing) that, “to give a man a fish means he will eat for a day; but, to teach a man to fish means he will be able to eat for a lifetime.”  Therefore, reading this text is not enough, you must do for yourself; hence, the exercise set follows. 

      

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

     

§ 1.4   EXERCISES.

 

1. Given the premises  A Þ (B Ú C), B Þ ØC; prove or disprove that A Þ B follows as a conclusion.

2. Given the premises  A Þ B, A Ú C Þ D; prove or disprove that B Þ D follows as a conclusion.

3. Given the premises A Þ B,  C Þ D, (B Ú D) Þ E,  E; prove or disprove that A ÞØ C  follows as a conclusion.

4. Given the premises  S Þ P, D Ú (Q Ù S), ØD; prove or disprove that P follows as a conclusion.

5. Given the premises  A Þ M, Ø(M Ù ØS), ØS Ù B; prove or disprove that ØA follows as a conclusion.

6. Given the premises D Ù ØN Ú S, S Þ ØJ; prove or disprove that J Þ D follows as a conclusion.

7. Given the premises D Ú S Þ A, D Ú A; prove or disprove that A follows as a conclusion.

8. Given the premises D Ú (S Þ A), D Ú A; prove or disprove that A follows as a conclusion.

9. Given the premises (D Ú S) Þ A, D Ú A; prove or disprove that A follows as a conclusion.

10. Given the premises  S Þ P, P Þ (W Ú J), ØW Ù S; prove or disprove that J follows as a conclusion.

11. Given the premises  A Þ U, ØU Ú (B Ù ØJ), ØA Þ ØB, Ø(ØJ Ù ØA) Ú B; prove or disprove that J Þ ØA follows as a conclusion.

12. Given the premises  A Þ U, ØU Ú (B Ù ØJ), ØA Þ ØB, Ø(ØJ Ù ØA) Ú B; prove or disprove that J Þ A follows as a conclusion.

13. Given the premises  A Þ U, ØU Ú (B Ù ØJ), ØA Þ ØB, Ø(ØJ Ù ØA) Ú B; prove or disprove that ØA Þ J follows as a conclusion.

14. Given the premises  P Þ Q, R Ú ØQ, Ø(ØP Ú ØS); prove or disprove that R Ù S follows as a conclusion.

15. Given the premises  ØP Þ (Q Þ R), R Ù S Þ T,  U Þ (Q Ù S), Ø(ØU Ú P); prove or disprove that T follows as a conclusion.

16. For the given set of premises, determine a suitable conclusion such that the argument is valid:

A. Premises:  p  ® q  ,  r ® Øq

B. Premises:  p  ® Øq  ,  q

C. Premises: p  ® Øq  ,  r ®p ,   q

17. Given the following “proof,” detect the error(s) in the “proof” and explain why it is (are) an error(s).    Please be brief, but write legibly and in compleat sentences!  Justification for each step will not be provided since it is not a proof.

Claim: Given the premises   ØB Ú C, ØA Þ B; the conclusion C Ù ØA follows. 

“Proof:”

1. ØA                                         6.   C Ù ØA

2. ØA Þ B                                 “QED”

3.  B

4. ØB Ú C

5.  C

§ 1.5   MORE ON LOGIC PROOFS.

 

       There are more proof techniques that we need to add to our ‘bag of tricks.’  One of these is the method of proof by cases. Cases is not like what we have discussed previously because the techniques of direct and indirect proof are truly different; whereas, proof by cases is a method that is subsumed under the other type of methods.  It is most useful in both algebra and analysis, so spend some time concentrating on the technique, when it is useful, and how to do it.[12]

Proof by cases: To prove  P Ú Q Þ R   it is necessary & sufficient to prove R follows from P and R follows from Q. The practical meaning of this is you do a proof (direct or indirect)  that R follows logically from P, then later you do a proof (any method)  R follows logically from Q , then logically P Ú Q Þ R.  Note that This can be generalised to P1 Ú P2  Ú P3 Ú  . . . Ú  Pk Þ R such that k is a natural number. As the number of cases increases, one generally pauses and considers trying a method other than cases; but, cases no matter if there are 2 or 1,000,000 will work if it works (a wonderfully obvious comment on my part).

 

Example 1.5.1

 

Claim: Given the premises   A Ú B,  B Þ ØC; prove or disprove the conclusion A Ú ØC follows. 

Proof :

1.    B Þ ØC                              1. Premise.

2.    A Ú B                                  2. Premise.

Case 1:  3a.    A             3a. Cases                          Case 2:   3b.  B     3b. Cases

               4a.   A Ú ØC    4a. Law of Addition (3a)           4b. ØC  4b. Modus Ponens (3b, 1)

                              5b. ØC Ú A  5b. Law of Add (4b)

                                                                                         6b. A Ú ØC 6b. Commutative (5b).

Hence, A Ú ØC.

QED

       Note that in each case the conclusion must follow.  Note that when executing case 2, nothing from case 1 can be referenced (so in the example above only lines 1 or 2 can be referenced in case 2; not lines 3a or 3b).       Hopefully, you can see the example was a bit stilted for there was an easier way to prove the claim; but, it suffices to illustrate that each case is done separately. 

       Now let us turn our attention to yet another method of proof that we may employ.  It is different than previous methods, but is still direct.

Direct Proof (3) (by contraposition):  To prove the implication A Þ B from a set of premises (say P1, P2, P3,  . . ., Pk ) it is sufficient to include ØB in the set of premises (e.g.: ØB, P1, P2, P3,  . . ., Pk) and show that ØA is provable as a consequent of the augmented set of premises (hypotheses).  Notice this is using the contrapositive form of the conclusion.  We are not assuming the negation of the conclusion (which would be Ø(A Þ B)) which is an indirect form of proof this contraposition form is direct.  The practical meaning is suppose you  want to prove ASSUMING  the  premises P1, P2, P3,  . . ., Pk that A Þ B follows from them, so, it is equivalent to: assume ØB, P1, P2, P3,  . . ., Pk are the premises and prove that ØA follows from these. I do not have acquaintance with many people who use this technique often; but, it is a valid method.  Further, it seems to me to be most useful when there are negations in the conclusion.  For example, consider: 

 

Example 1.5.2

 

Claim: Given the premises   A Ú  B, ØB, A Þ C, D Ù C Þ E; prove or disprove the conclusion ØE Þ ØD follows. 

Proof:

1.   Ø(ØD)                                  1. Negation of consequent of conclusion

2.    D                                         2. Law of Double Negation (1).

3.   ØB                                        3. Premise

4.    A Ú  B                                 4. Premise.

5.    A                                         5. Disjunctive Syllogism (3, 4).

6.    A Þ C                                6. Premise

7.    C                                         7. Modus Ponens (5, 6).

8.    D Ù C                                  8. Adjunction (2, 7)

9.    D Ù C Þ E                         9. Premise

10.  E                                          10. Modus Ponens (8, 9).

11.  Ø(ØE)                                  11. Law of Double Negation.

QED

       Finally, let us consider not really another proof technique so much as a particular type of conclusion which when claimed to conclude from a given set of premises, how we can ‘best’ write up an understandable and correct proof.

Proof for a biconditional: To prove the biconditional A Û B from a set of premises (say P1, P2, P3,  . . ., Pk ) it is sufficient to prove A Þ B as a consequent of the premises  and to prove B Þ A as a consequent of the premises.  Notice this is in fact doing two proofs (reminiscent of cases, but rather than cases we are using the fact that A Û B º (A Þ B Ù B Þ A).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Consider:

 

Example 1.5.3

 

Claim: Given the premises  C Þ A, ØC Þ ØJ, A Þ M,  ØM Ú J; it is the case that  J Û A follows as a conclusion.

Proof:

(Þ)        1.  J                              1. Hypothesis of the conclusion in the (Þ) direction[13].

2. ØC Þ ØJ                 2. Premise

3. J Þ C                      3. Contrapositive (2) [and law of double negation]

4. C Þ A                     4. Premise

5. J Þ A                      5. Hypothetical Syllogism (3, 4)

6. A                              6. Modus Ponens (1, 5).

(Ü)        1.  ØJ                           1. Negation of the consequent in the (Ü) direction[14].

2. ØM Ú J                    2. Premise

3. ØM                          3. Disjunctive Syllogism (1, 2)

4. A Þ M                    4. Premise

5. ØA                           5. Modus Tollens (3, 4)

QED

       Nonetheless, it is sufficient to show that a biconditional claim is false in one direction when the claim is indeed false.  Consider the claim:

 

Example 1.5.4

 

Claim: Given the premises  P Þ Q, R Ú ØQ, Ø(ØP Ú ØS); it is the case that ØR Û S follows as a conclusion.

Counterexample:

Let P be true, Q be true, R be true, and S be true. 

Consider the claim        [ (P Þ Q) Ù (R Ú ØQ) Ù (Ø(ØP Ú ØS))] Þ  (S Þ ØR)

Which is                       [ (T Þ T) Ù (T Ú ØT) Ù (Ø(ØT Ú ØT))] Þ  (T Þ ØT)

So,                               [ (   T     ) Ù  (T Ú  F  ) Ù (   T   Ù   T  )  ] Þ   (T Þ F)

Thus,                            [ (   T     ) Ù (    T    ) Ù (        T           ) ] Þ  F

Hence, So,                                               T                                  Þ  F

Which is false.

Since it is false in the (Ü) direction, it does not matter what the truth value of the  (Þ) direction is; hence, the claim is false.

EEF.

 

 

 

 

§ 1.5   EXERCISES.

 

1. Given the premises  A Þ (B Ú C), B Þ ØC; prove or disprove that A Û B follows as a conclusion.

2. Given the premises  (P Ù ØQ) Ú (Q Ù ØR),  P Þ S,  ØS Ú T, ØT; prove or disprove that Q follows as a conclusion.

3. Given the premises P Ú ØQ,  P Ú Q; prove or disprove that P follows as a conclusion.

4. Given the premises P Ú ØQ,  P Ú (Q ® R); prove or disprove that P follows as a conclusion.

5. Given the premises P Ú  R, Q ® R, ØR; prove or disprove that ØP follows as a conclusion.

6. Given the premises X ® A, P ® X, A ® M, ØM Ú P; prove or disprove that A Û P follows as a conclusion.

7. Given the premises X ® P, P ® (W Ú Z), ØW Ù X; prove or disprove that Z follows as a conclusion.

8. Given the premises ØE ® G, Ø(B Ù E); prove or disprove that B Þ G follows as a conclusion.

9. Translate the following arguments into symbols and prove or disprove the claim:

A. If Bob doesn’t win, then Kenneth will not win.  Sean will win, if Kenneth does not win. Sean didn’t win.  Therefore, Bob won.

C.    If Winston or Halbert wins then Luke and Susan cry.  Susan does not cry.  Thus, Halbert does not win.

D.    If I enroll in the course and study hard, then I will earn acceptable grades. If I make satisfactory grades, then I am content.  I am not content. Hence, either I did not enroll in this course or I did not study hard.

E.    If the population increases rapidly and production remains constant, then prices rise.   If prices rise then the government will control prices.  I am rich then I do not care about increases in prices.  It is not true that I am not rich. Either the government does not control prices or I do not care about increases in prices. Therefore, it is not the case that the population increases rapidly and production remains constant.

F.    Dean praises me only if I can be proud of myself.  Either I do well in classes or I cannot be proud of myself.  If I do my best in sports, then I cannot be proud of myself.  Therefore, if Dean praises me, then I do my best in sports.

G.  It was murder or suicide. There was no weapon found at the scene of the crime and if it was murder, there would be a motive.  If there was a motive, then there would be a weapon at the scene of the crime.  Thus, it was suicide.

H.  If he is elected, then he will go to Atlanta or Washington.  It is not the case that he will run for office and go to Washington. He will run for office and be elected.  Therefore, he will go to Atlanta.

I.  If he is a Democrat or a Republican, he shall run for office.  If he is not a Democrat, then he will run for office.  Therefore, he will run for office.

J.  If he is not cautious, then it is false that he is tempestuous and contemplative.  He is contemplative and he is tempestuous or strong. He isn’t strong.  Therefore, he is cautious.

 

 

 

 

§ 1.6   MORE ON FALLACIES.

 

There exist at least three functions or uses of language according to philosophy:

1) the informative function - in which language is used to inform;

2) the expressive function - in which language is used to express feelings, emotions, or attitudes of the actor or to evoke feelings, emotions, or attitudes to the listener or reader: and,

3) the directive function - in which language is used to cause or prevent certain overt or covert actions.

Only in case 1 of the above can we, perhaps, determine the veracity of a statement; indeed, there are many instances where the veracity may not be determinable. An example of a statement the veracity of which can be determined is, “It is the year 2002 A.D..”  An example of a statement the veracity of which cannot be determined is, “Julius Caesar said, ‘goodbye,’ to Livia before leaving for the Senate on the ides of March 44 B.C..”

       We have defined the three possible truth values of a statement (or argument) to be tautology, fallacy, and contradiction.  Further, we noted there are different types of fallacies, such as the fallacy of the assertion of the conclusion of a conditional, the fallacy of denial of  the hypothesis of a conditional, the fallacy of the inverse of a conditional, and the fallacy of the converse of a conditional.  

There are other types of fallacies which though may be emotionally, politically, psychologically, etc. persuasive are nonetheless fallacies because the are examples of incorrect reasoning. These are typically referred to as common or everyday fallacies of idiomatic English or fallacies of rhetoric. Rhetoric or elocution, a way with words, the “gift of gab,” advocacy, etc. are possibly fine traits and assist a person in everyday life but they have no place in mathematical reasoning. 

       The fallacy of Petitio Prencipii, or begging the question, is an example. 

       The fallacy of relevance is such that the premises are logically irrelevant to the conclusion.  Its premises are not relevant to the objective of establishing the truth of the conclusion.  One may easily see this if one notes the power of emotive language that through clever use of language a person may persuade an audience to accept a particular conclusion even though a logically correct argument was not used to show the particular conclusion must follow from a set of premises.

       The fallacy of Argumentum ad Bacculum, or the appeal to force, is such that one uses the threat of force or coercion to cause acceptance of a particular statement.  One cannot prove that Catholicism is true by arguing that you will be damned if you don’t agree that Catholicism is true!

       The fallacy of Argumentum ad Hominem takes on many form.  

The fallacy of Argumentum ad Hominem (1), or the abusive, is such that one tries to cause rejection of a proposition by attacking, insulting, criticising, disparaging, or abusing a person who asserts a proposition rather that presenting evidence to disprove the truth of a particular proposition. Oft used to cause anger, resentment, etc. in the audience so that said hostility  clings to the person proposing a statement and transfers to the proposition itself. It is perhaps sound advise to note that one’s attitude toward the person proposing a statement should be held independent of the actual statement since it is independent of the statement.

The fallacy of Argumentum ad Hominem (2), or the circumstantial (1), is such that two or more people disagree about the truth of some proposition and when one or more (the actors), instead of trying to prove the truth of the assertion, tries to cause acceptance of the assertion on the grounds that if follows from the other’s (adversary) beliefs. Just because it follows from one’s beliefs does not establish the veracity of a proposition for the beliefs themselves may be erroneous. The fallacy of Argumentum ad Hominem (2) is a valid form of debate for an actor to note an inconsistency in an adversary’s position; but, to conclude that the author’s position is correct is false since both positions might be in error.  

       The fallacy of Argumentum ad Hominem (3), or the circumstantial (2), is such that a person concludes that a particular position is false on the grounds that the opponent asserts the proposition because of special circumstance and not for an objective reason.  Showing self-interest in the opponent rather than objective evidence as to why the opponent’s position is wrong does not prove the proposition false. Once again, this fallacy may be an effective debating technique, but does nothing to establish whether a proposition is true or false.

       The fallacy of Argumentum ad Ignorantiam, or the argument from ignorance, is such that one argues a position based on false information, faulty information, lack of information, or one’s imagination; further one concludes a proposition is false since it has not been proved true or one concludes a proposition is true since it has not been proved false. 

This position is most easily represented by the position of “it is my opinion [even though there is no evidence to support such] . . .” as if one has a right to be wrong.  It can also be represented by, “the N. I. H. found no evidence to suggest that holistic medicine is harmful.   Thus, holistic medicine is good for you.” Perhaps my favourite example of argumentum ad ignorantiam is “statistics proves [fill in the blank].”[15]

       The fallacy of Argumentum ad Misericordiam, or the argument from misery or pity, is such that one ‘argues’ a position based on pity (the speaker emotes the audience to feel pity for him or his position, thus getting the audience to acquiesce to his conclusion).

       The fallacy of Argumentum ad Populum, or the argument from the popular, is such that one argues a position based on emotive advertising, propoganda, or appeal to the “majority.” There are two types most often refernced in this fallacy: the appeal to snobbery (example: the Polo crest) or the “band-wagon” effect (example: everyone is doing it...).

       The fallacy of Argumentum ad Verecundiam, or the appeal to authority, is such that one argues a position based on an appeal to an authority that is in fact not an authority on the particular subject.  For example, consider that Dr. Pepper recommends flossing one’s teeth.  That Dr. Pepper recommends flossing in no way establishes that flossing is an idea which should be accepted. Dr. Pepper is a soda not a dentist; but, there are many examples of the abuse of the term “doctor.”

       The fallacy of Accident is such that one argues a generalisation or heuristic is usually true, so therefore in a particular case it is true whereas it does not hold in the particular case. For example, consider that a claim that most students take 16 semestre hours each semestre does not imply that Mr. Y is taking sixteen hours.

       The fallacy of Converse Accident, or a hasty generalisation, is such that one argues that a property holds for an individual case or class of cases, therefore it holds in general. This is the fallacy of inductive reasoning since there is no guarantee that there is any reason for generalisation.[16]

       The fallacy of False Cause is such that one argues a particular causal effect from a given set of premises and a causal connection to a conclusion, which in fact erroneously connects the premises and conclusion. The most common example is when a researcher does not understand statistics and logic and notes that X preceded Y, there is a connection between the two (often a property called linear correlation), and thus X caused Y.

       The fallacy of Complex Question occurs when a complex question is posed such that a yes or no answer is given, but there remains a part (not posed) of the complex question assumed a priori answered which was not answered.  There are many types of complex questions, but a type which stands out is one where much previous is inferred.  For example, ”Are you in favour of pulling out of Afghanistan and letting Al Qaeda and the Taliban rape the country again?”  

       The fallacy of Ignoratio Elenchi, or irrelevant conclusion, is one where a person argues a given set of premises support a particular conclusion but the premises force a different conclusion. However, the argument may be so emotionally or psychologically appealing as to render the audience willing to agree that the proposed conclusion follows from the premises. 

       The fallacy of Ambiguity is a fallacious argument form relying on an ambiguous word or phrase which causes the argument to be fallacious with the shift in meaning of the word or phrase. There are at least five ways the fallacy of ambiguity can be committed: through equivocation, amphibole, accent, composition, or division. An example would be all beds are made. All maids are skirted.  Thus, all beds are skirted. In writing it is clearly fallacious, but in sound it could be misunderstood.

       Reviewing this short list of fallacies helps us to understand that rhetoric as opposed to proper logic is fraught with problems.  It is not the job of the mathematician to convince, influence, persuade, etc.  An argument properly constructed should do it (suffice).[17]

 

 

 

 


[1] We will drop the quotation marks when it is understood that we are referencing a symbol rather that a letter.  Often this is difficult to do; for example, suppose one wants to use the variable “a” and they wish to reference a particular one of the a’s.  It would be a problem to say let us consider a a.  Hopefully, this will not occur in this text.

[2] We will rigorous discuss the theory of sets in chapter 2.  Suffice it to say, I am assuming that you had some basic introduction to arithmetic and we are not moving beyond the scope of our introduction to logic by discussing these basic sets.  When introducing an area of mathematics to a student, it is oft times difficult because each student enters the course with some prior introduction to the area (whether it be a correct introduction or an incorrect introduction; more on this comment later).

[3] This will be made clear in Math 255, Set Theory.

[4] This is obvious, but let’s take a closer look.  Note P Ú ØP is logically equivalent to ØP  Ú  P which by the or form into implication form is P  Þ  P !!!!  Now, if anyone (usually in the Humanities or  Social Sciences) says the Law of the Excluded Middle is an antiquated, outdated, or invalid law ask them, “ ‘If - - - -, then  - - - -‘ [fill in the blank] is a fallacy?” 

[5] By the same token note that Ø(P Ú ØP) is logically equivalent to ØP  Ù Ø(ØP) which is  ØP  Ù  P which is

P  Ù  ØP.  Since ØP  Ú  P is always true it must be the case that P Ù ØP is always false.

[6] Recall F Þ T is true as well as F Þ F is true.

[7] A statement is neither valid nor invalid.  We are not assigning truth values to statements exclusive of the opposing possibility.

[8] Technically assumed to be true or agreed to be true since they cannot be proven true.

[9] My favourite method.  Note: this does not imply it will be yours or that you should always attempt to prove a claim using this method.  I am simply noting it is my favourite method for your edification.

[10] See chapter 2 for a definition of real, irrational, rational, etc. numbers

[11] This method is hard to write out & explain, but I believe you will find it the easiest to do and through the doing will understand it better.

[12] For example, in real analysis we have the trichotomy law which state that any real number x must be either less than zero, equal to zero, or greater than zero and never more than one of these at any time.  So, many times one considers a general w (a real) and does three cases (case 1: w < 0; case 2: w = 0; and, case 3: w > 0).

[13] Note this is direct proof (2) technique in the (Þ) direction.

[14] Note this is direct proof (3) technique in the (Ü) direction (so different methods can be employed in each direction).

[15] Since I have a Ph.D. in Statistics, suffice it to say that this bothers me.  Statistics do not prove a thing; statistics only demonstrates evidence to suggest something. 

[16] This should be distinguished from the valid method of proof called mathematical induction, which DOES prove a general claim.

[17] Note should does not imply would.  Whilst it is the case that a properly constructed argument (proof) cannot be denied, it is also the case that humans are full of contradiction, biases, etc.  Thus, we shall see that in mathematics as opposed to the “real world” our arguments will stand on their own. Such cannot be said about life in general or in particular.