Bağlaç normal formu - Conjunctive normal form

Gelen Boole mantığı , bir formül olan birleşik normal form ( CNF ) ya da Clausal normal formda eğer bu bir birlikte , bir ya da daha fazla maddeleri bir madde a,, ayrılma ve değişmez ; aksi halde , toplamların veya VE VEYA'ların bir çarpımıdır . Bir şekilde standart normal formda , bu yararlıdır otomatik teoremi ispatı ve devre teorisi .

Sırasıyla, tek harfli tümcelerin bağlaçları ve tek bir tümcenin bağlaçları olarak görülebileceğinden, tüm değişmezlerin bağlaçları ve değişmezlerin tüm ayrımları CNF'dedir. Ayırıcı normal formda (DNF) olduğu gibi, CNF'de bir formülün içerebileceği tek önermesel bağlaçlar ve , veya , ve değil . not operatörü yalnızca bir değişmezin parçası olarak kullanılabilir; bu, yalnızca bir önerme değişkeninden veya bir yüklem sembolünden önce gelebileceği anlamına gelir .

Otomatik teorem kanıtlamada, " kümülatif normal biçim " kavramı genellikle daha dar bir anlamda kullanılır, yani bir CNF formülünün bir dizi değişmez değer kümesi olarak belirli bir temsili anlamına gelir.

Örnekler ve örnek olmayanlar

Değişkenler aşağıdaki formüllerin bütün ve birleşik normal formda bulunmaktadır: ${\görüntüleme stili A,B,C,D,E}$${\görüntüleme stili F}$

• ${\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F)}$
• ${\ Displaystyle (A\lor B)\land (C)}$
• ${\görüntüleme stili (A\lor B)}$
• ${\görüntüleme stili (A)}$

Açıklık sağlamak için, ayırıcı cümleler yukarıda parantez içinde yazılmıştır. Gelen disjunctive Normal formda parantez konjünktif maddeleri ile, son durum aynı, fakat sonuncu yanındadır . true ve false sabitleri , boş bağlaç ve boş ayrılmadan oluşan bir yan tümce ile gösterilir, ancak normalde açıkça yazılır. ${\görüntüleme stili (A)\lor (B)}$

Aşağıdaki formüller değil birleşik normal formda:

• ${\displaystyle \neg (B\lor C)}$, bir VEYA bir DEĞİL içinde yuvalandığından
• ${\ Displaystyle (A\land B)\lor C}$
• ${\ Displaystyle A\land (B\lor (D\land E))}$, VE bir VEYA içinde yuvalandığından

Her formül, birleşik normal biçimde bir formül olarak eşdeğer olarak yazılabilir. CNF'de olmayan üç örnek şunlardır:

• ${\displaystyle (\neg B)\land (\neg C)}$
• ${\ Displaystyle (A\lor C)\land (B\lor C)}$
• ${\displaystyle (A)\land (B\lor D)\land (B\lor E).}$

CNF'ye dönüştürme

Her önerme formülü , CNF'de bulunan eşdeğer bir formüle dönüştürülebilir . Bu dönüşüm, mantıksal denkliklerle ilgili kurallara dayanmaktadır : çifte olumsuzlamanın ortadan kaldırılması , De Morgan yasaları ve dağıtım yasası .

Tüm önerme formülleri, birleştirici normal formda eşdeğer bir formüle dönüştürülebildiğinden, ispatlar genellikle tüm formüllerin CNF olduğu varsayımına dayanır. Bununla birlikte, bazı durumlarda CNF'ye bu dönüşüm, formülün üstel bir patlamasına yol açabilir. Örneğin, aşağıdaki CNF olmayan formülün CNF'ye çevrilmesi, yan tümceler içeren bir formül üretir : ${\ Displaystyle 2^{n}}$

${\displaystyle (X_{1}\wedge Y_{1})\vee (X_{2}\wedge Y_{2})\vee \dots \vee (X_{n}\wedge Y_{n}).}$

Özellikle, oluşturulan formül:

${\displaystyle (X_{1}\vee X_{2}\vee \cdots \vee X_{n})\wedge (Y_{1}\vee X_{2}\vee \cdots \vee X_{n})\ kama (X_{1}\vee Y_{2}\vee \cdots \vee X_{n})\kama (Y_{1}\vee Y_{2}\vee \cdots \vee X_{n})\wedge \ cdots \kama (Y_{1}\vee Y_{2}\vee \cdots \vee Y_{n}).}$

Bu formül tümceleri içerir ; her madde ya da her birini içerir . ${\ Displaystyle 2^{n}}$${\displaystyle X_{i}}$${\görüntüleme stili Y_{i}}$${\görüntüleme stili ben}$

Eşdeğerlik yerine tatmin ediciliği koruyarak boyutta üstel bir artıştan kaçınan CNF'ye dönüşümler vardır . Bu dönüşümlerin formülün boyutunu yalnızca doğrusal olarak artırması garanti edilir, ancak yeni değişkenler ortaya çıkar. Örneğin, yukarıdaki formül aşağıdaki gibi değişkenler eklenerek CNF'ye dönüştürülebilir : ${\displaystyle Z_{1},\ldots ,Z_{n}}$

${\displaystyle (Z_{1}\vee \cdots \vee Z_{n})\wedge (\neg Z_{1}\vee X_{1})\wedge (\neg Z_{1}\vee Y_{1} )\wedge \cdots \kama (\neg Z_{n}\vee X_{n})\kama (\neg Z_{n}\vee Y_{n}).}$

Bir yorum, bu formülü ancak yeni değişkenlerden en az birinin doğru olması durumunda karşılar. Bu değişken ise , o zaman hem ve hem de doğrudur. Bu, bu formülü sağlayan her modelin orijinalini de sağladığı anlamına gelir . Öte yandan, orijinal formülün sadece bazı modelleri bunu karşılar: orijinal formülde bahsedilmediğinden, değerleri onu tatmin etmekle ilgisizdir, son formülde durum böyle değildir. Bu, orijinal formülün ve çevirinin sonucunun eşdeğer olduğu, ancak eşdeğer olmadığı anlamına gelir . ${\displaystyle Z_{i}}$${\displaystyle X_{i}}$${\görüntüleme stili Y_{i}}$${\displaystyle Z_{i}}$

Alternatif bir çeviri olan Tseitin dönüşümü , cümleleri de içerir . Bu maddeler ile formül ; bu formül genellikle "tanımlamak" için bir ad olarak kabul edilir . ${\displaystyle Z_{i}\vee \neg X_{i}\vee \neg Y_{i}}$${\displaystyle Z_{i}\eşdeğer X_{i}\kama Y_{i}}$${\displaystyle Z_{i}}$${\displaystyle X_{i}\kama Y_{i}}$

Birinci dereceden mantık

Birinci dereceden mantıkta, daha sonra birinci dereceden çözünürlüğü gerçekleştirmek için kullanılabilecek bir mantıksal formülün yan tümceli normal formunu elde etmek için birleştirici normal form daha ileri alınabilir . Çözünürlük tabanlı otomatik teorem kanıtlamada, bir CNF formülü

${\görüntüleme stili (}$

${\görüntüleme stili l_{11}}$

${\görüntüleme stili \lor }$

${\görüntüleme stili \ldotlar }$

${\görüntüleme stili \lor }$

${\displaystyle l_{1n_{1}}}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \ldotlar }$

${\ Displaystyle \ arazi }$

${\görüntüleme stili (}$

${\displaystyle l_{m1}}$

${\görüntüleme stili \lor }$

${\görüntüleme stili \ldotlar }$

${\görüntüleme stili \lor }$

${\displaystyle l_{mn_{m}}}$

${\görüntüleme stili )}$

, değişmez değerlerle, genellikle bir dizi küme olarak temsil edilir ${\displaystyle l_{ij}}$

${\görüntüleme stili \{}$

${\görüntüleme stili \{}$

${\görüntüleme stili l_{11}}$

${\görüntüleme stili,}$

${\görüntüleme stili \ldotlar }$

${\görüntüleme stili,}$

${\displaystyle l_{1n_{1}}}$

${\görüntüleme stili\}}$

${\görüntüleme stili,}$

${\görüntüleme stili \ldotlar }$

${\görüntüleme stili,}$

${\görüntüleme stili \{}$

${\displaystyle l_{m1}}$

${\görüntüleme stili,}$

${\görüntüleme stili \ldotlar }$

${\görüntüleme stili,}$

${\displaystyle l_{mn_{m}}}$

${\görüntüleme stili\}}$

${\görüntüleme stili\}}$

.

Bir örnek için aşağıya bakın .

hesaplama karmaşıklığı

Hesaplama karmaşıklığındaki önemli bir problem seti , formül doğru olacak şekilde Bağlaç Normal Formda ifade edilen bir boole formülünün değişkenlerine atamalar bulmayı içerir. K -SAT sorun, her ayrılma en ihtiva ettiği CNF'den ifade edilen bir Boole formülüne bir tatmin atama bulma sorunudur k değişkenlerinin. 3-SAT , NP-tamamlanmıştır ( k >2 ile diğer tüm k -SAT problemleri gibi ), 2-SAT'ın ise polinom zamanında çözümlere sahip olduğu bilinmektedir . Sonuç olarak, bir formülü bir DNF'ye dönüştürme , tatmin ediciliği koruma görevi NP-zordur ; ikili olarak , CNF'ye dönüştürmek, geçerliliği korumak , aynı zamanda NP-zordur; dolayısıyla DNF veya CNF'ye eşdeğerliği koruyan dönüşüm yine NP-zordur.

Bu durumda tipik problemler, "3CNF"deki formülleri içerir: konjonkt başına üçten fazla değişken olmayan konjonktif normal form. Uygulamada karşılaşılan bu tür formüllerin örnekleri, örneğin 100.000 değişken ve 1.000.000 bağlaç ile çok büyük olabilir.

CNF bir formül "bir equisatisfiable formül dönüştürülebilir k için (CNF" k fazla olan her bir kavuşum değiştirerek ≥3) k değişkenlerinin iki conjuncts ile ve ile Z yeni bir değişken ve gerekli sıklıkta tekrar etmek. ${\displaystyle X_{1}\vee \cdots \vee X_{k}\vee \cdots \vee X_{n}}$${\displaystyle X_{1}\vee \cdots \vee X_{k-1}\vee Z}$${\displaystyle \neg Z\vee X_{k}\cdots \vee X_{n}}$

Birinci dereceden mantıktan dönüştürme

Birinci dereceden mantığı CNF'ye dönüştürmek için:

1. Olumsuzlama normal biçimine dönüştürün .
   1. Etkileri ve eşdeğerlikleri eleyin: defalarca değiştirmek ile ; yerine sahip . Sonunda, bu tüm oluşumlarını ortadan kaldıracaktır ve .${\ Displaystyle P\rightarrow Q}$${\görüntüleme stili \l değil P\lor Q}$${\displaystyle P\leftrightarrow Q}$${\displaystyle (P\lor \l değil Q)\land (\lnot P\lor Q)}$${\görüntüleme stili\sağ ok }$${\görüntüleme stili \sol sağ ok }$
   2. De Morgan Yasasını tekrar tekrar uygulayarak DEĞİL'leri içe doğru hareket ettirin . Özellikle, şununla değiştirin ; yerine ile ; ve değiştirme ile ; yerine ile ; ile . Bundan sonra, yalnızca bir yüklem sembolünden hemen önce ortaya çıkabilir.${\görüntüleme stili \l değil (P\lor Q)}$${\görüntüleme stili (\P değil)\arazi (\Q değil)}$${\displaystyle \lnot (P\land Q)}$${\görüntüleme stili (\P değil)\lor (\Q değil)}$${\görüntüleme stili \l değil\P değil}$${\görüntüleme stili P}$${\görüntüleme stili \l değil (\tüm xP(x))}$${\görüntüleme stili \var x\p(x) değil}$${\görüntüleme stili \l değil (\vardır xP(x))}$${\görüntüleme stili \için tüm x\l değil P(x)}$${\görüntüleme stili \l değil }$
2. Değişkenleri standartlaştır
   1. Aynı değişken adını iki kez kullanan cümleler için değişkenlerden birinin adını değiştirin. Bu, niceleyicileri düşürürken daha sonra karışıklığı önler. Örneğin, olarak yeniden adlandırılır .${\displaystyle (\forall xP(x))\lor (\xQ(x))}$${\displaystyle \forall x[\exists y\mathrm {Hayvan} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists y\mathrm {Loves} (y,x)] }$${\displaystyle \forall x[\exists y\mathrm {Hayvan} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists z\mathrm {Loves} (z,x)] }$
3. Skolemize deyimi
   1. Dışarı doğru nicelik taşı: sürekli olarak yerine ile ; yerine ile ; yerine ile ; yerine sahip . Önceki değişken standardizasyon adımı bunun gerçekleşmemesini sağladığından, bu değiştirmeler denkliği korur . Bu değiştirmelerden sonra, bir nicelik belirteci yalnızca formülün ilk önekinde olabilir, ancak asla bir , , veya içinde olamaz .${\displaystyle P\land (\forall xQ(x))}$${\displaystyle \forall x(P\land Q(x))}$${\görüntüleme stili P\lor (\tüm xQ(x))}$${\görüntüleme stili\tüm x(P\lor Q(x))}$${\displaystyle P\land (\xQ(x) var)}$${\görüntüleme stili \var x(P\land Q(x))}$${\görüntüleme stili P\lor (\vardır xQ(x))}$${\görüntüleme stili \var x(P\lor Q(x))}$${\görüntüleme stili x}$${\görüntüleme stili P}$${\görüntüleme stili \l değil }$${\ Displaystyle \ arazi }$${\görüntüleme stili \lor }$
   2. Defalarca değiştirmek ile , nerede bir yeni -ary işlev simgesi, bir sözde " Skolem fonksiyonu ". Bu, eşdeğerlikten ziyade yalnızca tatmin edilebilirliği koruyan tek adımdır. Tüm varoluşsal niceleyicileri ortadan kaldırır.${\displaystyle \forall x_{1}\ldots \forall x_{n}\;\exists y\;P(y)}$${\displaystyle \forall x_{1}\ldots \forall x_{n}\;P(f(x_{1},\ldots ,x_{n}))}$${\görüntüleme stili f}$${\görüntüleme stili n}$
4. Tüm evrensel niceleyicileri bırakın.
5. Eleştiri üzerine içeriye OR'leri dağıtın: defalarca değiştirmek ile .${\ Displaystyle P\lor (Q\land R)}$${\ Displaystyle (P\lor Q)\land (P\lor R)}$

Bir örnek olarak, formül söyleyerek "dönüş birileri tarafından sevilen içinde, bütün hayvanları seviyor herkes olduğu" CNF dönüştürülmüştür (ve ardından içine almaktadır hüküm aşağıdaki şekilde (yedek kuralı vurgulayarak son satırında formunda) redexes içinde ): ${\displaystyle {\color {red}{\text{red}}}}$

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\görüntüleme stili\tüm y}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\sağ ok }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili\sağ ok }$

${\görüntüleme stili (}$

${\görüntüleme stili \var }$

${\görüntüleme stili y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\görüntüleme stili\tüm y}$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\sağ ok }$

${\görüntüleme stili (}$

${\görüntüleme stili \var }$

${\görüntüleme stili y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

1.1 ile

${\görüntüleme stili\tüm x}$

${\displaystyle \color {kırmızı}\lnot }$

${\görüntüleme stili (}$

${\displaystyle {\color {red}{\forall y}}}$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\görüntüleme stili (}$

${\görüntüleme stili \var }$

${\görüntüleme stili y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

1.1 ile

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\ Displaystyle \ var y}$

${\displaystyle \color {kırmızı}\lnot }$

${\görüntüleme stili (}$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\lor }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\görüntüleme stili (}$

${\görüntüleme stili \var }$

${\görüntüleme stili y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

1.2 ile

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\ Displaystyle \ var y}$

${\displaystyle \color {kırmızı}\lnot }$

${\displaystyle \color {kırmızı}\lnot }$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\görüntüleme stili (}$

${\görüntüleme stili \var }$

${\görüntüleme stili y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

1.2 ile

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\displaystyle {\color {kırmızı}{\var y}}}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\görüntüleme stili (}$

${\displaystyle \color {kırmızı}\var }$

${\displaystyle \color {kırmızı}y}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili y}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

1.2 ile

${\görüntüleme stili\tüm x}$

${\görüntüleme stili (}$

${\ Displaystyle \ var y}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\lor }$

${\görüntüleme stili (}$

${\displaystyle \color {kırmızı}\var }$

${\displaystyle \color {kırmızı}z}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili z}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

2 ile

${\görüntüleme stili\tüm x}$

${\görüntüleme stili \var z}$

${\görüntüleme stili (}$

${\displaystyle {\color {kırmızı}{\var y}}}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\lor }$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili z}$

${\görüntüleme stili ,x)}$

3.1 ile

${\görüntüleme stili\tüm x}$

${\displaystyle {\color {kırmızı}{\var z}}}$

${\ Displaystyle \ var y}$

${\görüntüleme stili (}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili z}$

${\görüntüleme stili ,x)}$

3.1 ile

${\görüntüleme stili\tüm x}$

${\displaystyle {\color {kırmızı}{\var y}}}$

${\görüntüleme stili (}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\ Displaystyle \ arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili y}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\görüntüleme stili \lor }$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili g(x)}$

${\görüntüleme stili ,x)}$

3.2 ile

${\görüntüleme stili (}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili f(x)}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\arazi }$

${\görüntüleme stili \l değil }$

${\displaystyle \mathrm {Sevgiler} (x,}$

${\görüntüleme stili f(x)}$

${\görüntüleme stili )}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\lor }$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili g(x)}$

${\görüntüleme stili ,x)}$

4 tarafından

${\görüntüleme stili (}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili f(x)}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\lor }$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili g(x)}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili )}$

${\displaystyle \color {kırmızı}\arazi }$

${\görüntüleme stili (}$

${\displaystyle \lnot \mathrm {Aşklar} (x,f(x))}$

${\displaystyle \color {kırmızı}\lor }$

${\displaystyle \mathrm {Aşklar} (g(x),x)}$

${\görüntüleme stili )}$

5 tarafından

${\görüntüleme stili \{}$

${\görüntüleme stili \{}$

${\displaystyle \mathrm {Hayvan} (}$

${\görüntüleme stili f(x)}$

${\görüntüleme stili )}$

${\görüntüleme stili,}$

${\displaystyle \mathrm {Sevgiler} (}$

${\görüntüleme stili g(x)}$

${\görüntüleme stili ,x)}$

${\görüntüleme stili\}}$

${\görüntüleme stili,}$

${\görüntüleme stili \{}$

${\displaystyle \lnot \mathrm {Aşklar} (x,f(x))}$

${\görüntüleme stili,}$

${\displaystyle \mathrm {Aşklar} (g(x),x)}$

${\görüntüleme stili\}}$

${\görüntüleme stili\}}$

( madde temsili)

Gayri resmi olarak, Skolem işlevi , sevilen kişiyi teslim ederken , sevmeyen hayvanı (varsa) verir olarak düşünülebilir . Daha sonra aşağıdan 3 Son satır olarak okur " hayvan sevmez , ya da başka tarafından sevilir " . ${\görüntüleme stili g(x)}$${\görüntüleme stili x}$${\görüntüleme stili f(x)}$${\görüntüleme stili x}$${\görüntüleme stili x}$${\görüntüleme stili f(x)}$${\görüntüleme stili x}$${\görüntüleme stili g(x)}$

Yukarıdan 2. son satır CNF'dir. ${\displaystyle (\mathrm {Hayvan} (f(x))\lor \mathrm {Aşklar} (g(x),x))\land (\lnot \mathrm {Aşklar} (x,f(x))\ lor \mathrm {Aşklar} (g(x),x))}$

Notlar

Ayrıca bakınız

• cebirsel normal form
• Ayrık normal form
• boynuz cümlesi
• Quine–McCluskey algoritması

Referanslar

• J. Eldon Whitesitt (24 Mayıs 2012). Boole Cebiri ve Uygulamaları . Kurye Şirketi. ISBN'si 978-0-486-15816-7.
• Hans Kleine Büning; Theodor Lettmann (28 Ağustos 1999). Önerme Mantığı: Tümdengelim ve Algoritmalar . Cambridge Üniversitesi Yayınları. ISBN'si 978-0-521-63017-7.
• Paul Jackson, Daniel Sheridan: Boole Devreleri için Cümle Formu Dönüşümleri . İçinde: Holger H. Hoos, David G. Mitchell (Ed.): Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004, Vancouver, BC, Canada, 10-13 Mayıs 2004, Revize Selected Papers. Bilgisayar Bilimi Ders Notları 3542, Springer 2005, s. 183–198
• GS Tseitin: Önermeler hesabında türetmenin karmaşıklığı üzerine . In: Slisenko, AO (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics (Rusça'dan çevrilmiştir), s. 115–125. Steklov Matematik Enstitüsü (1968)

Dış bağlantılar

• "Birleşik normal biçim" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]
• Kullanılan yasaları gösteren, CNF ve DNF'ye dönüştürmek için Java uygulaması