# 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

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

## Categories

## You my also like

### Discrete Maths: Exercises & Solutions

557.4 KB29.4K10.6K### Section Clause 1 Concurrent statements

51.9 KB15.1K1.5K### Air, tent & tensile structures

158.4 KB62.2K22.4K### ProTech Professional Technical Services, Inc

148.9 KB62.3K19.3K### Validation of an Analytical Method Using HPLC for

578.4 KB89.1K9.8K### Measuring Information Architecture Quality: Prove It (or Not)!

22.6 KB89.8K35K### Quantification of caffeine in coffee using HPLC SOP

233.5 KB5.7K1.8K### Two Trace Analytical Methods for Determination of Hydroxylated

158.3 KB43.1K9.9K### mRNA translation is a therapeutic vulnerability necessary for

3.1 MB41.9K11.3K