Logic and Set Theory Prelim Reviewer PDF

Logic and Set Theory Prelim Reviewer 2SEDM-A Logic - study of reasoning and the principles that guide  5. IF AND ONLY IF (Bi-conditional) ↔ sound thinking. It is a fundamental branch of - both propositions m...

Logic and Set Theory Prelim Reviewer 2SEDM-A Logic - study of reasoning and the principles that guide  5. IF AND ONLY IF (Bi-conditional) ↔ sound thinking. It is a fundamental branch of - both propositions must have the same truth value for philosophy, mathematics, and computer science that the whole statement to be true. helps us understand how to construct valid arguments, p q p↔q identify fallacies, and solve problems systematically. T T T Key Aspects of Logic: T F F 1. Propositions: a statement that can be either true F T F or false. F F T 2. Arguments: consists of premises and a conclusion.  6. EXCLUSIVE OR ⊕ The premises are statements that provide support - ~ Bi-conditional for the conclusion. A valid argument is one where, p p p q if the premises are true, the conclusion must be T T F true. T F T 3. Deductive and Inductive Reasoning: F T T  Deductive Reasoning: Involves drawing specific conclusions from general premises. If the premises F F F are true, the conclusion must be true. For example, "All humans are mortal. Socrates is human. Truth Value - Value assigned to logical statement (T,F) Therefore, Socrates is mortal." Truth Table - Tool used to display the truth value. It  Inductive Reasoning: Involves making shows the possible combination of truth values. generalizations based on specific observations. The conclusion is probable but not guaranteed. For Truth tables work with existence, qualification and example, "The sun has risen every day in recorded validation conditions. history. Therefore, the sun will rise tomorrow." 4. Fallacies: These are errors in reasoning that 1. Existence Condition - requires that a particular undermine the logic of an argument. statement or set of statements is true for the - Common fallacies include: proposition to hold.  Ad Hominem: Attacking the person making the - Example: Let's define the following propositions: argument rather than the argument itself. P: "A solution exists for the equation."  Straw Man: Misrepresenting an opponent's Q: "The solution is positive." argument to make it easier to attack. R: "The solution satisfies all conditions."  False Dilemma: Presenting only two options when - We'll examine the statement: (P∧Q) →R, which means more are available. "If a solution exists and is positive, then the solution 5. Sentential connectives, also known as logical satisfies all conditions. connectives, are operators used in logic to connect propositions (sentences) and form more complex - Truth Table: statements.  1. AND (Conjunction) ∧ P Q R P∧Q (P ∧ Q) → R - true only when both p and q are true, otherwise false. T T T T T  2. OR (Disjunction) V T T F T F - false only when both p and q are false, otherwise true. T F T F T  3. NOT (Negation) ¬ ~ T F F F T - Negates the truth value of a statement F T T F T  4. IF...THEN (Implication) → F T F F T - p → q is true, unless p is true and q is false. F F T F T F F F F T p q p→q T T T - Explanation: The table shows that if both (existence) T F F and Q (qualification as positive) are true, then R F T T (validation of conditions) must be true for the entire F F T implication to hold. K.D.A. Logic and Set Theory Prelim Reviewer 2SEDM-A 2. 2. Qualification Condition - require a certain attribute or property to be true for a proposition to be valid. - Example: Let's define the following propositions: P: "The number is an integer." Q: "The number is greater than 0." R: "The number is even." - We'll examine the statement: (P∧Q) →R, which means "If the number is an integer and greater than 0, then the number is even." - Truth Table: P Q R P ∧Q (P ∧ Q) → R T T T T T T T F T F T F T F T T F F F T F T T F T F T F F T F F T F T F F F F T - Explanation: The implication (P Q) →R is only false when both P and Q are true, but R is false, meaning that if the number qualifies as a positive integer, it must also be even for the statement to hold. 3. Validation Condition - often refers to verifying whether a certain condition is satisfied. - Example: Let's define the following propositions: P: "The user submits the form." Q: "All required fields are filled." R: "The submission is valid." - We'll examine the statement: (P∧Q)→R, which means "If the user submits the form and all required fields are filled, then the submission is valid." - Truth Table: Week 4: Cantor’s Algebra of Sets P Q R P ∧Q (P ∧ Q) → R T T T T T Georg Ferdinand Ludwig Cantor was a pioneering T T F T F mathematician born on March 3, 1845, in Saint T F T F T Petersburg, Russia, into a well-to-do family of German T F F F T descent. F T T F T F T F F T F F T F T F F F F T - Explanation: The table illustrates that if both the form is submitted P and all required fields are filled Q, then the submission must be valid R for the entire argument to hold. The implication is false only when the form is submitted, all fields are filled, but the submission is still not valid. K.D.A. Logic and Set Theory Prelim Reviewer 2SEDM-A K.D.A. Logic and Set Theory Prelim Reviewer 2SEDM-A Week 5: Zermelo-Fraenkel Axioms (ZF) The Zermelo-Fraenkel axioms are a collection of axioms that define the properties and behavior of sets. They were developed by Ernst Zermelo and later expanded by Abraham Fraenkel. The axioms address issues like the existence of sets, how sets relate to each other, and how sets can be constructed. The axioms are: 1. Axiom of Extensionality: Two sets are equal if they have the same elements. ∀A ∀B (∀x (x ∈ A ⟺x ∈ B) ⟹A = B) 2. Axiom of Regularity (Foundation): Every non-empty set A contains an element that is disjoint from AAA. This prevents sets from containing themselves directly or indirectly. ∀A (A ≠ ∅ ⟹∃ B ∈ A (A ∩ B = ∅)) 3. Axiom of Pairing: For any two sets A and B, there exists a set {A,B} that contains exactly A and B as elements. ∀A ∀B ∃ C ∀D (D ∈ C ⟺D = A∨ D = B) 4. Axiom of Union: For any set A, there is a set that contains all elements that are members of A. ∀A ∃B ∀C (C ∈ B ⟺∃D∈A (C ∈ D)) 5. Axiom of Infinity: There exists a set that contains the empty set and is closed under the operation of taking the successor, which essentially allows the construction of the natural numbers. ∃A (∅∈A∧∀x (x ∈ A ⟹x ∪{x}∈A)) 6. Axiom of Power Set: For any set A, there exists a set containing all possible subsets of A. ∀A ∃B ∀C (C⊆A ⟹C∈B) 7. Axiom of Replacement: If AAA is a set and for every in A x ∈A, there is a unique y such that a property ϕ(x, y) holds, then there exists a set containing all such y. ∀A ∀ x ∈A ∃!y ϕ(x,y) ⟹∃B ∀y (y ∈ B ⟺∃ x ∈A ϕ(x, y)) 8. Axiom of Specification (Separation): For any set A and any property P definable in the language of set theory, there is a set containing exactly those elements of A for which P holds. ∀A ∃B ∀x (x ∈ B ⟺x ∈A ∧ P(x)) K.D.A. Logic and Set Theory Prelim Reviewer 2SEDM-A 9. Axiom of Choice: For any set AAA of non-empty sets, there exists a choice function f that selects one element from each set in A. ∀A (∅∉A ⟹∃f: A→⋃A ∀X∈A (f(X)∈X)) This axiom is sometimes added to ZF to form ZFC. The empty set, denoted as ∅, is the set that contains no elements. It is unique in the sense that no matter how you try to define a set with no elements, you will always get the empty set. Its existence is guaranteed by the Axiom of Infinity, which implies the existence of a set containing the empty set. The power set of a set A, denoted P(A), is the set of all subsets of A, including the empty set and A itself. For example, if A = {1,2}, then the power set of A is: P(A)={∅,{1},{2},{1,2}} The Axiom of Power Set ensures that for any set AAA, the set of all its subsets exists as a set. K.D.A.