Classical logic combines truth-valued propositions using defined connectives.
Key knowledge
In classical two-valued logic a proposition is true or false. Negation reverses its truth value; a conjunction is true when both parts are true, an inclusive disjunction when at least one is true, and an implication is false only when its antecedent is true and consequent false.
Conditions and scope
These are classical truth-functional meanings; other logical systems use different semantics.
Logical implication alone does not assert physical causation.
Sources · 3
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Two-valued proposition and connective definitions.
2026-10-10 · Checked truth conditions and inclusive-or convention.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Agreement within this scope
Classical negation, conjunction, inclusive disjunction and material implication.
The inspected truth table agrees; other logical semantics are outside this comparison.
A claim that P(x) holds for every x in a specified domain is false if an element of that domain makes P(x) false. Testing some successful examples does not establish the claim for an infinite domain.
Axioms are assumptions accepted within a mathematical system. A proof derives a proposition from those assumptions and previously established results through permitted logical deductions.
In classical first-order logic, ∀x φ holds when φ holds for every domain element; ∃x φ holds when it holds for at least one. Free variables require an assignment.
For a 3CNF formula with m clauses, make a vertex for each literal occurrence. Join occurrences from different clauses unless their literals are complementary. The formula is satisfiable exactly when the graph has a clique of size m: choose one true occurrence per clause; conversely the clique's consistent literals extend to an assignment.
A DFA's language is empty iff no accepting state is reachable from its start. Two DFAs are equivalent iff their product automaton's symmetric-difference language is empty. Product-state accepting rules also construct regular intersections and unions; swapping accepting/nonaccepting states complements a complete DFA.
NL=coNL: complements of nondeterministic logspace decision languages also lie in NL. The reachability proof certifies counts of reachable vertices, making nonreachability testable with nondeterministic logarithmic workspace.
Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions. For each language A∈NP and input x, a polynomial-size formula encodes a polynomial-time accepting computation tableau so that x∈A exactly when that formula is satisfiable; a satisfying assignment itself supplies the NP witness.
Introduce variables for Boolean subformula gates, constrain each gate to agree with its inputs using clauses of at most three literals, and require the output gate true. This constructs a linear-size equisatisfiable 3CNF formula, showing SAT≤ₚ3SAT and therefore 3SAT is NP-complete.
AND returns 1 exactly when both inputs are 1; inclusive OR returns 1 when at least one is 1; NOT exchanges 0 and 1. Two-input XOR returns 1 exactly when inputs differ. A truth table specifies every input combination; AND, OR and NOT suffice to express any finite-input Boolean function.
Boolean gate AND, inclusive OR and NOT implement conjunction, disjunction and negation on truth values.