Value functions

[system]

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[oh01ahyz]

Value functions
Dear all,

I have two questions on the value functions or interpretations:
I understand that we want to show that the interpretation of some formula A, i.e., I_{phi}(A), is true for all assignments {phi}.

1. In the solutions and script we have always I_{phi}(A) = T as starting point. I understand the target is to arrive at a tautology, i.e. A or not(A). How about actually starting from I_{phi}(A) = F and showing contradiction?

2. In Problem 11.2, subpoint 2, I am not 100% sure that I get the solution. I see that “a” only covers the constants that can result from variable X partially (“There is some a such that Interpretation of P(a) is false”), then an OR connection which covers all constants that variable Y can be specialized to (“for all b it holds that the Interpretation of P(b) is true”).

I do not see the tautology here, because “a” covers only part of the universe.

Thank you and kind regards,
Matthias

[Jonas_S]

---

@oh01ahyz

1. In the solutions and script we have always I_{phi}(A) = T as starting point. I understand the target is to arrive at a tautology, i.e. A or not(A). How about actually starting from I_{phi}(A) = F and showing contradiction?

Assuming that there exists a \phi, s.t. I_\phi (A) = F and arriving at a contradiction does indeed proof I_\phi (A) = T. That’s a proof by contradiction and also more or less what Theorem 5.1 says.

BUT! If I were you I would do it the canonical way, i.e., just proofing a tautology, since the contradiction lies in you deriving a tautology, which you can do without the extra step.

@oh01ahyz

2. In Problem 11.2, subpoint 2, I am not 100% sure that I get the solution. I see that „a“ only covers the constants that can result from variable X partially („There is some a such that Interpretation of P(a) is false“), then an OR connection which covers all constants that variable Y can be specialized to („for all b it holds that the Interpretation of P(b) is true“).

I honestly do not know what you are talking about. I assume you mean the formula ∃X.(P (X) ⇒ ∀Y.P (Y ))? What exactly do you mean by „a“ and „b“ and a „partial cover“? If you’re having trouble understanding the intuition why that formula must be true (I personally had trouble with that) you can negate the formula and see after the reorderings

~∃X.(P (X) ⇒ ∀Y.P (Y ))

∀X.~(P (X) ⇒ ∀Y.P (Y ))

∀X.(P (X) /\ ~∀Y.P (Y ))

why it must be true.

[oh01ahyz]

---

Thank you so far. I did also apply other methods to see that the formula must be valid, but I do not see how the validity is expressed by the last line of the solution.

I have attached a picture of the solution.

Attachment:
Unbenannt.JPG: https://fsi.cs.fau.de/unb-attachments/post_159509/Unbenannt.JPG

[tyr]

---

May I suggest that if you have a look at my more detailed solution here https://gl.kwarc.info/teaching/AI/blob/master/Marius/uebung11/marius_solution.pdf you may get a better understanding of it…

[Jazzpirate]

---

I do not see how the validity is expressed by the last line of the solution.

Well, the last line says: Either there is an a such that P(a) is false, or for all b, P(b) is true.

In other words: either there is a counter-example, or P holds for everyone. That’s clearly a tautology.

[Jazzpirate]

---

How about actually starting from I_{phi}(A) = F and showing contradiction?

Sure, you can do that in principle. But note the structure of the proof: It recursively deconstructs the formula into the definition of I_\phi on the top-most logical connective: e.g. I_\phi(A/\B)=T iff I_\phi(A)=T and I_\phi(B)=T - that is literally just the definition of I_\phi(/)

In other words: The proof is extremely straight-forward and mechanical, because you do nothing but expand the definition of I_\phi repeatedly. You will have to do the same thing to do a proof of by contradiction, except that in the end, you conclude that a value-function with the arrived-at attributes can not exist - which is just the inverse of stating that every value-function satisfies the original formula.

i.e. it’s the same proof, just expressed with a double negation

[oh01ahyz]

---

I think I got it now, thank you. My previous understanding was you need a “full overlap”, i.e., “for all … = False” OR “for all … =True”.