Logic Course Lesson 1

Logic Course Lesson 1

Logic Course 01 - Introduction

Consider the following problem:

John, Mary and Paul have different occupations. One is a doctory, one is a lawyer and one is an engineer. Paul is married to the engineer and John is not the lawyer. What are their occupations?

These problems are usually solved using a matrix to record information and to eliminate possibilities. A matrix for this problem would look like this:

John Mary Paul
Doctor .... .... ....
Lawyer .... .... ....
Engineer .... .... ....

We can determine that Mary is the Engineer because Paul is male and Mary is the only female. So we can now fill in the following parts of the table:

John Mary Paul
Doctor ....
no
 ....
Lawyer ....
no
 ....
Engineer
no
yes
no

We can determine that John is the Doctor because he is not the lawyer (this is given in the problem) and he is not the engineer (this is determined from the matrix). So we now have:

John Mary Paul
Doctor
yes
no
 ....
Lawyer
no
no
 ....
Engineer
no
yes
no

Paul must be the Lawyer because he isn't the Doctor and he isn't the Engineer (you can see this in the matrix). Here is the final matrix:

John Mary Paul
Doctor
yes
no
no
Lawyer
no
no
yes
Engineer
no
yes
no

This problem illustrates the use of logic in solving a problem. But what do we mean by logic? Is it the facts given to us? The matrix that we used? The outside knowledge that we have to understand what the facts imply?

In the context of this course, we will use logic in a few different ways.

The first definition of logic that we find in the Merriam-Webster Dictionary is that logic is a science that deals with the principles and criteria of validity of inference and demonstration. We will learn about two types of logic and then discuss the components of formal logical systems.

Propositional Logic

 In propositional logic, we deal with propositions that are either true or false. An example is the proposition:

Today is Tuesday

This proposition is either true or false. Generally speaking, there is a limited amount of power in propositional logic as you can't get inside propositions. You can only deal with the statement as being true or false.

Before starting in on propositional logic, we'll go over Boolean Expressions which will be useful for propositional logic later on.

Boolean Expressions

Boolean expressions are constructed from constants, variables and operators. Constants can be true or false. Variables can only take on the values true or false. And operators can be one of the following: Let's look at an example of a boolean expression:

( true ^ false ) _ true

This expression is read: the result of true and false, or true. true and false evaluates to false. false or true evaluates to true.

We can evaluate expressions by using truth tables. The truth table contains the names of variables in the upper left corner of the table. The leftmost column of the table contains a row for each of the possible combinations of true and false for the variables under consideration. In general, there are 2 to the nth power rows where n is the number of variables under consideration.

Here is a simple truth table with one variable. The variable has two possible values which are listed in the first column and they are true and false. The possible results are the same: true and false

p
p
t
f 		t
f

Next, we'll go through the operators mentioned above.

not (negation)

Not is a unary operator (it takes one argument) that returns the opposite value of its argument. The expression not true evaluates to false and the expression not false evaluates to true. We will use the symbol Ø before a constant or variable to mean the negation (not) of the constant or variable.

The truth table for not is:

p
Øp
t
f
f
t

and (conjunction)

And is a binary operator (it acts on two operands) and returns true when both operands are true. It returns false in all other cases. We use the ^ operator between two operands to indicate and. Operands a and b of a ^ b are called conjuncts.

The truth table for and is:

p
q
p^q
t
t
f
f
t
f
t
f
t
f
f
f

or (disjunction)

p
q
p_q
t
t
f
f
t
f
t
f
t
t
t
f

if-then (implication)

p
q
p®q
t
t
f
f
t
f
t
f
t
f
t
t

if-and-only-if (equivalence)

p
q
p«q
t
t
f
f
t
f
t
f
t
f
f
t

This page is maintained by Michael Moy mmoy@yahoo.com

and was updated on February 9, 2000 This page is Copyright by Michael Moy. All rights reserved though permission is granted for personal use. Permission is not granted for commercial use. 1