Set Theory Basics

Sets

• A set is a collection of unique objects, known as elements or members, which can be anything (numbers, words, objects, etc.)
• Ways of describing sets: roster form, set-builder form, and descriptive form
• Kinds of sets: finite, infinite, empty, singleton, and universal sets

Set Operations

• Union: combines elements of two or more sets
• Intersection: includes elements common to two or more sets
• Complement: includes elements not in a set
• Difference: includes elements in one set but not in another
• Cartesian product: combines elements of two sets to form pairs

Venn Diagrams

• Visual representations of sets and their relationships
• Used to illustrate set operations and relationships

Propositions and Logical Statements

• Propositions: statements that can be true or false
• Compound statements: statements composed of two or more propositions
• Truth tables: diagrams used to determine the truth value of compound statements

Logical Equivalences

• Statements that always have the same truth value
• Examples: De Morgan's laws, distributive laws, and associative laws

Predicate Logic

• Predicates: statements that contain variables and can be true or false
• Quantifiers: symbols used to indicate the scope of a predicate (universal, existential)
• Binding variables: variables that are bound to a specific value

Algorithm and Asymptotic Notation

• Algorithm: a step-by-step procedure for solving a problem
• Asymptotic notation: used to describe the time and space complexity of an algorithm (Big O, Omega, Theta)

Integers and Divisibility

• Divisibility: a relation between two integers, where one is divisible by the other
• Division algorithm: a procedure for finding the quotient and remainder of two integers

Sequences and Summation

• Sequence: a list of objects in a specific order
• Summation: the operation of finding the sum of a sequence

Basic Counting Principles

• Fundamentals of counting: permutations, combinations, and the principle of inclusion-exclusion

Matrices

• A rectangular array of numbers, symbols, or expressions
• Used to represent systems of linear equations and perform operations

Relations and Functions

• Relation: a set of ordered pairs
• Function: a relation where each input corresponds to exactly one output

Graph Theory

• Graph: a non-linear data structure consisting of vertices and edges
• Basic terms: vertices, edges, adjacency, incidence, and degree

Trees

• A connected graph with no cycles
• Terminologies: labelled tree, rooted tree, and forest
• Basic properties: height, depth, and level

Formal Grammar and Chomsky Hierarchy

• Formal grammar: a set of rules for generating a language
• Chomsky hierarchy: a classification of formal grammars based on generative power
• Regular languages: languages that can be generated by a regular grammar

Finite Automata

• A mathematical model for recognizing regular languages
• Used to design and implement computer algorithms

Learn about the fundamental concepts of sets, including ways of describing sets, types of sets, and basic set operations like union, intersection, and complement.