Mitglied seit 10/2018
15 Beiträge

09.02.2019, 16:24 #1
Betreff: 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 
Mitglied seit 07/2016
79 Beiträge

09.02.2019, 16: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. 
Mitglied seit 10/2018
15 Beiträge

09.02.2019, 16: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. 
Der Autor hat eine Datei an diesen Beitrag angehängt:
Unbenannt.JPG 25,7 kBytes
Du hast keine Berechtigung, diese Datei zu öffnen. 
Mitglied seit 10/2014
93 Beiträge

09.02.2019, 18: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

Mitglied seit 10/2016
743 Beiträge

09.02.2019, 19:30 #5
Antwort auf Beitrag #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. 
Mitglied seit 10/2016
743 Beiträge

09.02.2019, 19:38 #6
Antwort auf Beitrag #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 
Mitglied seit 10/2018
15 Beiträge

10.02.2019, 00: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