การเขียนโปรแกรมเชิงตรรกะเป็นกระบวนทัศน์การเขียนโปรแกรมที่รวมถึงภาษาต่างๆ ที่อิงตามตรรกะเชิงรูปธรรม เช่นDatalogและPrologบทความนี้จะอธิบายไวยากรณ์และความหมายของ ส่วนย่อย แบบประกาศ ล้วนๆ ของภาษาเหล่านี้ ที่น่าสับสนคือ ชื่อ "การเขียนโปรแกรมเชิงตรรกะ" ยังหมายถึง ภาษาการเขียนโปรแกรม เฉพาะ ภาษาหนึ่ง ที่โดยคร่าวๆ แล้วสอดคล้องกับส่วนย่อยแบบประกาศของ Prolog ด้วย น่าเสียดายที่ในบทความนี้จำเป็นต้องใช้คำนี้ในทั้งสองความหมาย

โปรแกรมตรรกะเชิงประกาศประกอบด้วยกฎในรูปแบบต่อไปนี้ ทั้งหมด

H :- B1 , ..., BN .

กฎแต่ละข้อดังกล่าวสามารถตีความได้ว่าเป็นนัยยะ :

${\displaystyle B_{1}\land \ldots \land B_{n}\rightarrow H}$

หมายความว่า "ถ้าแต่ละข้อเป็นจริงแล้ว ข้อนั้นก็จะเป็นจริงด้วย" โปรแกรมตรรกะจะคำนวณชุดข้อเท็จจริงที่ได้จากกฎของมัน ${\displaystyle B_{i}}$${\displaystyle H}$

การใช้งาน Datalog, Prolog และภาษาที่เกี่ยวข้องจำนวนมากได้เพิ่มคุณสมบัติเชิงกระบวนการ เช่นตัวดำเนินการ cut ของ Prolog หรือคุณสมบัตินอกเหนือจากตรรกะ เช่น อิน เท อร์เฟซฟังก์ชันภายนอกความหมายเชิงรูปธรรมของส่วนขยายดังกล่าวอยู่นอกเหนือขอบเขตของบทความนี้

Datalogเป็นภาษาการเขียนโปรแกรมเชิงตรรกะที่ง่ายที่สุดและมีการศึกษาอย่างกว้างขวาง มีคำจำกัดความหลักสามประการเกี่ยวกับความหมายของ Datalog ซึ่งทั้งหมดนั้นเทียบเท่ากัน ไวยากรณ์และความหมายของภาษาการเขียนโปรแกรมเชิงตรรกะอื่นๆ เป็นส่วนขยายและการวางนัยทั่วไปของไวยากรณ์และความหมายของ Datalog

โปรแกรม Datalog ประกอบด้วยรายการของกฎ ( ข้อความ Horn ) ^{[ 1 ]}ถ้าค่าคงที่และตัวแปรเป็น เซต ที่นับได้ของค่าคงที่และตัวแปรตามลำดับ และความสัมพันธ์เป็นเซตที่นับได้ของสัญลักษณ์ภาค แสดง ไวยากรณ์ BNFต่อไปนี้จะแสดงโครงสร้างของโปรแกรม Datalog:

< program > ::= < rule > < program > | "" < rule > ::= < atom > ":-" < atom-list > "." < atom > ::= < relation > "(" < term-list > ")" < atom-list > ::= < atom > | < atom > "," < atom-list > | "" < term > ::= < constant > | < variable > < term-list > ::= < term > | < term > "," < term-list > | "" 

อะตอมยังถูกเรียกว่าลิเทอรัล ด้วย อะตอมทางซ้ายของ:-สัญลักษณ์เรียกว่าส่วนหัวของกฎ อะตอมทางขวาเรียกว่าส่วนเนื้อหาโปรแกรม Datalog ทุกโปรแกรมต้องเป็นไปตามเงื่อนไขที่ว่าตัวแปรทุกตัวที่ปรากฏในส่วนหัวของกฎจะต้องปรากฏในส่วนเนื้อหาด้วย (เงื่อนไขนี้บางครั้งเรียกว่าข้อจำกัดช่วง ) ^{[ 1 ] [ 2 ]}

กฎที่มีเนื้อหาว่างเปล่าเรียกว่าข้อเท็จจริงตัวอย่างเช่น กฎต่อไปนี้เป็นข้อเท็จจริง:

r ( x ) :- .

การใช้งานการเขียนโปรแกรมเชิงตรรกะหลายรูปแบบได้ขยายไวยากรณ์ข้างต้นเพื่อให้สามารถเขียนข้อเท็จจริงได้โดยไม่ต้องใช้เครื่องหมายจุลภาค:-ดังนี้:

r ( x ).

นอกจากนี้ หลายโปรแกรมยังอนุญาตให้เขียนความสัมพันธ์แบบศูนย์-อารีโดยไม่ต้องใช้วงเล็บ ดังนี้:

พี:- คิว.

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

โปรแกรมต่อไปนี้คำนวณความสัมพันธ์pathซึ่งเป็นการปิดแบบถ่ายทอดของความedgeสัมพันธ์

ขอบ( x , y ). ขอบ( y , z ). เส้นทาง( A , B ) :- ขอบ( A , B ). เส้นทาง( A , C ) :- เส้นทาง( A , B ), ขอบ( B , C ).

มีแนวทางที่ใช้กันอย่างแพร่หลาย 3 แนวทางสำหรับความหมายของโปรแกรม Datalog ได้แก่แนวทางเชิงทฤษฎีแบบจำลองแนวทางเชิงจุดคงที่และแนวทางเชิงทฤษฎีการพิสูจน์แนวทางทั้งสามนี้สามารถพิสูจน์ได้ว่าเทียบเท่ากัน^{[ 3 ]}

อะตอมจะเรียกว่าอะตอมพื้นฐานหากไม่มีส่วนประกอบย่อยใดเป็นตัวแปร โดยสัญชาตญาณแล้ว ความหมายแต่ละอย่างจะกำหนดความหมายของโปรแกรมให้เป็นเซตของอะตอมพื้นฐานทั้งหมดที่สามารถอนุมานได้จากกฎของโปรแกรม โดยเริ่มต้นจากข้อเท็จจริง

กฎจะเรียกว่าเป็นกฎพื้นฐานได้ก็ต่อเมื่ออะตอมทั้งหมด (ส่วนหัวและส่วนลำตัว) ของกฎนั้นเป็นพื้นฐาน กฎพื้นฐานR ₂เป็นตัวอย่างพื้นฐานของกฎR ₁ถ้าR ₂เป็นผลลัพธ์ของการแทนที่ค่าคงที่ลงในตัวแปรทั้งหมดใน R ₁

ฐานเฮอร์แบรนด์ของโปรแกรมดาต้าล็อกคือเซตของอะตอมพื้นฐานทั้งหมดที่สามารถสร้างขึ้นได้จากค่าคงที่ที่ปรากฏในโปรแกรมการตีความ (หรือที่เรียกว่าอินสแตนซ์ฐานข้อมูล ) คือเซตย่อยของฐานเฮอร์แบรนด์ อะตอมพื้นฐานจะเป็นจริงในการตีความIถ้ามันเป็นองค์ประกอบของIกฎจะเป็นจริงในการตีความIถ้าสำหรับแต่ละอินสแตนซ์พื้นฐานของกฎนั้น ถ้าอะตอมทั้งหมดในส่วนเนื้อหาเป็นจริงในIแล้วส่วนหัวของกฎก็จะเป็นจริงในIด้วย

แบบจำลอง Herbrandของโปรแกรม Datalog PคือการตีความIของPซึ่งมีข้อเท็จจริงพื้นฐานทั้งหมดของPและทำให้กฎทั้งหมดของPเป็นจริงในI ความหมาย เชิงแบบจำลองระบุว่าความหมายของโปรแกรม Datalog คือแบบจำลอง Herbrand ขั้นต่ำ (เทียบเท่ากับการตัดกันของแบบจำลอง Herbrand ทั้งหมด) ^{[ 4 ]}

ตัวอย่างเช่น โปรแกรมนี้:

ขอบ( x , y ). ขอบ( y , z ). เส้นทาง( A , B ) :- ขอบ( A , B ). เส้นทาง( A , C ) :- เส้นทาง( A , B ), ขอบ( B , C ).

จักรวาลของเฮอร์แบรนด์มีดังนี้: x, y,z

และฐาน Herbrand นี้: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ...,path(z, z)

และโมเดล Herbrand ที่เรียบง่ายนี้: edge(x, y), edge(y, z), path(x, y), path(y, z),path(x, z)

ให้Iเป็นเซตของการตีความโปรแกรม Datalog Pนั่นคือI = P ( H )โดยที่Hคือฐาน Herbrand ของPและPคือตัวดำเนินการเซตกำลัง ตัวดำเนินการผลลัพธ์ทันทีสำหรับPคือแผนที่T ต่อไปนี้ จากIไปยังI : สำหรับแต่ละอินสแตนซ์พื้นฐานของแต่ละกฎในPถ้าทุกข้อความในส่วนเนื้อหาอยู่ในการตีความอินพุต ให้เพิ่มหัวของอินสแตนซ์พื้นฐานไปยังการตีความเอาต์พุต แผนที่T นี้ เป็นแบบโมโนโทนิกเมื่อเทียบกับลำดับบางส่วนที่กำหนดโดยการรวมเซตย่อยบนTตามทฤษฎีบท Knaster–Tarskiแผนที่นี้มีจุดตรึงที่เล็กที่สุด ตามทฤษฎีบทจุดตรึงของ Kleeneจุดตรึงคือค่าสูงสุดของโซ่จุดตรึงที่เล็กที่สุดของMตรงกับแบบจำลอง Herbrand ขั้นต่ำของโปรแกรม^{[ 5 ]}${\displaystyle T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots }$

ความหมาย ของจุดตรึง (fixpoint semantics ) เสนออัลกอริทึมสำหรับการคำนวณแบบจำลองเฮอร์แบรนด์ (Herbrand model) ที่เล็กที่สุด: เริ่มต้นด้วยชุดข้อเท็จจริงพื้นฐานในโปรแกรม จากนั้นเพิ่มผลลัพธ์ของกฎซ้ำๆ จนกว่าจะถึงจุดตรึง อัลกอริทึมนี้เรียกว่าการประเมินแบบง่าย (naïve evaluation )

กำหนดให้โปรแกรมP ต้นไม้พิสูจน์ของอะตอมพื้นฐานAคือต้นไม้ที่มีรากกำกับด้วยAใบกำกับด้วยอะตอมพื้นฐานจากส่วนหัวของข้อเท็จจริงในPและกิ่งก้านที่มีลูกกำกับด้วยอะตอมพื้นฐานGโดยที่ต้องมีอินสแตนซ์พื้นฐานอยู่จริง ${\displaystyle A_{1},\ldots ,A_{n}}$

G :- A1, ..., An.

ของกฎในPความหมายเชิงทฤษฎีการพิสูจน์กำหนดความหมายของโปรแกรม Datalog ให้เป็นเซตของอะตอมพื้นฐานที่สามารถอนุมานได้จากต้นไม้ดังกล่าว เซตนี้สอดคล้องกับแบบจำลอง Herbrand ขั้นต่ำ^{[ 6 ]}

บางคนอาจสนใจที่จะรู้ว่าอะตอมพื้นฐานเฉพาะตัวใดตัวหนึ่งปรากฏอยู่ในแบบจำลอง Herbrand ขั้นต่ำของโปรแกรม Datalog หรือไม่ โดยอาจไม่สนใจส่วนอื่นๆ ของแบบจำลองมากนัก การอ่านแบบจากบนลงล่างของแผนผังการพิสูจน์ที่อธิบายไว้ข้างต้น ชี้ให้เห็นถึงอัลกอริทึมสำหรับการคำนวณผลลัพธ์ของการสอบถามดังกล่าว การอ่านแบบนี้เป็นข้อมูลพื้นฐานสำหรับ อัลกอริทึม การแก้ปัญหา SLDซึ่งเป็นพื้นฐานสำหรับการประเมิน Prolog

ความหมายของ Datalog ยังได้รับการศึกษาในบริบทของ fixpoints บนsemiringsทั่วไปอีกด้วย^{[ 7 ]}

แม้ว่าชื่อ "การเขียนโปรแกรมเชิงตรรกะ" จะถูกใช้เพื่ออ้างถึงกระบวนทัศน์ทั้งหมดของภาษาการเขียนโปรแกรม รวมถึง Datalog และ Prolog แต่เมื่อพูดถึงความหมายเชิงรูปธรรม โดยทั่วไปแล้วจะหมายถึงส่วนขยายของ Datalog ที่มีสัญลักษณ์ฟังก์ชัน การ เขียน โปรแกรมเชิงตรรกะยังเรียกว่าโปรแกรมข้อความฮอร์นการเขียนโปรแกรมเชิงตรรกะตามที่กล่าวถึงในบทความนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับส่วนย่อย "บริสุทธิ์" หรือ แบบ ประกาศของProlog

ไวยากรณ์ของการเขียนโปรแกรมเชิงตรรกะขยายไวยากรณ์ของ Datalog ด้วยสัญลักษณ์ฟังก์ชัน การเขียนโปรแกรมเชิงตรรกะยกเลิกข้อจำกัดช่วง ทำให้ตัวแปรสามารถปรากฏในส่วนหัวของกฎที่ไม่ปรากฏในส่วนเนื้อหาได้^{[ 8 ]}

เนื่องจากการมีอยู่ของสัญลักษณ์ฟังก์ชัน โมเดล Herbrand ของโปรแกรมตรรกะจึงสามารถเป็นอนันต์ได้ อย่างไรก็ตาม ความหมายของโปรแกรมตรรกะยังคงถูกกำหนดให้เป็นโมเดล Herbrand ขั้นต่ำ ในทำนองเดียวกัน จุดตรึงของตัวดำเนินการผลลัพธ์ทันทีอาจไม่บรรจบกันในจำนวนขั้นตอนที่จำกัด (หรือไปยังเซตที่จำกัด) อย่างไรก็ตาม อะตอมพื้นฐานใดๆ ในโมเดล Herbrand ขั้นต่ำจะมีต้นไม้พิสูจน์ที่จำกัด นี่คือเหตุผลที่ Prolog ถูกประเมินจากบนลงล่าง^{[ 8 ]}เช่นเดียวกับใน Datalog ความหมายทั้งสามสามารถพิสูจน์ได้ว่าเทียบเท่ากัน

การเขียนโปรแกรมเชิงตรรกะมีคุณสมบัติที่พึงประสงค์คือ นิยามหลักทั้งสามประการของความหมายของโปรแกรมเชิงตรรกะสอดคล้องกัน ในทางตรงกันข้าม มีข้อเสนอที่ขัดแย้งกันมากมายเกี่ยวกับความหมายของโปรแกรมเชิงตรรกะที่มีการปฏิเสธ สาเหตุของความไม่ลงรอยกันคือ โปรแกรมเชิงตรรกะมีแบบจำลอง Herbrand ขั้นต่ำที่ไม่ซ้ำกัน แต่โดยทั่วไปแล้ว โปรแกรมเชิงตรรกะ (หรือแม้แต่ Datalog) ที่มีการปฏิเสธนั้นไม่มีแบบจำลองดังกล่าว

การปฏิเสธเขียนด้วยสัญลักษณ์notและสามารถปรากฏอยู่หน้าอะตอมใดๆ ก็ได้ในตัวบทของกฎ

< atom-list > ::= < atom > | "not" < atom > | < atom > "," < atom-list > | "" 

โปรแกรมตรรกะที่มีการปฏิเสธจะถูกแบ่งชั้นเมื่อสามารถกำหนดความสัมพันธ์แต่ละรายการให้กับชั้น บางชั้น ^ได้โดยที่หากความสัมพันธ์Rปรากฏการปฏิเสธในเนื้อหาของความสัมพันธ์Sแล้วRจะอยู่ในชั้นที่ต่ำกว่าS ^{[ 9} ] ความหมายเชิงแบบจำลองและจุดคงที่ของ Datalog สามารถขยายเพื่อจัดการกับการปฏิเสธแบบแบ่งชั้นได้ และส่วนขยายดังกล่าวสามารถพิสูจน์ได้ว่าเทียบเท่ากัน

การใช้งาน Datalog จำนวนมากใช้รูปแบบการประเมินจากล่างขึ้นบน ซึ่งได้รับแรงบันดาลใจจากความหมายของจุดคงที่ เนื่องจากความหมายนี้สามารถจัดการกับการปฏิเสธแบบแบ่งชั้นได้ การใช้งาน Datalog หลายรูปแบบจึงนำการปฏิเสธแบบแบ่งชั้นมาใช้

แม้ว่าการปฏิเสธแบบแบ่งชั้นจะเป็นส่วนขยายทั่วไปของ Datalog แต่ก็มีโปรแกรมที่สมเหตุสมผลที่ไม่สามารถแบ่งชั้นได้ โปรแกรมต่อไปนี้อธิบายเกมสองผู้เล่นที่ผู้เล่นชนะหากคู่ต่อสู้ไม่มีการเคลื่อนไหว: ^{[ ​​10 ]}

ย้าย( a , b ). ชนะ( X ) :- ย้าย( X , Y ), ไม่ชนะ( Y ).

โปรแกรมนี้ไม่ได้แบ่งระดับ แต่ดูเหมือนว่าจะเป็นไปได้ที่aจะชนะเกมนี้

ความหมายของแบบจำลองเสถียรจะกำหนดเงื่อนไขสำหรับการเรียกแบบจำลอง Herbrand บางแบบของโปรแกรมว่าเสถียรตามสัญชาตญาณ แบบจำลองเสถียรคือ "ชุดความเชื่อที่เป็นไปได้ที่ตัวแทนที่มีเหตุผลอาจมี โดยพิจารณาจาก [โปรแกรม]" เป็นข้อสมมติ^{[ 11 ]}

โปรแกรมที่มีการปฏิเสธอาจมีแบบจำลองที่เสถียรหลายแบบหรืออาจไม่มีแบบจำลองที่เสถียรเลยก็ได้ ตัวอย่างเช่น โปรแกรม

p : - ไม่ใช่q q : - ไม่ใช่p

มีโมเดลเสถียรสองแบบคือโปรแกรมกฎเดียว ${\displaystyle \{p\}}$${\displaystyle \{q\}}$

p :- ไม่ใช่p .

ไม่มีโมเดลที่เสถียร

แบบจำลองเสถียรทุกแบบเป็นแบบจำลองเฮอร์แบรนด์ขั้นต่ำสุด โปรแกรม Datalog ที่ไม่มีการปฏิเสธจะมีแบบจำลองเสถียรเพียงแบบเดียว ซึ่งก็คือแบบจำลองเฮอร์แบรนด์ขั้นต่ำสุดนั่นเอง ความหมายของแบบจำลองเสถียรจะกำหนดความหมายของโปรแกรมตรรกะที่มีการปฏิเสธให้เป็นแบบจำลองเสถียร หากมีอยู่เพียงแบบเดียว อย่างไรก็ตาม การตรวจสอบ แบบจำลองเสถียร ทั้งหมด (หรืออย่างน้อยหลายแบบ) ของโปรแกรมอาจเป็นประโยชน์ ซึ่งเป็นเป้าหมายของ การ เขียน โปรแกรมแบบชุดคำตอบ

มีการเสนอและศึกษาการขยาย Datalog อื่นๆ อีกหลายอย่าง รวมถึงรูปแบบต่างๆ ที่รองรับ ค่าคงที่ จำนวนเต็มและฟังก์ชัน (รวมถึงDatalogZ ) ^{[ 12 ] [ 13 ]} ข้อจำกัดความ ไม่เท่าเทียมกันในตัวกฎ และฟังก์ชัน รวม

การเขียนโปรแกรมเชิงตรรกะแบบมีข้อจำกัดช่วยให้สามารถนำข้อจำกัดเกี่ยวกับโดเมน เช่นจำนวนจริงหรือจำนวนเต็มมาใส่ไว้ในส่วนของกฎได้

• โครงสร้างของเฮอร์แบรนด์
• การเขียนโปรแกรมเชิงตรรกะ
• การปฏิเสธคือความล้มเหลว
• ไวยากรณ์และความหมายของ Prolog