aiwiki.page
English

Discrete Math & Logic

150 entriesPage 1 of 3
Adjacency Matrix

An adjacency matrix represents a graph by recording connections between ordered pairs of vertices, enabling algebraic analysis of its structure and efficient computation of network properties.

adjacency-matrix
Alfred Tarski

Alfred Tarski was a Polish-American logician and mathematician whose work transformed truth theory, model theory, algebraic logic, and the foundations of geometry.

alfred-tarski
Algebra of Sets

The algebra of sets studies set operations and their identities, and the families of sets closed under finite unions and complements.

algebra-of-sets
Alonzo Church

Alonzo Church was an American logician whose work on lambda calculus, undecidability, and effective computation helped establish the foundations of theoretical computer science.

alonzo-church
Antisymmetric Relation

An antisymmetric relation is a binary relation in which two elements can be related in both directions only if they are equal.

antisymmetric-relation
Augustus De Morgan

Augustus De Morgan was a British mathematician, logician, and educator whose work helped establish modern symbolic logic and the study of relations.

augustus-de-morgan
Axiom

An axiom is a statement accepted as a starting assumption within a theory, from which other statements are derived using rules of inference.

axiom
Axiom of Choice

The axiom of choice asserts that every set-indexed family of nonempty sets admits a function selecting one element from each member.

axiom-of-choice
Axiom Schema

An axiom schema is a formal template specifying a family of axioms through permitted substitutions, often providing a finite description of infinitely many statements.

axiom-schema
Barber Paradox

The barber paradox describes a barber who shaves exactly those people who do not shave themselves, yielding a contradiction when the rule is applied to the barber.

barber-paradox
Bell Number

A Bell number counts the ways to partition a finite set into nonempty, unordered blocks, forming a fundamental sequence in combinatorics.

bell-number
Binary Relation

A binary relation is a set of ordered pairs specifying which elements of one set are related to elements of another.

binary-relation
Binomial Coefficient

A binomial coefficient counts unordered selections of a fixed size from a set and gives a coefficient in the expansion of a binomial power.

binomial-coefficient
Boolean Algebra

Boolean algebra studies operations on truth values and complemented distributive structures, providing a mathematical foundation for classical logic and digital circuits.

boolean-algebra
Boolean Function

A Boolean function maps binary inputs to a binary output and provides a mathematical foundation for logic, digital computation, complexity theory, and cryptography.

boolean-function
Brouwer–Heyting–Kolmogorov Interpretation

An explanation of intuitionistic logic in which propositions specify constructions and proofs supply the corresponding constructive evidence.

bhk-interpretation
Calculus of Inductive Constructions

The Calculus of Inductive Constructions is a dependent type theory combining higher-order functions, inductive definitions, and a propositions-as-types interpretation of proofs.

calculus-of-inductive-constructions
Cantor’s Diagonal Argument

Cantor’s diagonal argument constructs an object missing from any proposed enumeration, proving that infinite sets can have different cardinalities.

cantors-diagonal-argument
Cantor's Theorem

Cantor’s theorem states that every set has strictly smaller cardinality than its power set, establishing that there is no largest size of infinity.

cantors-theorem
Cardinality

Cardinality measures the size of a set through one-to-one correspondence, extending ordinary counting to distinguish different sizes of infinity.

cardinality
Cartesian Product

The Cartesian product forms a set of ordered combinations by taking one element from each of several sets.

cartesian-product
Catalan Number

Catalan numbers form an integer sequence that counts many recursively structured objects, including balanced parentheses, binary trees, polygon triangulations, and noncrossing partitions.

catalan-number
Combinatorics

Combinatorics studies discrete structures, their enumeration, existence, properties, and optimal arrangements.

combinatorics
Compactness Theorem

The compactness theorem states that a set of first-order sentences has a model exactly when every finite subset has a model.

compactness-theorem
Conjecture

A conjecture is a mathematical statement proposed as true but not yet established by an accepted proof.

conjecture
Conjunctive Normal Form

Conjunctive normal form expresses a logical formula as an AND of clauses, each an OR of literals, and is fundamental to automated reasoning and satisfiability solving.

conjunctive-normal-form
Continuum Hypothesis

The continuum hypothesis asserts that no infinite cardinality lies strictly between those of the natural numbers and the real numbers.

continuum-hypothesis
Contradiction (Logic)

A contradiction is a formula that is false under every classical interpretation, or, more narrowly, a statement conjoined with its own negation.

contradiction-logic
Contraposition

Contraposition replaces an implication with one that reverses and negates its antecedent and consequent; the two are equivalent in classical logic.

contraposition
Corollary

A corollary is a mathematical result presented as a direct consequence of an established theorem or other previously proved results.

corollary
Countable Set

A countable set is a finite set or an infinite set whose elements can be put in one-to-one correspondence with the natural numbers.

countable-set
Curry–Howard Correspondence

A structural relationship between logical propositions and types, proofs and programs, and proof simplification and computation.

curry-howard-correspondence
David Hilbert

David Hilbert was a German mathematician whose work shaped modern algebra, geometry, analysis, mathematical physics, and the foundations of mathematics.

david-hilbert
De Morgan’s Laws

De Morgan’s laws describe how negation interchanges conjunction and disjunction, with corresponding identities for sets and quantified statements.

de-morgans-laws
Degree (Graph Theory)

The degree of a vertex counts its incident edge ends, providing a basic measure of local connectivity and a foundation for many graph-theoretic results.

vertex-degree
Directed acyclic graph

A directed acyclic graph is a graph with directed edges and no directed cycles, used to represent ordered dependencies and probabilistic relationships.

directed-acyclic-graph
Directed Graph

A graph whose edges have a direction, representing ordered connections between vertices.

directed-graph
Disjoint Union

A disjoint union combines sets while preserving each element’s source, using tags when necessary to keep overlapping elements distinct.

disjoint-union
Disjunctive Normal Form

Disjunctive normal form expresses a Boolean formula as a disjunction of conjunctions of literals, providing a standard representation for logical analysis and digital circuit design.

disjunctive-normal-form
Double-Negation Elimination

Double-negation elimination is the classical logical principle that a proposition follows from the negation of its negation.

double-negation-elimination
Empty Set

The empty set is the unique set containing no elements, fundamental to set theory, logic, and mathematical constructions.

empty-set
Entscheidungsproblem

The Entscheidungsproblem asks for an algorithm deciding first-order logical validity; Church and Turing proved in 1936 that no such algorithm exists.

entscheidungsproblem
Equivalence Class

An equivalence class is the set of all elements equivalent to a given element under a specified equivalence relation.

equivalence-class
Equivalence Relation

An equivalence relation is a reflexive, symmetric, and transitive relation that partitions a set into classes of mutually equivalent elements.

equivalence-relation
Eulerian Trail

An Eulerian trail traverses every edge of a graph exactly once; its existence is characterized by connectivity and vertex-degree conditions.

eulerian-trail
Exclusive OR

Exclusive OR is a logical operation that is true when exactly one of two inputs is true, equivalent to addition modulo two.

exclusive-or
Factorial

The factorial of a nonnegative integer is the product of all positive integers up to it, with zero factorial defined as one.

factorial
Fibonacci Sequence

An integer sequence in which each term is the sum of the preceding two, linking recurrence relations, counting problems, and the golden ratio.

fibonacci-sequence
Finite Set

A finite set is a set whose elements can be counted by a nonnegative integer, including zero for the empty set.

finite-set
First-Order Logic

A formal system for expressing properties, relations, and quantified statements about objects, with precise rules for interpretation and deduction.

first-order-logic
Formal Proof

A formal proof is a derivation whose statements and inference steps obey explicitly specified rules within a formal system.

formal-proof
Formal System

A formal system specifies a symbolic language and explicit rules for deriving conclusions from axioms or assumptions.

formal-system
Free Variable

A free variable is a variable occurrence not governed by a binding operator; in linear algebra, it is an unknown that can be chosen as a solution parameter.

free-variable
Generating Function

A generating function encodes a sequence as coefficients of a series, enabling algebraic and analytic methods to solve counting problems, recurrences, and probability calculations.

generating-function
Georg Cantor

Georg Cantor founded modern set theory, established different sizes of infinity, and developed the arithmetic of transfinite numbers.

georg-cantor
George Boole

George Boole was an English mathematician whose algebraic treatment of logic helped establish mathematical logic and the foundations of digital computation.

george-boole
Gerhard Gentzen

Gerhard Gentzen was a German mathematician who founded structural proof theory, introduced natural deduction and sequent calculus, and proved the consistency of arithmetic using transfinite induction.

gerhard-gentzen
Giuseppe Peano

Giuseppe Peano was an Italian mathematician whose work on arithmetic, symbolic logic, analysis, and mathematical notation helped shape modern mathematics.

giuseppe-peano
Gödel Numbering

Gödel numbering encodes formal expressions and proofs as natural numbers, allowing arithmetic to express statements about syntax, computation, and provability.

godel-numbering
Gödel's Completeness Theorem

A foundational theorem establishing that every semantic consequence in classical first-order logic has a formal proof.

godels-completeness-theorem