Lógicas polivalentes y bases de Gröbner

L´ OGICAS POLIVALENTES Y BASES DE GR¨ OBNER Jos´e An onio Alonso Jim´enez Emilio B iales Mo ales Depa amen o de Algeb a Facul ad de Ma em´a icas Uni e sidad de Se illa The aim o his pape is o desc ibe he applica ion o he G ¨obne bases o au o- ma ed heo em p o ing in Many–Valued Logic INTRODUCCI´ ON El obje i o de la comunicaci´on es p esen a una aplicaci´on de las bases de G ¨obne a la demos aci´on au om´a ica en l´ogicas p oposicionales poli alen es. La es uc u a de la comunicaci´on es la siguien e: En la secci´on 1, eco damos concep os sin ´ac icos y sem´an icos de las l´ogicas poli alen es. A con inuaci´on, educimos el p oblema de la alidez en l´ogicas poli alen es al de pe enencia a un ideal (secci´on 2) y al de c´alculo de una base de G ¨obne (secci´on 3). Finalmen e, en la secci´on 4 damos algo i mos pa a esol e los an e io es p oblemas. 1 L´ OGICAS POLIVALENTES 1.1 No aciones. En lo que sigue: (1) n,sson dos n´ume os en e os posi i os. (2) {X1, . . . , Xn}es un conjun o cuyos elemen os se in e p e a ´an como a iables p oposicionales. (3) { 1, . . . , s}es un conjun o, disjun o con {X1, . . . , Xn}, cuyos elemen os se in e - p e a ´an como conec i as. (4) Pa a cada j∈ {1, . . . , s},δ(j) es un n´ume o en e o posi i o que se in e p e a ´a como la a idad de la conec i a j. 1.2 De inici´on. El conjun o P(X1, . . . , Xn) de las p oposiciones en las a iables X1, . . . , Xn y las conec i as 1, . . . , sse de ine ecu si amen e po : (1) Pa a odo i∈ {1, . . . , n},Xi∈P(X1, . . . , Xn). (2) Si j∈ {1, . . . , s}yA1, . . . , Aδ(j)∈P(X1, . . . , Xn), en onces j(A1, . . . , Aδ(j))∈ P(X1, . . . , Xn). 1.3 No aciones. En lo que sigue: (1) Usa emos las le as A,B(posiblemen e con sub´ındices) como a iables pa a p oposiciones. (2) pes un n´ume o p imo. (3) Zpes el cue po de los en e os m´odulo p, cuyos elemen os se in e p e a ´an como alo es de e dad. En pa icula , 0 se in e p e a ´a como also y 1 como e - dade o. (4) Pa a cada j∈ {1, . . . , s},Hjes una aplicaci´on de Zδ(j) pen Zpque se in e p e a ´a como la abla de e dad de la conec i a j. 1.4 Ejemplo. En el sis ema i alen e de Lukasiewicz, L3,p= 3; 2 se in e p e a como inde- e minado; las conec i as son 1=¬(negaci´on), 2=♦(posibilidad), 3= ÃL (necesidad), 4=∨(disyunci´on), 5=∧(conjunci´on), 6=→(implicaci´on) y 7=↔(equi alencia); las a idades son δ(1) = δ(2) = δ(3) = 1, δ(4) = · · · =δ(7) = 2; y las ablas de e dad son las unciones Hide inidas po a H1(a)H2(a)H3(a) 0 1 0 0 1 0 1 1 2 2 1 0 a b H4(a, b)H5(a, b)H6(a, b)H7(a, b) 0 0 0 0 1 1 0 1 1 0 1 0 0 2 2 0 1 2 1 0 1 0 0 0 1 1 1 1 1 1 1 2 1 2 2 2 2 0 2 0 2 2 2 1 1 2 1 2 2 2 2 2 1 1 1.5 De iniciones. (1) Una alo aci´on es una aplicaci´on :{X1, . . . , Xn} → Zp. (2) Pa a cada alo aci´on se de ine ˆ :P(X1, . . . , Xn)→Zp ecu si amen e po : ˆ (A) = ½ (A),si A∈ {X1, . . . , Xn}; Hj(ˆ (A1), . . . , ˆ (Aδ(j))),si Aes j(A1, . . . , Aδ(j)). (3) Aes una au olog´ıa,|=A, si pa a oda alo aci´on , ˆ (A) = 1. (4) Aes una consecuencia au ol´ogica de {B1, . . . , Bm},{B1, . . . , Bm} |=A, si pa a oda alo aci´on , ˆ (B1) = · · · = ˆ (Bm) = 1 =⇒ˆ (A) = 1. 1.6 Ejemplos. En L3se iene: (1) |=X↔ ¬¬X. (2) X∨ ¬Xy (♦X∧(X→Y)) → ♦Yno son au olog´ıas. (3) {♦X, X →Y} |=♦Y. 1.7 No a. El obje i o del p esen e abajo consis e en esol e median e algo i mos alge- b aicos los siguien es p oblemas: •P oblema 1 Dada una p oposici´on A, decidi si |=A. •P oblema 2 Dada una p oposici´on A0y un conjun o ini o de p oposiciones {A1, . . . , Am}, decidi si {A1, . . . , Am} |=A0. 2 2 TAUTOLOGIAS E IDEALES 2.1 No aci´on. En lo que sigue: (1) Zp[X1, . . . , Xn] es el anillo de polinomios en las inde e minadas X1, . . . , Xny con coe icien es en Zp. (2) Usa emos las le as p,q, (posiblemen e con sub´ındices) como a iables pa a polinomios. (3) Usa emos las le as F,G(posiblemen e con sub´ındices) como a iables pa a con- jun os de polinomios dis in os de ce o. 2.2 De inici´on. Pa a cada alo aci´on , ∗:Zp[X1, . . . , Xn]→Zpes el ´unico homomo ismo al que ∗(Xi) = (Xi), pa a odo i∈ {1, . . . , n}. 2.3 De inici´on. (1) Pa a cada conec i a jse de ine la aplicaci´on θj:Zp[X1, . . . , Xn]δ(j)→Zp[X1, . . . , Xn] po θj(q1, . . . , qδ(j)) = X 0≤i1≤p−1 ··············· 0≤iδ(j)≤p−1 Hj(i1, . . . , iδ(j))Li1(q1). . . Liδ(j)(qδ(j)), donde L0(q) = 1 −qp−1yLi(q) = L0(q−i) pa a i∈ {1, . . . , p −1}. (2) La aplicaci´on θ:P(X1, . . . , Xn)→Zp[X1, . . . , Xn] es ´a de inida po : θ(A) = ½A, si A∈ {X1, . . . , Xn}; θj(θ(A1), . . . , θ(Aδ(j))),si Aes j(A1, . . . , Aδ(j)). 2.4 Ejemplo. En L3, θ1(q) = 2q+ 1, θ2(q) = q2, θ3(q) = 2q2+ 2, θ4(q1, q2)= 2q2 1q2 2+q2 1q2+q1q2 2+q1q2+q1+q2, θ5(q1, q2)= q2 1q2 2+ 2q2 1q2+ 2q1q2 2+ 2q1q2, θ6(q1, q2)= q2 1q2 2+ 2q2 1q2+ 2q1q2 2+ 2q1q2+ 2q1+ 1, θ7(q1, q2)= 2q2 1q2 2+q2 1q2+q1q2 2+q1q2+ 2q1+ 2q2+ 1. 2.5 Lema. Pa a oda alo aci´on , ˆ = ∗◦θ. Demos aci´on: Po inducci´on sob e la longi ud de las p oposiciones. 2.6 De inici´on. El ideal engend ado po F={q1, . . . , qm}es I(F) = ½m X i=1 iqi: i∈Zp[X1, . . . , Xn]¾ 3 Esc ibi emos (q1, . . . , qm) en luga de I({q1, . . . , qm}). 2.7 Lema. Si I= (Xp 1−X1, . . . , Xp n−Xn), en onces son equi alen es: (a) q∈I. (b) Pa a oda alo aci´on , ∗(q) = 0. Demos aci´on: (a) =⇒(b): Po el P ime Teo ema de Fe ma . (b) =⇒(a): Po inducci´on sob e n. 2.8 Teo ema. Sea A∈P(X1, . . . , Xn). En onces |=A⇐⇒ θ(A)−1∈(Xp 1−X1, . . . , Xp n−Xn) Demos aci´on: |=A⇐⇒ (∀ )[ˆ (A) = 1] [po 1.5] ⇐⇒ (∀ )[ ∗(θ(A)) = 1] [po 2.5] ⇐⇒ (∀ )[ ∗(θ(A)−1) = 0] ⇐⇒ θ(A)−1∈(Xp 1−X1, . . . , Xp n−Xn) [po 2.7] 2.9 Lema. Sean q0, q1, . . . qm∈Zp[X1, . . . , Xn]. Son equi alen es: (a) Pa a oda alo aci´on , ∗(q1) = · · · = ∗(qm) = 0 =⇒ ∗(q0) = 0. (b) Pa a oda alo aci´on , ∗((q0+q1+···+qm)(qp−1 1−1) ···(qp−1 m−1)) = 0. (c) (q0+q1+· · · +qm)(qp−1 1−1) · · · (qp−1 m−1) ∈(Xp 1−X1, . . . , Xp n−Xn). (d) q0∈(q1, . . . , qm, Xp 1−X1, . . . , Xp n−Xn). Demos aci´on: (a) =⇒(b): Po se ∗homomo ismo y po el P ime Teo ema de Fe ma . (b) =⇒(c): Po el Lema 2.7. (c) =⇒(d): T i ial. (d) =⇒(a): Po el P ime Teo ema de Fe ma . 2.10 Teo ema. Sean A0, A1, . . . , Am∈P(X1, . . . , Xn). Son equi alen es: (a) {A1, . . . , Am} |=A0. (b) θ(A0)−1∈(θ(A1)−1, . . . , θ(Am)−1, Xp 1−X1, . . . , Xp n−Xn). (c) m X i=0 (θ(Ai)−1) m Y j=1 p−1 X k=1 θ(Aj)k∈(Xp 1−X1, . . . , Xp n−Xn). Demos aci´on: (a) ⇐⇒ (b): Po 1.5, 2.5 y 2.9, se iene {A1, . . . , Am} |=A0⇐⇒ ⇐⇒ (∀ )[ˆ (A1) = · · · = ˆ (Am) = 1 =⇒ˆ (A0) = 1] ⇐⇒ (∀ )[ ∗(θ(A1)) = ···= ∗(θ(Am)) = 1 =⇒ ∗(θ(A0)) = 1] ⇐⇒ (∀ )[ ∗(θ(A1)−1) = · · · = ∗(θ(Am)−1) = 0 =⇒ ∗(θ(A0)−1) = 0] ⇐⇒ θ(A0)−1∈(θ(A1)−1, . . . , θ(Am)−1, Xp 1−X1, . . . , Xp n−Xn) (b) ⇐⇒ (c): Po el Lema 2.9. 4 2.11 No a. Median e los Teo emas 2.8 y 2.10, los P oblemas de la No a 1.7 se educen al siguien e: •P oblema 3 Dado un conjun o ini o de polinomios {q1, . . . , qm}y un polinomio q0 , decidi si q0∈(q1, . . . , qm). 3 IDEALES Y BASES DE GR¨ OBNER 3.1 No aci´on. En lo que sigue: (1) Usa emos la le a a(posiblemen e con sub´ındices) como a iable pa a ´e minos (i.e. polinomios de la o ma Xα1 1. . . Xαn n). (2) Usa emos la le a u(posiblemen e con sub´ındices) como a iable pa a elemen os de Zp. 3.2 De inici´on. En el conjun o de los ´e minos de Zp[X1, . . . , Xn] se de ine la elaci´on >T po : Xα1 1. . . Xαn n>TXβ1 1. . . Xβn nsyss α1+· · · +αn> β1+· · · +βn´o α1+···+αn=β1+· · ·+βny (∃i∈ {1, . . . , n})[αi> βi∧(∀j)[1 ≤j < i →αj=βj]] 3.3 De inici´on. Sea qun polinomio dis in o de ce o. (1) Pa a cada ´e mino a, coe (a, q), ep esen a el coe icien e de aen q. (2) El ´e mino l´ıde de q, TL(q), es el mayo ´e mino a( espec o de >T) al que coe (a, q)6= 0. (3) El coe icien e l´ıde de qes CL(q) = coe (TL(q), q). (4) El es o de qes R(q) = q−CL(q)TL(q). 3.4 De inici´on. Sea qun polinomio dis in o de ce o, Fun conjun o de polinomios dis in os de ce o y aun ´e mino. (1) ρ(q, a) : Zp[X1, . . . , Xn]→Zp[X1, . . . , Xn] es ´a de inida po : ρ(q, a)( ) = −coe (aTL(q), ) CL(q)aq. (2) 1−→q,a 2si 2=ρ(q, a)( 1)6= 1. (3) 1−→q 2si exis e un ´e mino a al que 1−→q,a 2. (4) 1−→F 2si exis e un q∈F al que 1−→q 2. (5) 1 ∗ −→F 2si exis en k∈Nyq0, . . . , qk∈Zp[X1, . . . , Xn] ales que 1=q0−→Fq1−→F· · · −→Fqk= 2. 3.5 De inici´on. Sea Fun conjun o ini o de polinomios dis in os de ce o. (1) qes educible ( espec o de F) si exis e un al que q−→F ; en caso con a io, se dice que qes i educible ( espec o de F). 5 (2) qes una o ma i educible ( espec o de F) de si qes i educible espec o de Fy ∗ −→Fq. 3.6 No a. Dado un conjun o ini o Fde polinomios dis in os de ce o, cada polinomio iene al menos una o ma i educible espec o de F; pe o puede ene m´as de una ( e ejemplo en 4.1.2). 3.7 De inici´on. Un conjun o ini o Fde polinomios dis in os de ce o es una base de G ¨obne si cada polinomio iene una ´unica o ma i educible espec o de F. 3.8 Teo ema (Buchbe ge , 1976). Si Fes una base de G ¨obne , en onces I(F) = {q∈Zp[X1, . . . , Xn] : q∗ −→F0}. 3.9 No a. Median e el Teo ema an e io , el P oblema 3 de la No a 2.11 se educe a los siguien es: •P oblema 4 Dado un conjun o ini o Fde polinomios dis in os de ce o y un poli- nomio q, calcula una o ma i educible de q espec o de F. •P oblema 5 Dado un conjun o ini o Fde polinomios dis in os de ce o, calcula una base de G ¨obne G al que I(G) = I(F). 4 ALGORITMOS Y EJEMPLOS 4.1 Algo i mo de o ma no mal 4.1.1 Algo i mo. (de o ma no mal pa a el P oblema 4) En ada: Un conjun o ini o F={q1, . . . , qm}de polinomios dis in os de ce o y un polinomio q=u1a1+···+ukak Salida: Una o ma i educible de q espec o de F. P ocedimien o: FN(q, F) i:= 1 mien as–que i≤m j:= 1 mien as–que j≤k si TL(qi) di ide a aj en onces FNµq−ujaj CL(qi)TL(qi)qi, F¶ en–o o–caso j:= j+ 1 i:= i+ 1 de ol e q 4.1.2 Ejemplo. En Z3[X, Y ] se conside an el conjun o F={q1=X2−1, q2=X2Y2+ 2X2Y+ 2XY 2+ 2XY + 2X, q3=X3−X, q4=Y3−Y}. En onces FN(X3Y3, F) = XY , pe o XY no es la ´unica o ma i educible de X3Y3 espec o de F(po ejemplo, XY 2+Y2+ 2Yes o a). Po an o, Fno es una base de G ¨obne . 4.1.3 No a. Es ´acil de comp oba que el algo i mo an e io e mina y es co ec o. 6 4.2 Algo i mo de base de G ¨obne 4.2.1 De inici´on. Sean q1,q2dos polinomios dis in os de ce o. El S-polinomio de q1yq2 es S(q1, q2) = a1u1 q1− a2u2 q2, donde ai= CL(qi), ui= TL(qi) y = mcm(u1, u2). 4.2.2 Algo i mo. (de base de G ¨obne pa a el P oblema 5) En ada: Un conjun o ini o F={q1, . . . , qm}de polinomios dis in os de ce o. Salida: Una base de G ¨obne G al que I(G) = I(F). P ocedimien o: BG(F) (∀i∈ {1, . . . , m})· i:= qi CL(qi)¸ G:= { i:i∈ {1, . . . , m}} G:= Reduce(G) [Supongamos que G={q0 1, . . . , q0 k}] B:= {(q0 i, q0 j) : 1 ≤i < j ≤k} mien as–que B6=∅hace (q0 i, q0 j) un elemen o de B B:= B− {(q0 i, q0 j)} := FN(S(q0 i, q0 j), G) si 6= 0 en onces BG(G∪ { }) de ol e G Subalgo i mo. (de educci´on) En ada: Un conjun o ini o F={q1, . . . , qm}de polinomios m´onicos dis in os de ce o. Salida: Un conjun o Gde polinomios m´onicos al que I(G) = I(F) y FN(q, G − {q}) = qpa a odo q∈G. P ocedimien o: Reduce(F) G:= F si (∃q∈G)[FN(q, G − {q})6=q] en onces i:= in {j∈ {1, . . . , m}:FN(qj, G − {qj})6=qj} G:= G− {qi} q:= FN(qi, G) si q= 0 en onces Reduce(G) en–o o–caso Reduce(G∪ {q/CL(q)}) en-o o-caso de ol e G 4.2.3 Ejemplo. Vamos a aplica el algo i mo de bases de G ¨obne al conjun o Fdel Ejemplo 4.1.2: En p ime luga aplicamos el algo i mo de educci´on y ob enemos G={q0 1= X2−1, q0 2=Y3−Y, q0 3=XY 2+XY + 2Y2+X+Y}yB={(q0 1, q0 2),(q0 1, q0 3),(q0 2, q0 3)}. Elegimos (q0 1, q0 3)∈By calculamos =FN(S(q0 1, q0 3), G) = XY + 2X+Y+ 2. Pues o que 6= 0, enemos que calcula BG({q0 1, q0 2, q0 3, }). Al aplica el algo i mo de educci´on se ob iene G={q0 1=X2−1, q0 2=XY + 2X+Y+ 2, q0 3=Y2+ 2}. Pues o que, 7 FN(S(q0 1, q0 2), G) = 0, FN(S(q0 1, q0 3), G) = 0, FN(S(q0 2, q0 3), G) = 0, se iene que BG(F) = {X2−1, XY + 2X+Y+ 2, Y 2+ 2}. 4.2.4 Teo ema. El algo i mo de la base de G ¨obne es co ec o. Demos aci´on (Esquema): La e minaci´on se demues a a pa i del eo ema de la base de Hilbe y la co ecci´on pa cial a pa i del siguien e eo ema: Teo ema (Buchbe ge ) Ges una base de G ¨obne syss pa a odo q1, q2∈G, S(q1, q2)∗ −→G0. 4.3 Algo i mos de alidez 4.3.1 Algo i mo. (de deducci´on) En ada: Una p oposici´on A0y un conjun o ini o Γ = {A1, . . . , Am}de p oposiciones. Salida: “S´”, si Γ |=A0; “NO”, en caso con a io. P ocedimien o: G:= BG(({θ(Ai)−1 : 1 ≤i≤m}∪{Xp i−Xi: 1 ≤i≤n})− {0}) q:= FN(θ(A0)−1, G) si q= 0 en onces de ol e “S´” en–o o–caso de ol e “NO” 4.3.2 Teo ema. El algo i mo de deducci´on es co ec o. Demos aci´on: Sean F={θ(A1)−1, . . . , θ(Am)−1, Xp 1−X1, . . . , Xp n−Xn}yG=BG(F− {0}). Γ|=A0⇐⇒ θ(A0)−1∈I(F) [po 2.10] ⇐⇒ θ(A0)−1∈I(G) [po 4.2.4] ⇐⇒ θ(A0)−1∗ −→G0 [po 3.8] ⇐⇒ FN(θ(A0)−1, G) = 0, ya que FN(θ(A0)−1, G) es la ´unica o ma i educible de θ(A0)−1 espec o de G. 4.3.3 Ejemplo. Conside emos, en L3, la p oposici´on A0=♦Yy el conjun o Γ = {A1, A2}, siendo A1=♦XyA2=X→Y. Vamos a usa el algo i mo de deducci´on pa a decidi si Γ|=A0. G=BG({X2−1, X2Y2+ 2X2Y+ 2XY 2+ 2XY + 2X, X3−X, Y 3−Y} ={X2−1, XY + 2X+Y+ 2, Y 2+ 2}, po el Ejemplo 4.2.3. Pues o que, F N(θ(A0)−1, G) = FN(Y2−1, G) = 0, esul a que Γ|=A0. 4.3.4 Algo i mo. (de alidez) En ada: Una p oposici´on A. Salida: “S´”, si |=A; “NO”, en caso con a io. P ocedimien o: G:= {Xp i−Xi: 1 ≤i≤n} q:= FN(θ(A)−1, G) si q= 0 en onces de ol e “S´” en–o o–caso de ol e “NO” 8 4.3.5 Teo ema. El algo i mo de alidez es co ec o. Demos aci´on: An´aloga a la del Teo ema 4.3.2, obse ando que {Xp i−Xi: 1 ≤i≤n}es una base de G ¨obne . 4.3.6 Ejemplo. Vamos a aplica el algo i mo an e io pa a es udia la alidez en L3de las siguien es p oposiciones: A1=X↔ ¬¬X(eliminaci´on de la doble negaci´on), A2=X∨¬X (ley del e cio excluido) y A3= (♦X∧(X→Y)) → ♦Y. Sea F={X3−X}. Pues o que, FN(θ(A1)−1, F) = FN(2X4+ 2X3+X2+ X, F) = 0, FN(θ(A2)−1, F) = FN(2X4+2X3+2X, F) = 2X2+XyFN(θ(A3)−1, F) = X2Y2+ 2X2+ 2XY 2+X+ 1, esul a que A1es una au olog´ıa de L3yA2, A3no lo son. 4.3.7 Algo i mo. (de deducci´on. Ve si´on 2) En ada: Una p oposici´on A0y un conjun o ini o Γ = {A1, . . . , Am}de p oposiciones. Salida: “S´”, si Γ |=A0; “NO”, en caso con a io. P ocedimien o: G:= {Xp i−Xi: 1 ≤i≤n} q:= FNµm X i=0 (θ(Ai)−1) m Y j=1 p−1 X k=1 θ(Aj)k, G¶ si q= 0 en onces de ol e “S´” en–o o–caso de ol e “NO” 4.3.8 Teo ema. El algo i mo an e io es co ec o. Demos aci´on: An´aloga a la del Teo ema 4.3.5. 5 IMPLEMENTACI´ ON Los an e io es algo i mos pueden implemen a se di ec amen e en REDUCE. El Ap´endice A es un p og ama en REDUCE de los algo i mos 4.3.4 y 4.3.7 pa a la l´ogica i alen e de Lukasiewicz. El Ap´endice B es una sesi´on en REDUCE usando el p og ama an e io (en la que se ha sub ayado los mensajes del sis ema). BIBLIOGRAF´A Buchbe ge , B. (1985), “G ¨obne Basis: An Algo i hmic Me hod in Polynomial Ideal The- o y”, en N.K. Bose, ed. Mul idimensional Sys ems Theo y. Reidel, Do d ech . Hsiang, J. (1985), “Re u a ional Theo em P o ing using Te m–Rew i ing Sys ems” A i- icial In elligence,25, pp. 255–300. Kapu , D. y P. Na end an (1985) “An Equa ional App oach o Theo em P o ing in Fi s O de P edica e Calculus”, en 9 h IJCAI. Moisil, G.C. (1969) The Algeb aic Theo y o Swi ching Ci cui s Pe gamon P ess, Ox o d. Resche , N. (1969) Many– alued Logic. McG aw–Hill, New Yo k. 9