
3.3 Logic and Uncertainty 3.3.1 Natural Language to Logic: Formalization and Solving
Paper example, Figure 2: order three vehicles by age.
A tractor, a convertible and a minivan have distinct age ranks.
The tractor ranks second-newest.
The minivan is newer than the convertible.
Question: Which vehicle is oldest?
Core idea: the LLM specifies variables and constraints.
A symbolic solver searches for assignments satisfying them.

The LLM uses in-context examples to generate task-specific symbols and constraints.
The CSP solver (python-constraint) returns
c=1,\quad t=2,\quad m=3.
Map rank 1 back to the answer:
the convertible is oldest.
| Step | Information passed to the next component |
|---|---|
| Execute | Send the generated formalization to its solver |
| On execution error | Return the faulty form, the error message and repair demonstrations to the LLM |
| Revise and retry | Generate a revised formalization and run the solver again |
| Stop | No execution error, or the revision limit is reached |
Paper example of an error class: an FOL variable has no binding quantifier.
Self-refinement repairs generated text at inference time.
Successful execution still requires a separate check of semantic fidelity.
GPT-4 accuracy (%) · original Table 2 · no self-refinement
| Dataset | CoT | Logic-LM | Δ pp |
|---|---|---|---|
| PrOntoQA | 98.79 | 83.20 | −15.59 |
| ProofWriter | 68.11 | 79.66 | +11.55 |
| FOLIO | 70.58 | 78.92 | +8.34 |
| LogicalDeduction | 75.25 | 87.63 | +12.38 |
| AR-LSAT | 35.06 | 43.04 | +7.98 |
Separate refinement analysis (Table 3): GPT-4 FOLIO executable rate 79.9% → 85.8%; accuracy among executable cases 80.4% → 79.9%. These are different metrics.
Every rectangle has four sides.
Anything with four sides is a shape.
Query: Must every rectangle be a shape?
LLM role: translate both premises and the query into first-order logic.
Query:
Prover9 result: True.
The premises entail the query.
CoT asks the LLM to produce the deduction.
LINC assigns semantic parsing to the LLM and deduction to Prover9.

GPT-4 / ProofWriter:
CoT 72.2% → LINC 98.3% (+26.1 pp)
GPT-4 / FOLIO:
CoT 75.3% → LINC 72.5% (−2.8 pp)
FOLIO: 182 retained validation examples; ProofWriter: 360 balanced OWA examples. FOLIO difference is not significant (paper: p=0.58). Different subsets and voting protocols prevent direct comparison with Logic-LM’s table.
| Question | Support supplied by these methods | Remaining requirement |
|---|---|---|
| What does the text mean? | Explicit formulas expose variables, conditions and scope | Check the translation against the source |
| Does the conclusion follow? | A solver checks the formal problem | Valid syntax, consistent premises and sufficient resources |
| Are the premises reliable? | The derivation is conditional on the supplied premises | Evidence about the underlying facts |
Logic-LM and LINC address formalization and deduction.
Noisy observations and rules with exceptions require an uncertainty model.

3.3 Logic and Uncertainty 3.3.2 Uncertain Evidence and Soft Rules



















Markov Random Fields












0
|
0
|
3
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
3
|

0
|
0
|
3/8
|
0
|
1
|
1/8
|
1
|
0
|
1/8
|
1
|
1
|
3/8
|









Markov Logic Networks













“张宁的父亲是李明。” Which Li Ming does the name refer to?
| Candidate | Born | Local belief |
|---|---|---|
| Li Ming A | 1965 | 0.40 |
| Li Ming B | 1998 | 0.60 |
The name and local context favor B.
Zhang Ning is already linked:
born in 1995.
The relation extractor assigns
0.90 to the father relation.
A father should be older than his child.
Conflict: B was born after the child.
Joint inference can revise the link or reject the extracted relation.
Teaching construction inspired by DeepDive-style relational inference; people, dates and numbers are illustrative.
X=1: link to A; X=0: link to B
R=1: the father relation is correct
| Grounding | Fixed age evidence | Simplified formula |
|---|---|---|
| e=A (1965) | \operatorname{Older}(A,\mathrm{child})=\mathrm{true} | R\land X\Rightarrow\mathrm{true}: always true |
| e=B (1998) | \operatorname{Older}(B,\mathrm{child})=\mathrm{false} | R\land\neg X\Rightarrow\mathrm{false}: R\Rightarrow X |
Weight 3: R\Rightarrow X. Penalize accepting the relation while linking to B.
Rejecting the relation leaves either candidate possible.
Teaching model: exactly one of A/B; child identity and birth years are fixed observations.
Use local beliefs to define unary potentials; add one relational factor.
| Evidence / preference | Formula | Weight |
|---|---|---|
| Local P(A)=0.40 | X | \theta_X=\ln\dfrac{0.4}{0.6}\approx-0.405 |
| Local P(R=1)=0.90 | R | \theta_R=\ln\dfrac{0.9}{0.1}\approx2.197 |
| Age consistency | \neg R\lor X | w=3 |
An isolated unary formula gives odds \exp(\theta)=\frac{p}{1-p}.
Once coupled, local inputs and posterior probabilities differ.
E denotes the fixed input evidence. All weights are specified for this demonstration; no learning is performed here.
Equivalent scoring: multiply local potentials, then penalize a violation.
| Link | Relation | Rule | Unnormalized mass m | Posterior |
|---|---|---|---|---|
| B · X=0 | reject · R=0 | satisfied | 0.6\times0.1=0.0600 | 12.32% |
| B · X=0 | accept · R=1 | violated | 0.6\times0.9\times e^{-3}\approx0.0269 | 5.52% |
| A · X=1 | reject · R=0 | satisfied | 0.4\times0.1=0.0400 | 8.22% |
| A · X=1 | accept · R=1 | satisfied | 0.4\times0.9=0.3600 | 73.94% |
Only “B + accept” violates the rule; its mass is multiplied by e^{-3}\approx0.0498.
Exact enumeration of the specified two-variable MLN; displayed probabilities are rounded to two decimal places.
(X^{*},R^{*})=\underset{x,r}{\arg\max}\;P(x,r\mid E)
A + accept the relation
73.94% probability of this world
Commit to both the link and the relation.
P(A\mid E)=\sum_r P(X=1,r\mid E)
8.2155\%+73.9394\%
82.15% total probability of A
Sum over accepting and rejecting the relation.
Relational consistency changes the linking belief.
Remaining uncertainty: P(B\mid E)=17.85\%.
MAP gives a complete assignment; a marginal preserves uncertainty about the other variable.
Sum over both relation states using unrounded probabilities; all numbers come from the specified teaching model.
Keep local P(A)=0.40; vary the rule or the relation evidence.
| Setting | Local P(R=1) | Rule w | Posterior P(A) | Joint MAP |
|---|---|---|---|---|
| No relation coupling | 0.90 | 0 | 40.00% | B + accept |
| Strong relation evidence | 0.90 | 3 | 82.15% | A + accept |
| Weak relation evidence | 0.10 | 3 | 42.42% | B + reject |
Strong relation evidence makes
A + accept more plausible.
Weak relation evidence allows
B + reject to remain most plausible.
MLN combines evidence; it does not force one repair.
We held weights fixed for inference. Learning those weights is a separate step.
Exact inference under three specified settings; finite soft weights allow violations, while hard constraints exclude them.

Probabilistic Soft Logic

Let a = v(A), b = v(B) ∈ [0, 1]. The last column uses a = 0.8, b = 0.6.
| Operation | Truth value | Logical meaning | Ex. |
|---|---|---|---|
| ⊥ Falsity | 0 | Always false. | 0 |
| ⊤ Truth | 1 | Always true. | 1 |
| ¬A Negation | 1 − a | “Not A”: the complement of A’s truth degree. | 0.2 |
| A ⇒ B Implication | min(1, 1 − a + b) | “If A, then B”: fully true when a ≤ b. | 0.8 |
| A ∨ B Weak OR | max(a, b) | “A or B”: take the larger truth degree. | 0.8 |
| A ∧ B Weak AND | min(a, b) | “A and B”: take the smaller truth degree. | 0.6 |
| A ⇔ B Equivalence | 1 − |a − b| | Both implications hold; fully true when a = b. | 0.8 |
| A ⊕ B Strong OR | min(1, a + b) | “A or B”: add truth degrees, capped at 1. | 1 |
| A ⊙ B Strong AND | max(0, a + b − 1) | “A and B”: subtract both shortfalls from 1, floor at 0. | 0.4 |
| A ⊖ B Difference | max(0, a − b) | A ⊙ ¬B: how much A exceeds B; violation of A ⇒ B. | 0.2 |
PSL rule AND/OR use the strong operations ⊙/⊕, usually written ∧/∨ in PSL.
The weak min/max rows are included for comparison; ⊕ here does not mean XOR.

1. Rule truth: A ⇒ B is ¬A ⊕ B, using Łukasiewicz strong OR.
t = v(A ⇒ B) = min(1, (1 − a) + b)
2. Violation is the shortfall from full truth: d = 1 − t.
d = 1 − min(1, 1 − a + b) = max(0, a − b)
a ≤ b: fully satisfied, d = 0.
Example: a = 0.6, b = 0.8 → d = 0.
a > b: penalize the gap, d = a − b.
Example: a = 0.8, b = 0.6 → d = 0.2.
3. Multiple premises: for A ⊙ B ⇒ C, let c = v(C).
L = max(0, a + b − 1), d = max(0, L − c) = max(0, a + b − c − 1)
4. Weighted loss and MAP: φi(x) = di(x)p, minimize Σi wiφi(x).
x ∈ [0, 1]n; observed values fixed. Nonnegative wi, p ∈ {1, 2}, affine hinges
and a convex feasible set give convex MAP inference. Soft truth is not P(B | A).

