ในตรรกศาสตร์เซตตัวเชื่อมตรรกะหรือตัวดำเนินการบูลีนที่สมบูรณ์ในเชิงฟังก์ชันคือเซตที่สามารถใช้แสดงตารางความจริงที่ เป็นไปได้ทั้งหมด โดยการรวมสมาชิกของเซตเข้ากับนิพจน์บูลีน [ ^{1 ] [ 2 ] เซต}ตัวเชื่อมที่สมบูรณ์ที่รู้จักกันดีคือ{ AND , NOT }แต่ละเซตเดี่ยว{ NAND }และ{ NOR }นั้นสมบูรณ์ในเชิงฟังก์ชัน อย่างไรก็ตาม เซต{ AND , OR } นั้น ไม่สมบูรณ์ เนื่องจากไม่สามารถแสดง NOT ได้

ประตู (หรือชุดประตู) ที่ทำงานได้อย่างสมบูรณ์สามารถเรียกว่าประตูสากล (หรือชุดประตูสากล) ได้เช่นกัน

ในบริบทของตรรกะเชิงประพจน์ชุดตัวเชื่อมที่สมบูรณ์ตามหน้าที่เรียกว่า( แสดงออก ) เพียงพอ^{[ 3 ]}

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

ตำราตรรกศาสตร์สมัยใหม่โดยทั่วไปจะใช้ตัวเชื่อมทางตรรกศาสตร์บางส่วนเป็นพื้นฐาน ได้แก่ การเชื่อม ( conjunction ) ( ); การแยก (disjunction ) ( ) ; การปฏิเสธ ( negation ) ( ); เงื่อนไขเชิงวัตถุ (material conditional ) ( ); และอาจ รวมถึงเงื่อนไขสองทาง ( biconditional ) ( ) ด้วย หากต้องการ สามารถกำหนดตัวเชื่อมทางตรรกศาสตร์เพิ่มเติมได้ โดยกำหนดจากพื้นฐานเหล่านี้ ตัวอย่างเช่น NOR (การปฏิเสธของการแยก ซึ่งบางครั้งใช้สัญลักษณ์) สามารถแสดงได้เป็นการเชื่อมของการปฏิเสธสองครั้ง: ${\displaystyle \land }$${\displaystyle \lor }$${\displaystyle \neg }$${\displaystyle \to }$${\displaystyle \leftrightarrow }$${\displaystyle \downarrow }$

${\displaystyle A\downarrow B:=\neg A\land \neg B}$

ในทำนองเดียวกัน การปฏิเสธของการเชื่อมประโยค NAND (บางครั้งใช้สัญลักษณ์) สามารถนิยามได้ในรูปของการเชื่อมประโยคแบบแยกและการปฏิเสธ ตัวเชื่อมประโยคแบบไบนารีทุกตัวสามารถนิยามได้ในรูปของซึ่งหมายความว่าเซตนั้นสมบูรณ์ในเชิงฟังก์ชัน อย่างไรก็ตาม เซตนี้มีความซ้ำซ้อน กล่าวคือ เซตนี้ไม่ใช่ เซตที่สมบูรณ์ในเชิงฟังก์ชัน ขั้นต่ำเนื่องจากเงื่อนไขและเงื่อนไขสองทางสามารถนิยามได้ในรูปของตัวเชื่อมประโยคอื่นๆ เช่น ${\displaystyle \uparrow }$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

ดังนั้นเซตที่เล็กกว่าจึงสมบูรณ์ในเชิงฟังก์ชันเช่นกัน (ความสมบูรณ์ในเชิงฟังก์ชันของเซตนี้ยังได้รับการพิสูจน์โดยทฤษฎีบทรูปแบบปกติแบบแยกส่วน ) ^{[ 4 ]}แต่เซตนี้ก็ยังไม่ใช่เซตขั้นต่ำ เนื่องจากสามารถกำหนดได้ดังนี้ ${\displaystyle \{\neg ,\land ,\lor \}}$${\displaystyle \lor }$

${\displaystyle A\lor B:=\neg (\neg A\land \neg B).}$

หรืออาจนิยามได้ในลักษณะที่คล้ายคลึงกัน หรืออาจนิยามได้ในแง่ของ: ${\displaystyle \land }$${\displaystyle \lor }$${\displaystyle \lor }$${\displaystyle \rightarrow }$

${\displaystyle \ A\vee B:=\neg A\rightarrow B.}$

ไม่สามารถลดรูปให้ง่ายขึ้นได้อีกแล้ว ดังนั้น เซตตัวเชื่อมสององค์ประกอบทุกเซตที่ประกอบด้วยและหนึ่งในนั้นจึง เป็น เซตย่อยที่สมบูรณ์เชิงฟังก์ชันขั้นต่ำของ${\displaystyle \neg }$${\displaystyle \{\land ,\lor ,\rightarrow \}}$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

กำหนดให้โดเมนบูลีนB = {0, 1}เซตFของฟังก์ชันบูลีนf _i  : B ^{n _i} → Bจะสมบูรณ์เชิงฟังก์ชันก็ต่อเมื่อโคลนบนBที่สร้างขึ้นโดยฟังก์ชันพื้นฐานf _iประกอบด้วยฟังก์ชันf  : B ⁿ → B ทั้งหมด สำหรับจำนวนเต็ม บวก n ≥ 1 ทุก ตัวกล่าวอีกนัยหนึ่ง เซตจะสมบูรณ์เชิงฟังก์ชันก็ต่อเมื่อฟังก์ชันบูลีนทุกฟังก์ชันที่มีตัวแปรอย่างน้อยหนึ่งตัวสามารถแสดงในรูปของฟังก์ชันf _iได้ เนื่องจากฟังก์ชันบูลีนทุกฟังก์ชันที่มีตัวแปรอย่างน้อยหนึ่งตัวสามารถแสดงในรูปของฟังก์ชันบูลีนไบนารีได้ ดังนั้น Fจะสมบูรณ์เชิงฟังก์ชันก็ต่อเมื่อฟังก์ชันบูลีนไบนารีทุกฟังก์ชันสามารถแสดงในรูปของฟังก์ชันในFได้

เงื่อนไขที่เป็นธรรมชาติมากกว่าคือ โคลนที่สร้างโดยFประกอบด้วยฟังก์ชันf  : B ⁿ → B ทั้งหมด สำหรับจำนวนเต็มn ≥ 0 ทั้งหมด อย่างไรก็ตาม ตัวอย่างที่ให้มาข้างต้นไม่สมบูรณ์ในเชิงฟังก์ชันในความหมายที่เข้มงวดกว่านี้ เพราะเป็นไปไม่ได้ที่จะเขียน ฟังก์ชัน ศูนย์ (nullary function) กล่าวคือ นิพจน์ค่าคงที่ ในรูปของFหากFเองไม่มีฟังก์ชันศูนย์อย่างน้อยหนึ่งฟังก์ชัน ด้วยนิยามที่เข้มงวดกว่านี้ เซตที่สมบูรณ์ในเชิงฟังก์ชันที่เล็กที่สุดจะมี 2 องค์ประกอบ

เงื่อนไขตามธรรมชาติอีกประการหนึ่งคือ โคลนที่สร้างโดยFพร้อมกับฟังก์ชันคงที่ศูนย์สองตัวจะต้องสมบูรณ์ในเชิงฟังก์ชัน หรือเทียบเท่ากับสมบูรณ์ในเชิงฟังก์ชันในความหมายที่เข้มงวดของย่อหน้าก่อนหน้า ตัวอย่างของฟังก์ชันบูลีนที่กำหนดโดยS ( x , y , z ) = zถ้าx = yและS ( x , y , z ) = xในกรณีอื่น ๆ แสดงให้เห็นว่าเงื่อนไขนี้อ่อนกว่าความสมบูรณ์ในเชิงฟังก์ชันอย่างเคร่งครัด^{[ 5 ] [ 6 ] [ 7 ]}

เอมิล โพสต์พิสูจน์ว่าเซตของตัวเชื่อมทางตรรกะจะสมบูรณ์ในเชิงฟังก์ชันก็ต่อเมื่อเซตนั้นไม่ใช่เซตย่อยของเซตตัวเชื่อมทางตรรกะใดๆ ต่อไปนี้:

• ตัว เชื่อม แบบโมโนโทนิกการเปลี่ยนค่าความจริงของตัวแปรที่เชื่อมต่อใดๆ จากFเป็นTโดยไม่เปลี่ยนค่าใดๆ จากT เป็น F จะไม่ทำให้ตัวเชื่อมเหล่านี้เปลี่ยนค่าส่งคืนจากTเป็นFเช่น${\displaystyle \vee ,\wedge ,\top ,\bot }$
• ตัว เชื่อม เชิงเส้น (affine connectives) ซึ่งตัวแปรที่เชื่อมต่อแต่ละตัวจะมีผลต่อค่าความจริงที่ตัวเชื่อมเหล่านี้ส่งคืนเสมอหรือไม่มีผลเลยเช่น${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• ตัว เชื่อม แบบคู่ตัวเองซึ่งเท่ากับคู่เดอ มอร์แกน ของตัวเอง หากค่าความจริงของตัวแปรทั้งหมดถูกกลับค่า ค่าความจริงที่ตัวเชื่อมเหล่านี้ส่งคืนก็จะถูกกลับค่าเช่นกันเช่นmaj ( p , q , r )${\displaystyle \neg }$
• ตัว เชื่อม ที่รักษาค่าความจริงไว้จะคืนค่าความจริงTภายใต้การตีความใดๆ ที่กำหนดค่าTให้กับตัวแปรทั้งหมดเช่น${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }$
• ตัว เชื่อม ที่รักษาค่าความเท็จไว้จะคืนค่าความจริงFภายใต้การตีความใดๆ ที่กำหนดค่าFให้กับตัวแปรทั้งหมดเช่น${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$

Post ได้ให้คำอธิบายที่สมบูรณ์ของแลตทิซของโคลน ทั้งหมด (เซตของการดำเนินการที่ปิดภายใต้การประกอบและประกอบด้วยการฉายภาพทั้งหมด) บนเซตสององค์ประกอบ{ T , F }ซึ่งปัจจุบันเรียกว่าแลตทิซของ Postซึ่งบ่งชี้ถึงผลลัพธ์ข้างต้นเป็นผลลัพธ์ที่ง่าย: เซตของตัวเชื่อมทั้งห้าที่กล่าวถึงนั้นเป็นโคลนที่ไม่สำคัญสูงสุดอย่างแท้จริง^{[ 8 ]}

เมื่อตัวเชื่อมตรรกะหรือตัวดำเนินการบูลีนตัวเดียวมีความสมบูรณ์ในเชิงฟังก์ชันด้วยตัวมันเอง จะเรียกว่าฟังก์ชัน Sheffer ^{[ 9 ]}หรือบางครั้ง เรียก ว่าตัวดำเนินการเพียงพอเพียงตัวเดียวไม่มี ตัวดำเนินการเอก ภาคที่มีคุณสมบัตินี้NANDและNORซึ่งเป็นคู่กันเป็นฟังก์ชัน Sheffer ไบนารีเพียงสองตัวเท่านั้น ฟังก์ชันเหล่านี้ถูกค้นพบ แต่ไม่ได้ตีพิมพ์ โดยCharles Sanders Peirceประมาณปี 1880 และถูกค้นพบใหม่และตีพิมพ์โดยอิสระโดยHenry M. Shefferในปี 1913 ^{[ 10 ]} ในศัพท์ทางอิเล็กทรอนิกส์ดิจิทัล เกต NAND ไบนารี (↑) และเกต NOR ไบนารี (↓) เป็นเกตตรรกะสากลไบนารีเพียงสองตัว เท่านั้น

ต่อไปนี้คือชุดตัวเชื่อมตรรกะที่สมบูรณ์ขั้นต่ำที่มีอาร์ริตี ≤ 2: ^{[ 11 ]}

องค์ประกอบหนึ่ง

{↑}, {↓}.

สององค์ประกอบ

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , ,${\displaystyle \{\wedge ,\neg \}}$${\displaystyle \{\to ,\neg \}}$${\displaystyle \{\gets ,\neg \}}$${\displaystyle \{\to ,\bot \}}$${\displaystyle \{\gets ,\bot \}}$${\displaystyle \{\to ,\nleftrightarrow \}}$${\displaystyle \{\gets ,\nleftrightarrow \}}$${\displaystyle \{\to ,\nrightarrow \}}$${\displaystyle \{\to ,\nleftarrow \}}$${\displaystyle \{\gets ,\nrightarrow \}}$${\displaystyle \{\gets ,\nleftarrow \}}$${\displaystyle \{\nrightarrow ,\neg \}}$${\displaystyle \{\nleftarrow ,\neg \}}$${\displaystyle \{\nrightarrow ,\top \}}$${\displaystyle \{\nleftarrow ,\top \}}$${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$${\displaystyle \{\nleftarrow ,\leftrightarrow \}.}$

สามองค์ประกอบ

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, , , , ,${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}.}$

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

บทความของAlfred Tarski เรื่อง "On the Primitive Term of Logistic" พิสูจน์แล้วว่า สมบูรณ์ในเชิง ฟังก์ชัน ^{[ 12 ]}แต่สิ่งนี้จะใช้ได้ก็ต่อเมื่อใช้การกำหนดปริมาณเหนือข้อเสนอ (อุปกรณ์จากตรรกะลำดับที่สอง ) ดังนั้นจึงไม่นับรวมในรายการข้างต้น ${\displaystyle \{\leftrightarrow \}}$

• ตัวอย่างการใช้NANDความสมบูรณ์ (↑) ดังที่แสดงโดย^{[ 13 ]}
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• ตัวอย่างการใช้NORความสมบูรณ์ (↓) ดังที่แสดงโดย^{[ 14 ]}
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

โปรดทราบว่าวงจรไฟฟ้าหรือฟังก์ชันซอฟต์แวร์สามารถปรับให้เหมาะสมที่สุดได้โดยการนำกลับมาใช้ใหม่ เพื่อลดจำนวนเกต ตัวอย่างเช่น การดำเนินการ " A ∧ B " เมื่อแสดงด้วยเกต ↑ จะถูกนำไปใช้โดยการนำ " A ↑ B " กลับมาใช้ใหม่

X ≡ ( A ↑ B ); A ∧ B ≡ X ↑ X

นอกเหนือจากตัวเชื่อมตรรกะ (ตัวดำเนินการบูลีน) แล้ว ความสมบูรณ์เชิงฟังก์ชันยังสามารถนำมาใช้ในโดเมนอื่นๆ ได้อีกด้วย ตัวอย่างเช่น เซตของ เกต แบบย้อนกลับได้จะเรียกว่าสมบูรณ์เชิงฟังก์ชัน หากสามารถแสดงตัวดำเนินการแบบย้อนกลับได้ทุกตัว

เกตเฟรดกินแบบ 3 อินพุตเป็นเกตแบบย้อนกลับได้ที่สมบูรณ์ในเชิงฟังก์ชันด้วยตัวมันเอง – เป็นตัวดำเนินการเพียงพอเพียงตัวเดียว นอกจากนี้ยังมีเกตตรรกะสากลแบบ 3 อินพุตอื่นๆ อีกมากมาย เช่นเกตทอฟโฟลี

ในการคำนวณควอนตัม เกตHadamard , CNOT และเกต Tเป็นเกตสากล แม้ว่าจะมี นิยามที่เข้มงวด กว่าความสมบูรณ์เชิงฟังก์ชัน เล็กน้อย ก็ตาม

มีการสมสัณฐานระหว่างพีชคณิตของเซตและพีชคณิตบูลีนกล่าวคือ ทั้งสองมีโครงสร้าง เหมือนกัน ดังนั้น หากเราแปลงตัวดำเนินการบูลีนเป็นตัวดำเนินการเซต ข้อความข้างต้นที่ "แปล" แล้วก็จะใช้ได้กับเซตด้วยเช่นกัน กล่าวคือ มี "เซตตัวดำเนินการทฤษฎีเซตที่สมบูรณ์ขั้นต่ำ" จำนวนมากที่สามารถสร้างความสัมพันธ์ของเซตอื่นๆ ได้ "เซตตัวดำเนินการที่สมบูรณ์ขั้นต่ำ" ที่ได้รับความนิยมมากกว่าคือ{¬, ∩}และ{¬, ∪}หากเซตสากลถูกห้ามตัวดำเนินการเซตจะถูกจำกัดให้รักษาความเท็จ (Ø) และไม่สามารถเทียบเท่ากับพีชคณิตบูลีนที่สมบูรณ์เชิงฟังก์ชันได้

• พีชคณิตของเซต  – เอกลักษณ์และความสัมพันธ์ที่เกี่ยวข้องกับเซต
• พีชคณิตบูลีน  – การจัดการทางพีชคณิตของค่า "จริง" และ "เท็จ"
• ความสมบูรณ์ (ตรรกะ)  – คุณลักษณะของระบบตรรกะบางระบบ
• ความสัมพันธ์แบบคู่ขนานระหว่างการเชื่อมโยงและการแยก  – คุณสมบัติที่เชื่อมโยงการเชื่อมโยงและการแยกเชิงตรรกะ
• รายชื่อหัวข้อพีชคณิตบูลีน
• ตรรกะ NAND  – ตรรกะที่สร้างขึ้นจากเกต NAND เท่านั้น
• ตรรกะ NOR  – การสร้างเกตอื่นๆ โดยใช้เพียงเกต NOR เท่านั้น
• คอมพิวเตอร์ชุดคำสั่งเดียว  – เครื่องจักรนามธรรมที่ใช้คำสั่งเพียงชุดเดียว