bits.

FREE HISTORICAL FIGURES OF COMPUTING PROFILE

Jan Łukasiewicz

1878–1956 · Logician

Jan Łukasiewicz

Logician and philosopher · 1878–1956 · Poland and Ireland

Łukasiewicz made major contributions to propositional logic, many-valued logic and the history of logic. His prefix notation also gives a particularly clear exercise in representing syntax. The connection to computing becomes stronger when we explain the mechanism and its conditions, rather than claim that all uncertainty-handling software implements his ideas.

Life and chronology

Born on 21 December 1878 in Lwów, then in Austrian Galicia and now Lviv, Ukraine, Łukasiewicz studied under Kazimierz Twardowski. His 1902 doctorate concerned induction as the inverse of deduction, not a dissertation simply titled probability. He taught in Lwów and Warsaw, served as Polish minister of education in 1919, and was a leading figure in the Warsaw school of logic alongside Leśniewski and Tarski. Scholarly biography.

His three-valued logic was published in 1920. The scholarly account dates Polish notation to 1924, rather than the loosely repeated 1917–1920 range. His study of Aristotle's principle of contradiction appeared in 1910, and Aristotle's Syllogistic in 1951. His formal reconstructions are contributions to historical interpretation, not definitive replacements for reading ancient texts in context. Biography, notation history.

War disrupted his work. After leaving Warsaw in 1944 and passing through Germany and Belgium, he arrived in Dublin in 1946 and became professor of mathematical logic at the Royal Irish Academy. He died there on 13 February 1956. The documented itinerary is preferable to invented claims about what all Soviet authorities thought of independent logicians. Career and exile.

Worked mechanism: recovering a tree from prefix notation

In Polish notation, an operator comes before its operands. Let C be binary implication, K binary conjunction and N unary negation. Variables such as p and q are complete formulas. The string CKpqNr has exactly this parse:

C
├── K
│   ├── p
│   └── q
└── N
    └── r

In infix notation it is (p and q) implies (not r). No precedence rule is needed because the arity of each operator tells us how many subexpressions to read. The claim depends on recognizable tokens, known fixed arities and a finite expression. Variable-length names need token boundaries; an operator accepting an unspecified number of operands needs an additional delimiter or count. Formation rules.

Here is an original trace using the open-slot invariant. Start with one slot for the whole expression. Reading a token fills one slot and opens as many new slots as its arity. A variable opens none; N opens one; C and K open two.

Token consumedSlots remaining
Start1
C2
K3
p2
q1
N1
r0

A valid complete expression reaches zero exactly at its end. If input ends with a positive count, an operand is missing. If the count reaches zero while tokens remain, the suffix lies outside the completed expression. This condition checks structure for the stated token grammar; it says nothing about whether the resulting proposition is true.

Postfix notation places each operator after its operands. For a binary operator, pop the right operand first and the left operand second, then push the result. The order matters for subtraction and division. For 8 3 - 2 *, the stacks are [8], [8,3], [5], [5,2], [10]. This is a modern stack-evaluation example, not a claim that Łukasiewicz designed a particular calculator or virtual machine.

Many values require explicit operations

A three-valued logic is not specified by listing three names. We must define the operations and say which values count as designated truth for validity. For Łukasiewicz's three-valued propositional logic Ł3, use values 0, 1/2 and 1, with only 1 designated. In the standard presentation:

not a       = 1 - a
 a implies b = min(1, 1 - a + b)
 a and b     = min(a,b)
 a or b      = max(a,b)

Here “and” and “or” are the lattice conjunction and disjunction. Other derived connectives, including strong conjunction, have different operations; naming them explicitly prevents equivocation. Many-valued systems.

Take p = 1/2. Then not-p = 1/2, so both p or not-p and not (p and not-p) evaluate to 1/2. Neither is a tautology when a tautology must have designated value 1 under every valuation. Yet it is still impossible for p itself to have both numerical values 1 and 0 in one valuation. These are different claims: a formula's validity is not the same as saying a function assigns one value.

By contrast, p implies p evaluates to min(1, 1 - p + p) = 1 for all three values. At the middle value the Ł3 conditional therefore differs from the expression not-p or p, which evaluates to 1/2. In classical two-valued logic those expressions agree, but that equivalence cannot simply be imported.

SQL, probability and historical limits

SQL implementations use a third logical outcome, unknown, for many comparisons involving NULL. PostgreSQL's documentation gives the AND, OR and NOT tables. If unknown is represented by 1/2, those tables match the lattice operations just displayed. But implementing implication as NOT a OR b gives unknown when both arguments are unknown; Ł3 implication gives 1. SQL's logical behavior therefore is not simply the whole of Ł3. Official truth tables.

A truth degree is also not automatically a probability. Suppose two events each have probability 1/2. Their conjunction has probability 1/4 if they are independent, 1/2 if they are the same event, and 0 if they are complementary. Marginal probabilities alone do not determine the conjunction. A truth-functional operation, by contrast, computes its output from the input values using its fixed table. Any comparison with probabilistic reasoning must account for this difference.

Earlier thinkers had questioned bivalence, and Emil Post published many-valued work in 1921. Łukasiewicz's achievement should be placed in this history rather than advertised as the first person in 2,300 years to consider alternatives. Shared vocabulary also does not make all modal, quantum, intuitionistic and fuzzy logics instances of one system. Historical overview.

Exercises

  1. Parse C N p K q r and trace its slot counts. Explain precisely why C p and C p q r are invalid as single complete formulas under this grammar.
  2. Evaluate p implies q, not-p or q, and not (p and not-p) when p = q = 1/2. Which are designated? Explain why the original two-valued identity for implication fails.
  3. Convert (9 - 4) × (8 - 6) to prefix and postfix forms. Trace the postfix stack. Then explain why a three-valued truth table alone cannot calculate the probability that two events both occur when their individual probabilities are known.
Compare your reasoning with the worked solutions
  1. The parse is (not p) implies (q and r). Starting from 1, the counts after C, N, p, K, q, r are 2, 2, 1, 2, 1, 0. For C p, one slot remains unfilled, so the second operand is missing. For C p q r, the count reaches zero after q; r is an extra expression outside the completed conditional. Zero at the end alone is insufficient if a prefix has already completed or become invalid.
  2. Ł3 implication is min(1,1 - 1/2 + 1/2) = 1, so it is designated. not-p or q is max(1/2,1/2) = 1/2, not designated. The non-contradiction formula is 1 - min(1/2,1/2) = 1/2, also not designated. A classical equivalence is a fact about particular connective semantics. Changing the table can invalidate it while leaving a consistent, precisely specified alternative logic.
  3. Prefix is * - 9 4 - 8 6; postfix is 9 4 - 8 6 - *. Stack states are [9], [9,4], [5], [5,8], [5,8,6], [5,2], [10]. Reversing the pop order changes subtraction. For probabilities, the missing information is dependence between events. Equal marginals can coexist with different joint probabilities, so no fixed operation on those marginals alone can give the right conjunction probability in every case.

Sources and further study