Finden des Komplements einer Menge durch Negieren logischer Aussagen

Im Rahmen einer Übung habe ich die Aufgabe erhalten, das Komplement der folgenden Aussage zu finden:

L = {P⊆{0,1}*: P ist eine gültige Kodierung eines C-Programms, und P endet bei allen außer einer endlichen Menge von Eingaben}

Die Art und Weise, wie ich die Frage angegangen bin, ist wie folgt:
X = P ist eine legale Codierung eines C-Programms
Y = P endet bei allen außer einer endlichen Menge von Eingaben.
Daher ist die Anweisung, für die ich das Komplement finden muss, X UND Y, was
NICHT bedeutet (X AND Y) = NOT(X) OR NOT(Y)
das ist jetzt der Teil, wo ich gegen eine Wand stoße,
NOT(X) = P ist keine legale Kodierung eines C-Programms
NOT(Y) = ?? ?

Ich bin mir ehrlich gesagt nicht sicher, wie ich diese Aussage negieren soll, ich habe über mehrere Aussagen wie folgt nachgedacht:
1. Es gibt eine nicht endliche Menge von Eingaben, auf die P nicht endet
2. Es gibt eine endliche Menge von Eingaben, die P endet auf
3. 1 ODER 2 (logisches ODER)
4. etwas anderes?

Ich freue mich über jede Hilfe oder jeden Vorschlag!

Was bedeutet * in diesem Zusammenhang?
{0,1}* bedeutet alle möglichen binären Zeichenfolgen der Länge 0 oder mehr, IE {ε,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000....}
Es scheint mir, dass die richtige Wahl für NOT (Y) "P endet nicht bei einer unendlichen Menge von Eingaben" ist.
@MauroALLEGRANZA Sache ist, die Negation der Tatsache, dass es für alle endet, sollte sein, dass es mindestens eine gibt, auf der es nicht endet, oder irre ich mich mit meiner Annahme?

Antworten (1)

Lassen ICH P sei die Menge der Eingaben für P . Ich kann umformulieren Y als: Es existiert eine endliche Menge N ⊂ ICH P so dass P endet nicht am N , und so das P endet am T = ICH P − N (die eingestellte Differenz, die Menge der Eingaben nicht in N ).

Die Verneinung NICHT ( Y ) dieser Aussage ist: Es gibt keine endliche Menge ... und so weiter wie oben, aber wenn es eine solche endliche Menge nicht gibt, dann die Menge der Eingaben für die P endet nicht, muss unendlich sein.

So NICHT ( Y ) endet als: Es existiert eine unendliche Menge N ⊂ ICH P so dass P endet nicht am N , und so das P endet am T = ICH P − N (die eingestellte Differenz, die Menge der Eingaben nicht in N ).

Oder kurz (und informell): P endet nicht für eine unendliche Anzahl von Eingaben.

Danke für die ausführliche Erklärung, das war meiner Meinung nach die richtige Richtung, obwohl ich es nicht so aufschlüsseln konnte wie Sie!
Finden des Komplements einer Menge durch Negieren logischer Aussagen
AntwortenHierDatenschutz-Bestimmungen1y, 0v