discrete math

alohaf

09_Goldstein_Schneider_Siegel_Chapter12withnotes.pptx

Home >Mathematics homework help >discrete math

1 of 120

Chapter 12

Logic

2 of 120

Outline

12.1 Introduction to Logic

12.2 Truth Tables

12.3 Implication

12.4 Logical Implication and Equivalence

12.5 Valid Argument

12.6 Predicate Calculus

12.7 Logic Circuits

3 of 120

12.1 Introduction to Logic

Statement and Truth Value

Compound Statement

Variables

Logical Connectives

4 of 120

Statement and Truth Value

A statement is a declarative sentence that is either true or false.

The truth value of a statement is either TRUE or FALSE.

Although statements are either true or false (and never both), we may not have enough information to know its truth value.

5 of 120

George Washington was the first president of the United States.

This is a true statement.

The New York Knicks won the NBA basketball championship in 1989.

This is a false statement.

The number of atoms in the universe is 1075.

This statement is either true or false but we don’t know which it is.

Example Statement

6 of 120

Compound Statement

A simple statement is a statement that is formed using the words “and,” “or,” “not,” or “if, then.”

A compound statement is formed by combining statements using the words “and,” “or,” “not,” or “if, then.”

A simple statement is a statement that is not a compound statement.

7 of 120

Variables

To develop the rules of logic and logical arguments, we need to deal with any logical statement, rather than specific examples. We use the variables p, q, r, and so on to represent simple statements.

8 of 120

The number 6 is even and the number 5 is odd.

This compound statement is of the form p and q where p = “The number 6 is even” and q = “The number 5 is odd.”

Tom Jones does a term paper or takes the final exam.

This compound statement is of the form p or q where p = “Tom Jones does a term paper” and q = “Tom Jones takes the final exam.”

Example Compound Statement

9 of 120

Logical Connectives

When writing compound statements in terms of its component parts, the following logic symbols are used:

Word	Symbol
and
or
not	~
if, then

10 of 120

Define p and q and determine the logical connective to rewrite the following statement:

Fred and Cindy like each other.

Let p = “Fred likes Cindy.”

Let q = “Cindy likes Fred.”

Example Compound Statement with

The symbolic statement then becomes p q.

11 of 120

Define p and q and determine the logical connective to rewrite the following statement:

The train stops in New York or Washington.

Let p = “The train stops in New York.”

Let q = “The train stops in Washington.”

Example Compound Statement with

The symbolic statement then becomes p q.

12 of 120

Define p and q and determine the logical connective to rewrite the following statement:

Fred likes Cindy but Cindy does not like Fred.

Let p = “Fred likes Cindy.”

Let q = “Cindy likes Fred.”

Example Compound Statement with

The symbolic statement then becomes p ~q.

13 of 120

Define p and q and determine the logical connective to rewrite the following statement:

If the train stops in New York, it does not stop in Washington.

Let p = “The train stops in New York.”

Let q = “The train stops in Washington.”

Example Compound Statement with

The symbolic statement then becomes p ~ q.

14 of 120

A logical statement (proposition) is a declarative sentence that is either TRUE or FALSE.

Summary Section 12.1

Logical statements frequently have

Connectives such as and , or , not ~, and

implies (if, then ) .

15 of 120

12.2 Truth Tables

Statement Form

Propositional Calculus

Truth Table

Tautology and Contradiction

Exclusive Or

Tree

Logic and Computer Languages

16 of 120

Statement Form

A statement form is an expression formed from simple statements and connectives according to the following rules:

A simple statement is a statement form.

If p is a statement form, ~p is a statement form.

If p and q are statement forms, then so are p q,

p q, and p q.

17 of 120

Example Statement Form

a) ( p ~ r ) r is a statement form.

b) ~ ( p ( q ~ r )) is a statement form.

If p, q, and r are simple statements, then

18 of 120

Propositional Calculus

The propositional calculus is the manipulation, verification, and simplification of logical statement forms. Truth tables and trees diagrams will be used to determine the truth values of statement forms.

19 of 120

Truth Table

A truth table is a table that includes:

A column for each simple statement;

A column for the compound statement;

A row for each possible combination (arrangement) of the truth values for the simple statements;

The column for the statement form has its truth value depending on the truth values of the simple statements in the corresponding row.

20 of 120

Survey the crowd

A statement form that has truth value TRUE regardless of the truth values of the individual statement variables it contains is called a

_______.

21 of 120

Survey the crowd

A statement form that has truth value TRUE regardless of the truth values of the individual statement variables it contains is called a tautology.

A statement form that has truth value FALSE regardless of the truth values of the individual statement variables it contains is called a __________.

22 of 120

Tautology and Contradiction

A statement form that has truth value TRUE regardless of the truth values of the individual statement variables it contains is called a tautology.

A statement form that has truth value FALSE regardless of the truth values of the individual statement variables it contains is called a contradiction.

23 of 120

Example Truth Table of Negation ( ~ )

p	~ p
T	F
F	T

Note: T means TRUE and F means FALSE.

The statement form ~ p has the opposite truth value as the statement form p.

24 of 120

Example Truth Table of Conjunction ( )

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

The statement form p q is TRUE if and only if both statement forms p and q are TRUE.

25 of 120

Example Truth Table of Disjunction ( )

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

The statement form p q is FALSE if and only if both statement forms p and q are FALSE.

26 of 120

Truth Table for More Than One Connective

If a statement form contains more than one connective, the truth table often includes the truth values of the intermediate steps. See the following example.

27 of 120

Example More Than One Connective

T	T
T	F
F	T
F	F
1	2

Find the truth table for ( p q ) ~ ( p q ).

( p q)

( p q )

28 of 120

Survey the crowd

The statement of the previous example

( p q ) ~ ( p q )

can be read as “p or q but not both p and q.”

This is what familiar combination?

29 of 120

Exclusive Or

The statement of the previous example

( p q ) ~ ( p q )

can be read as “p or q but not both p and q.”

This is what familiar combination?

Exclusive OR

30 of 120

Survey the crowd

The statement of the previous example

( p q ) ~ ( p q )

can be read as “p or q but not both p and q.”

This is what familiar combination?

Exclusive OR

And what single Boolean symbol is used to represent the XOR?

31 of 120

Exclusive Or

The statement of the previous example

( p q ) ~ ( p q )

can be read as “p or q but not both p and q.”

This is what familiar combination?

Exclusive OR

And what single Boolean symbol is used to represent the XOR?

32 of 120

Exclusive Or

The statement of the previous example

( p q ) ~ ( p q )

can be read as “p or q but not both p and q.” This is the exclusive or and is denoted by the symbol .

p q

33 of 120

Example More Than Two Variables

Construct the truth table for

( p q ) (( p r ) ~ q ).

34 of 120

Example More Than Two Variables

( p q ) (( p r ) ~ q )

35 of 120

Tree

Another method of describing a statement form is by using a tree. The statement form is written at the top of the tree. The statement is then separated along the branches into its operands until only simple statements are at the end of the branches.

~ q

( p ~ q )

For example:

( p ~ q ) r

36 of 120

Example Tree

Use a tree to find the truth value of

( p ~ q ) r

if p is true and q and r are both false.

The statement is TRUE.

37 of 120

Example Tree

Use a tree to find the truth value of

( p ~ q ) r

if p is true and q and r are both false.

The statement is TRUE.

38 of 120

Logic and Computer Languages

Many computer languages and graphing calculators use logical connectives in programs that depend on logical decision making.

For example in a TI-83/84 Plus:

Calculator Function

Logic symbol

AND

NOT

XOR

39 of 120

Example Excel

Use an Excel spreadsheet to find the truth value of

( p ~ q ) r

if p is TRUE and q and r are both FALSE.

40 of 120

Summary Section 12.2 - Part 1

A statement without any connectives is called a simple statement. A statement form is a simple statement or simple statements with connectives. The truth value of a statement form depends only on the truth values of the simple statements it contains.

The exclusive or, denoted by p q, is TRUE only if one of p or q is TRUE but not both. Otherwise, it is FALSE.

41 of 120

Summary Section 12.2 - Part 2

A truth table or tree can be used to determine the truth value of a statement form.

The truth table for the connectives ~, , and is

~ p

p q

42 of 120

Summary Section 12.2 - Part 3

A statement that always has a truth value TRUE is called a tautology. A statement that always has a truth value FALSE is called a contradiction.

The logical connectives used in computer languages and calculators AND, OR, NOT and XOR correspond to the symbols , , ~ and , respectively.

43 of 120

12.3 Implication

Conditional Connective

English Equivalents

Converse

Biconditional Connective

Order of Precedence

Implication and Computer Languages

The logic symbol is called the conditional connective.

The statement p q is FALSE only if the hypothesis p is TRUE and the conclusion q is FALSE.

Otherwise, it is TRUE.

44 of 120

Conditional Connective

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

45 of 120

English Equivalents

There are several ways to read p q in English.

p implies q.

If p, then q.

p only if q.

q, if p.

p is sufficient for q.

q is a necessary condition for p.

46 of 120

Survey the crowd

There are several ways to read p q in English.

In this implication, the p portion is called the

___________?

47 of 120

Survey the crowd

There are several ways to read p q in English.

In this implication, the p portion is called the

antecedent.

48 of 120

Survey the crowd

There are several ways to read p q in English.

In this implication, the p portion is called the

antecedent.

And the q portion is called the

________?

49 of 120

Survey the crowd

There are several ways to read p q in English.

In this implication, the p portion is called the

antecedent.

And the q portion is called the

consequent.

50 of 120

Example English Equivalences

Determine the hypothesis and the conclusion for each of the following.

Bill goes to the party only if Greta goes to the party.

Sue goes to the party if Craig goes to the party.

For 6 to be even, it is sufficient that its square, 36, be even.

51 of 120

Example English Equivalences (a)

Bill goes to the party only if Greta goes to the party.

The statement is of the form p only if q.

The hypothesis p is “Bill goes to the party.”

The conclusion q is “Greta goes to the party.”

52 of 120

Example English Equivalences (b)

Sue goes to the party if Craig goes to the party.

The statement is of the form q, if p.

The hypothesis p is “Craig goes to the party.”

The conclusion q is “Sue goes to the party.”

53 of 120

Example English Equivalences (c)

For 6 to be even, it is sufficient that its square, 36, be even.

The statement is of the form p is sufficient for q.

The hypothesis p is “The square of the integer 6 is even.”

The conclusion q is “The integer 6 is even.”

54 of 120

Converse

The implication q p is the converse of the statement p q.

For example, the converse of the statement

“If x = -6, then x2 = 36”

“If x2 = 36, then x = -6.”

55 of 120

Example Converse

Construct the truth table for ( p q ) ( q p ).

( p q )

( q p )

56 of 120

Biconditional

The statement form ( p q ) ( q p ) is referred to as the biconditional, which we write as p q. It is read as “p, if and only if q.”

The biconditional is TRUE only if both statements p and q have the same truth value. Otherwise the statement is FALSE.

57 of 120

Order of Precedence

Whenever two or more connectives are listed in a statement form with no parentheses to indicate the order of the connectives, the following order of precedence is to be used:

~, , , , .

58 of 120

Example Order of Precedence

Insert parentheses in the statement

p q r ~ s r

to show the proper order for the application of the connectives.

p q r ~s r

59 of 120

Example Order of Precedence

Insert parentheses in the statement

p q r ~ s r

to show the proper order for the application of the connectives.

60 of 120

Implication and Computer Languages

The logical connective is used in writing computer programs. One example is the

“IF … THEN … ELSE”

statement. The computer checks to see if the statement following IF is TRUE. If it is, then the statement following THEN is executed. If it is not TRUE, then the statement following ELSE is executed.

61 of 120

Survey the crowd

For the given input values of A and B, use the program to determine the value of C.

IF (A*B + 6 > 10)

THEN LET C = A*B

ELSE LET C = 10

a) A = -2, B = -7 b) A = -2, B = 3

62 of 120

Example IF … THEN … ELSE (a)

a) A = -2, B = -7:

IF (A*B + 6 > 10):

A*B + 6 > 10 is (-2)(-7) + 6 > 10.

The above statement is TRUE.

THEN LET C = A*B:

C = A*B becomes C = 14.

The computer sets C to 14.

63 of 120

Example IF … THEN … ELSE (b)

b) A = -2, B = 3:

IF (A*B + 6 > 10):

A*B + 6 > 10 is (-2)(3) + 6 > 10.

The above statement is FALSE.

ELSE LET C = 10:

The computer sets C to 10.

64 of 120

Summary Section 12.3 - Part 1

The truth table for the conditional connective and the biconditional connective is

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

65 of 120

Summary Section 12.3 - Part 2

The order of precedence of logical connectives is ~, , , , . If parentheses are present in the statement, then they take precedence over the above order.

The converse of p q is q p. If an implication is TRUE, its converse is not necessarily TRUE.

66 of 120

Summary Section 12.3 - Part 3

The statement p q is the implication “if p, then q (or p implies q).” It is FALSE only when p is TRUE and q is FALSE. The two-way implication p q is TRUE whenever p and q have the same truth value and FALSE otherwise.

The logical connective used in computer languages IF…THEN corresponds to the logical symbol .

67 of 120

12.4 Logical Implication and Equivalence

Logically Equivalent

Statements as Variables

De Morgan’s Laws

Other Equivalences

Substitution Principles

Logical Implications

68 of 120

Logically Equivalent

Two statement forms that have the same truth tables are called logically equivalent.

A statement that has the truth value TRUE regardless of the truth value of its component statements is called a tautology and we denote it with the letter t.

A statement that has the truth value FALSE regardless of the truth value of its component statements is called a contradiction and we denote it by the letter c.

69 of 120

Example Logically Equivalent

Verify that ~(p q) (~p ~q).

~( p q ) ( ~p ~q )

70 of 120

Statements as Variables

In this case, we write P Q.

For convenience, we denote compound statement forms by capital letters.

P is logically equivalent to Q if and only if P Q is a tautology.

71 of 120

De Morgan’s Laws

The following two statements are called

De Morgan’s laws.

~ (p q) (~ p ~ q)

72 of 120

Example De Morgan’s Laws

Negate the statement “The earth’s orbit is round and a year has 365 days.”

If p is “The earth’s orbit is round” and q is “A year has 365 days,” then the original statement is p q. We want ~ (p q) (~ p ~ q).

The negation is “The earth’s orbit is not round or a year does not have 365 days.”

73 of 120

Other Equivalences (1)

Double negation:

Commutative laws:

Associative laws:

74 of 120

Other Equivalences (2)

Distributive laws:

Idempotent laws:

Identity laws:

From:	Conclude:
P	P Q	Addition
P Q	P	Subtraction
P ( P Q )	Q	Modus ponens
	~ P	Modus tollens
	Q	Disjunctive syllogism
		Hypothetical syllogism
		Constructive dilemmas

1.		Hypothesis
2.		Hypothesis
3.	~ p	Hypothesis
4.	q, since	Disjunctive syllogism (1,3)
5.	~ r, since

1.	p	Negation of conclusion
2.	p  ~ q	Hypothesis
3.	~ q	Modus ponens (1, 2)
4.		Hypothesis
5.	r	Disjunctive syllogism (3, 4)

From:	Conclude:
P	P Q	Addition
P Q	P	Subtraction
P ( P Q )	Q	Modus ponens
	~ P	Modus tollens
	Q	Disjunctive syllogism
		Hypothetical syllogism
		Constructive dilemmas

Union:
Intersection:
Complement:
Symmetric Difference:
Subset
Equal