Discrete Structures Final Term PDF

**QUANTIFIERS\ **- are words that tell us how many, two types of quantifiers are: 1\. **EXISTENSIAL** -- a quantifier indicating that the sentential function within its scope is true for at least one value of the variable included in the quantifier. Examples are:\ some, sometimes, there is, there e...

**QUANTIFIERS\ **- are words that tell us how many, two types of quantifiers are: 1\. **EXISTENSIAL** -- a quantifier indicating that the sentential function within its scope is true for at least one value of the variable included in the quantifier. Examples are:\ some, sometimes, there is, there exists\ 2. **UNIVERSAL** -- convey the idea of totality. Examples are:\ all, always, none, never **PROPOSOTIONAL EQUIVALENCES**\ - use in constructing arguments which has three different types: 1\. **TAUTOLOGY** -- is a statement that is always true.\ Ex. ( p → q ) ↔ ( \~p v q )\ 2. **CONTRADICTION** -- is a statement that is always false.\ Ex. p \^ \~p\ 3. **CONTINGENCY** -- a compound proposition that is neither tautology nor contradiction.\ Ex. p \^ q **LOGICAL EQUIVALENCE**\ - compound propositions that have the same truth values in all possible cases are called logically equivalent. **EQUIVALENCE LAWS:** *IDENTITY LAWS* -- the first of the three classical laws of thought. It states that each thing is the same with itself and different from another.\ p \^ T = p\ p v F = p *DOMINATION LAWS* -- the truth value is the most important, powerful, or influential.*\ *p v T = T\ p \^ F = F *DOUBLE NEGATION* -- the theorem that states that "if a statement is true, then it is not the case that the statement is not true.\ \~ ( \~p ) = p\ \ *IDEMPOTENT LAWS* -- states that combining a quantity with itself through logical is the equivalent of the quantity.\ p \^ p = p\ p v p = p *COMMUTATIVE LAWS* -- states that we can swap components over and still get the same answer.\ p v q = q v p\ p \^ q = q \^ p *ASSOCIATIVE LAWS* -- states that it doesn't matter how we group the components.\ ( p v q ) v r = p v ( q v r )\ ( p \^ q ) \^ r = p \^ ( q \^ r ) *DISTRIBUTIVE LAWS* -- states that taking the component of a compound of intersection of two other compound is the same as taking the component of the original set and both the other two compound separately, and then taking the intersection of the results.\ p v ( q \^ r ) = ( p v q ) \^ ( p v r )\ p \^ ( q v r ) = ( p \^ q ) v ( p \^ r ) *De MORGAN'S LAWS* -- a pair of transformation rules that are both valid rules on inference.\ \~ ( p \^ q ) = \~p v \~q\ \~ ( p v q ) = \~p \^ \~q *ABSORPTION LAWS* -- states that a process of including a component into a compound but still have the result of the component.\ p v ( p \^ q ) = p\ p \^ ( p v q ) = p *NEGATION LAWS* -- also called logical complement, is an operation that takes a proposition p to another proposition "not p", which is interpreted intuitively as being true when p is false and false when p is true.\ p v \~p = T\ p \^ \~p = F *IMPLICATION LAW* -- a valid rule of replacement that allows for a conditional statement to be replaced by a disjunction in which the antecedent is negated.\ p → q = \~p v q *BICONDITIONAL PROPERTY* -- (sometimes known as material biconditional) is the logical connective of two statements asserting "p if and only if q", where p is an antecedent (event that existed before or logically precedes another) and q is a consequent (following as a result or effect / an event that follows another).\ p ↔ q = ( p \^ q ) v ( \~p \^ \~q ) *CONTRAPOSITIVE OF CONDITIONAL STATEMENT* -- switching the hypothesis and conclusion of a conditional statement and negating both.\ p → q = \~q → \~p **AXIOM\ ** - things known to be true (facts or proven theorems).\ - things believed to be true but cannot be proved. **PROOF**\ - we can use a proof to demonstrate that a particular statement is true. A proof consists of a sequence of statements that form an argument. **RULES OF INFERENCE\ ** - the steps that connect the statements in such a sequence. **FALLACIES\ ** - cases of incorrect reasoning. **THEOREM\ ** - a statement that can be shown to be true.\ - Often have two parts; conditions and conclusion. **LEMMA\ **- a simple theorem used as an intermediate result in the proof of another theorem. **COROLLARY\ ** - a proposition that follows directly from a theorem that has been proved. **CONJECTURE**\ - a statement whose truth value is unknown. Once it is proven, it becomes a theorem. **CORRECT PROOF (DEDUCTIVE)**\ - if the conditions are true then the conclusion is true.\ - example: Condition → Conclusion is a tautology **ARGUMENT\ **- often there are missing pieces between conditions and conclusion. **SET THEORY** **SET\ **- collection of objects (called elements).\ - Order of elements is insignificant.\ - it does not matter how often the same element is listed (repetition doesn't count). **SET EQUALITY\ **- set A and B are equal if and only if they contain exactly the same elements. **EXAMPLE FOR SETS -- "STANDARD" SETS:\ **- NATURAL NUMBERS N = {0, 1, 2, 3,...}\ - INTEGERS Z = {..., -2, -1, 0, 1, 2,...}\ - POSITIVE INTEGERS Z^+^ = {1, 2, 3, 4,...}\ - REAL NUMBERS R = {47.30, π,...}\ - RATIONAL NUMBERS Q = {1.5, 2.6, -3.8,...} **SUBSET\ ** - "A is a subset of B" if and only if every element of A is also an element of B.\ - example: A = {3, 9}, B = {5, 9, 1, 3} **TRUE** **USEFUL RULES:\ **- A = B ↔ ( A is a subset of B ) \^ ( B is a subset of A )\ - ( A is a subset of B ) \^ ( B is a subset of C ) → A is a subset of C (see Venn Diagram) **\ **