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, K^C 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