不同签名下逻辑蕴涵Γ⊨φ的判定方法技术问询

Great question! This is a common point of confusion when working with propositional logic entailment, so let's break it down clearly with definitions and your example.

Key Background: Extending Interpretations #

First, let's clarify how to handle interpretations that don't cover all symbols in the target formula φ:

• A propositional interpretation for signature σ is a function mapping σ to {T, F}. But when Γ uses a signature σ₁ that's a proper subset of φ's signature σ₂, we need to consider all possible extensions of σ₁-interpretations to the full signature σ₁∪σ₂.
• For any interpretation I that satisfies Γ (i.e., I makes all formulas in Γ true), we can extend I to a new interpretation I' that assigns truth values to every symbol in σ₂. The extra symbols (like q in your example) can get either T or F—we have to account for all possible assignments to these "new" symbols.

Applying the Entailment Definition #

Recall the formal definition:

Γ⊨φ if and only if every interpretation that satisfies all formulas in Γ also satisfies φ.

When signatures are subsets, this translates to:

Every extension of a Γ-satisfying interpretation (to cover φ's full signature) must satisfy φ. If even one extension fails to satisfy φ, then Γ does not entail φ.

Your Example: {p} ⊨ p∧q? #

Let's walk through this step by step:

1. Γ's signature is {p}, φ's signature is {p,q}. We need to look at all interpretations over {p,q}:
   • Interpretation 1: p=T, q=T → satisfies Γ (p is true), and satisfies p∧q (T∧T=T)
   • Interpretation 2: p=T, q=F → satisfies Γ (p is true), but does not satisfy p∧q (T∧F=F)
   • Interpretations where p=F: These don't satisfy Γ, so we can ignore them.
2. Since there exists an interpretation that satisfies Γ but not φ (the second one), {p} does NOT entail p∧q.

General Decision Procedure #

To determine Γ⊨φ when Γ's signature is a proper subset of φ's:

• Step 1: Combine the signatures of Γ and φ into a single full signature σ = σ₁ ∪ σ₂.
• Step 2: Either:
  • Enumerate all interpretations over σ, filter those that satisfy Γ, then check if every filtered interpretation satisfies φ; OR
  • Use logical equivalence: Γ⊨φ is equivalent to the formula (∧Γ) → φ being a tautology (true under all interpretations). If this formula isn't a tautology, Γ does not entail φ.

For your example, p → (p∧q) simplifies to ¬p ∨ q, which is clearly not a tautology (it's false when p=T and q=F)—confirming our earlier conclusion.

内容的提问来源于stack exchange，提问作者Nuttywhal