The document introduces key concepts in discrete structures including propositions, propositional functions, predicates, truth tables, and logical operators. It discusses how propositional functions become propositions when variables are instantiated and how universal and existential quantifiers are used to form statements about predicates over a domain. Examples are provided to illustrate propositional functions, quantification, negation, and nested quantifiers.
The document introduces key concepts in discrete structures including propositions, propositional functions, predicates, truth tables, and logical operators. It discusses how propositional functions become propositions when variables are instantiated and how universal and existential quantifiers are used to form statements about predicates over a domain. Examples are provided to illustrate propositional functions, quantification, negation, and nested quantifiers.
The document introduces key concepts in discrete structures including propositions, propositional functions, predicates, truth tables, and logical operators. It discusses how propositional functions become propositions when variables are instantiated and how universal and existential quantifiers are used to form statements about predicates over a domain. Examples are provided to illustrate propositional functions, quantification, negation, and nested quantifiers.
The document introduces key concepts in discrete structures including propositions, propositional functions, predicates, truth tables, and logical operators. It discusses how propositional functions become propositions when variables are instantiated and how universal and existential quantifiers are used to form statements about predicates over a domain. Examples are provided to illustrate propositional functions, quantification, negation, and nested quantifiers.
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 15
Discrete Structures
CMSC 203 - DISCRETE STRUCTURES Spring 2003
1 •Proposition • Statement, Truth value, • Proposition, Propositional symbol, Open proposition •Operators • Define by truth tables • Composite propositions • Tautology and contradiction •Equivalence of propositional statements • Definition • Proving equivalence (by truth table or equivalence laws)
CMSC 203 - DISCRETE STRUCTURES Spring 2003 2
PROPOSITIONAL FUNCTIONS & PREDICATES •Propositional function (open sentence): •statement involving one or more variables, • e.g.: x-3 > 5. •Let us call this propositional function P(x), where P is the predicate and x is the variable. What is the truth value of P(2) ? false What is the truth value of P(8) ? false What is the truth value of P(9) ? true When a variable is given a value, it is said to be instantiated Truth value depends on value of variable CMSC 203 - DISCRETE STRUCTURES Spring 2003 3 PROPOSITIONAL FUNCTIONS •Let us consider the propositional function Q(x, y, z) defined as:
•x + y = z. •Here, Q is the predicate and x, y, and z are the variables. What is the truth value of Q(2, 3, 5) ? true What is the truth value of Q(0, 1, 2) ? false What is the truth value of Q(9, -9, 0) ? true A propositional function (predicate) becomes a proposition when all its variables are instantiated. CMSC 203 - DISCRETE STRUCTURES Spring 2003 4 PROPOSITIONAL FUNCTIONS •Other examples of propositional functions
•Person(x), which is true if x is a person
Person(Socrates) = T Person(dolly-the-sheep) = F ITCourse(x), which is true if x is a computer engineering course ITCourse(Discrete155) = T ITourse(Music155) = F How do we say All humans are mortal One CpE course CMSC 203 - DISCRETE STRUCTURES Spring 2003 5 UNIVERSAL QUANTIFICATION •Let P(x) be a predicate (propositional function).
•Universally quantified sentence:
•For all x in the universe of discourse P(x) is true.
•Using the universal quantifier :
•x P(x) “for all x P(x)” or “for every x P(x)”
•(Note: x P(x) is either true or false, so it is a proposition, not a
propositional function.)
CMSC 203 - DISCRETE STRUCTURES Spring 2003 6
UNIVERSAL QUANTIFICATION •Example: Let the universe of discourse be all people S(x): x is a UMBC student. G(x): x is a genius.
•What does x (S(x) G(x)) mean ?
•“If x is a UMBC student, then x is a genius.” or •“All UMBC students are geniuses.” •If the universe of discourse is all UMBC students, then the same statement can be written as x G(x)
CMSC 203 - DISCRETE STRUCTURES Spring 2003 7
EXISTENTIAL QUANTIFICATION •Existentially quantified sentence: •There exists an x in the universe of discourse for which P(x) is true.
•Using the existential quantifier :
•x P(x) “There is an x such that P(x).” • “There is at least one x such that P(x).”
•(Note: x P(x) is either true or false, so it is a proposition, but
no propositional function.)
CMSC 203 - DISCRETE STRUCTURES Spring 2003 8
EXISTENTIAL QUANTIFICATION •Example: •P(x): x is a UMBC professor. •G(x): x is a genius.
•What does x (P(x) G(x)) mean ?
•“There is an x such that x is a UMBC professor and x is a genius.”
•or •“At least one UMBC professor is a genius.”
CMSC 203 - DISCRETE STRUCTURES Spring 2003 9
QUANTIFICATION •Another example: •Let the universe of discourse be the real numbers.
•What does xy (x + y = 320) mean ?
•“For every x there exists a y so that x + y = 320.”
Is it true? yes
Is it true for the natural numbers? no
CMSC 203 - DISCRETE STRUCTURES Spring 2003 10
DISPROOF BY COUNTEREXAMPLE •A counterexample to x P(x) is an object c so that P(c) is false.
•Statements such as x (P(x) Q(x)) can be disproved by
simply providing a counterexample.
Statement: “All birds can fly.”
Disproved by counterexample: Penguin.
CMSC 203 - DISCRETE STRUCTURES Spring 2003 11
NEGATION
• (x P(x)) is logically equivalent to x (P(x)).
• (x P(x)) is logically equivalent to x (P(x)).
NESTED QUANTIFIER • A predicate can have more than one variables. • S(x, y, z): z is the sum of x and y • F(x, y): x and y are friends • We can quantify individual variables in different ways • x, y, z (S(x, y, z) (x <= z y <= z)) • x y z (F(x, y) F(x, z) (y != z) F(y, z)
CMSC 203 - DISCRETE STRUCTURES Spring 2003 14
SUMMARY, SECTIONS 1.3, 1.4 • Propositional functions (predicates) • Universal and existential quantifiers, and the duality of the two • When predicates become propositions • All of its variables are instantiated • All of its variables are quantified • Nested quantifiers • Quantifiers with negation • Logical expressions formed by predicates, operators, and quantifiers
