Lauselogikassa

Lauselogikassa, or propositional logic, is a formal system for analyzing the truth-functional relationships between propositions. It provides a language to express what follows from given statements and to evaluate the truth of complex statements.

Syntax: A proposition is an atomic statement represented by a symbol (p, q, r, …). Built formulas use connectives such as negation (not), conjunction (and), disjunction (or), implication (if... then), and biconditional (if and only if). Formulas are formed recursively with parentheses to indicate structure.

Semantics: A valuation assigns truth values to atomic propositions. Each connective has a truth table; the value of any formula is determined by the valuation. A formula is satisfiable if there exists a valuation making it true; valid if it is true under all valuations; two formulas are logically equivalent if they share truth values under all valuations.

Proof and inference: To derive conclusions, one uses rules of inference or a Hilbert-style or natural deduction system. Modus ponens—from p and p → q infer q—is central. Theorems include tautologies such as p → p. The semantic notions of soundness and completeness connect proofs to truth.

Computational aspects: Propositional logic is decidable. Truth-table methods provide a straightforward decision procedure. The satisfiability problem (SAT) is NP-complete, and tautology checking is co-NP-complete. In practice, conjunctive normal form (CNF) and resolution, or modern SAT solvers, are widely used for automated reasoning.

Applications and history: Propositional logic underpins computer science, digital circuit design, formal verification, and artificial intelligence. Its modern development began in the 19th and 20th centuries, with foundational work by Frege, and later by Russell and Whitehead in Principia Mathematica, among others, solidifying its syntax, semantics, and proof theory.