Discrete Mathematics - Lecture 1.1 Propositional Logic PDF

Preview

Summary

Discrete Mathematics - Lecture 1.1 Propositional Logic...

Description

Math 3336 Section 1.1 Propositional Logic What is a proposition? Definition: A proposition is a sentence that is either

, but

.

Examples of Propositions: a. Austin is the capital of Texas. b. Texas is the largest state of the United States. c. 1 + 0 = 1 Examples that are NOT Propositions: a. Watch out! b. What time is it? c. ฀ ฀ + 3 = 5 Try this one: Classify the following as a true statement, false statement, or neither. a. ฀ ฀ > 5 b. Washington DC is the capital of the United States. c. Moon is made of cheese. d. Keep calm. e. Nike manufactures the world’s best running shoes. f. This sentence is false. • •

Letters are used to denote propositions: ฀฀, ฀฀, ฀฀, ฀฀… The truth value of a proposition that is always denoted by proposition that is always denoted by

New propositions ( operators.

, the truth value of a

propositions) can be formed from existing propositions using logical

Definition: Let ฀฀ be a proposition. The of ฀฀, denoted by “It is not the case that ฀฀.” Example: a. Proposition: A triangle has three sides. Negation: It is not the case that triangle has three sides. Negation in simple English: A triangle does have three sides b. Proposition: fish can swim. Negation: It is not the case that all fish can swim. Negation in simple English: S e fish can swim.

Page 1 of 8

, the statement

Try this one What is the negation of each of these propositions? a. Proposition: 2 + 3 = 5 Negation:

b. Proposition: Mike has more than 100 friends on Facebook. Negation:

A proposition and its negation have

E truth values!

Construct a truth table for the negation of ฀฀. ¬฀฀

฀฀

Definition: Let ฀฀ and ฀฀ be propositions. The proposition “฀฀ ฀฀ ” The conjunction i otherwise.

nd ฀฀, denoted ฀฀ and ฀฀ are

Try this one: Construct a truth table for the conjunction. ฀฀

฀฀

Page 2 of 8

฀฀ ∧ ฀฀

฀฀, is the is false

Try this one: Find the conjunction of the following propositions and determine its truth value. a. ฀฀: All birds can fly. ฀฀: 2 + 3 = 5 Conjunction:

Definition: Let ฀฀ and ฀฀ be propositions. Th proposition “ .” The disjunction is otherwise.

and ฀฀, denoted ฀฀ and ฀฀ are

, is the is true

Try this one: Construct the truth table for the disjunction. ฀฀

฀฀

T

T

T

F

F

T

฀฀ ∨ ฀฀

Try this one: Find the disjunction of the following propositions and determine its truth value. a. ฀฀: Triangles are square. ฀฀: Circles are round.

b. ฀฀: 2 = 5 ฀฀: 1 + 1 = 7 Disjunction:

Page 3 of 8

Definition: Let ฀฀ and ฀฀ be propositions. The ” The excl

฀฀ and ฀฀, denoted by when of ฀฀ and ฀฀ i

, is the and is

Example: Students who have taken calculus r computer science can take this class. Soup

salad comes with this entrée.

Try this one: Construct the truth table for the exclusive. ฀฀

฀฀

T

T

F

F

฀฀⨁฀฀

Definition: Let ฀฀ and ฀฀ be propositions. The conditional statement ( proposition “

is the

The conditio

then

, and true otherwise.

In the condit

called

alled c

.

Example: The Truth Table for the Conditional Statement ฀฀ → ฀฀.

฀฀

฀฀

฀฀ → ฀฀

T

T

T

T

F

F

F

T

T

F

F

T

Page 4 of 8

• •

Connection between the hypothesis and conclusion is Think:

Different Ways of Expressing if p, then q

p im

es q

if p, q q when p q if p q follows from p a necessary condition for p is q a sufficient condition for q is p

Example: . a. It is hot w

Definitions: The proposition The proposition The proposition

r it is sunny.

alled c is call is call

. Page 5 of 8

necessary.

Try this one: Write the converse, inverse, and contrapositive for the following statement.

b. I come to class

there is going to be a quiz.

Inverse:

Definition: Let ฀฀ and ฀฀ be propositions. The The biconditional statem lse otherwise. ” Example: You can drive a car if and only if your gas tank is not empty. Page 6 of 8

on E

Try this one: The Truth Table for the Biconditional Statement ฀฀ ↔ ฀฀ . ฀฀

฀฀

T

F

F

T

฀฀↔฀฀

Expressing the Biconditional p is necessary and sufficient for q if p then q , and conversely p iff q Truth Tables for Compound Propositions Construction of a truth table: 1. • Need a row for s for the . 2. Columns • Need a column for the compound proposition (usually at far right) • Need a column for the truth value of each expression that occurs in the compound proposition as it is built up. Example: Construct a truth table for (฀฀ ∨ ¬฀฀) → (฀฀ ∧ ฀฀ )

Page 7 of 8

Equivalent Propositions Definition: Two propositions are

have the

Example: Show using a truth tabl

uivalent

Precedence of Logical Operators Operator

Precedence

¬

1

∧ ∨

2 3

→ ↔

4 5

E ฀฀ ∨ ฀฀ → ¬฀฀ is equivalent to If the intended meaning is ฀฀ ∨

→¬

then parentheses must be used.

Page 8 of 8...