ตรรกะ NOR
ในตรรกะบูลีน ตรรกะ NOR [ 1 ]การไม่แยกหรือการปฏิเสธร่วม[ 1 ]เป็นตัวดำเนินการเชิงฟังก์ชันความจริงซึ่งสร้างผลลัพธ์ที่เป็นการปฏิเสธของตรรกะ orนั่นคือ ประโยคในรูปแบบ ( p NOR q ) จะเป็นจริงก็ต่อเมื่อทั้งpและqไม่เป็นจริง กล่าวคือ เมื่อทั้งpและqเป็นเท็จมันเทียบเท่าทางตรรกะกับและโดยที่สัญลักษณ์หมายถึงการปฏิเสธ เชิง ตรรกะหมายถึงหรือและหมายถึงและ
โดยทั่วไปแล้ว การเชื่อมแบบไม่แยกส่วน (Non-disjunction) จะถูกแสดงด้วยสัญลักษณ์หรือหรือ(คำนำหน้า) หรือ.
เช่นเดียวกับตัวดำเนินการ NAND (หรือที่รู้จักกันในชื่อSheffer strokeซึ่งมีสัญลักษณ์เป็น หรือ ) ซึ่ง เป็นตัวดำเนิน การคู่ขนานกัน,หรือNOR สามารถใช้ได้ด้วยตัวเอง โดยไม่ต้องใช้ตัวดำเนินการตรรกะอื่นใด เพื่อสร้างระบบตรรกะ ที่เป็นทางการ (ทำให้ NOR มีความสมบูรณ์ในเชิงฟังก์ชัน )
คอมพิวเตอร์ที่ใช้ในยานอวกาศที่นำมนุษย์ไปดวงจันทร์ เป็นครั้งแรก ซึ่งก็คือApollo Guidance Computerนั้น สร้างขึ้นโดยใช้เกต NOR ทั้งหมดที่มีอินพุตสามตัว[ 2 ]
คำนิยาม
ตัวดำเนินการ NORเป็นการดำเนินการทางตรรกะ กับ ค่าตรรกะสอง ค่า ซึ่งโดยทั่วไปคือค่าของประพจน์ สองประพจน์ โดยจะให้ค่าเป็นจริงก็ต่อเมื่อตัวถูกดำเนินการทั้งสองเป็นเท็จ กล่าวอีกนัยหนึ่งคือ จะให้ค่าเป็นเท็จก็ต่อเมื่อตัวถูกดำเนินการอย่างน้อยหนึ่งตัวเป็นจริง
ตารางความจริง
ตารางความจริงของมีรายละเอียดดังนี้:
| เอฟ | เอฟ | ที |
| เอฟ | ที | เอฟ |
| ที | เอฟ | เอฟ |
| ที | ที | เอฟ |
ความสมมูลเชิงตรรกะ
ตรรกะ NORคือการปฏิเสธของการเชื่อมแบบ "หรือ":
สัญลักษณ์และชื่อทางเลือก
Peirceเป็นคนแรกที่แสดงให้เห็นถึงความสมบูรณ์เชิงฟังก์ชันของการแยกแบบไม่ใช่การแยก แม้ว่าเขาจะไม่ได้เผยแพร่ผลลัพธ์ของเขา[ 3 ] [ 4 ] Peirce ใช้สำหรับคำที่ไม่เชื่อมและสำหรับการเชื่อมประโยคแบบไม่แยก (อันที่จริง สิ่งที่เพียร์ซเองใช้คือ...)และเขาไม่ได้แนะนำตัวในขณะที่บรรณาธิการของ Peirce ใช้คำที่มีความหมายชัดเจนเช่นนั้น) [ 4 ] Peirce เรียกที่แอมเฟ็ค (จากภาษากรีกโบราณ ἀμφήκης , amphēkēs , "ตัดได้ทั้งสองทาง") [ 4 ]
ในปี ค.ศ. 1911 สแตมม์เป็นคนแรกที่ตีพิมพ์คำอธิบายเกี่ยวกับทั้งการไม่เชื่อมโยงกัน (โดยใช้(ตะขอของ Stamm) และการไม่แยก (โดยใช้ดาว Stamm) และแสดงให้เห็นถึงความสมบูรณ์ของฟังก์ชัน[ 5 ] [ 6 ]โปรดทราบว่าการใช้งานส่วนใหญ่ในสัญกรณ์ตรรกะของใช้สิ่งนี้สำหรับการปฏิเสธ
ในปี ค.ศ. 1913 เชฟเฟอร์ได้อธิบายถึงการแยกส่วนที่ไม่เกิดขึ้น (non-disjunction) และแสดงให้เห็นถึงความสมบูรณ์เชิงฟังก์ชันของมัน เชฟเฟอร์ใช้สำหรับคำที่ไม่เชื่อมติดกัน และสำหรับการเชื่อมแบบไม่แยก (non-disjunction)
ในปี ค.ศ. 1935 โดนัลด์ แอล. เวบบ์ ได้อธิบายปรากฏการณ์การแยกตัวไม่สมบูรณ์ (non-disjunction) ไว้ดังนี้ตรรกะแบบมีค่า และใช้สำหรับตัวดำเนินการ ดังนั้นบางคนจึงเรียกมันว่าตัวดำเนินการของ Webb [ 7 ] การ ดำเนินการของ Webb [ 8 ]หรือฟังก์ชันของ Webb [ 9 ]
ในปีควินน์ได้อธิบายถึงการแยกส่วนที่ไม่สมบูรณ์และการใช้งานไว้ด้วยสำหรับตัวดำเนินการ[ 10 ]ดังนั้นบางคนจึงเรียกตัวดำเนินการว่าลูกศรเพียร์ซหรือมีดสั้นควินน์
ในปี ค.ศ. 1944 เชิร์ชยังได้อธิบายถึงการแยกส่วนที่ไม่สมบูรณ์และการใช้งานด้วยสำหรับผู้ดำเนินการ[ 11 ]
ในปี 1954 โบเชนสกีได้ใช้ในสำหรับการไม่แยกใน สัญกร ณ์โปแลนด์[ 12 ]
คุณสมบัติ
NOR มีคุณสมบัติการสลับที่ได้ แต่ไม่มีคุณสมบัติการจัดกลุ่ม ซึ่งหมายความว่าแต่[ 14 ]
ความสมบูรณ์เชิงฟังก์ชัน
NOR เชิงตรรกะ เมื่อพิจารณาด้วยตัวมันเอง ถือเป็นชุดตัวเชื่อมที่สมบูรณ์ในเชิง ฟังก์ชัน [ 15 ]สามารถพิสูจน์ได้โดยการแสดงตารางความจริง ก่อน ว่ามีค่าเทียบเท่าเชิงฟังก์ชันความจริงกับ[ 16 ]จากนั้นเนื่องจากมีค่าเทียบเท่าเชิงฟังก์ชันความจริงกับ[ 16 ]และเทียบเท่ากับ[ 16 ]ตรรกะ NOR เพียงพอที่จะกำหนดเซตของตัวเชื่อม[ 16 ]ซึ่งแสดงให้เห็นว่าสมบูรณ์ตามฟังก์ชันความจริงโดยทฤษฎีบท รูป แบบปกติแบบแยกส่วน[ 16 ]
สิ่งนี้สามารถเห็นได้จากข้อเท็จจริงที่ว่า ตัวดำเนินการเชิงตรรกะ NOR ไม่มีคุณสมบัติทั้งห้าประการ (รักษาความจริง รักษาความเท็จ เป็นเชิงเส้น เป็น เอกภาคและเป็นคู่ในตัวเอง) ซึ่งเป็นคุณสมบัติที่จำเป็นต้องมีอย่างน้อยหนึ่งตัวในกลุ่มตัวดำเนินการที่สมบูรณ์แบบในเชิง ฟังก์ชัน
การดำเนินการบูลีนอื่นๆ ในแง่ของตรรกะ NOR
ตัวดำเนิน การ NOR มีคุณสมบัติที่น่าสนใจอย่างหนึ่งคือ ตัวดำเนินการตรรกะอื่นๆ ทั้งหมดสามารถแสดงได้ด้วยการดำเนินการ NOR แบบสลับกัน ตัวดำเนินการ ตรรกะ NANDก็มีคุณสมบัตินี้เช่นกัน
แสดงในรูปของ NORตัวดำเนินการทั่วไปของตรรกศาสตร์เชิงประพจน์ ได้แก่: