กลับไปหน้าบทความ

อ่าน 5 นาที

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

ใน ตรรกะบู ลี น ตรรกะ NOR [ 1 ] การไม่แยก หรือ การปฏิเสธร่วม [ 1 ] เป็นตัวดำเนินการเชิงฟังก์ชันความจริงซึ่งสร้างผลลัพธ์ที่เป็นการปฏิเสธของ ตรรกะ or นั่นคือ ประโยคในรูปแบบ ( p NOR..

ตรรกะ NOR

ในตรรกะบูลีน ตรรกะ NOR [ 1 ]การไม่แยกหรือการปฏิเสธร่วม[ 1 ]เป็นตัวดำเนินการเชิงฟังก์ชันความจริงซึ่งสร้างผลลัพธ์ที่เป็นการปฏิเสธของตรรกะ orนั่นคือ ประโยคในรูปแบบ ( p NOR q ) จะเป็นจริงก็ต่อเมื่อทั้งpและqไม่เป็นจริง กล่าวคือ เมื่อทั้งpและqเป็นเท็จมันเทียบเท่าทางตรรกะกับ¬(พีq){\displaystyle \neg (p\lor q)}และ¬พี¬q{\displaystyle \neg p\land \neg q}โดยที่สัญลักษณ์¬{\displaystyle \neg }หมายถึงการปฏิเสธ เชิง ตรรกะ{\displaystyle \lor }หมายถึงหรือและ{\displaystyle \land }หมายถึงและ

โดยทั่วไปแล้ว การเชื่อมแบบไม่แยกส่วน (Non-disjunction) จะถูกแสดงด้วยสัญลักษณ์{\displaystyle \downarrow }หรือ¯{\displaystyle {\overline {\vee }}}หรือX{\displaystyle X}(คำนำหน้า) หรือก็ไม่เช่นกัน{\displaystyle \operatorname {NOR} }.

เช่นเดียวกับตัวดำเนินการ NAND (หรือที่รู้จักกันในชื่อSheffer strokeซึ่งมีสัญลักษณ์เป็น หรือ ) ซึ่ง เป็นตัวดำเนิน การคู่ขนานกัน{\displaystyle \uparrow },{\displaystyle \mid }หรือ/{\displaystyle /}NOR สามารถใช้ได้ด้วยตัวเอง โดยไม่ต้องใช้ตัวดำเนินการตรรกะอื่นใด เพื่อสร้างระบบตรรกะ ที่เป็นทางการ (ทำให้ NOR มีความสมบูรณ์ในเชิงฟังก์ชัน )

คอมพิวเตอร์ที่ใช้ในยานอวกาศที่นำมนุษย์ไปดวงจันทร์ เป็นครั้งแรก ซึ่งก็คือApollo Guidance Computerนั้น สร้างขึ้นโดยใช้เกต NOR ทั้งหมดที่มีอินพุตสามตัว[ 2 ]

คำนิยาม

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

ตารางความจริง

ตารางความจริงของเอบี{\displaystyle A\downarrow B}มีรายละเอียดดังนี้:

เอ{\displaystyle A}บี{\displaystyle B}เอบี{\displaystyle A\downarrow B}
เอฟเอฟที
เอฟทีเอฟ
ทีเอฟเอฟ
ทีทีเอฟ

ความสมมูลเชิงตรรกะ

ตรรกะ NOR{\displaystyle \downarrow }คือการปฏิเสธของการเชื่อมแบบ "หรือ":

พีคิว{\displaystyle P\downarrow Q}    {\displaystyle \Leftrightarrow }    ¬(พีคิว){\displaystyle \neg (P\lor Q)}
    {\displaystyle \Leftrightarrow }    ¬{\displaystyle \neg }

สัญลักษณ์และชื่อทางเลือก

Peirceเป็นคนแรกที่แสดงให้เห็นถึงความสมบูรณ์เชิงฟังก์ชันของการแยกแบบไม่ใช่การแยก แม้ว่าเขาจะไม่ได้เผยแพร่ผลลัพธ์ของเขา[ 3 ] [ 4 ] Peirce ใช้¯{\displaystyle {\overline {\curlywedge }}}สำหรับคำที่ไม่เชื่อมและ{\displaystyle \curlywedge }สำหรับการเชื่อมประโยคแบบไม่แยก (อันที่จริง สิ่งที่เพียร์ซเองใช้คือ...){\displaystyle \curlywedge }และเขาไม่ได้แนะนำตัว¯{\displaystyle {\overline {\curlywedge }}}ในขณะที่บรรณาธิการของ Peirce ใช้คำที่มีความหมายชัดเจนเช่นนั้น) [ 4 ] Peirce เรียก{\displaystyle \curlywedge }ที่แอมเฟ็ค (จากภาษากรีกโบราณ ἀμφήκης , amphēkēs , "ตัดได้ทั้งสองทาง") [ 4 ]

ในปี ค.ศ. 1911 สแตมม์เป็นคนแรกที่ตีพิมพ์คำอธิบายเกี่ยวกับทั้งการไม่เชื่อมโยงกัน (โดยใช้~{\displaystyle \sim }(ตะขอของ Stamm) และการไม่แยก (โดยใช้*{\displaystyle *}ดาว Stamm) และแสดงให้เห็นถึงความสมบูรณ์ของฟังก์ชัน[ 5 ] [ 6 ]โปรดทราบว่าการใช้งานส่วนใหญ่ในสัญกรณ์ตรรกะของ~{\displaystyle \sim }ใช้สิ่งนี้สำหรับการปฏิเสธ

ในปี ค.ศ. 1913 เชฟเฟอร์ได้อธิบายถึงการแยกส่วนที่ไม่เกิดขึ้น (non-disjunction) และแสดงให้เห็นถึงความสมบูรณ์เชิงฟังก์ชันของมัน เชฟเฟอร์ใช้{\displaystyle \mid }สำหรับคำที่ไม่เชื่อมติดกัน และ{\displaystyle \wedge }สำหรับการเชื่อมแบบไม่แยก (non-disjunction)

ในปี ค.ศ. 1935 โดนัลด์ แอล. เวบบ์ ได้อธิบายปรากฏการณ์การแยกตัวไม่สมบูรณ์ (non-disjunction) ไว้ดังนี้n{\displaystyle n}ตรรกะแบบมีค่า และใช้{\displaystyle \mid }สำหรับตัวดำเนินการ ดังนั้นบางคนจึงเรียกมันว่าตัวดำเนินการของ Webb [ 7 ] การ ดำเนินการของ Webb [ 8 ]หรือฟังก์ชันของ Webb [ 9 ]

ในปีควินน์ได้อธิบายถึงการแยกส่วนที่ไม่สมบูรณ์และการใช้งานไว้ด้วย{\displaystyle \downarrow }สำหรับตัวดำเนินการ[ 10 ]ดังนั้นบางคนจึงเรียกตัวดำเนินการว่าลูกศรเพียร์ซหรือมีดสั้นควินน์

ในปี ค.ศ. 1944 เชิร์ชยังได้อธิบายถึงการแยกส่วนที่ไม่สมบูรณ์และการใช้งานด้วย¯{\displaystyle {\overline {\vee }}}สำหรับผู้ดำเนินการ[ 11 ]

ในปี 1954 โบเชนสกีได้ใช้X{\displaystyle X}ในXพีq{\displaystyle Xpq}สำหรับการไม่แยกใน สัญกร ณ์โปแลนด์[ 12 ]

APLใช้สัญลักษณ์ที่รวม a กับ a เข้าด้วย ~กัน[ 13 ]

คุณสมบัติ

NOR มีคุณสมบัติการสลับที่ได้ แต่ไม่มีคุณสมบัติการจัดกลุ่ม ซึ่งหมายความว่าพีคิวคิวพี{\displaystyle P\downarrow Q\leftrightarrow Q\downarrow P}แต่(พีคิว)อาร์พี(คิวอาร์){\displaystyle (P\downarrow Q)\downarrow R\not \leftrightarrow P\downarrow (Q\downarrow R)}[ 14 ]

ความสมบูรณ์เชิงฟังก์ชัน

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

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

การดำเนินการบูลีนอื่นๆ ในแง่ของตรรกะ NOR

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

แสดงในรูปของ NOR{\displaystyle \downarrow }ตัวดำเนินการทั่วไปของตรรกศาสตร์เชิงประพจน์ ได้แก่:

¬พี{\displaystyle \neg P}    {\displaystyle \Leftrightarrow }    พีพี{\displaystyle P\downarrow P}
¬{\displaystyle \neg }    {\displaystyle \Leftrightarrow }    
   
พีคิว{\displaystyle P\rightarrow Q}    {\displaystyle \Leftrightarrow }    ((พีพี)คิว){\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}{\displaystyle \downarrow }((พีพี)คิว){\displaystyle {\Big (}(P\downarrow P)\downarrow Q{\Big )}}
    {\displaystyle \Leftrightarrow }    {\displaystyle \downarrow }
 
พีคิว{\displaystyle P\land Q}    {\displaystyle \Leftrightarrow }    (พีพี){\displaystyle (P\downarrow P)}{\displaystyle \downarrow }(คิวคิว){\displaystyle (Q\downarrow Q)}
    {\displaystyle \Leftrightarrow }    {\displaystyle \downarrow }
   
พีคิว{\displaystyle P\lor Q}    {\displaystyle \Leftrightarrow }    (พีคิว){\displaystyle (P\downarrow Q)}{\displaystyle \downarrow }(พีคิว){\displaystyle (P\downarrow Q)}
    {\displaystyle \Leftrightarrow }    {\displaystyle \downarrow }

ดูเพิ่มเติม

  • โลโก้ Wikimedia Commonsสื่อที่เกี่ยวข้องกับLogical NOR ใน Wikimedia Commons

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

ใน ตรรกะบู ลี น ตรรกะ NOR [ 1 ] การไม่แยก หรือ การปฏิเสธร่วม [ 1 ] เป็นตัวดำเนินการเชิงฟังก์ชันความจริงซึ่งสร้างผลลัพธ์ที่เป็นการปฏิเสธของ ตรรกะ or นั่นคือ ประโยคในรูปแบบ ( p NOR..

คำนิยาม

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

ตารางความจริง

ตาราง ความจริง ของ เอ ↓ บี {\displaystyle A\downarrow B} มีรายละเอียดดังนี้:

ความสมมูลเชิงตรรกะ

ตรรกะ NOR ↓ {\displaystyle \downarrow } คือการปฏิเสธของการเชื่อมแบบ "หรือ":