Introduction to Logic

In order to understand mathematics and its language, we need a first trip to the land of Logic. Very often students wonders about the difficulties encountered in dealing with proofs, but the real problem facing them is more related to their grasp of logic.


Basic logical terms


A statement such as:"Mexico is a continent" is clearly a false statement. There are other statements which are difficult to determine whether they are true or not. For example, the statement :"Mozart said minute before his death, I love Mexico...", will be very hard to check. The problem of checking whether a statement is true or false is the main concern of Logic. We will see how this relates to mathematics later on. A statement will be also called a proposition. For examples

1.

" is rational"

2.

"two lines parallel have the same slope"

3.

"Mozart died on a Monday"

are propositions. Note that these propositions are simple or atomic meaning they do not involve other propositions. Compound propositions can be formed by combining more than one proposition.


Logical Connectives


Definition. Let P and Q be two propositions.

1.

The conjunction of P and Q, denoted , is the proposition . Note that is true if and only if P and Q are both true.

2.

The disjunction of P and Q, denoted , is the proposition . Note that is true if and only if P or Q is true.

3.

The negation of P, denoted , is the proposition . Note that is true if and only if P is false.

and are called logical connectives.


Using this definition, one may combine simple or atomic propositions, to generate more complicated ones (compound ones). A propositional form is an expression involving finitely many logical symbols such as , , and letters. For example, the expression



is a propositional form. In order to check whether such expressions are true or false, we use the truth tables.

Example. Write down the truth table of the propositional form .

Answer. Since P and Q are the only atomic propositions involved in this expression, we have



As you see the truth table of the proposition P and the propositional form are the same. That is the two propositions have the same truth value (true or false). In this case, we say they are equivalent. Another example of equivalent propositions is given by P and . In deed, we have



Example. Find the truth table of .

Answer. We have



This example is very interesting since it shows that there exists propositional forms which are always true. We call them Tautologies. A contradiction is the negation of a tautology. For example, is a contradiction.


Section
Mohamed Khamsi
Wed Aug 27 17:17:43 MDT 1997