Statement of Proposition CSCI 1900 Discrete Structures


Download Statement of Proposition CSCI 1900 Discrete Structures


Preview text

CSCI 1900 Discrete Structures
Logical Operations Reading: Kolman, Section 2.1

CSCI 1900 – Discrete Structures

Logical Operations – Page 1

Statement of Proposition
• Statement of proposition – a declarative sentence that is either true or false, but not both
• Examples:
– The earth is round: statement that is true 2+3=5: statement that is true
– Do you speak English? This is a question, not a statement

CSCI 1900 – Discrete Structures

Logical Operations – Page 2

More Examples of Statements of
Proposition
• 3-x=5: is a declarative sentence, but not a statement since it is true or false depending on the value of x
• Take two aspirins: is a command, not a statement
• The temperature on the surface of the planet Venus is 800oF: is a declarative statement of whose truth is unknown to us
• The sun will come out tomorrow: a statement that is either true or false, but not both, although we will have to wait until tomorrow to determine the answer

CSCI 1900 – Discrete Structures

Logical Operations – Page 3

Logical Connectives and Compound Statements
• x, y, z, … denote variables that can represent real numbers
• p, q, r,… denote prepositional variables that can be replaced by statements.
– p: The sun is shining today – q: It is cold

CSCI 1900 – Discrete Structures

Logical Operations – Page 4

Negation

• If p is a statement, the negation of p is the statement not p
• Denoted ~p
• If p is true, ~p is false
• If p is false, ~p is true
• ~p is not actually connective, i.e., it doesn’t join two of anything
• not is a unary operation for the collection of statements and ~p is a statement if p is

CSCI 1900 – Discrete Structures

Logical Operations – Page 5

Examples of Negation
• If p: 2+3 >1 then If ~p: 2+3 <1 • If q: It is cold then ~q: It is not the case
that it is cold, i.e., It is not cold.

CSCI 1900 – Discrete Structures

Logical Operations – Page 6

1

Conjunction
• If p and q are statements, then the conjunction of p and q is the compound statement “p and q”
• Denoted p∧q • p∧q is true only if both p and q are true • Example:
– p: ETSU parking permits are expensive – q: ETSU has plenty of parking – p∧q = ?

CSCI 1900 – Discrete Structures

Logical Operations – Page 7

Disjunction
• If p and q are statements, then the disjunction of p and q is the compound statement “p or q”
• Denoted p∨q • p∨q is true if either p or q are true • Example:
– p: I am a male – q: I am under 40 years old – p∨q = ?

CSCI 1900 – Discrete Structures

Logical Operations – Page 8

Exclusive Disjunction
• If p and q are statements, then the exclusive disjunction is the compound statement, “either p or q may be true, but both are not true at the same time.”
• Example:
– p: It is daytime – q: It is night time – p∨q (in the exclusive sense) = ?

CSCI 1900 – Discrete Structures

Logical Operations – Page 9

Inclusive Disjunction
• If p and q are statements, then the inclusive disjunction is the compound statement, “either p or q may be true or they may both be true at the same time.”
• Example:
– p: It is cold – q: It is night time – p∨q (in the inclusive sense) = ?

CSCI 1900 – Discrete Structures

Logical Operations – Page 10

Exclusive versus Inclusive
• Depending on the circumstances, some disjunctions are inclusive and some of exclusive.
• Examples of Inclusive
– “I have a dog” or “I have a cat” – “It is warm outside” or “It is raining”
• Examples of Exclusive
– Today is either Tuesday or it is Thursday – Pat is either male or female

CSCI 1900 – Discrete Structures

Logical Operations – Page 11

Compound Statements
• A compound statement is a statement made from other statements
• For n individual propositions, there are 2n possible combinations of truth values
• A truth table contains 2n rows identifying the truth values for the statement represented by the table.
• Use parenthesis to denote order of precedence • ∧ has precedence over ∨

CSCI 1900 – Discrete Structures

Logical Operations – Page 12

2

Truth Tables are Important Tools for this Material!

p q p∧q TT T TF F FT F FF F

p q p∨q

TT

T

TF

T

FT

T

FF

F

CSCI 1900 – Discrete Structures

Logical Operations – Page 13

Compound Statement Example (p ∧ q) ∨ (~p)

p

q

p ∧q

T

T

T

T

F

F

F

T

F

F

F

F

CSCI 1900 – Discrete Structures

~p (p ∧ q) ∨ (~p)

F

T

F

F

T

T

T

T

Logical Operations – Page 14

Quantifiers
• Back in Section 1.1, a set was defined {x | P(x)}
• For an element t to be a member of the set, P(t) must evaluate to “true”
• P(x) is called a predicate or a propositional function

CSCI 1900 – Discrete Structures

Logical Operations – Page 15

Computer Science Functions
• if P(x), then execute certain steps • while Q(x), do specified actions

CSCI 1900 – Discrete Structures

Logical Operations – Page 16

Universal quantification of a predicate P(x)
• Universal quantification of predicate P(x) = For all values of x, P(x) is true
• Denoted ∀x P(x) • The symbol ∀ is called the universal
quantifier
• The order in which multiple quantifications are considered does not affect the truth value (e.g., ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y) )

CSCI 1900 – Discrete Structures

Logical Operations – Page 17

Examples:

• P(x): -(-x) = x
– This predicate makes sense for all real numbers x.
– The universal quantification of P(x), ∀x P(x), is a true statement, because for all real numbers, -(-x) = x
• Q(x): x+1<4
– ∀x Q(x) is a false statement, because, for example, Q(5) is not true

CSCI 1900 – Discrete Structures

Logical Operations – Page 18

3

Existential quantification of a predicate P(x)
• Existential quantification of a predicate P(x) is the statement “There exists a value of x for which P(x) is true.”
• Denoted ∃x P(x) • Existential quantification may be applied to
several variables in a predicate • The order in which multiple quantifications are
considered does not affect the truth value

CSCI 1900 – Discrete Structures

Logical Operations – Page 19

Applying both universal and existential quantification
• Order of application does matter • Example: Let A and B be n x n matrices • The statement ∀A ∃B A + B = In • Reads “for every A there is a B such that A + B =
In” • Prove by coming up for equations for bii and bij (j≠i) • Now reverse the order: ∃B ∀A A + B = In • Reads “there exists a B such that for all A A + B =
In” • THIS IS FALSE!

CSCI 1900 – Discrete Structures

Logical Operations – Page 20

Assigning Quantification to Proposition
• Let p: ∀x P(x) • The negation of p is false when p is true
and true when p is false • For p to be false, there must be at least
one value of x for which P(x) is false. • Thus, p is false if ∃x ~P(x) is true. • If ∃x ~P(x) is false, then for every x, ~P(x)
is false; that is ∀x P(x) is true.

CSCI 1900 – Discrete Structures

Logical Operations – Page 21

Okay, what exactly did the
previous slide say?
• Assume a statement is made that “for all x, P(x) is true.”
– If we can find one case that is not true, then the statement is false.
– If we cannot find one case that is not true, then the statement is true.
• Example: ∀ positive integers, n, P(n) = n2 + 41n + 41 is a prime number.
– This is false because ∃ an integer resulting in a non-prime value, i.e., ∃n such that P(n) is false.

CSCI 1900 – Discrete Structures

Logical Operations – Page 22

4

Preparing to load PDF file. please wait...

0 of 0
100%
Statement of Proposition CSCI 1900 Discrete Structures