Probabilistic Logic

Origin. Nils Nilsson introduced probabilistic logic for AI (1986). Combines first-order logic with probability assignments to formulas. Halpern's work on probabilistic reasoning about knowledge (1990s). Markov Logic Networks (Richardson & Domingos, 2006) combine first-order logic and probabilistic graphical models. Multiple traditions: logical, AI, statistical.

Models. Assigning probabilities to logical formulas. Classical logic: formulas are true or false. Probabilistic logic: formulas have probabilities. "P(Flies(x) | Bird(x)) = 0.9" — birds probably fly. Combines logical structure with uncertainty quantification.

Formalism.

Probability on formulas: Given a set of possible worlds W, probability P: W → [0,1] with Σ P(w) = 1. P(φ) = Σ{P(w) : w ⊨ φ}

Probabilistic sentences: w(φ) ≥ r — "probability of φ is at least r" w(φ) = r — "probability of φ is exactly r"

Nilsson's probabilistic logic:

• Logical constraints (FOL sentences)
• Probabilistic constraints: linear inequalities on P(φᵢ)
• Entailment: determine bounds on query probabilities

Example: Given: P(Bird) = 0.3, P(Flies|Bird) = 0.9, P(Flies|¬Bird) = 0.01 Query: P(Bird|Flies) = ? (Bayes' theorem applies)

Markov Logic Networks (MLNs): First-order formulas as soft constraints with weights.

• Formula φᵢ with weight wᵢ
• Probability of world: P(w) ∝ exp(Σᵢ wᵢ · nᵢ(w)) where nᵢ(w) = number of true groundings of φᵢ in w

Hard constraint: infinite weight (must be satisfied). Soft constraint: finite weight (preference, not requirement).

Inference:

• MAP inference: find most probable world
• Marginal inference: compute P(φ)
• Weight learning: learn wᵢ from data

Probabilistic databases: Tuples with probabilities; query answering under uncertainty.

Symbols.

Metatheory. Nilsson's entailment problem is a linear program over the 2ⁿ world probabilities, and the decision version — probabilistic satisfiability, PSAT — was shown NP-complete by Georgakopoulos, Kavvadias and Papadimitriou (1988); membership is not obvious, since the natural witness is exponential, and follows from the fact that a feasible linear system has a basic feasible solution with support bounded by the number of constraints, so a small model suffices. Fagin, Halpern and Megiddo (1990) gave a propositional logic of linear inequalities over probabilities together with a sound and complete axiomatization and the same small-model property, which yields NP-completeness for that language too. The first-order case is far worse: Abadi and Halpern (1994) proved the validity problem for first-order logics of probability to be Π²₁-complete, hence not merely undecidable but outside the arithmetical hierarchy, for probabilities on the domain and on possible worlds alike. Halpern (1990) had already separated the two readings — statistical probability over a domain from degree of belief over worlds — as distinct logics with distinct properties.

Applies to. Uncertain reasoning in AI. Knowledge base uncertainty. Statistical relational learning. Information extraction. Social network analysis. Natural language understanding. Combining logic and machine learning.

Limitations. Probability is not truth-functional: P(φ ∧ ψ) is not a function of P(φ) and P(ψ), so probabilistic logic is not a many-valued logic and no truth table computes it. Nilsson entailment returns an interval, and the interval is frequently the whole of [0,1] — chaining even two uncertain conditionals gives vacuous bounds unless independence is stipulated, which the framework has no way to express. Adding a connective for the conditional is blocked outright: Lewis's triviality result rules out a binary → with P(φ → ψ) = P(ψ|φ) for all probability functions in a nontrivial algebra. Classical closure fails to transfer to belief: the lottery and preface paradoxes show that high probability is not closed under conjunction, so no threshold turns the logic into a consequence relation on accepted sentences. Markov logic networks require a finite domain to ground into a well-defined distribution, and different Herbrand domains give different probabilities for the same formulas.

© 2026 Lingenic LLC