Not logged in. · Lost password · Register

oh01ahyz
Member since Oct 2018
18 posts
Subject: 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
Member since Jul 2016
93 posts
Quote by 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.

Quote by 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
Member since Oct 2018
18 posts
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.
The author has attached one file to this post:
Unbenannt.JPG | Save   25.7 kBytes
Image
tyr
Avatar
Member since Oct 2014
93 posts
May I suggest that if you have a look at my more detailed solution here https://gl.kwarc.info/teaching/AI/blob/master/Marius/uebun… you may get a better understanding of  it...
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #3
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
Member since Oct 2016
803 posts
In reply to post #1
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
Member since Oct 2018
18 posts
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".
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen