The topics discussed in this chapter are: The concrete data structures that can be used to store information, the basic forms of memory allocation, the prototypical examples of these: arrays and linked lists, other data structures, finally we will discuss the run-time of queries and operations on arrays and linked lists. | (CSC 102) Lecture 6 Discrete Structures Previous Lectures Summary Different forms of arguments Modus Ponens and Modus Tollens Additional Valid Arguments Valid Argument with False Conclusion Invalid argument with a true Conclusion Converse and Inverse error Contradictions and valid arguments Predicates and Quantified statements I Today’s Lecture Predicates Set Notation Universal and Existential Statement Translating between formal and informal language Universal conditional Statements Equivalent Form of Universal and Existential statements Implicit Qualification Negations of Universal and Existential statements Predicates A predicate is a sentence which contains finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable Truth Set If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that make P(x) true when substituted for x. The truth set of P(x) is denoted by read as “the set of all x in D such that P(x)”. For any two predicates P(x) and Q(x), the notation means that every element in the truth set of P(x) is in the truth set of Q(x). The notation means that P and Q have identical truth sets. Consider the predicate: The truth set of the above predicate is Notation Example Let P(x) = x is a factor of 8, Q(x)= x is a factor of 4 and R(x)= x < 5 and . The domain of x is assumed to be . Use symbols , to indicate true relationships among P(x), Q(x) and R(x). The truth set of P(x) is {1,2,4,8}, Q(x) is {1,2,4}. Since every element in the truth set of Q(x) is in the truth set of P(x), So The truth Set of R(x) is {1,2,4}, which is identical to the truth set of Q(x). Hence . Cont Cont Let Q(x, y) be the statement x + y = x − y where the domain for x and y is the set of all real numbers. Determine the truth value of: (a) Q(5,−2). (b) Q(, 0). (c) Determine the set of all | (CSC 102) Lecture 6 Discrete Structures Previous Lectures Summary Different forms of arguments Modus Ponens and Modus Tollens Additional Valid Arguments Valid Argument with False Conclusion Invalid argument with a true Conclusion Converse and Inverse error Contradictions and valid arguments Predicates and Quantified statements I Today’s Lecture Predicates Set Notation Universal and Existential Statement Translating between formal and informal language Universal conditional Statements Equivalent Form of Universal and Existential statements Implicit Qualification Negations of Universal and Existential statements Predicates A predicate is a sentence which contains finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable Truth Set If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that .
