Questions & explanations
1. Compare the three logics: Łukasiewicz, Gödel, and product. Give a formula that is valid in one but not the others.
The formula (φ → ψ) ∨ (ψ → φ) is valid in Gödel logic but not in Łukasiewicz or product logic. In Gödel logic, for any two truth values, either φ ≤ ψ or ψ ≤ φ, so one implication is true. In Łukasiewicz, take φ=0.4, ψ=0.6: φ→ψ=1, ψ→φ=0.8, so disjunction is 0.8, not 1. In product, same values: φ→ψ=1, ψ→φ=0.6/0.4=1.5? Actually product implication: if ψ≤φ? 0.6 not ≤0.4, so ψ→φ=0.4/0.6≈0.667, disjunction max=1, so it is 1? Wait, check: φ→ψ=1, ψ→φ=0.667, max=1, so valid? Actually in product, for φ=0.4, ψ=0.6, φ→ψ=1, so disjunction is 1. Need a counterexample: take φ=0.3, ψ=0.5: φ→ψ=1, ψ→φ=0.3/0.5=0.6, max=1. So maybe product also validates? Let's try φ=0.6, ψ=0.3: φ→ψ=0.3/0.6=0.5, ψ→φ=1, max=1. So it seems product also validates? Actually, in product, φ→ψ is 1 if φ≤ψ, else ψ/φ. So if φ≤ψ, first implication is 1; if ψ≤φ, second is 1. So always one implication is 1? Wait, if φ=0.5, ψ=0.5, both implications are 1. So indeed (φ→ψ)∨(ψ→φ) is valid in product as well? Actually, no: if φ=0.5, ψ=0.5, both are 1. So it seems product also validates? But I recall that the formula is valid in Gödel bu
2. If a person is a doctor, they went to medical school. John did not go to medical school. Can we conclude John is not a doctor?
Yes, that is valid. It's called 'denying the antecedent'? Actually, no: denying the antecedent would be 'If doctor then med school. John is not a doctor. Therefore John did not go to med school.' That is invalid. Here we have 'If doctor then med school. John did not go to med school. Therefore John is not a doctor.' That is valid modus tollens. Wait, the question asks about denying the antecedent. Let me correct: The fallacy of denying the antecedent is: If P then Q. Not P. Therefore not Q. Example: If it's a dog, it has fur. It's not a dog. Therefore it has no fur. That's wrong because cats also have fur. So the answer: No, we cannot conclude John is not a doctor from 'If doctor then med school' and 'John did not go to med school'? Actually, that is valid. I need to re-check. The fallacy is: If P then Q. Not P. Therefore not Q. If doctor then med school. Not doctor. Therefore not med school. That is invalid. But here we have not Q, so it's valid. I'll answer the fallacy: Denying the antecedent is the error: If P then Q, not P, therefore not Q. Example: If it's a cat, it's a mammal.
3. Give an example of a formula that is valid in S5 but not in S4.
The formula ◇□P → □◇P is valid in S5 but not in S4. In S5, because the accessibility relation is symmetric, if there is a world where □P holds, then in all accessible worlds, ◇P holds. In S4, without symmetry, this can fail. For instance, consider a frame with worlds w1, w2, w3 where w1 sees w2, w2 sees w3, and no other relations. Let P be true only at w3. Then at w1, ◇□P is true (via w2 where □P holds because w2 sees only w3 and P is true there), but □◇P is false at w1 because w1 sees w2, and at w2, ◇P is true (since w2 sees w3 where P is true), so actually □◇P is true? Wait, need a counterexample. Better: In S4, the formula is not valid. For a simple counterexample, take a frame with two worlds w1 and w2, w1 sees w2, and no other relations. Let P be true only at w2. Then at w1, ◇□P is true? □P at w2? w2 sees no worlds, so □P is vacuously true at w2, so ◇□P is true at w1. But □◇P at w1: w1 sees w2, and at w2, ◇P is false because w2 sees no world where P is true (w2 does not see itself), so □◇P is false. Thus ◇□P → □◇P fails.
4. In a frame that is Euclidean and reflexive, does Axiom 5 hold? Explain.
Yes. A Euclidean frame satisfies: if w sees v and w sees u, then v sees u. Reflexivity means every world sees itself. For ◇p at w, there is some v with w sees v and p at v. For any u with w sees u, by Euclideanness, v sees u. Since p at v, and v sees u, p is possible at u? Actually, we need ◇p at u: we need u to see a world with p. But Euclideanness only gives v sees u, not u sees something. However, with reflexivity, u sees itself, but p may not be at u. So Axiom 5 may fail. Wait, correct: In a reflexive Euclidean frame, ◇p → □◇p holds. Proof: Suppose ◇p at w. Then there is v with wRv and p at v. For any u with wRu, by Euclideanness, vRu. Since p at v, we have ◇p at u (because u sees v? Actually u sees v? No, vRu means v sees u, not u sees v. We need u to see a world with p. But from vRu, we do not get uRv. So we need symmetry? In S5, the relation is an equivalence, so it is symmetric. Without symmetry, reflexivity + Euclideanness gives symmetry? Actually, a reflexive Euclidean relation is an equivalence. So yes, it holds.
5. Compare the axiomatization of common knowledge with that of distributed knowledge.
Distributed knowledge is represented by the operator D_G. Its axioms include: (1) D_G φ → φ (truth); (2) D_G φ → D_G D_G φ (positive introspection); (3) if φ → ψ is valid, then D_G φ → D_G ψ (normality). Unlike common knowledge, distributed knowledge does not require an induction rule because it is not an infinite hierarchy. Instead, distributed knowledge satisfies the principle that D_G φ is equivalent to the conjunction of what each agent knows? Actually, distributed knowledge is not simply the conjunction; it is the knowledge that would result from combining all agents' knowledge. The axiomatization often includes the fact that if each agent individually knows φ, then distributed knowledge includes φ, but the converse may not hold. The completeness proof for distributed knowledge is simpler because it can be reduced to the knowledge of a single agent with access to all agents' information.
6. Give an example of the fallacy of four terms.
Consider: 'All men are human. All women are human. So all men are women.' This has four terms: men, human, women, and human again (but human is repeated, so it is three terms? Actually, the fallacy is that 'human' is used in two premises but the conclusion uses 'men' and 'women' without a middle term linking them. A clearer example: 'All apples are fruit. Some fruit are sweet. So all apples are sweet.' Here terms: apples, fruit, fruit (again), sweet – but fruit appears twice, so four terms? Wait, the fallacy is when a word has two meanings. For instance: 'Nothing is better than eternal happiness. A ham sandwich is better than nothing. So a ham sandwich is better than eternal happiness.' Here 'nothing' is used in two different senses, creating four terms: nothing (as 'no thing'), better than, eternal happiness, and nothing (as 'a sandwich' is better than 'nothing' meaning 'no sandwich').
7. Give an example of a valid formula in public announcement logic.
Consider the formula [p]Kq → (p → Kq). This says: if after announcing p you know q, then if p is true, you already knew q before the announcement. Is this valid? Not necessarily. Suppose you don't know q initially, but after learning p, you deduce q. Then [p]Kq holds, but p → Kq may be false because p is true but you didn't know q before. So this formula is not valid. A valid example is [p]Kp, which is equivalent to p → Kp? Actually, [p]Kp is always true because after announcing p, you know p. But p → Kp is not valid (you may not know p even if it's true). So [p]Kp is valid, but its reduction gives p → Kp? Wait, the reduction axiom for knowledge is more complex. Actually, [p]Kq reduces to p → K(p → q). So [p]Kp reduces to p → K(p → p), which is p → K(true) and that is valid because K(true) holds. So [p]Kp is valid.
8. Give an example of a property that can be expressed with 'since' but not with only 'until'.
Consider the property 'the alarm has been ringing at some point in the past'. Using 'since', we can say: true S (alarm), meaning there is a past time when alarm was true and since then true has held (which is always true). Actually, 'true S alarm' means that alarm was true at some past moment and since then true has been true, which is equivalent to 'alarm was true at some past time'. With only 'until', we cannot directly refer to the past. However, we can sometimes encode past using future if the time structure is infinite in both directions? But on the natural numbers (starting at 0), past is not accessible. So 'since' is essential for expressing past properties. Another example: 'the system has been stable since the last reset' requires 'since' to refer to the last reset event.
9. Give an example where distributed knowledge differs from common knowledge.
Suppose Alice knows that the safe code is 1234, and Bob knows that the safe is in the office. Then distributed knowledge includes both facts: the code and the location. But common knowledge does not include the code because Bob does not know it, and Alice does not know that Bob knows the location? Actually, common knowledge requires everyone to know each fact individually. Here, Alice does not know the location (she might not know where the safe is), and Bob does not know the code. So neither fact is common knowledge. However, if they share their information, they can open the safe. Distributed knowledge captures this combined knowledge, while common knowledge does not. This shows that distributed knowledge can be more powerful than common knowledge.
10. How does Kamp's theorem relate to the expressiveness of LTL with past operators?
Linear temporal logic (LTL) traditionally has only future operators like 'next' (X), 'until' (U), 'eventually' (F), and 'always' (G). Adding past operators like 'since' (S) and 'previous' (Y) makes LTL with past. Kamp's theorem shows that LTL with past (including U and S) is expressively complete for first-order logic over natural numbers. However, it is known that LTL without past (only future operators) is strictly less expressive than first-order logic. For example, the property 'p holds at every even time' cannot be expressed in LTL without past, but can be expressed in first-order logic. Therefore, adding past operators increases expressiveness, and Kamp's theorem tells us that U and S are exactly the operators needed to match first-order logic.
11. What is an example of a property that cannot be expressed with 'until' and 'since'?
Kamp's theorem says that over the natural numbers, any first-order definable property can be expressed with U and S. So there is no such property over natural numbers. However, over other structures like the real numbers, U and S are not enough to express all first-order properties. For example, the property 'there is a dense set of times where p holds' (i.e., between any two times there is a time with p) is first-order definable but cannot be expressed with U and S alone. This is because U and S are 'continuous' in a sense that they cannot capture the density condition. So the expressive completeness of U and S depends on the time domain: it holds for discrete linear orders like the natural numbers but not for dense orders like the reals.
12. Compare Büchi automata with Muller automata for infinite words.
Both Büchi and Muller automata accept infinite words, but they differ in their acceptance conditions. A Büchi automaton accepts if some accepting state is visited infinitely often. A Muller automaton uses a set of sets of states: a run is accepting if the set of states that occur infinitely often is exactly one of the designated sets. Muller automata are more expressive than Büchi automata in general? Actually, they are equivalent in expressive power for ω-regular languages, but Muller automata can be more succinct. However, Büchi automata are simpler and more commonly used in practice. The determinization of Büchi automata is more complex than for Muller automata. In terms of decidability, both are decidable for emptiness.