Encontrar el complemento de un conjunto mediante la negación de declaraciones lógicas

Como parte de un ejercicio, se me ha asignado la tarea de encontrar el complemento de la siguiente declaración:

L = {P⊆{0,1}*: P es una codificación legal de un programa C, y P termina en todas menos en un conjunto finito de entradas}

La forma en que abordé la pregunta es la siguiente,
X = P es una codificación legal de un programa C
Y = P termina en todas menos en un conjunto finito de entradas.
Por lo tanto, la declaración para la que tengo que encontrar el complemento es X E Y, lo que significa
NO (X AND Y) = NOT(X) OR NOT(Y)
ahora esta es la parte donde estoy chocando contra una pared,
NOT(X) = P no es una codificación legal de un programa C
NOT(Y) = ?? ?

Honestamente, no estoy seguro de cómo negar esa declaración, he estado pensando en varias declaraciones de la siguiente manera:
1. existe un conjunto no finito de entradas en las que P no termina
2. existe un conjunto finito de entradas que P termina en
3. 1 O 2 (OR lógico)
4. ¿Algo más?

¡Apreciaré cualquier ayuda o sugerencia!

¿Qué significa * en este contexto?
{0,1}* significa todas las cadenas binarias posibles de longitud 0 o más, IE {ε,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000....}
Me parece que la elección correcta para NOT(Y) es "P no termina en un conjunto infinito de entradas".
La cosa de @MauroALLEGRANZA es que la negación del hecho de que termina para todos debería ser que hay al menos uno en el que no termina, ¿o estoy equivocado con mi suposición?

Respuestas (1)

Dejar I PAG Sea el conjunto de entradas para PAG . puedo reformular Y como: Existe un conjunto finito norte ⊂ I PAG tal que PAG no termina en norte , y tal que PAG termina en T = I PAG − norte (la diferencia establecida, el conjunto de entradas que no están en norte ).

la negación NO ( Y ) de esta declaración es: No existe un conjunto finito... y así sucesivamente como arriba, pero si no existe tal conjunto finito, entonces el conjunto de entradas para el cual PAG no termina, debe ser infinito.

Entonces NO ( Y ) termina como: existe un conjunto infinito norte ⊂ I PAG tal que PAG no termina en norte , y tal que PAG termina en T = I PAG − norte (la diferencia establecida, el conjunto de entradas que no están en norte ).

O en resumen (e informalmente): PAG no termina para un número infinito de entradas.

Gracias por la explicación detallada, esto es lo que pensé que era la dirección correcta, ¡aunque no pude desglosarlo como lo hiciste tú!
Encontrar el complemento de un conjunto mediante la negación de declaraciones lógicas
RespuestasAquíPolítica de privacidad1y, 0v