Discrete Structure Reviewer PDF

DISCRETE STRUCTURE REVIEWER Continuous Mathematics Deals with continuous number lines or real numbers. Between any two numbers, there is an infinite set of numbers. Discrete Mathematics Deals with distinct, separate values. Between any two points, there is a countable num...

DISCRETE STRUCTURE REVIEWER Continuous Mathematics Deals with continuous number lines or real numbers. Between any two numbers, there is an infinite set of numbers. Discrete Mathematics Deals with distinct, separate values. Between any two points, there is a countable number of points. LOGIC What is Logic? Logic is the study of reasoning. It establishes rules and techniques for determining whether arguments are valid. Example: If Peter solved seven problems correctly, then he earned an A grade. Peter earned an A grade. Therefore, Peter solved seven problems correctly. Logic operates on propositions—statements that are either true (T) or false (F), corresponding to 1 and 0 in digital circuits. Proposition Definition: A proposition is a statement that can be judged as either true or false, but not both. Examples of Propositions: 4 is an integer. 5 is an integer. Washington, DC, is the capital of the USA. Non-Propositions: "How are you?" (a question)  "Close the door." (a command) Statement A statement expresses a proposition in language. Examples of Statements: "The grass is green." (true if grass is green) "The Earth is flat." (false because the Earth is round) Statement vs. Proposition Game: Elephants are bigger than mice: Proposition (True) 520 < 111: Proposition (False) y > 5: Not a proposition (depends on the value of y). Statement Variables: Symbols like p,q,r,…p, q, r, \dotsp,q,r,… are used to represent statements. Exercise: Which are statements? 1. 2 is an even integer. (Yes) 2. Why should we study Mathematics? (No) 3. 7+3=117 + 3 = 117+3=11. (Yes) 4. Please be quiet. (No) 5. There will be snow in December in the Philippines. (Yes) Sets and Truth Tables Set: A set is a collection of objects, and each object is called an element of the set. Truth Table: A truth table is a tool for determining the truth value of propositions and the validity of arguments. Logical Connectives Negation - consider the following statements P: 2 is positive Q: It is not the case that 2 is positive Let p be a statement. The negation of p, written p, is the statement obtained by negating statement p. p: 2 is positive. ~p : It is not the case that 2 is positive. p ~p T F F T Five connectives: Conjunction AND Symbol ^ Disjunction OR Symbol v Negation Symbol ~ Implication Symbol —> Double implication Symbol Conjunction (AND) Consider the following statements: p: 2 is an even integer. q: 7 divides 14. Let p and q be statements. The conjunction of p and q, written p ^ q, is the statement formed by joining statements p and q using the word “and”. p q p^q T T T  T F F F T F F F F Disjunction (OR) Consider the following statements: p: 5 is an even integer. q: 3 is greater than 5. p q pvq T T T T F T F T F F F F Exclusive OR The Exclusive Or or Xor of two propositions is true when exactly one of the propositions is true and the other one is false. Example: The circuit is ON or OFF, but not both. You may have ice cream or cake, but not both. p q p⊕ q T T F T F T F T T F F F Implication In each of the statements, two statements are connected by “if…then” to form a new statement.  p q p —> q T T T T F F F T T F F T Let p and q be statements (i) The statement q→p is called the converse of the implication of p→q. (ii) The p→q is called the inverse of the implication p→q. (iii) The q→p is called the contrapositive of the implication p→q Biimplication Given two statements we form a new statement by putting the phrase “if and only if” between the two statements. p q p q T T T T T F F F F F F T Statement Formulas (A), (AB), (AB), (A→B), and (AB) The symbol ~,^ v, , →, and are called logical connectives. The symbols p,q,r,…, called statement variables