รูปแบบปกติของการเชื่อมคำ

Q: การแปลงเป็น CNF

ใน ตรรกศาสตร์คลาสสิก สูตรประพจน์ แต่ละ สูตร สามารถแปลงเป็น สูตร ที่เทียบเท่ากัน ซึ่งอยู่ใน CNF ได้ [ 1 ] การแปลงนี้ขึ้นอยู่กับกฎเกี่ยวกับ ความสมมูลเชิงตรรกะ ได้แก่การ กำจัดการปฏิเสธซ้ำซ้อน กฎของเดอ มอร์แกน และกฎ การกระจาย

ในพีชคณิตบูลีนสูตรจะอยู่ในรูปแบบปกติแบบเชื่อมโยง ( CNF ) หรือรูปแบบปกติแบบประโยคถ้าสูตรนั้นเป็นการเชื่อม โยง ของ ประโยคหนึ่งประโยคขึ้นไปโดยที่ประโยคแต่ละประโยคเป็นการแยกของตัวแปรหรืออีกนัยหนึ่งคือผลคูณของผลรวมหรือเป็นผลรวมแบบ AND ของ OR

ในการพิสูจน์ทฤษฎีบทอัตโนมัติแนวคิด " รูปแบบปกติแบบประโยค " มักถูกใช้ในความหมายที่แคบกว่า ซึ่งหมายถึงการแสดงสูตร CNF ในรูปแบบเฉพาะเจาะจงในรูปของเซตของเซตของตัวอักษร

คำนิยาม

สูตรตรรกะจะถือว่าอยู่ในรูปแบบ CNF ก็ต่อเมื่อเป็นการเชื่อมโยงของการแยก อย่างน้อยหนึ่งรายการ ของตัวแปร อย่างน้อยหนึ่งตัว เช่นเดียวกับในรูปแบบปกติแบบแยก (DNF) ตัวดำเนินการเชิงประพจน์เพียงอย่างเดียวใน CNF คือ " หรือ " ( $\vee$ ), และ ( $\land$ ) และไม่ใช่ ( $\neg$ ตัว ดำเนินการ ` not`สามารถใช้ได้เฉพาะเป็นส่วนหนึ่งของค่าคงที่เท่านั้น ซึ่งหมายความว่าจะต้องอยู่หน้าตัวแปรเชิงประพจน์ เท่านั้น

ต่อไปนี้เป็นไวยากรณ์ที่ไม่ขึ้นกับบริบทสำหรับ CNF:

ซีเอ็นเอฟ

\,\to \,

แยกส่วน

\,\mid \,

แยกส่วน

\,\land \,

ซีเอ็นเอฟ

แยกส่วน

\,\to \,

อย่างแท้จริง

\,\mid \,

อย่างแท้จริง

\,\lor \,

แยกส่วน

อย่างแท้จริง

\,\to \,

ตัวแปร

\,\mid \,

\,\neg \,

ตัวแปร

โดยที่Variableคือตัวแปรใดๆ ก็ได้

สูตรทั้งหมดต่อไปนี้อยู่ในตัวแปร $A,B,C,D,E,$ และ $F$ อยู่ในรูปกริยาเชื่อมประโยคปกติ:

$(A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F)$
$(A\lor B)\land (C)$
$(A\lor B)$
$(A)$

สูตรต่อไปนี้ไม่ได้ อยู่ ในรูปแบบปกติแบบเชื่อมโยง:

$\neg (A\land B)$ เนื่องจากตัวดำเนินการ AND ซ้อนอยู่ภายในตัวดำเนินการ NOT
$\neg (A\lor B)\land C$ เนื่องจาก OR นั้นซ้อนอยู่ภายใน NOT
$A\land (B\lor (D\land E))$ เนื่องจากตัวดำเนินการ AND ซ้อนอยู่ภายในตัวดำเนินการ OR
$A\land (B\lor (C\lor D))$ เนื่องจากตัวดำเนินการ OR ซ้อนกันควรเขียนโดยไม่ต้องมีวงเล็บ

การแปลงเป็น CNF

ในตรรกศาสตร์คลาสสิก สูตรประพจน์แต่ละ สูตร สามารถแปลงเป็น สูตร ที่เทียบเท่ากันซึ่งอยู่ใน CNF ได้^{[ 1 ]}การแปลงนี้ขึ้นอยู่กับกฎเกี่ยวกับความสมมูลเชิงตรรกะได้แก่การกำจัดการปฏิเสธซ้ำซ้อน กฎของเดอ มอร์แกนและกฎการกระจาย

อัลกอริทึมพื้นฐาน

อัลกอริทึมสำหรับคำนวณค่าเทียบเท่า CNF ของสูตรเชิงประพจน์ที่กำหนดให้ $\phi$ สร้างต่อยอดจาก $\lnot \phi$ ในรูปแบบปกติแบบแยกส่วน (DNF) : ขั้นตอนที่ 1. ^{[ 2 ]} จากนั้น $\lnot \phi _{DNF}$ ถูกแปลงเป็น $\phi _{CNF}$ โดยการสลับ AND กับ OR และในทางกลับกัน พร้อมทั้งกลับค่าตัวอักษรทั้งหมด ลบทั้งหมด $\lnot \lnot$ [ ¹^]

การแปลงโดยวิธีการทางไวยากรณ์

แปลงสูตรเชิงประพจน์ให้อยู่ในรูปแบบ CNF $\phi$ .

ขั้นตอนที่ 1 : แปลงการปฏิเสธให้เป็นรูปแบบปกติแบบแยกส่วน^{[ 2 ]}

$\lnot \phi _{DNF}=(C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})$ [ ³^]

โดยที่แต่ละ $C_{i}$ เป็นการเชื่อมโยงของตัวอักษร $l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}}$ [ ⁴^]

ขั้นตอนที่ 2 : ยกเลิก $\lnot \phi _{DNF}$ จากนั้นจึงเปลี่ยนเกียร์ $\lnot$ เข้าไปภายในโดยการใช้หลักสมดุลของเดอ มอร์แกน (แบบทั่วไป)จนกว่าจะไม่สามารถทำได้อีกต่อไป ${\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot (C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})\\&\leftrightarrow \lnot C_{1}\land \lnot C_{2}\land \ldots \land \lnot C_{i}\land \ldots \land \lnot C_{m}&&{\text{// (generalized) DM}}\end{aligned}}$ ที่ไหน ${\begin{aligned}\lnot C_{i}&=\lnot (l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}})\\&\leftrightarrow (\lnot l_{i1}\lor \lnot l_{i2}\lor \ldots \lor \lnot l_{in_{i}})&&{\text{// (generalized) DM}}\end{aligned}}$

ขั้นตอนที่ 3 : ลบการปฏิเสธซ้ำซ้อนทั้งหมดออก

ตัวอย่าง

แปลงสูตรเชิงประพจน์ให้อยู่ในรูปแบบ CNF $\phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))$ [ ⁵^]

DNF เทียบเท่าแบบเต็มของสิ่งที่ปฏิเสธคือ^{[ 2 ]} $\lnot \phi _{DNF}=(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)$

${\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot \{(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)\}\\&\leftrightarrow {\underline {\lnot (p\land q\land r)}}\land {\underline {\lnot (p\land q\land \lnot r)}}\land {\underline {\lnot (p\land \lnot q\land \lnot r)}}\land {\underline {\lnot (\lnot p\land q\land \lnot r)}}&&{\text{// generalized D.M. }}\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor \lnot \lnot r)\land (\lnot p\lor \lnot \lnot q\lor \lnot \lnot r)\land (\lnot \lnot p\lor \lnot q\lor \lnot \lnot r)&&{\text{// generalized D.M. }}(4\times )\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)&&{\text{// remove all }}\lnot \lnot \\&=\phi _{CNF}\end{aligned}}$

การแปลงโดยวิธีการทางความหมาย

สูตรที่เทียบเท่ากับรูปแบบ CNF สามารถหาได้จากตารางค่าความจริง ของสูตรนั้น ลองพิจารณาสูตรนี้อีกครั้ง $\phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))$ [ ⁵^]

ตารางความจริงที่เกี่ยวข้องคือ

$p$	$q$	$r$	$\lnot$	$(p\land q)$	$\leftrightarrow$	$\lnot r$	$\uparrow$	$(p\oplus q)$
ที	ที	ที	เอฟ	ที	เอฟ	เอฟ	ที	เอฟ
ที	ที	เอฟ	เอฟ	ที	เอฟ	ที	ที	เอฟ
ที	เอฟ	ที	ที	เอฟ	ที	เอฟ	ที	ที
ที	เอฟ	เอฟ	ที	เอฟ	เอฟ	ที	เอฟ	ที
เอฟ	ที	ที	ที	เอฟ	ที	เอฟ	ที	ที
เอฟ	ที	เอฟ	ที	เอฟ	เอฟ	ที	เอฟ	ที
เอฟ	เอฟ	ที	ที	เอฟ	ที	เอฟ	ที	เอฟ
เอฟ	เอฟ	เอฟ	ที	เอฟ	ที	ที	ที	เอฟ

เทียบเท่า CNF ของ $\phi$ เป็น $(\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)$

การเชื่อมโยงแบบ "หรือ" แต่ละครั้งสะท้อนถึงการกำหนดตัวแปรซึ่ง $\phi$ ประเมินค่าเป็น F(เท็จ) หากในการกำหนดค่าดังกล่าว ตัวแปร $V$

ถ้า T(จริง) ค่าตัวอักษรจะถูกตั้งเป็น $\lnot V$ ในการเชื่อมแบบ "ไม่"
ถ้าเป็น F(เท็จ) ค่าตัวอักษรจะถูกตั้งเป็น $V$ ในการเชื่อมแบบ "หรือ"

แนวทางอื่นๆ

เนื่องจากสูตรเชิงประพจน์ทั้งหมดสามารถแปลงเป็นสูตรที่เทียบเท่ากันในรูปแบบปกติเชิงเชื่อมโยง (Conjunctive Normal Form หรือ CNF) ได้ การพิสูจน์จึงมักอาศัยสมมติฐานว่าสูตรทั้งหมดเป็น CNF อย่างไรก็ตาม ในบางกรณี การแปลงเป็น CNF อาจทำให้สูตรมีขนาดใหญ่ขึ้นอย่างมาก ตัวอย่างเช่น การแปลสูตรที่ไม่ใช่ CNF

$(X_{1}\wedge Y_{1})\vee (X_{2}\wedge Y_{2})\vee \ldots \vee (X_{n}\wedge Y_{n})$

เมื่อนำไปผสมกับ CNF จะได้สูตรที่มี $2^{n}$ ข้อกำหนด:

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

แต่ละข้อความประกอบด้วยอย่างใดอย่างหนึ่ง $X_{i}$ หรือ $Y_{i}$ สำหรับแต่ละคน $i$ .

มีการแปลงเป็น CNF ที่หลีกเลี่ยงการเพิ่มขนาดแบบเลขชี้กำลังโดยการรักษาความสามารถในการทำให้ เป็นจริง แทนที่จะเป็นความเท่าเทียมกัน [ ^{6 ] [}^{7 ] การ}แปลงเหล่านี้รับประกันว่าจะเพิ่มขนาดของสูตรขึ้นแบบเชิงเส้นเท่านั้น แต่จะเพิ่มตัวแปรใหม่ ตัวอย่างเช่น สูตรข้างต้นสามารถแปลงเป็น CNF ได้โดยการเพิ่มตัวแปร $Z_{1},\ldots ,Z_{n}$ ดังต่อไปนี้:

$(Z_{1}\vee \ldots \vee Z_{n})\wedge (\neg Z_{1}\vee X_{1})\wedge (\neg Z_{1}\vee Y_{1})\wedge \ldots \wedge (\neg Z_{n}\vee X_{n})\wedge (\neg Z_{n}\vee Y_{n}).$

การตีความจะสอดคล้องกับสูตรนี้ก็ต่อเมื่อตัวแปรใหม่ตัวใดตัวหนึ่งเป็นจริงอย่างน้อยหนึ่งตัว ถ้าตัวแปรนั้นคือ $Z_{i}$ จากนั้นทั้งสอง $X_{i}$ และ $Y_{i}$ ก็เป็นจริงเช่นกัน นั่นหมายความว่าทุกแบบจำลองที่ตรงตามสูตรนี้ก็ตรงตามสูตรดั้งเดิมด้วย ในทางกลับกัน มีเพียงบางแบบจำลองของสูตรดั้งเดิมเท่านั้นที่ตรงตามสูตรนี้ เนื่องจาก $Z_{i}$ เนื่องจากตัวแปรเหล่านี้ไม่ได้ถูกกล่าวถึงในสูตรดั้งเดิม ค่าของตัวแปรเหล่านี้จึงไม่เกี่ยวข้องกับการทำให้สูตรนั้นเป็นจริง ซึ่งแตกต่างจากสูตรสุดท้าย นั่นหมายความว่าสูตรดั้งเดิมและผลลัพธ์ของการแปลงนั้นสามารถทำให้เป็นจริงได้เหมือนกันแต่ไม่เท่ากัน

การแปลอีกแบบหนึ่ง คือการแปลงแบบ Tseitinนั้น ยังรวมถึงข้อความย่อยต่างๆ ด้วย $Z_{i}\vee \neg X_{i}\vee \neg Y_{i}$ ด้วยเงื่อนไขเหล่านี้ สูตรดังกล่าวจึงหมายความว่า $Z_{i}\equiv X_{i}\wedge Y_{i}$ สูตรนี้มักถูกมองว่าเป็นการ "กำหนด" $Z_{i}$ เพื่อเป็นชื่อสำหรับ $X_{i}\wedge Y_{i}$ .

จำนวนการเชื่อมแบบ "หรือ" สูงสุด

พิจารณาสูตรเชิงประพจน์ที่มี $n$ ตัวแปร $n\geq 1$ .

มีอยู่ $2n$ ตัวอักษรที่อาจเป็นไปได้: $L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}$ .

$L$ มี $(2^{2n}-1)$ เซตย่อยที่ไม่ว่างเปล่า^{[ 8 ]}

นี่คือจำนวนการแยกสูงสุดที่ CNF สามารถมีได้^{[ 9 ]}

การรวมกันเชิงฟังก์ชันความจริงทั้งหมดสามารถแสดงได้ด้วย $2^{n}$ การเชื่อมแบบ "หรือ" (disjunctions) หนึ่งอันสำหรับแต่ละแถวของตารางความจริงในตัวอย่างด้านล่าง การเชื่อมแบบ "หรือ" จะถูกขีดเส้นใต้

ตัวอย่าง

พิจารณาสูตรที่มีตัวแปรสองตัว $p$ และ $q$ .

CNF ที่ยาวที่สุดที่เป็นไปได้คือ $2^{(2\times 2)}-1=15$ การแยก: ^{[ 9 ]} ${\begin{array}{lcl}(\lnot p)\land (p)\land (\lnot q)\land (q)\land \\(\lnot p\lor p)\land {\underline {(\lnot p\lor \lnot q)}}\land {\underline {(\lnot p\lor q)}}\land {\underline {(p\lor \lnot q)}}\land {\underline {(p\lor q)}}\land (\lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q)\land (\lnot p\lor p\lor q)\land (\lnot p\lor \lnot q\lor q)\land (p\lor \lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q\lor q)\end{array}}$

สูตรนี้ขัดแย้งกันเองสามารถทำให้ง่ายขึ้นได้เป็น $(\neg p\land p)$ หรือถึง $(\neg q\land q)$ ซึ่งสิ่งเหล่านี้ก็เป็นข้อขัดแย้งเช่นกัน แต่ก็เป็น CNF ที่ถูกต้องด้วย

ความซับซ้อนในการคำนวณ

ปัญหาชุดสำคัญในความซับซ้อนของการคำนวณเกี่ยวข้องกับการค้นหาการกำหนดค่าให้กับตัวแปรของสูตรบูลีนที่แสดงในรูปแบบปกติแบบเชื่อมโยง โดยที่สูตรนั้นเป็นจริง ปัญหา k -SAT คือปัญหาของการค้นหาการกำหนดค่าที่น่าพอใจให้กับสูตรบูลีนที่แสดงใน CNF ซึ่งแต่ละการเชื่อมโยงมีตัวแปร ไม่เกิน k ตัว3-SATเป็น ปัญหา NP-complete (เช่นเดียวกับ ปัญหาk -SAT อื่นๆ ที่ k > 2) ในขณะที่2-SATเป็นที่ทราบกันว่ามีวิธีแก้ปัญหาในเวลาพหุนามผลที่ตามมาคือ^{[ 10 ]}งานของการแปลงสูตรเป็นDNFโดยรักษาความสามารถในการทำให้เป็นจริงจึงเป็นNP-hardในทำนองเดียวกันการแปลงเป็น CNF โดยรักษาความถูกต้องก็เป็น NP-hard เช่นกัน ดังนั้นการแปลงเป็น DNF หรือ CNF ที่รักษาความเท่าเทียมกันจึงเป็น NP-hard อีกครั้ง

ปัญหาทั่วไปในกรณีนี้เกี่ยวข้องกับสูตรในรูปแบบ "3CNF": รูปแบบปกติเชิงเชื่อมโยง (conjunctive normal form) ที่มีตัวแปรไม่เกินสามตัวต่อส่วนเชื่อมโยง ตัวอย่างของสูตรดังกล่าวที่พบได้ในทางปฏิบัติอาจมีขนาดใหญ่มาก เช่น มีตัวแปร 100,000 ตัว และส่วนเชื่อมโยง 1,000,000 ส่วน

สูตรในรูปแบบ CNF สามารถแปลงเป็นสูตรที่สามารถทำให้เป็นจริงได้ในรูปแบบ " k CNF" (สำหรับk ≥ 3) โดยการแทนที่ส่วนประกอบแต่ละส่วนด้วย ตัวแปรมากกว่าk ตัว $X_{1}\vee \ldots \vee X_{k}\vee \ldots \vee X_{n}$ โดยสองจุดบรรจบกัน $X_{1}\vee \ldots \vee X_{k-1}\vee Z$ และ $\neg Z\vee X_{k}\lor \ldots \vee X_{n}$ โดยให้ $Z$ เป็นตัวแปรใหม่ และทำซ้ำบ่อยเท่าที่จำเป็น

ตรรกะลำดับที่หนึ่ง

ในตรรกศาสตร์ลำดับที่หนึ่ง รูปแบบปกติเชิงเชื่อมโยง (Conjunctive Normal Form หรือ CNF) สามารถนำไปใช้ต่อเพื่อให้ได้รูปแบบปกติเชิงประโยค (Clausal Normal Form หรือ CNF) ของสูตรตรรกศาสตร์ ซึ่งสามารถนำไปใช้ในการแก้ปัญหาลำดับที่หนึ่งได้ในการพิสูจน์ทฤษฎีบทอัตโนมัติโดยใช้การแก้ปัญหา สูตร CNF สามารถนำไป ใช้ได้

(

l_{11}

\lor

\ldots

\lor

l_{1n_{1}}

)

\land

\ldots

\land

(

l_{m1}

\lor

\ldots

\lor

l_{mn_{m}}

)

[ ¹¹^{] มักจะ}^แสดงเป็นเซตของเซต

\{

\{

l_{11}

,

\ldots

,

l_{1n_{1}}

\}

,

\ldots

,

\{

l_{m1}

,

\ldots

,

l_{mn_{m}}

\}

\}

.

ดูตัวอย่างด้านล่าง

การแปลงจากตรรกะลำดับที่หนึ่ง

เพื่อแปลงตรรกะลำดับแรกเป็น CNF: ^{[ 12 ]}

แปลงเป็นรูปแบบปกติของการปฏิเสธ
1. ขจัดความคลุมเครือและความเท่าเทียมกัน: แทนที่ซ้ำๆ $P\rightarrow Q$ กับ $\lnot P\lor Q$ ; แทนที่ $P\leftrightarrow Q$ กับ $(P\lor \lnot Q)\land (\lnot P\lor Q)$ ในที่สุดแล้ว วิธีนี้จะช่วยขจัดปัญหาทั้งหมดได้ $\rightarrow$ และ $\leftrightarrow$ .
2. ย้าย NOT เข้าด้านในโดยใช้กฎของเดอ มอร์แกน ซ้ำๆ โดยเฉพาะอย่างยิ่ง ให้แทนที่ $\lnot (P\lor Q)$ กับ $(\lnot P)\land (\lnot Q)$ ; แทนที่ $\lnot (P\land Q)$ กับ $(\lnot P)\lor (\lnot Q)$ และแทนที่ $\lnot \lnot P$ กับ $P$ ; แทนที่ $\lnot (\forall xP(x))$ กับ $\exists x\lnot P(x)$ ; $\lnot (\exists xP(x))$ กับ $\forall x\lnot P(x)$ หลังจากนั้น $\lnot$ อาจปรากฏได้เฉพาะก่อนหน้าสัญลักษณ์แสดงภาคแสดงเท่านั้น
ทำให้ตัวแปรเป็นมาตรฐาน
1. สำหรับประโยคเช่น $(\forall xP(x))\lor (\exists xQ(x))$ หากใช้ชื่อตัวแปรเดียวกันสองครั้ง ให้เปลี่ยนชื่อตัวแปรตัวใดตัวหนึ่ง เพื่อหลีกเลี่ยงความสับสนในภายหลังเมื่อตัดตัวระบุปริมาณออก ตัวอย่างเช่น $\forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists y\mathrm {Loves} (y,x)]$ เปลี่ยนชื่อเป็น $\forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists z\mathrm {Loves} (z,x)]$ .
สโกเลไมซ์คำแถลง
1. ย้ายตัวบ่งปริมาณออกไปด้านนอก: แทนที่ซ้ำๆ $P\land (\forall xQ(x))$ กับ $\forall x(P\land Q(x))$ ; แทนที่ $P\lor (\forall xQ(x))$ กับ $\forall x(P\lor Q(x))$ ; แทนที่ $P\land (\exists xQ(x))$ กับ $\exists x(P\land Q(x))$ ; แทนที่ $P\lor (\exists xQ(x))$ กับ $\exists x(P\lor Q(x))$ การแทนที่เหล่านี้ยังคงรักษาความเท่าเทียมกันไว้ เนื่องจากขั้นตอนการกำหนดมาตรฐานตัวแปรก่อนหน้านี้ได้ทำให้มั่นใจได้ว่า $x$ ไม่เกิดขึ้นใน $P$ หลังจากทำการแทนที่เหล่านี้แล้ว ตัวบ่งปริมาณอาจปรากฏได้เฉพาะในส่วนนำหน้าของสูตรเท่านั้น แต่จะไม่ปรากฏอยู่ภายในสูตร $\lnot$ , $\land$ , หรือ $\lor$ .
2. เปลี่ยนซ้ำๆ $\forall x_{1}\ldots \forall x_{n}\;\exists y\;P(y)$ กับ $\forall x_{1}\ldots \forall x_{n}\;P(f(x_{1},\ldots ,x_{n}))$ , ที่ไหน $f$ เป็นของใหม่ $n$ สัญลักษณ์ฟังก์ชัน -ary หรือที่เรียกว่า " ฟังก์ชัน Skolem " นี่เป็นขั้นตอนเดียวที่รักษาไว้ซึ่งความสามารถในการทำให้เป็นจริงเท่านั้น ไม่ใช่ความเท่าเทียมกัน มันกำจัดตัวบ่งปริมาณเชิงมีอยู่ทั้งหมด
ลบตัวระบุปริมาณสากลทั้งหมดออก
กระจายการดำเนินการ OR เข้าไปด้านในเหนือการดำเนินการ AND: แทนที่ซ้ำๆ $P\lor (Q\land R)$ กับ $(P\lor Q)\land (P\lor R)$ .

ตัวอย่าง

ตัวอย่างเช่น สูตรที่กล่าวว่า"ใครก็ตามที่รักสัตว์ทุกชนิด ย่อมได้รับความรักตอบแทนจากผู้อื่น"สามารถแปลงเป็นรูปแบบ CNF (และต่อมาเป็น รูปแบบ ประโยคย่อยในบรรทัดสุดท้าย) ได้ดังนี้ (โดยเน้นกฎการแทนที่redexไว้) ${\color {red}{\text{red}}}$ ):

\forall x

(

\forall y

\mathrm {Animal} (

y

)

\color {red}\rightarrow

\mathrm {Loves} (x,

y

)

)

\rightarrow

(

\exists

y

\mathrm {Loves} (

y

,x)

)

\forall x

(

\forall y

\lnot

\mathrm {Animal} (

y

)

\lor

\mathrm {Loves} (x,

y

)

)

\color {red}\rightarrow

(

\exists

y

\mathrm {Loves} (

y

,x)

)

โดย 1.1

\forall x

\color {red}\lnot

(

{\color {red}{\forall y}}

\lnot

\mathrm {Animal} (

y

)

\lor

\mathrm {Loves} (x,

y

)

)

\lor

(

\exists

y

\mathrm {Loves} (

y

,x)

)

โดย 1.1

\forall x

(

\exists y

\color {red}\lnot

(

\lnot

\mathrm {Animal} (

y

)

\color {red}\lor

\mathrm {Loves} (x,

y

)

)

)

\lor

(

\exists

y

\mathrm {Loves} (

y

,x)

)

โดย 1.2

\forall x

(

\exists y

\color {red}\lnot

\color {red}\lnot

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\lor

(

\exists

y

\mathrm {Loves} (

y

,x)

)

โดย 1.2

\forall x

(

{\color {red}{\exists y}}

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\lor

(

\color {red}\exists

\color {red}y

\mathrm {Loves} (

y

,x)

)

โดย 1.2

\forall x

(

\exists y

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\color {red}\lor

(

\color {red}\exists

\color {red}z

\mathrm {Loves} (

z

,x)

)

โดย 2

\forall x

\exists z

(

{\color {red}{\exists y}}

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\color {red}\lor

\mathrm {Loves} (

z

,x)

โดย 3.1

\forall x

{\color {red}{\exists z}}

\exists y

(

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\lor

\mathrm {Loves} (

z

,x)

โดย 3.1

\forall x

{\color {red}{\exists y}}

(

\mathrm {Animal} (

y

)

\land

\lnot

\mathrm {Loves} (x,

y

)

)

\lor

\mathrm {Loves} (

g(x)

,x)

โดย 3.2

(

\mathrm {Animal} (

f(x)

)

\color {red}\land

\lnot

\mathrm {Loves} (x,

f(x)

)

)

\color {red}\lor

\mathrm {Loves} (

g(x)

,x)

โดย 4

(

\mathrm {Animal} (

f(x)

)

\color {red}\lor

\mathrm {Loves} (

g(x)

,x)

)

\color {red}\land

(

\lnot \mathrm {Loves} (x,f(x))

\color {red}\lor

\mathrm {Loves} (g(x),x)

)

โดย 5

\{

\{

\mathrm {Animal} (

f(x)

)

,

\mathrm {Loves} (

g(x)

,x)

\}

,

\{

\lnot \mathrm {Loves} (x,f(x))

,

\mathrm {Loves} (g(x),x)

\}

\}

( การแสดง ข้อความ )

โดยไม่เป็นทางการ หน้าที่ของสโกเลม $g(x)$ อาจมองได้ว่าเป็นการมอบตัวให้กับบุคคลที่... $x$ เป็นที่รัก ในขณะที่ $f(x)$ ให้ผลผลิตเป็นสัตว์ (ถ้ามี) ที่ $x$ ไม่รัก บรรทัดที่สามจากท้ายสุดด้านล่างอ่านว่า" $x$ ไม่รักสัตว์ $f(x)$ มิเช่นนั้น $x$ เป็นที่รักของ $g(x)$ " .

บรรทัดรองสุดท้ายจากด้านบน $(\mathrm {Animal} (f(x))\lor \mathrm {Loves} (g(x),x))\land (\lnot \mathrm {Loves} (x,f(x))\lor \mathrm {Loves} (g(x),x))$ คือ CNF

ดูเพิ่มเติม

รูปแบบปกติเชิงพีชคณิต
ความเป็นคู่ของการเชื่อมต่อ/การแยก
รูปแบบปกติแบบแยกส่วน
อนุประโยคฮอร์น (Horn clause ) – อนุประโยคฮอร์นเป็นอนุประโยค เชื่อมประโยคแบบเลือกอย่างใดอย่างหนึ่ง ( การเชื่อมประโยคแบบเลือกอย่างใด อย่างหนึ่ง ของตัวแปร ) ที่มีตัวแปรเชิงบวกอย่างมากที่สุดเพียงหนึ่งตัว กล่าวคือตัวแปรที่ไม่ถูกปฏิเสธ
อัลกอริทึมควิน-แมคคลัสกีย์

หมายเหตุ

1 2 Howson 2005 , หน้า 46.
1 2 3ดูรูปแบบปกติแบบแยกส่วน § การแปลงเป็น DNF
↑ $1\leq m\leq$ จำนวนการเชื่อมคำสูงสุดสำหรับ $\phi$
↑ $1\leq in_{i}\leq$ จำนวนตัวอักษรสูงสุดสำหรับ $\phi$
1 2 $\phi$ = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q)))
↑ Tseitin 1968 .
↑แจ็กสันและ เชอริ แดน 2004
↑ $\left|{\mathcal {P}}(L)\right|=2^{2n}$
1 2ถือว่าการทำซ้ำและการเปลี่ยนแปลง (เช่น $(a\land b)\lor (b\land a)\lor (a\land b\land b)$ ) โดยอาศัยสมบัติการสลับที่และการจัดกลุ่มของ $\lor$ และ $\land$ ไม่เกิดขึ้น
↑เนื่องจากวิธีหนึ่งในการตรวจสอบความน่าพอใจของ CNF คือการแปลงเป็น DNFซึ่งสามารถตรวจสอบความน่าพอใจได้ในเวลาเชิงเส้น
↑ $1\leq m\leq$ จำนวนการเชื่อมแบบ "หรือ" สูงสุด $1\leq in_{i}\leq$ จำนวนตัวอักษรสูงสุด
↑ Russel & Norvig 2010 , หน้า 345–347, 9.5.1 รูปแบบปกติเชิงเชื่อมโยงสำหรับตรรกะลำดับที่หนึ่ง

ลิงก์ภายนอก

"รูปแบบปกติเชิงเชื่อมโยง" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]

"เครื่องมือ Java สำหรับ แปลงตารางความจริงเป็น CNF และ DNF"มหาวิทยาลัยมาร์บูร์กสืบค้นเมื่อ31 ธันวาคม 2023

[FOOTNOTEHowson200546-1] 1 2 Howson 2005 , หน้า 46.

[dnf-2] 1 2 3ดูรูปแบบปกติแบบแยกส่วน § การแปลงเป็น DNF

[3] $1\leq m\leq$ จำนวนการเชื่อมคำสูงสุดสำหรับ $\phi$

[4] $1\leq in_{i}\leq$ จำนวนตัวอักษรสูงสุดสำหรับ $\phi$

[phiverbose-5] 1 2 $\phi$ = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q)))

[FOOTNOTETseitin1968-6] Tseitin 1968 .

[FOOTNOTEJacksonSheridan2004-7] แจ็กสันและ เชอริ แดน 2004

[8] $\left|{\mathcal {P}}(L)\right|=2^{2n}$

[noreps-9] 1 2ถือว่าการทำซ้ำและการเปลี่ยนแปลง (เช่น $(a\land b)\lor (b\land a)\lor (a\land b\land b)$ ) โดยอาศัยสมบัติการสลับที่และการจัดกลุ่มของ $\lor$ และ $\land$ ไม่เกิดขึ้น

[10] เนื่องจากวิธีหนึ่งในการตรวจสอบความน่าพอใจของ CNF คือการแปลงเป็น DNFซึ่งสามารถตรวจสอบความน่าพอใจได้ในเวลาเชิงเส้น

[11] $1\leq m\leq$ จำนวนการเชื่อมแบบ "หรือ" สูงสุด $1\leq in_{i}\leq$ จำนวนตัวอักษรสูงสุด

[FOOTNOTERusselNorvig2010345–3479.5.1_Conjunctive_normal_form_for_first-order_logic-12] Russel & Norvig 2010 , หน้า 345–347, 9.5.1 รูปแบบปกติเชิงเชื่อมโยงสำหรับตรรกะลำดับที่หนึ่ง

[ 1 ]

[ 2 ]

3

4

5

6 ] [

7 ] การ

[ 8 ]

[ 9 ]

[ 10 ]

11

[ 12 ]

ไม่มีชื่อบทความ

รูปแบบปกติของการเชื่อมคำ

คำนิยาม

การแปลงเป็น CNF

อัลกอริทึมพื้นฐาน

การแปลงโดยวิธีการทางไวยากรณ์

การแปลงโดยวิธีการทางความหมาย

แนวทางอื่นๆ

จำนวนการเชื่อมแบบ "หรือ" สูงสุด

ความซับซ้อนในการคำนวณ

ตรรกะลำดับที่หนึ่ง

การแปลงจากตรรกะลำดับที่หนึ่ง

ดูเพิ่มเติม

หมายเหตุ

ลิงก์ภายนอก

ข้อมูลสำคัญจากบทความ