Member since Oct 2018
18 posts

20190209, 15:24 #1
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 
Member since Jul 2016
94 posts

20190209, 15:44 #2
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.
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. 
Member since Oct 2018
18 posts

20190209, 15:59 #3
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:

Member since Oct 2014
123 posts

20190209, 17:30 #4
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 CookieClicker

Member since Oct 2016
813 posts

20190209, 18:30 #5
In reply to post #3
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 counterexample, or P holds for everyone. That's clearly a tautology. 
Member since Oct 2016
813 posts

20190209, 18:38 #6
In reply to post #1
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 topmost 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 straightforward 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 valuefunction with the arrivedat attributes can not exist  which is just the inverse of stating that every valuefunction satisfies the original formula. i.e. it's the same proof, just expressed with a double negation 
Member since Oct 2018
18 posts

20190209, 23:10 #7
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".

Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen