CS 240 Midterm 1: - Logico Zybooks: Logic: study of formal reasoning Proposition: statement that is either true or false (can’t be both) - A declarative sentence - Truth value is either known true or false, unknown or opinion Compound proposition: individual propositions with logical operations Exclusive or: true when one is true and the other is false  Precedence of logical operations: - Parenthesis- Negation- Conjunction- Disjunction- Implication - Biconditional  Truth table:- If there a n variables, then there are 2n rows Conditional/Implication: - P  Q, false when P is true and Q false- P is called premise/hypothesis and Q is called consequence/conclusion- English expressions: o Q, if Po Q is necessary for Po P only if Q  Converse: not logically equivalent to initial logical expression - Q  P Contrapositive: still logically equivalent to initial logical expression- Q  P Inverse: not logically equivalent to initial logical expression- P  Q Biconditional/Equivalence: - True when variables have the same truth value - English expressions: o P is necessary and sufficient for Qo If and only if, iffo If P then Q, and conversely  Tautology: if the proposition is always true regardless of the truth values Contradiction: if the proposition is always false regardless of the truth values Logical Equivalence: - two variables are said to be logically equivalent if they have the same truth values regardless of their individual propositions’ truth values De Morgan’s Law: - Logical equivalence that show how to correctly to distribute a negation operation inside a parenthesized expressiono (P Q) ∨ ≅ P ∧ Qo (P Q) ∧ ≅ P ∨ Q Logical Laws: - A B A ∨ ≅  B- (A  B) (B ∧  A) A ↔ B≅- A (A B) A | A (A B) A∨ ∧ ≅ ∧ ∨ ≅- (A (A ∧  B)) T≅- (A B) ∨ ∧ (A ∨ B) ∧ A F≅ Predicate: a logical statement whose truth value is a function of one or more variables - Domain: set of all possible values for a variable in a predicate Universal Quantifier: For every x…- Need to prove all variables are true to prove statement is true- Need only one counterexample to prove statement is wrong Existential Quantifier: There exists a x…- Need only one true variable to prove statement is true- Need to prove all variables are false to prove statement is wrong Quantified Statements: statements constructed with quantifiers and logical operations.  Free variable: a variable that is free to take on any value in the domain of a predicate Bound variable: a variable is bound to a quantifier- A statement with no free variables is a proposition De Morgan’s Law for Quantified Statements:  Nested Quantifiers: logical expression with more than one quantifier that bind different variables in the same predicate De Morgan’s Law for Nested Quantifiers: o Handout: Stable pair: x and y prefer their partners than others Disruptive pair: some x and some y prefer each other to their current partner Axiom: basic fact/underlying assumption that we take for grantedo Discussion: Exclusive OR (XOR) is opposite of biconditional  Biconditional: includes implication and converse of implication- Sets:o Zybooks: Set: is a collection of objects Element: an object in a set  Roster notation: - Depiction of a set by a list of elements enclosed in curly braces and separated by commas Empty set: set with no elements- Aka null set Finite Set: set with finite elements Infinite Set: set with infinite elements Cardinality: number of elements in a set- Cardinality of empty set is 0 Set Builder Notation: - Set is defined by specifying that the set includes all elements in a larger set that also satisfy certain conditions. - Colon “:” means such that- Universal Set: set that contains all elements mentioned in a particular context Subset: - A is a subset of B, if every element in A is in Bo A  B- Note: if not every element of B is in A, then A is a proper subset of Bo A  B Set Equality:- A and B are equal if A is a subset of B and B is a subset of A Intersection operation: - A intersects B: A  B- Set of all elements that are both in set A and set B Union operation: - A union B: A  B- Set of all elements that are elements of set A or set B- Includes elements of intersection set, as union is an inclusive or  Set difference: - A – B- Set of elements that are in A but not in Bo Doesn’t include intersection elements  Symmetric Difference: - A  B = (A – B) U (B – A) - Set of elements that are a member of exactly one of A and B, but not both Complement: -´A: set of all elements in U(universal set) that are not elements of A- this operation requires the universal set (U) to be well-defined - can also be denoted  U – A Ordered Pair: (x, y) - First entry  x- Second entry  y - ()  signifies the order of entries is significant, unlike {} Cartesian Product: - A x B- Set of all ordered pairs in which the first entry is in A and the second entry is in B - A x B is not same as B x A unless A = B - Cardinality of the Cartesian product is the cardinality of set A times cardinality of set Bo |A x B| = |A| * |B| Ordered Triple: (x, y, z) for 3 sets Ordered n-Tuple: (x, y, z, n…) for n sets Cartesian product of a set with itself:  Set Identities: set operations defined as logical operations- An equation involving sets that is true regardless of the contents of the sets in the expression o Similar to logic equivalenceo Simplifying expressions  Power Set: - P(A)- Set of all subsets of A- Cardinality: let A be a finite set with a cardinality of n, then cardinality of P(A)  |P(A)| = 2n Disjoint: when two sets intersection is an empty seto Handout: No duplicate elements are allowed in a set Well defined: for every element of the domain, it can be determined whether the element belongs in the set or not Proper subset is aka strict subset  Countable Set: - A set if countable, if and only if, it is finite, or it is infinite and there is anenumeration consisting exactly of all elements in that set o 1 to 1 correspondence/matching - To show an enumeration is countable: o Given i is a positive integer, find ith element in the enumeration of So Given k is in set S, find what position k shows up in enumeration Uncountable sets: