¿Cómo expresar "nnn es una potencia de primo" como una fórmula lógica sin usar notación exponencial?

Question

¿Cómo expresar "nnn es una potencia de primo" como una fórmula lógica sin usar notación exponencial?

Matemáticas
cuantificadores
números primos
lógica de predicados

sensei wu

Este es un problema que encontré mientras estudiaba matemáticas discretas por mi cuenta en el MIT:

Exprese cada uno de los siguientes predicados y proposiciones en notación lógica formal. El dominio del discurso son los números enteros no negativos, $\Bbb N$ .

Además, además de los operadores proposicionales, variables y cuantificadores, puede definir predicados usando símbolos de suma, multiplicación e igualdad, y constantes enteras no negativas ( $0, 1, ...$ ), pero sin exponenciación (como $x^y$ ) .

Por ejemplo, el predicado “ $n$ es un número par” podría definirse mediante cualquiera de las siguientes fórmulas:

$\exists m.(2m= n )$ o alternativamente $\exists m.(m+m = n )$

(a) $m$ es un divisor de $n$ .

(b) $n$ es un número primo.

(C) $n$ es una potencia de un número primo.

Ahora,

Ya tengo (a) y (b), pero necesito ayuda con (c).

(a) $\exists m\exists p. (mp=n)$

(b) $ISPrime(n) ::=$ (n > 1) $∧ \neg (\exists x \exists y. (x \gt 1 \land y \gt 1 \land (x.y=n) ))$

(C) ?

Quizá hubiera sido más fácil expresar que $n$ es un producto de dos números primos distintos. Pero, aquí estoy luchando por expresar una relación recursiva que es " $n$ es una potencia de un número primo".

$n$ solo se puede obtener multiplicando $p$ consigo mismo $k$ tiempos (donde $k$ en un entero no negativo), pero esto tiene que ser expresado sin usar notación exponencial (una restricción impuesta en la pregunta). Potencialmente podría reutilizar $ISPrime(p)$ de (b), pero ¿cómo?

Actualizar:

La solución a (b) se corrigió para dar cuenta de un comentario.

Ethan Bolker

Su respuesta a (b) permite que 1 sea primo. Esa no es la definición habitual.

sensei wu

gracias, corregido para agregar otra condición

ben voigt

El uso del operador de implicación debería simplificar la vida, por ejemplo

I s PAG r i metro mi (norte) ::= (norte > 1) \land ((X \cdot y = norte) ⟹ X \in {- norte, - 1, 1, norte})

$IsPrime(n) ::= (n > 1) \land ((x \cdot y = n) \implies x \in \{-n, -1, 1, n \})$

Oscar Cunningham

¿Por qué no simplemente 'si a divide n y b divide n entonces a divide b o b divide a'? No es necesario utilizar IsPrime.

eric

El existencial externo en su respuesta a (a) me parece incorrecto, introduce un segundo

m

$m$ variable que hace que

m p

$mp$ ambiguo sobre cuál

m

$m$ se refiere (haciéndolo redundante o incorrecto respectivamente).

sensei wu

@Eric correcto, como lo que se pide es que diga "m es un divisor de n", probablemente no debería haberlo presentado

m

$m$ como una nueva variable

Respuestas (2)

¿Cómo expresar "nnn es una potencia de primo" como una fórmula lógica sin usar notación exponencial?

Su respuesta a (b) permite que 1 sea primo. Esa no es la definición habitual.
El uso del operador de implicación debería simplificar la vida, por ejemplo $I s PAG r i metro mi (norte) ::= (norte > 1) \land ((X \cdot y = norte) ⟹ X \in {- norte, - 1, 1, norte})$ $IsPrime(n) ::= (n > 1) \land ((x \cdot y = n) \implies x \in \{-n, -1, 1, n \})$
¿Por qué no simplemente 'si a divide n y b divide n entonces a divide b o b divide a'? No es necesario utilizar IsPrime.
El existencial externo en su respuesta a (a) me parece incorrecto, introduce un segundo $m$ variable que hace que $mp$ ambiguo sobre cuál $m$ se refiere (haciéndolo redundante o incorrecto respectivamente).
@Eric correcto, como lo que se pide es que diga "m es un divisor de n", probablemente no debería haberlo presentado $m$ como una nueva variable

Ethan Bolker · Answer 1

Ethan Bolker

Si tiene IsPrime, entonces puede decir que n es un múltiplo de un número primo como máximo.

Ethan Bolker

Sí. "múltiple" es mejor que "producto". En cualquier caso, creo que estás asumiendo el teorema fundamental de la aritmética.

sensei wu

eso es ingenioso. Entonces algo como 𝐼𝑆𝑃𝑟𝑖𝑚𝑒(p) ∧ ¬(∃q.(𝐼𝑆𝑃𝑟𝑖𝑚𝑒(q) ∧ (𝑝q=𝑛)) ?

serpiente

@senseiwu No exactamente. Primero, debe agregar cuantificadores para su

p

$p$ y

n

$n$ . En segundo lugar, desea escribir algo como: "no existen dos números primos

p, q

$p,q$ tal que

n

$n$ es múltiplo de

p q

$pq$ ". (Equivalentemente: tal que

n

$n$ es múltiplo de

p

$p$ y un múltiplo de

q

$q$ .)

sensei wu

@Snaw Por lo general, soy bueno usando at-least , pero no tanto con at-most . Entonces, mi próximo intento es

((n = p q) ⟹ I S P R I M E (p) \land I S P R I M E (q) \land (p = q))

$((n=pq) \implies ISPRIME(p) \land ISPRIME(q) \land (p=q))$ . ¿Qué opinas?

serpiente

@senseiwu Todavía hay un problema, por ejemplo

27 = 3^{3}

$27=3^3$ pero

27 = 27 \cdot 1

$27=27\cdot 1$ donde ninguno de los dos

27, 1

$27,1$ son primos. O peor,

81 = 3^{4}

$81=3^4$ pero

81 = 9 \cdot 9

$81=9\cdot 9$ dónde

9

$9$ no es primo Intente traducir la oración que ofrecí en mi comentario anterior a notación matemática.

sensei wu

Cierto, pasé por alto ese aspecto. Ahora finalmente tengo

\neg (\exists p \exists q . (I S P R I M E (p) \land I S P R I M E (q) \land n = p q))

$\neg (\exists p \exists q . (ISPRIME(p) \land ISPRIME(q) \land n = pq))$ . La razón de mi incomodidad intelectual, aunque entiendo completamente la solución desde el teorema fundamental de la perspectiva aritmética, es que en ninguna parte establece que

n = p . p . p . . .

$n=p.p.p...$ . Más o menos afirmamos que no hay dos números primos que se puedan combinar para producir

n

$n$

Ethan Bolker

@senseiwu Todavía no he terminado. tienes que afirmar

p \neq q

$p \ne q$ . Tenga en cuenta que todavía está permitiendo

1

$1$ ser una potencia de un número primo, pero eso probablemente esté bien ya que es el

0

$0$ ª potencia de cualquier número primo. El hecho de que

n

$n$ es entonces una potencia de

p

$p$ depende del hecho de que todo número es un producto de números primos. (No necesita la parte de unicidad del teorema fundamental de la aritmética).

sensei wu

@EthanBolker Gracias por señalar lo incompleto. Dado que usted es profesor, me tomo la libertad de hacerle aquí otra pregunta (aunque estoy de acuerdo en que este no es el foro para una discusión tan detallada). Ha sido mi experiencia al hacer ejercicios de este libro de texto donde encontré la pregunta (lehman, meyer), que las preguntas se subdividen en 3 o 4 partes de dificultad creciente. ¿Es así como algunas universidades estadounidenses logran distinguir las capacidades de los estudiantes y categorizar sus calificaciones en consecuencia (los estudiantes A pueden resolver (c)/s y (d)s)? Solo curiosidad y gracias!!

Ethan Bolker

@senseiwu Esa estructura de ejercicios en un libro de texto está destinada a proporcionar pistas sobre cuán difícil puede ser un (parte de un) problema. Eso puede ayudar a un estudiante a aprender. Nunca he pensado en ello como una parte explícita de una calificación. Si pongo esa pregunta en un examen, los estudiantes que hicieron más partes obtendrán mejores calificaciones.

keith backman

¿Qué tal algo como

ISprime(p) \land n = r p \Rightarrow \neg (\exists q \neq p . (ISprime(q) \land n = s q))

$\text{ISprime(p)} \land n=rp \Rightarrow \lnot (\exists q \ne p.(\text{ISprime(q)}\land n=sq))$

PMMar · Answer 2

PMMar

Intente expresar una característica única de los poderes principales. Aquí está mi opinión:

Prime-Power(x) == 'Hay un P tal que: (a) P es primo; (b) Si y divide a x, entonces y=1 o P divide a y'. [formalizar en su notación favorita]

(razonarlo)

sensei wu

Esa seria la parte b y ya esta solucionada. Tuve problemas con la parte c donde están involucrados los poderes principales

Ethan Bolker

@senseiwu Esto no es (b). está satisfecho por

9 = 3^{2}

$9=3^2$ . Esta respuesta podría ser marginalmente mejor que la mía, ya que evita tener que conocer el Teorema fundamental de la aritmética.

sensei wu

@EthanBolker Lo tengo, entonces lo confundí. Todavía mantengo tu respuesta tan verde como era más fácil de seguir

sensei wu

@PMar esta también es una gran respuesta, ahora que entiendo tu lógica. Además, se construye ordenadamente sobre las soluciones a los problemas anteriores (a) y (b)

¿Cómo expresar "nnn es una potencia de primo" como una fórmula lógica sin usar notación exponencial?

sensei wu

Ethan Bolker

sensei wu

ben voigt

Oscar Cunningham

eric

sensei wu

Respuestas (2)

Ethan Bolker

Ethan Bolker

sensei wu

serpiente

sensei wu

serpiente

sensei wu

Ethan Bolker

sensei wu

Ethan Bolker

keith backman

PMMar

sensei wu

Ethan Bolker

sensei wu

sensei wu

Análisis I (Terence Tao)—Variables libres y ligadas

Traducir sentencia a lógica de predicados

Traducción de lógica de predicados a confusión en inglés.

Expresar las declaraciones lógicas cuantificadas usando los predicados

¿Cuál es la traducción correcta de "Dos ríos no pueden desembocar el uno en el otro".

Restricciones de las reglas de inferencia del cuantificador

Lógica de predicados que traduce "Todos menos uno"

Declaraciones lógicas con múltiples cuantificadores - matemáticas discretas

Traducción de la oración a la pregunta FOL

¿Cuál es la diferencia entre ∀x[(∃yPxy)⟶ϕ]∀x[(∃yPxy)⟶ϕ]\forall x [ (\exists y Pxy) \longrightarrow \phi ] y ∀x∃y[Pxy⟶ϕ] ∀x∃y[Pxy⟶ϕ]\forall x \exists y [Pxy \longrightarrow \phi]?