propositional logic
In plain wordsThe simplest formal logic: whole statements that are either true or false, joined by 'and', 'or', 'not' and 'if… then', with exact rules for working out whether the combination is true.
A formal logic whose atomic formulas are propositional variables (p, q, r…), each standing for a whole statement that is true or false, combined with connectives such as ¬ (not), ∧ (and), ∨ (or), → (implies) and ↔ (if and only if). Truth tables fix the meaning: an assignment of truth values to the variables determines the value of every formula. A formula is satisfiable if some assignment makes it true and valid (a tautology) if every assignment does. Unlike first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI., it has no quantifiers and no internal structure within statements, so 'every bird flies' can be expressed only by listing cases; in exchange, validity is decidable, although deciding satisfiability is the canonical NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all. problem, SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.. It underlies digital circuit design, SAT-based verification and planning as satisfiability.
Origin
Truth-functional reasoning with connectives goes back to the Stoic logicians, notably Chrysippus in the 3rd century BCE. George Boole algebraized it in The Mathematical Analysis of Logic (1847) and The Laws of Thought (1854); Frege axiomatized it in 1879, and Emil Post and Ludwig Wittgenstein made truth tables explicit in 1921.
Related
- first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI.
- Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.
- resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known.
- Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.
- fuzzy logicfuzzy logic, n.: A kind of logic that allows degrees of truth, so a statement like 'the room is warm' can be 70 percent true, which helps machines handle vague everyday categories.
- first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI.
- fuzzy logicfuzzy logic, n.: A kind of logic that allows degrees of truth, so a statement like 'the room is warm' can be 70 percent true, which helps machines handle vague everyday categories.
Sources
- Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly, London.
- Post, E. L. (1921). Introduction to a General Theory of Elementary Propositions. American Journal of Mathematics 43(3), 163–185.
Mentioned in
Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., first-order logicfirst-order logic, n.: A precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI., fuzzy logicfuzzy logic, n.: A kind of logic that allows degrees of truth, so a statement like 'the room is warm' can be 70 percent true, which helps machines handle vague everyday categories., Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.