張燕

中山大學(xué)邏輯與認(rèn)知研究所

zhang85@mail2.sysu.edu.cn

沈榆平

中山大學(xué)邏輯與認(rèn)知研究所

shyping@mail.sysu.edu.cn

趙希順

中山大學(xué)邏輯與認(rèn)知研究所

hsszxs@mail.sysu.edu.cn

?

前提嵌套程序和基數(shù)約束程序的簡(jiǎn)潔性研究*，?

張燕

中山大學(xué)邏輯與認(rèn)知研究所

zhang85@mail2.sysu.edu.cn

沈榆平

中山大學(xué)邏輯與認(rèn)知研究所

shyping@mail.sysu.edu.cn

趙希順

中山大學(xué)邏輯與認(rèn)知研究所

hsszxs@mail.sysu.edu.cn

直觀地說(shuō)，簡(jiǎn)潔性是指一個(gè)邏輯系統(tǒng)緊湊表示問(wèn)題的能力。近年來(lái)關(guān)于簡(jiǎn)潔性的研究逐漸得到人們的關(guān)注。本文將討論兩類(lèi)邏輯程序，即基數(shù)約束程序（Cardinality Constraint Programs，CCP）與前提嵌套程序（Nested Logic Programs，NLP）之間的簡(jiǎn)潔性。我們?cè)O(shè)計(jì)了一個(gè)從CCP到NLP多項(xiàng)式長(zhǎng)度的等價(jià)翻譯，這極大改進(jìn)了Ferraris和Lifschitz提出的指數(shù)長(zhǎng)度翻譯方法，由此證明NLP至少與CCP一樣簡(jiǎn)潔。

簡(jiǎn)潔性；回答集；基數(shù)約束程序；前提嵌套程序

1　引言

邏輯系統(tǒng)的簡(jiǎn)潔性指該系統(tǒng)緊湊表示問(wèn)題的能力。簡(jiǎn)單地說(shuō)，對(duì)于系統(tǒng)C 和C′，若C′中的每個(gè)理論都可等價(jià)翻譯（不添加輔助變?cè)镃中的理論而不會(huì)引起該理論長(zhǎng)度的指數(shù)增長(zhǎng)，則稱(chēng)C至少與C′一樣簡(jiǎn)潔（C′?C）。最近，對(duì)基于回答集語(yǔ)義的邏輯程序（Answer Set Programs，ASP，［1，5，7］）的簡(jiǎn)潔性研究已經(jīng)引起領(lǐng)域內(nèi)的興趣。（［8，12］）ASP是處理規(guī)劃、診斷、常識(shí)推理等應(yīng)用的一種人工智能邏輯，它包括許多子類(lèi)，如基數(shù)約束程序（Cardinality Constraint Programs，CCP，［3］）、前提嵌套程序（Nested Logic Programs，NLP，［9］）等。人們已經(jīng)知道CCP和NLP有相同的表達(dá)能力（它們與命題邏輯等價(jià)）和推理復(fù)雜性（一致性檢測(cè)為NP-完全，［3，9，12］），但它們之間的相對(duì)簡(jiǎn)潔性尚無(wú)明確結(jié)論。

本文將證明CCP?NLP，即NLP至少與CCP一樣簡(jiǎn)潔，或者說(shuō)，每一個(gè)CCP程序都可以等價(jià)翻譯為一個(gè)多項(xiàng)式長(zhǎng)度的NLP程序。具體而言，CCP是一類(lèi)含有基數(shù)約束（Cardinality Constraints，CC）的程序，即允許在文字集上表達(dá)數(shù)值約束的程序，而NLP是一類(lèi)允許規(guī)則前提有命題嵌套公式的程序，此處的命題嵌套公式指由弱否定符（not）、析取符（；）和合取符（，）在文字集上形成的表達(dá)式。在2005年，F(xiàn)erraris和Lifschitz（［3］）對(duì)CCP程序與NLP程序之間的等價(jià)翻譯關(guān)系進(jìn)行了深入研究，他們構(gòu)造了一個(gè)從CCP程序到NLP程序的等價(jià)翻譯，但該翻譯一般會(huì)導(dǎo)致程序長(zhǎng)度產(chǎn)生指數(shù)增長(zhǎng)，因此并沒(méi)有回答CCP與NLP之間的簡(jiǎn)潔性問(wèn)題。

在本文中，我們通過(guò)基于布爾函數(shù)（［11，14］）的緊湊表示技術(shù)將上述翻譯降低為多項(xiàng)式長(zhǎng)度，并在此基礎(chǔ)上證明CCP?NLP。我們對(duì)Ferraris和Lifschitz的工作改進(jìn)主要在于將基數(shù)約束拆分為計(jì)數(shù)函數(shù)、比較函數(shù)并將它們改寫(xiě)成多項(xiàng)式長(zhǎng)度的嵌套表示，最終得到多項(xiàng)式長(zhǎng)度的等價(jià)翻譯。本文第二部分回顧基本知識(shí)；第三部分回顧Ferraris和Lifschitz的的構(gòu)造方法；第四部分是主要證明過(guò)程，最后得到相關(guān)結(jié)論。

2　基礎(chǔ)知識(shí)

一個(gè)字母表Σ為一個(gè)有窮原子集合。一個(gè)正文字是Σ中的一個(gè)原子（或命題變?cè)﹛。一個(gè)負(fù)文字是Σ中的一個(gè)原子x的否定not x。正文字或負(fù)文字均稱(chēng)為文字。按習(xí)慣，我們約定在討論中均預(yù)設(shè)了一個(gè)字母表。

2.1基數(shù)約束程序

下面的背景來(lái)自［3，10］。一個(gè)基數(shù)約束是形如：

的表達(dá)式，其中ci（i=1，2，...，m）是文字，L，U是整數(shù)或是?∞，+∞之一。若L=?∞，則L可以省略；若U=+∞，則U可以省略。為方便，也可忽略≤號(hào)，記（1）為L(zhǎng)｛c1，...，cm｝U。

一條CCP規(guī)則是形如：的表達(dá)式，其中n≥0，C、Ci（i=1，2，...，n）為基數(shù)約束。我們稱(chēng)C1...，Cn為該規(guī)則的前提，C為該規(guī)則的結(jié)論。若n=0，則（2）可記為C←（或C←?）。

一個(gè)CCP程序Π是有窮條規(guī)則（2）組成的集合。一條規(guī)則（2）的長(zhǎng)度是指基數(shù)約束C和Ci（i=1，2，...，n）的總個(gè)數(shù)。一個(gè)CCP程序Π的長(zhǎng)度|Π|指Π中所有規(guī)則的長(zhǎng)度之和。

令I(lǐng)為原子集合，x∈Σ為一個(gè)原子，稱(chēng)I滿足x，記為I|=x，如果x∈I。稱(chēng)I滿足not x，如果I?x。我們約定I總滿足?，且永不滿足⊥。對(duì)于基數(shù)約束C，記lit（C）為C中出現(xiàn)的所有文字的集合。記v（C，I）為C中被I滿足的文字的個(gè)數(shù)，即v（C，I）=|｛c∈lit（C）：I|=c｝|。令C為基數(shù)約束L｛c1，...，cm｝U，若L≤v（C，I）≤U，則稱(chēng)I滿足C，記為I|=C。

對(duì)規(guī)則C←C1，...，Cn，如果I滿足C或I不滿足前提中某個(gè)Ci（i= 1，...，n），那么稱(chēng)I滿足此規(guī)則。如果I滿足程序Π中所有規(guī)則，則稱(chēng)I滿足Π（或I在Π下封閉），記為I|=Π。

例1考慮下面的CCP規(guī)則：

原子集｛x1，x2｝滿足其前提，因?yàn)関（1｛x1，not x2，not x3｝3，｛x1，x2｝）=|｛x1，not x3｝|=2，但｛x1，x2｝不滿足其結(jié)論，因?yàn)関（0｛x1，x2｝1，｛x1，x2｝）=|｛x1，x2｝|=2。據(jù)定義，｛x1，x2｝不滿足規(guī)則（3）。此外，可觀察到原子集｛x2，x3｝不滿足其前提，因?yàn)関（1｛x1，not x2，not x3｝3，｛x2，x3｝）=|?|=0。據(jù)定義，｛x2，x3｝滿足規(guī)則（3）。

對(duì)基數(shù)約束C，令atom（C）為C中出現(xiàn)的正文字集合，即｛x∈lit（C）：x∈Σ是原子｝。一個(gè)形如L≤lit（C）的基數(shù)約束C相對(duì)于原子集合I的歸約，記為CI，是一個(gè)基數(shù)約束L′≤atom（C），其中L′=L?|｛not x∈lit（C）：I|=not x｝|。

例2令C為2｛x1，not x2，not x3｝，I=｛x1，x2｝。注意atom（C）=｛x1｝，且｛x1，x2｝滿足C中的負(fù)文字not x3，L′=2?|｛not x3｝|=1，因此CI為L(zhǎng)′≤atom（C）=1｛x1｝。

給定規(guī)則C←C1，...，Cn和原子集I，其中每個(gè)Ci形如Li≤lit（Ci）≤Ui，那么該規(guī)則相對(duì)于I的歸約為以下規(guī)則的集合：

如果對(duì)每個(gè)i∈｛1，...，n｝，I|=lit（Ci）≤Ui，其中a∈atom（C）∩I；否則，為?。

例3規(guī)則1｛x1，x2｝2←1｛not x2，x3｝3相對(duì)于｛x1，x3｝的歸約是

一個(gè)CCP程序Π相對(duì)于原子集I的歸約ΠI是Π中所有規(guī)則相對(duì)于I的歸約的并集。我們記Cn（ΠI）為滿足ΠI的極小原子集。注意ΠI不含not，且Cn（ΠI）是唯一的。若I=Cn（ΠI）且I|=Π，則稱(chēng)I為Π的回答集。

例4令Π為程序1｛x1，not x2｝2←。可觀察到Π有兩個(gè)回答集：?和｛x1｝。因?|=Π，且Cn（Π?）=Cn（?）=?；類(lèi)似地，｛x1｝|=Π且Cn（Π｛x1｝）= Cn（｛x1←｝）=｛x1｝。再考慮程序｛x1，x2｝←，可觀察到?，｛x1｝，｛x2｝，｛x1，x2｝均為其回答集。比如，｛x1，x2｝|=｛x1，x2｝←，且Cn（｛｛x1，x2｝←｝｛x1，x2｝）= Cn（｛x1←，x2←｝）=｛x1，x2｝。

關(guān)于CCP的更多細(xì)節(jié)，可參考［3，10］。

2.2前提嵌套程序（NLP）

下面的背景來(lái)自［9］。令Σ為字母表，一個(gè)NLP公式F定義如下：

其中x∈Σ，⊥和?是零元連接詞，弱否定符（not）是一元連接詞，合取符（，）和析取符（；）是二元連接詞。

一個(gè)NLP程序Π是有窮條如下形式的規(guī)則組成的集合：

其中F為原子或⊥，稱(chēng)為結(jié)論，G為公式，稱(chēng)為前提。一個(gè)NLP程序Π的長(zhǎng)度|Π|指Π中連接詞的總數(shù)。若F=⊥，則上式稱(chēng)為限制規(guī)則。

原子集合I和NLP公式F，G之間的可滿足關(guān)系|=N定義如下：

·對(duì)每個(gè)原子x∈Σ，如果x∈I，那么I|=Nx，否則，I/|=Nx；

·I|=N?，I?N⊥；

·如果I|=NF且I|=NG，那么I|=N（F，G）；

·如果I|=NF或I|=NG，那么I|=N（F；G）；

·如果I?NF，那么I|=Nnot F。

我們稱(chēng)I滿足一條規(guī)則F←G，如果I?NG或I|=NF。NLP公式、規(guī)則和一個(gè)程序Π相對(duì)于原子集合I的歸約按照如下方式遞歸定義：

·對(duì)每個(gè)原子x，xI=x；

·⊥I=⊥，?I=?；

·（F，G）I=（FI，GI）；

·（F；G）I=（FI；GI）；

·（F←G）I=FI←GI；

·ΠI=｛（F←G）I：F←G∈Π｝。

注意到ΠI是一個(gè)不含not及not not聯(lián)結(jié)詞的程序。這樣的程序也稱(chēng)為基本程序。類(lèi)似地，若Π是一個(gè)基本程序，則Cn（Π）指滿足Π的極小原子集合（又稱(chēng)演繹封閉）。例如，滿足程序｛x2←x1，x1←，x3←x3｝的極小原子集為｛x1，x2｝。不難看出，任何一個(gè)基本程序Π的演繹封閉Cn（Π）是唯一的。

令Π為NLP程序，I為原子集合，若I=Cn（ΠI），則稱(chēng)I是Π的回答集。為方便，無(wú)論是CCP程序還是NLP程序Π，我們記Ans（Π）為程序Π的回答集的集合。

例5對(duì)程序Π=｛x←not not x｝，我們有Ans（Π）=｛?，｛x｝｝。因Cn（Π?）= Cn（?）=?；Cn（Π｛x｝）=Cn（｛x←｝）=｛x｝，且Π沒(méi)有其它回答集。此外，不難看出程序｛x←x｝僅有一個(gè)回答集?！這意味著在NLP回答集語(yǔ)義下，兩個(gè)相鄰的弱否定not并不能夠直接抵消。

2.3問(wèn)題的表示及簡(jiǎn)潔性

一個(gè)（二元）字符串是｛0，1｝組成的有窮序列。長(zhǎng)度為n的字符串w（即w∈｛0，1｝n），可記為w1w2...wn，其中wi∈｛0，1｝（i=1，2，...，n）。一個(gè)長(zhǎng)度為n的字符串w可看成原子集合｛x1，...，xn｝的子集。例如，1010表示｛x1，x3｝，其中n=4。

一個(gè)問(wèn)題L是一個(gè)字符串的集合。

定義1［6，12］給定一個(gè)問(wèn)題L和邏輯程序系統(tǒng)C，若C中存在程序公式序列｛Πn|n=1，2，...｝，使得對(duì)于每個(gè)字符串w∈｛0，1｝n，有

則稱(chēng)L可以由C表示（L∈C）。若L∈C且|Πn|≤p（n），其中p（n）為某個(gè)多項(xiàng)式，則稱(chēng)L在C中有多項(xiàng)式長(zhǎng)度的表示（L∈Poly-C）。

定義2（［4，6，12］） 已知C和C′是兩個(gè)邏輯程序系統(tǒng)，若對(duì)每個(gè)問(wèn)題L，

·L∈C?L∈C′，且

·L∈Poly-C′?L∈Poly-C。

則稱(chēng)C至少與C′一樣簡(jiǎn)潔（C′?C）。若L∈Poly-C但L/∈Poly-C′，則稱(chēng)L將C從C′中分離（CC′）。若C′?C且CC′，則稱(chēng)C嚴(yán)格比C′簡(jiǎn)潔（C′?C）。

例6為理解簡(jiǎn)潔性的直觀含義，我們以命題邏輯為例進(jìn)行介紹。命題公式（Propositional Formulas，PF）是建立在原子集合和連接詞∨，∧，?，←，?上的表達(dá)式，我們可將經(jīng)典地滿足命題公式的原子集視為模型（或回答集）。在上述約定下：（i）PF嚴(yán)格比僅含聯(lián)結(jié)詞∨，∧，?的合取范式（Conjunctive Normal Form，CNF）簡(jiǎn)潔。因?yàn)橐话愣詫⒚}公式等價(jià)地轉(zhuǎn)換成合取范式將導(dǎo)致公式長(zhǎng)度（即聯(lián)結(jié)詞個(gè)數(shù)）指數(shù)增長(zhǎng)1更準(zhǔn)確地說(shuō)，我們可以找到一個(gè)問(wèn)題，使得該問(wèn)題在PF中可以用長(zhǎng)度多項(xiàng)式增長(zhǎng)的公式序列表示，但該問(wèn)題在CNF中無(wú)法用長(zhǎng)度多項(xiàng)式增長(zhǎng)的公式序列表示。；而合取范式本身就是特殊的命題公式。（ii）合取范式與析取范式（Disjunctive Normal Form，DNF）簡(jiǎn)潔性是不可比較的。因?yàn)槎叩南嗷サ葍r(jià)翻譯一般情況下都導(dǎo)致公式長(zhǎng)度指數(shù)增長(zhǎng)。更多的例子可見(jiàn)［4，6，12］。

2.4CCP及NLP與命題邏輯的等價(jià)性

我們之前提及CCP和NLP與命題邏輯是等價(jià)的，即它們有相同的表示能力，可以表示任意命題模型集/問(wèn)題。本節(jié)簡(jiǎn)要討論它們之間的等價(jià)構(gòu)造。

先考慮從命題邏輯公式到程序的轉(zhuǎn)換。令?為一個(gè)固定字母表Σ上的CNF公式：

其中l(wèi)i，j為Σ上的經(jīng)典命題邏輯文字。

·構(gòu)造等價(jià)于?的CCP程序。對(duì)每一個(gè)x∈Σ，引入規(guī)則

對(duì)于每個(gè)?的子句（li，1∨···∨li，j），引入規(guī)則

其中||li，k||是將li，k中可能出現(xiàn)的?替換成not得到的文字。根據(jù)［10，13］中CCP的語(yǔ)義，不難看出得到的CCP程序與?是等價(jià)的，即有相同的模型（回答集）。因?yàn)椋?）的功能是任意選擇x的真假，（7）則表達(dá)子句的約束功能，直觀上，（7）的含義是若一個(gè)子句中無(wú)被滿足的文字，則去掉該回答集。

·構(gòu)造等價(jià)于?的NLP程序。對(duì)每一個(gè)x∈Σ，引入規(guī)則

對(duì)于每個(gè)?的子句（li，1∨···∨li，j），引入規(guī)則

其中||li，k||是將li，k中可能出現(xiàn)的?替換成not得到的文字。根據(jù)［9］中

NLP的語(yǔ)義，不難看出得到的NLP程序與?是等價(jià)的，即有相同的模型

（回答集）。因?yàn)椋?），（9）分別與（6），（7）類(lèi)似，不再詳細(xì)解釋。

對(duì)于從CCP和NLP程序等價(jià)構(gòu)造命題公式，可從語(yǔ)義的角度考慮。比如，令程序Π的全部回答集為｛S1，...，Sn｝，其中Si?Σ為原子集｛xi，1，...，xi，j｝。我們很容易構(gòu)造一個(gè)等價(jià)的DNF，其每個(gè)合取子句對(duì)應(yīng)一個(gè)Si，具體為：

其中｛yi，1，...，yi，k｝=ΣSi。

由上述討論可知，CCP和NLP與命題邏輯具有相同的表達(dá)能力。不過(guò)，從邏輯程序到命題邏輯的等價(jià)語(yǔ)法轉(zhuǎn)換是一個(gè)較復(fù)雜的過(guò)程，有興趣的讀者可參考［2］。

3　Ferraris和Lifschitz指數(shù)增長(zhǎng)的等價(jià)翻譯

本節(jié)中我們回顧Ferraris和Lifschitz提出的從CCP程序到NLP程序的等價(jià)翻譯（［3］），并將通過(guò)分析指出該方法可導(dǎo)致翻譯結(jié)果的指數(shù)增長(zhǎng)。

對(duì)文字c1，...，cm和｛1，...，m｝的子集的集合X（即X?2｛1，...，m｝），定義〈c1，...，cm〉：X為以下NLP公式：

例如，X=｛｛1，2｝，｛2，3｝，｛1，3｝｝，則〈c1，c2，c3〉：X為公式（c1，c2）；（c2，c3）；（c1，c3）。不難看出本例中X是｛1，2，3｝所有元素個(gè)數(shù)≥2的子集的集合。因此，該公式直觀含義為文字c1，c2，c3中至少有兩個(gè)為真。換句話說(shuō)，對(duì)任意原子集I，I滿足該公式當(dāng)且僅當(dāng)I滿足c1，c2，c3中至少兩個(gè)文字。

值得指出的是，記法〈c1，...，cm〉：X所指的公式（10）本質(zhì)上是一種對(duì)基數(shù)約束的直接枚舉，其長(zhǎng)度一般而言相對(duì)于m是指數(shù)大的。比如，根據(jù)組合原理中常用的Stirling不等式，｛1，...，m｝所有m/2個(gè)元素的子集的個(gè)數(shù)這說(shuō)明若使用公式（10）表達(dá)c1，...，cm有一半文字為真，則公式中聯(lián)結(jié)詞的個(gè)數(shù)將

在上述定義的基礎(chǔ)上，我們介紹Ferraris和Lifschitz的翻譯方法如下：

1.基數(shù)約束L≤｛c1，...，cm｝的翻譯是〈c1，...，cm〉：｛Y?｛1，...，m｝：

L≤|Y|｝。為方便，記L≤S的翻譯為［L≤S］。

2.基數(shù)約束｛c1，...，cm｝≤U的翻譯是not（〈c1，...，cm〉：｛Y?｛1，...，m｝：

U＜|Y|｝）。為方便，記S≤U的翻譯為［S≤U］。

3.基數(shù)約束L≤S≤U的翻譯是［L≤S］，［S≤U］。

4.對(duì)任意CCP程序?，其翻譯［?］是將?中每一條形如C←C1，...，Cn的

規(guī)則改寫(xiě)為以下p+1條規(guī)則：

·cj←not not cj，［C1］，...，［Cn］（1≤j≤p）

·⊥←not［C］，［C1］，...，［Cn］.

而得到的，其中c1，...，cp是C中出現(xiàn)的所有正文字。

定理1（［3］） 令?為一個(gè)CCP程序，?與［?］有相同的回答集。

此定理說(shuō)明上述翻譯是等價(jià)的。不過(guò)由于翻譯的第1，2步涉及到聯(lián)結(jié)詞個(gè)數(shù)的指數(shù)增長(zhǎng)，所以該方法可導(dǎo)致整體翻譯長(zhǎng)度指數(shù)增長(zhǎng)。下面進(jìn)行具體些的分析。考慮如下問(wèn)題：

簡(jiǎn)單地說(shuō)，HALF是所有那些恰有一半字符（向上取整）為1的字符串的集合。不難看出，可用CCP程序序列｛?n|n=1，2，...，｝表示HALF，其中每個(gè)?n僅含一條規(guī)則：根據(jù)之前的討論，翻譯所得的［?n］將含有個(gè)聯(lián)結(jié)詞。以下命題顯然。

命題1存在CCP程序序列｛?n|n=1，2，...，｝，其對(duì)應(yīng)的NLP程序序列｛［?n］|n=1，2，...，｝，每一個(gè)［?n］的長(zhǎng)度

換言之，在極端情況下，F(xiàn)erraris及Lifschitz的等價(jià)翻譯是長(zhǎng)度指數(shù)增長(zhǎng)的。因此，該方法并沒(méi)有對(duì)CCP與NLP的相對(duì)簡(jiǎn)潔性給出明確結(jié)論。

4　NLP至少與CCP一樣簡(jiǎn)潔

本節(jié)中我們將構(gòu)建從CCP到NLP的多項(xiàng)式等價(jià)翻譯，由此證明NLP至少與CCP一樣簡(jiǎn)潔。我們將首先為基數(shù)約束引入一種多項(xiàng)式增長(zhǎng)的命題公式等價(jià)翻譯，其核心思路來(lái)源于布爾電路設(shè)計(jì)理論（［11，14］）。

4.1布爾電路和命題公式

定義3（［11，14］） 布爾電路是一個(gè)有向無(wú)環(huán)圖，其中結(jié)點(diǎn)為標(biāo)記了∧，∨，?的門(mén)或布爾變?cè)獂1，x2，...或常元0，1。結(jié)點(diǎn)的入度（或出度）為指向（或離開(kāi)）該結(jié)點(diǎn)的邊的個(gè)數(shù)。電路的輸入為布爾變?cè)虺Ｔ?，1，其入度為0。輸出為出度為0的門(mén)。但為方便，也常在輸出處標(biāo)上無(wú)后繼的指示箭頭。

簡(jiǎn)單地說(shuō)，電路ψ在輸入x1，...，xn下的值，記為ψ（x1，...，xn），是將輸入與電路中的門(mén)通過(guò)連續(xù)布爾運(yùn)算得到的結(jié)果。電路ψ的大小|ψ|為ψ中門(mén)的總數(shù)。如果ψ只有一個(gè)輸出且每個(gè)門(mén)的出度為1，那么電路ψ本質(zhì)上是一個(gè)命題公式。此時(shí)，可將原子集I?｛x1，...，xm｝視為輸入，即xi∈I當(dāng)且僅當(dāng)xi=1。我們定義I|=Pψ如果ψ（I）=1，否則I?Pψ。不難看出，|=P本質(zhì)上是經(jīng)典命題邏輯的可滿足關(guān)系。

圖1是一個(gè)電路例子，易見(jiàn)ψ（｛x1｝）=ψ（1，0）=1，因此｛x1｝|=Pψ。又如ψ（｛x1，x2｝）=ψ（1，1）=0，所以｛x1，x2｝?Pψ。

命題2令ψ為由∨，∧，?構(gòu)成的經(jīng)典命題邏輯公式，?′為將ψ中的∨，∧，?對(duì)應(yīng)替換成；，not得到的NLP公式。則對(duì)于任意原子集I，

證明.據(jù)NLP公式的可滿足性定義顯然可得。

圖1　：布爾電路ψ=（?x1∧x2）∨（x1∧?x2）

4.2基于電路方法的基數(shù)約束等價(jià)翻譯

我們先將形如L≤｛c1，...，cm｝≤U的基數(shù)約束翻譯成NLP公式：

1.對(duì)基數(shù)約束L≤｛c1，...，cm｝，若m＜L，則翻譯成⊥，否則，翻譯成電路

其中l(wèi)i=xi，如果ci是正文字（原子）xi，li=?xi，如果ci是負(fù)文字not xi。另外，wL是L的二進(jìn)制數(shù)，長(zhǎng)度為「log2（m+1）」，不足位用0補(bǔ)充。特別地，構(gòu)建wL時(shí)，可用xi∨?xi表示1，xi∧?xi表示0，其中xi是任意原子。最后，將（13）中所有∧，∨，?門(mén)分別替換成，；not，記結(jié)果為［［L≤S］］，其中S=｛c1，...，cm｝。顯然，［［L≤S］］是一個(gè)NLP公式。一個(gè)簡(jiǎn)單的基數(shù)約束1≤｛x1，not x2｝電路可見(jiàn)圖2（a）。

2.對(duì)基數(shù)約束｛c1，...，cm｝≤U，若m＜U，則翻譯成?，否則，翻譯成電路

其中l(wèi)i=xi，如果ci是正文字（原子）xi，li=?xi，如果ci是負(fù)文字not xi。另外，wU是U的二進(jìn)制數(shù)，長(zhǎng)度為「log2（m+1）」，不足位用0補(bǔ)充。同理，構(gòu)建wU時(shí)，可用xi∨?xi表示1，xi∧?xi表示0，其中xi是任意原子。最后，將（14）中所有∧，∨，?門(mén)分別替換成，；not，記結(jié)果為［［S≤U］］，其中S=｛c1，...，cm｝。顯然，［［S≤U］］是一個(gè)NLP公式。一個(gè)簡(jiǎn)單的基數(shù)約束｛x1，not x2｝≤2電路可見(jiàn)圖2（b）。注意，［［S≤U］］以兩個(gè)弱否定詞not not開(kāi)頭，在NLP的回答集語(yǔ)義下，兩個(gè)相鄰的弱否定詞并不能相互抵消。

3.對(duì)于基數(shù)約束L≤S≤U，翻譯成NLP公式（［［L≤S］］，［［S≤U］］），也記作［［L≤S≤U］］。

命題3令I(lǐng)為一個(gè)原子集，對(duì)任意基數(shù)約束L≤S≤U，其中S= ｛c1，...，cn｝是一個(gè)文字集，我們有

其中［［L≤S≤U］］相對(duì)于n為多項(xiàng)式大小，即|［［L≤S≤U］］|∈O（nk），k∈N。

證明.根據(jù)相關(guān)可滿足關(guān)系定義以及對(duì)應(yīng)的電路語(yǔ)義，不難看出：

圖2　：基數(shù)約束1≤｛x1，not x2｝和｛x1，not x2｝≤2的電路圖示

I|=L≤S≤U當(dāng)且僅當(dāng)L≤v（L≤S≤U，I）≤U，

當(dāng)且僅當(dāng)L≤|｛c∈S：I|=c｝|≤U，

下面對(duì)［［L≤S≤U］］公式的大小進(jìn)行分析。首先［［L≤S］］的大小由電路，電路及wL電路構(gòu)成決定，根據(jù)定理2和定理3，前兩個(gè)電路大小分別為O（nk1），及O（「log2（n+1）」k2），k1，k2∈N。不難看出wL電路大小為O（n），因此［［L≤S］］大小為O（nk1）+O（「log2（n+1）」k2）+O（n）。同理，容易看出［［S≤U］］的大小為O（nk1）+O（「log2（n+1）」k2）+O（n）+2。整個(gè)［［L≤S≤U］］公式由上述兩部分電路合取得到，根據(jù)復(fù)雜性分析原理忽略次要量，則公式總大小為O（nk），k∈N，即多項(xiàng)式大小。

4.3從CCP到NLP的多項(xiàng)式等價(jià)翻譯

利用上一小節(jié)的基數(shù)約束多項(xiàng)式等價(jià)翻譯，我們現(xiàn)在構(gòu)造從CCP程序到NLP程序的多項(xiàng)式等價(jià)翻譯。

令?為任意CCP程序，令［［?］］為將?中每一條形如C←C1，...，Cn的規(guī)則改寫(xiě)為以下p+1條規(guī)則：

得到的NLP程序，其中c1，...，cp是C中出現(xiàn)的所有正文字。

命題4令?為任意CCP程序，則［［?］］相對(duì)于?為多項(xiàng)式長(zhǎng)度，即|［［?］］|∈O（|?|k），k∈N。

證明.記?的長(zhǎng)度，即其中含有基數(shù)約束的個(gè)數(shù)為n。因每條CCP規(guī)則至少含有一個(gè)基數(shù)約束，所以?中規(guī)則條數(shù)為O（n）。注意?和［［?］］使用固定的字母表（翻譯過(guò)程不引入輔助變?cè)?，其大小記為O（1）。那么，?中的正文字也最多為O（1）個(gè)。由上可知，［［?］］中規(guī)則的個(gè)數(shù)是O（n）?（p+1）=O（n）?（O（1）+1）=O（n）。同時(shí)，每個(gè)規(guī)則中最多有O（n）個(gè)基數(shù)約束對(duì)應(yīng)翻譯得到的NLP公式，據(jù)命題3，此類(lèi)NLP公式的大小是O（nk），k∈N。因此，［［?］］中由基數(shù)約束翻譯得到NLP公式的總大小為O（n）?O（n）?O（nk），注意在（15）和（16）中除基數(shù)翻譯外使用的not個(gè)數(shù)為O（n）?O（1）。最終，［［?］］的大小，即其中含有的聯(lián)結(jié)詞個(gè)數(shù)為O（nk+2）+O（n）?O（1）=O（nk+2），為多項(xiàng)式大小。

注意，無(wú)論?的組成如何，［［?］］總由形如（15）和（16）的規(guī)則組成。為方便，我們記（15）部分的規(guī)則為?1，記（16）部分的規(guī)則為?2，則［［?］］=?1∪?2。即，我們把NLP程序［［?］］中的規(guī)則劃分成兩部分，一部分是以原子開(kāi)頭的規(guī)則，另一部分是⊥開(kāi)頭的（限制）規(guī)則。對(duì)于這個(gè)區(qū)分，我們可直接應(yīng)用［9］中的一個(gè)一般結(jié)論。

引理1（［9］） 一個(gè)原子集I是［［?］］的回答集，當(dāng)且僅當(dāng)I是?1的回答集且I|=N?2。

引理2對(duì)任意原子集I，I|=?當(dāng)且僅當(dāng)I|=N?2。

證明.為方便，考慮?中僅有一條規(guī)則C←C1，...，Cn。此時(shí)，I|=?當(dāng)且僅當(dāng)

另外，I|=N?2當(dāng)且僅當(dāng)

據(jù)命題3，條件（?）與（??）是等價(jià)的（當(dāng)且僅當(dāng)關(guān)系成立）。注意?含有多條規(guī)則的情形也類(lèi)似。因此，命題得證。

引理3對(duì)任意兩個(gè)原子集合I，I′和基數(shù)約束L≤S，則

證明.根據(jù)［［L≤S］］的構(gòu)造語(yǔ)義和歸約（L≤S）I的定義，不難看出：

I′|=N［［L≤S］］I當(dāng)且僅當(dāng)L≤|｛c∈S：I′|=NcI｝|，

當(dāng)且僅當(dāng)L≤|｛c∈S：I′|=cI｝|，

當(dāng)且僅當(dāng)L?|｛c∈S：I′|=cI且cI=?｝|

≤|｛c∈S：I′|=cI且cI=c｝|，

當(dāng)且僅當(dāng)I′|=（L≤S）I。

引理4對(duì)任意原子集合I，基數(shù)約束S≤U，則

證明.首先，注意到本文翻譯方法中，［［S≤U］］是一個(gè)以not開(kāi)頭的NLP公式，據(jù)2.2節(jié)中的定義，其相對(duì)于I歸約要么為?，要么為⊥。更準(zhǔn)確地說(shuō)：

進(jìn)一步地，根據(jù)命題3，I|=N［［S≤U］］當(dāng)且僅當(dāng)I|=S≤U。原題得證。

引理5對(duì)任意原子集I，I′，I′|=?I當(dāng)且僅當(dāng)I′|=N?I1。

證明.為方便，考慮?中僅有一條規(guī)則

的規(guī)則組成，其中c∈S為S中的正文字?？紤]以下情形：

·對(duì)任意i，1≤i≤n，都有I|=Si≤Ui。據(jù)引理4，每個(gè)［［Li≤Si］］I均為?。此外，如果c/∈I那么（not not c）I為⊥，I′顯然滿足（17）。因此，I′|=N當(dāng)且僅當(dāng)對(duì)任意I中正文字c

另一方面，據(jù)CCP歸約的定義，?I由所有形如

的規(guī)則組成，其中c∈S為S中的正文字。因此，I′|=?I當(dāng)且僅當(dāng)對(duì)任意I中正文字c

顯然，據(jù)引理3，這與條件（18）是等價(jià)的。

·存在i，1≤i≤n使得I?Si≤Ui。據(jù)引理4，［［Li≤Si］］I為⊥，因此

I′|=N?I1。另一方面，此情況下?I為空集，顯然I′|=?I。

?中含有多條規(guī)則的情況類(lèi)似。原題得證。

引理6對(duì)任意原子集I，I=Cn（?I）當(dāng)且僅當(dāng)I=Cn（）。

證明.注意，?I及均為不帶not的程序，Cn（·）被定義成為滿足這些程序的極小原子集。據(jù)引理5，?I及總被相同的原子集滿足，命題得證。

定理4（翻譯的等價(jià)性） 令?為任意CCP程序，則?與［［?］］具有相同的回答集。

證明.據(jù)CCP回答集的定義，一個(gè)原子集I是?的回答集，當(dāng)且僅當(dāng)

據(jù)引理6和2，上述條件等價(jià)于

據(jù)引理1，上述條件意味著I是［［?］］的回答集。

定理5（主定理CCP?NLP） NLP至少與CCP一樣簡(jiǎn)潔。

證明.據(jù)定理4及命題4，每一個(gè)CCP程序?，都存在一個(gè)等價(jià)的NLP程序［［?］］，使得|［［?］］|≤p（|?|），其中p是一個(gè)多項(xiàng)式函數(shù)。因此，對(duì)于任意CCP程序的序列｛?n|n∈N｝，其中|?n|≤q（n），q為一個(gè)多項(xiàng)式函數(shù)，總是存在等價(jià)的NLP程序序列｛［［?］］n|n∈N｝，使得|［［?］］n|≤p（q（n））。注意p（q（n））仍為多項(xiàng)式函數(shù)。這意味著對(duì)任何語(yǔ)言L，L∈Poly-CCP?L∈Poly-NLP。又，CCP與NLP是邏輯等價(jià)的，據(jù)定義2，NLP至少與CCP一樣簡(jiǎn)潔，即CCP?NLP。

5　結(jié)語(yǔ)

在本文中，我們提供了一個(gè)從CCP程序到NLP程序的多項(xiàng)式長(zhǎng)度等價(jià)翻譯方法。該方法改進(jìn)了Ferraris和Lifschitz的結(jié)果，并意味著NLP至少與CCP一樣簡(jiǎn)潔。這為進(jìn)一步研究ASP以及不同類(lèi)別的邏輯程序之間的關(guān)系提供了新的進(jìn)展。據(jù)我們所知，CCP是否至少與NLP一樣簡(jiǎn)潔依舊是開(kāi)問(wèn)題。典范邏輯程序（CP）作為NLP的子類(lèi)，要求每條規(guī)則中的前提只能是規(guī)則元素（a，not a，not not a）合取的形式。CCP與CP之間的關(guān)系也引起了我們的興趣，［12］指出存在PARITY問(wèn)題，使得PARITY∈Poly-CCP，但PARITY/∈Poly-CP，即CCPCP。CCP似乎嚴(yán)格比CP簡(jiǎn)潔，但這需要我們進(jìn)一步研究。

［1］ G.Brewka，T.EiterandM.Truszczynski，2011，“Answersetprogrammingataglance”，Communications of the ACM，54（12）：92-103.

［2］ P.Ferraris，J.Lee and V.Lifschitz，2006，“A generalization of the Lin-Zhao theorem”，Annals of Mathematics and Artificial Intelligence，47（1-2）：79-101.

［3］ P.Ferraris and V.Lifschitz，2005，“Weight constraints as nested expressions”，Theory and Practice of Logic Programming，5（1-2）：45-74.

［4］ T.French，W.van der Hoek，P.Iliev and B.Kooi，2013，“On the succinctness of some modal logics”，Artificial Intelligence，197：56-85.

［5］ M.Gelfond and V.Lifschitz，1988，“The stable model semantics for logic programming”，in R.Kowalski and K.Bowen（eds.），Proceedings of International Logic Programming Conference and Symposium，pp.1070-1080，Seattle，WA：MIT Press.

［6］ G.Gogic，H.A.Kautz，C.H.Papadimitriou and B.Selman，1988，“The comparative linguistics of knowledge representation”，in C.Mellish（ed.），Proceedings of the 14th International Joint Conference on Artificial Intelligence，pp.862-869，San Fransisco，CA，USA：Morgan Kaufmann Publishers Inc.

［7］ V.Lifschitz，2008，“What is answer set programming？”，in A.Cohn（ed.），Proceedings of the 23rd National Conference on Artificial Intelligence，Vol.3，pp.1594-1597，Chicago，IL：AAAI Press.

［8］ V.Lifschitz and A.Razborov，2006，“Why are there so many loop formulas？”，ACM Transactions on Computational Logic，7（2）：261-268.

［9］ V.Lifschitz，L.R.Tang and H.Turner，1999，“Nested expressions in logic programs”，Annals of Mathematics and Artificial Intelligence，25：369-389.

［10］ I.Niemela and P.Simons，2001，“Extending the smodels system with cardinality and weight constraints”，Logic-based Artificial Intelligence，597（14）：491-521.

［11］ J.E.Savage，1998，Models of Computation：Exploring the Power of Computing，Addison Wesley Longman Publishing Co.Inc.

［12］ Y.Shen and X.Zhao，2014，“Canonical logic programs are succincly incomparable with propositional formulas”，in C.Baral，G.Giacomo and T.Eiter（eds.），Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning，Vol.3，pp.665-668，Vienna，Austria：MIT Press.

［13］ P.Simons，I.Niemela and T.Soininen，2002，“Extending and implementing the stable model semantics”，Artificial Intelligence，138（1-2）：181-234.

［14］ I.Wegener，1987，The Complexity of Boolean Functions，John Wiley and Sons Inc.

（責(zé)任編輯：羅心澄）

Abstract

Simply speaking，succinctness means the ability of a logical system to compactly represent a problem.Recently，the study of succinctness has gained a lot of attention.In this paper，we will discuss the succinctness between two classes of logic programs，that is，cardinality constraint programs（CCP）and nested logic programs（NLP）.We prove that NLP is at least as succinct as CCP，it means every CCP program can be equivalently translated into a NLP program within polynomial-size growth.This significantly improves the result of Ferraris and Lifschitz，which states that every CCP program can be equivalently translated into an exponential-size NLP program.

On the Succinctness of Logic Programs with Nested Bodies and Cardinality Constraints

Yan Zhang
Institute of Logic and Cognition，Sun Yat-sen University zhang85@mail2.sysu.edu.cn
Yuping Shen
Institute of Logic and Cognition，Sun Yat-sen University shyping@mail.sysu.edu.cn
Xishun Zhao
Institute of Logic and Cognition，Sun Yat-sen University hsszxs@mail.sysu.edu.cn

B81

A

2015-03-05；

2016-05-06

本文受?chē)?guó)家社會(huì)科學(xué)基金青年項(xiàng)目《邏輯系統(tǒng)的簡(jiǎn)潔性研究》（14CZX058）資助。

?致謝：感謝審稿人對(duì)本文的幫助。趙希順為本文通訊作者。