Concept

Tautology

A formula that is true under every assignment of truth values to its letters. It is checked by a truth table in classical logic, and intuitionistic logic accepts only some of them as provable, though every one survives double negation.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled.

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

logic · Truth functions

Excluded middle fails at one point, and its double negation does not. Open sets of the real line as truth values: p = (0, ∞), ¬p = (−∞, 0), p ∨ ¬p misses 0, ¬(p ∨ ¬p) is empty and ¬¬(p ∨ ¬p) is the whole line.

Every tautology survives double negation

Intuitionistic logic refuses excluded middle, Peirce's law and every other classical principle that claims more than can be shown. Glivenko proved in 1929 that it refuses nothing outright: put ¬¬ in front of any classical tautology and the result is intuitionistically valid. Every Kripke model of up to four states confirms it for eight famous laws, a census of 11,451 formulas confirms it one by one, and a model with a growing domain shows where it stops.

logic · Non classical logic

Named alongside it

The objects these essays reach for when they reach for this one.

Assignment Connective Double negation Excluded middle Exhaustive search Hypercube Intuitionistic logic Kripke model Normal form Propositional formula Satisfiability Truth function

All concepts