Нахождение дополнения множества путем отрицания логических утверждений

В рамках упражнения мне дали задание найти дополнение к следующему утверждению:

L = {P⊆{0,1}*: P является допустимым кодированием программы C, и P завершается на всех входных данных, кроме конечного набора}

Я подошел к этому вопросу следующим образом:
X = P является допустимым кодированием программы на языке C.
Y = P завершается на всех входах, кроме конечного
набора.
(X И Y) = НЕ(Х) ИЛИ НЕ(Y)
теперь это та часть, где я врезаюсь в стену,
НЕ(Х) = P недопустимая кодировка программы C
НЕ(Y) = ?? ?

Честно говоря, я не уверен, как опровергнуть это утверждение, я думал о нескольких следующих утверждениях:
1. существует неконечный набор входов, на котором P не заканчивается
2. существует конечный набор входов, которые P завершается на
3. 1 ИЛИ 2 (логическое ИЛИ)
4. что-то еще?

Будем признательны за любую помощь или предложение!

Что означает * в данном контексте?
{0,1}* означает все возможные двоичные строки длины 0 или более, IE {ε,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000....}
Мне кажется, что правильный выбор для NOT (Y) - это «P не заканчивается на бесконечном наборе входов».
@MauroALLEGRANZA дело в том, что отрицание того факта, что он заканчивается для всех, должно заключаться в том, что есть хотя бы один, на котором он не заканчивается, или я ошибаюсь в своем предположении?

Ответы (1)

Позволять я п быть набором входов для п . я могу перефразировать Д как: Существует конечное множество Н ⊂ я п такой, что п не заканчивается на Н , и такой, что п заканчивается на Т "=" я п − Н (установленная разница, набор входов не в Н ).

Отрицание НЕТ ( Д ) этого утверждения: не существует конечного множества ... и так далее, как указано выше, но если такого конечного множества не существует, то множество входов, для которых п не заканчивается, должен быть бесконечным.

Так НЕТ ( Д ) заканчивается так: существует бесконечное множество Н ⊂ я п такой, что п не заканчивается на Н , и такой, что п заканчивается на Т "=" я п − Н (установленная разница, набор входов не в Н ).

Или коротко (и неформально): п не завершается для бесконечного числа входов.

Спасибо за подробное объяснение, это то, что я думал, было правильным направлением, хотя я не мог разбить его, как вы!
Нахождение дополнения множества путем отрицания логических утверждений
СпросиСетьПолитика конфиденциальности1y, 0v