COMPSCI 225 Flashcards

Propositions

• A proposition is a statement that can be classified as either true or false.
• Simple propositions are indivisible and cannot be broken down into smaller propositions.
• Compound propositions result from combining two or more propositions using logical connectives.

Connectives

• Connectives are symbols like "and" (Λ), "or" (V), and "implies" (→) that relate propositions.
• Truth tables illustrate how propositions interact under different connectives.

Truth Tables

• The truth table for "and" (Λ) shows that it is only true when both propositions are true.
• The truth table for "or" (V) indicates it is true when at least one proposition is true.
• The "implies" (→) truth table showcases a false result only when the first proposition is true and the second is false.
• "If and only if" (↔) shows equivalency, being true only when both propositions share the same truth value.

Types of Propositions

• A tautology is a proposition that is always true.
• A contradiction is a proposition that is always false.
• A contingent proposition can vary between true and false based on its components.

Logical Relationships

• Logical Equivalence occurs if two propositions yield the same truth value across all scenarios.
• Logical Implication denotes that if one proposition is true, the other must also be true if their implication form is a tautology.

Theorems and Proofs

• A theorem is a proposition that has been proven as true under specified conditions.
• A hypothesis is a starting assumption for reaching a conclusion in logical reasoning.
• Proofs can take various forms, including direct proof, proof by contradiction, proof by construction, and proof by induction.

Mathematical Structures

• Natural Numbers (N) encompass all non-negative integers starting from 0.
• Integers (Z) comprise all whole numbers, both positive and negative.
• Prime numbers are whole numbers with exactly two distinct positive factors: 1 and themselves.

Algorithms and Correctness

• An algorithm is deemed correct if it successfully terminates and fulfills its purpose.
• The Euclidean Algorithm helps determine the greatest common divisor (gcd) of two integers through iterative division.

Graph Theory Basics

• A graph consists of vertices (nodes) and edges (connections between nodes).
• Simple graphs do not include multiple edges or loops, while multigraphs may allow multiple edges between the same vertices.
• Directed graphs have edges with direction, whereas undirected graphs treat edges as bidirectional.

Special Graphs

• A complete graph is one where every vertex is connected to every other vertex.
• A bipartite graph contains two distinct sets of vertices with edges only connecting between these sets.
• The handshaking theorem states that the sum of degrees of all vertices is twice the number of edges in the graph.

Euler and Hamiltonian Paths

• An Euler path visits every edge exactly once; an Euler circuit returns to the start vertex.
• A Hamiltonian path visits every vertex exactly once, while a Hamiltonian circuit does so, returning to the starting point.

Set Theory Concepts

• A set is an unordered collection of distinct elements, while an ordered tuple maintains element order.
• The power set of a set includes all possible subsets, with a size of 2^n, where n is the number of elements in the original set.

Relations and Properties

• A binary relation is a subset of the Cartesian product of two sets, defining relationships between elements.
• Reflexivity, symmetry, and transitivity are properties important for classifying relations.
• An equivalence relation is reflexive, symmetric, and transitive, leading to the notion of equivalence classes.

Partitions and Orderings

• A partition of a set divides it into disjoint subsets that cover all elements without overlap.
• A partial ordering (or poset) is a relation that is reflexive, anti-symmetric, and transitive, enabling a structured hierarchy among elements.