Nicht angemeldet. · Kennwort vergessen · Registrieren

oh01ahyz
Mitglied seit 10/2018
15 Beiträge
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
Jonas S
Mitglied seit 07/2016
79 Beiträge
Zitat von 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.

Zitat von 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
Mitglied seit 10/2018
15 Beiträge
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.
tyr
KI 1 Tutor WS18/19
Avatar
Mitglied seit 10/2014
93 Beiträge
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
Mitglied seit 10/2016
743 Beiträge
Antwort auf Beitrag #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
Mitglied seit 10/2016
743 Beiträge
Antwort auf Beitrag #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
Mitglied seit 10/2018
15 Beiträge
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".
Schließen Kleiner – Größer + Auf diesen Beitrag antworten:
Prüfcode: VeriCode Gib bitte das Wort aus dem Bild ins folgende Textfeld ein. (Nur die Buchstaben eingeben, Kleinschreibung ist in Ordnung.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Weitere Zeichen:
Gehe zu Forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen