นอสกิน อันเดรย์ นิโคลาวิช
ครูไอที
หมวดหมู่คุณสมบัติสูงสุด
ผู้สมัครสาขาวิชาวิทยาศาสตร์การทหาร, รองศาสตราจารย์
GBOU Lyceum หมายเลข 1575 มอสโก

วิธีการทำแผนที่ที่ปรับให้เหมาะสมสำหรับการแก้ปัญหา 23 จาก KIM Unified State Examination ในสาขาวิทยาการคอมพิวเตอร์และ ICT

หนึ่งในงานที่ยากที่สุดใน Unified State Exam KIM คือปัญหา 23 ซึ่งคุณต้องค้นหาจำนวนชุดค่าต่างๆ ของตัวแปรลอจิคัลที่ตรงตามเงื่อนไขที่ระบุ
งานนี้อาจเป็นงานที่ยากที่สุดของ KIM Unified State Examination ในสาขาวิทยาการคอมพิวเตอร์และ ICT ตามกฎแล้วผู้สอบไม่เกิน 5% สามารถรับมือกับมันได้ (1)
นักเรียนส่วนน้อยที่ทำภารกิจนี้สำเร็จจะอธิบายได้ดังต่อไปนี้:
- นักเรียนอาจสับสน (ลืม) สัญญาณของการดำเนินการเชิงตรรกะ
- ข้อผิดพลาดทางคณิตศาสตร์ในกระบวนการคำนวณ
- ข้อผิดพลาดในการให้เหตุผลเมื่อค้นหาวิธีแก้ไข
- ข้อผิดพลาดในกระบวนการลดความซับซ้อนของนิพจน์เชิงตรรกะ
- ครูแนะนำให้แก้ไขปัญหานี้หลังจากทำงานทั้งหมดเสร็จแล้วเนื่องจากมีความน่าจะเป็น
ข้อผิดพลาดมีขนาดใหญ่มากและ “น้ำหนัก” ของงานเป็นเพียงจุดหลักจุดเดียวเท่านั้น
นอกจากนี้ ครูบางคนเองก็มีปัญหาในการแก้ปัญหาประเภทนี้ จึงพยายามแก้ไขปัญหาที่ง่ายกว่ากับเด็กๆ
สิ่งที่ทำให้สถานการณ์ซับซ้อนคือในบล็อกนี้มีงานที่แตกต่างกันจำนวนมาก และเป็นไปไม่ได้ที่จะเลือกโซลูชันเทมเพลตใดๆ
เพื่อแก้ไขสถานการณ์นี้ ชุมชนการสอนกำลังสรุปวิธีการหลักสองวิธีในการแก้ปัญหาประเภทนี้: การแก้ปัญหาโดยใช้บิตเชน (2) และวิธีการแมป (3)
ความจำเป็นในการปรับแต่ง (เพิ่มประสิทธิภาพ) วิธีการเหล่านี้เกิดจากการที่งานมีการเปลี่ยนแปลงตลอดเวลาทั้งในโครงสร้างและจำนวนตัวแปร (ตัวแปร X เพียงประเภทเดียว, ตัวแปร X และ Y สองประเภท, สามประเภท: X, Y , ซี)
ความยากลำบากในการฝึกฝนวิธีการเหล่านี้ในการแก้ปัญหาได้รับการยืนยันจากข้อเท็จจริงที่ว่าบนเว็บไซต์ของ K.Yu Polyakov มีการวิเคราะห์ปัญหาประเภทนี้ 38 ครั้ง (4) การวิเคราะห์บางอย่างมีวิธีแก้ไขปัญหามากกว่าหนึ่งประเภท
ล่าสุดใน KIM Unified State Examination สาขาวิทยาการคอมพิวเตอร์ มีปัญหากับตัวแปร X และ Y สองประเภท
ฉันได้ปรับวิธีการแสดงผลให้เหมาะสมแล้ว และสนับสนุนให้นักเรียนใช้วิธีการปรับปรุงนี้
สิ่งนี้ให้ผลลัพธ์ เปอร์เซ็นต์ของนักเรียนของฉันที่สามารถรับมือกับงานนี้แตกต่างกันไปมากถึง 43% ของผู้ที่สอบผ่าน ตามกฎแล้วทุกปีจาก 25 ถึง 33 คนจากเกรด 11 ทั้งหมดจะเข้าสอบ Unified State ในสาขาวิทยาการคอมพิวเตอร์
ก่อนที่จะเกิดปัญหากับตัวแปรสองประเภท นักเรียนใช้วิธีการทำแผนที่ได้สำเร็จมาก แต่หลังจากการปรากฏตัวของ Y ในนิพจน์เชิงตรรกะ ฉันเริ่มสังเกตเห็นว่าคำตอบของเด็กไม่ตรงกับการทดสอบอีกต่อไป ปรากฎว่าพวกเขายังไม่ชัดเจนเกี่ยวกับวิธีการสร้างตารางการแมปด้วยตัวแปรประเภทใหม่ จากนั้นฉันก็เกิดความคิดว่าเพื่อความสะดวกควรลดการแสดงออกทั้งหมดให้เป็นตัวแปรประเภทเดียวตามความสะดวกสำหรับเด็ก
ฉันจะให้เทคนิคนี้โดยละเอียดยิ่งขึ้น เพื่อความสะดวกผมจะพิจารณาโดยใช้ตัวอย่างระบบนิพจน์เชิงตรรกะที่ให้ไว้ใน (4)
ระบบสมการลอจิกมีคำตอบที่แตกต่างกันกี่ข้อ?

(x1 ^ ใช่ 1)=(€x2 วี ¬ ย 2 )
(x2 ^ ใช่ 2)= (¬ x 3 วี ¬ ย 3 )
...
(x5 ^ ใช่ 5) = (¬ x 6 วี ¬ ย 6 )

ที่ไหนx 1 , …, x 6 , ย 1 , …, ย 6 , - ตัวแปรเชิงตรรกะ? คำตอบไม่จำเป็นต้องแสดงรายการชุดตัวแปรต่างๆ ทั้งหมดที่มีความเท่าเทียมกันนี้ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว
สารละลาย:
1. จากการวิเคราะห์ระบบสมการลอจิกพบว่ามีตัวแปรอยู่ 6 ตัว เอ็กซ์และตัวแปร 6 ตัว ยู- เนื่องจากตัวแปรใดๆ เหล่านี้สามารถรับได้เพียงสองค่า (0 และ 1) เราจึงแทนที่ตัวแปรเหล่านี้ด้วยตัวแปรประเภทเดียวกัน 12 ตัว เช่น Z
2. ตอนนี้เรามาเขียนระบบใหม่ด้วยตัวแปรใหม่ที่เป็นประเภทเดียวกัน ความยากของงานคือการจดบันทึกอย่างระมัดระวังเมื่อเปลี่ยนตัวแปร

(ซี 1 ^ ซี 2)= (€z3วี¬ z 4 )
(ซี 3 ^ ซี 4)= (¬ z 5 วี¬ z 6 )
...
(ซี 9 ^ ซี 10) = (¬ z 11 วี¬ z 12)

3. มาสร้างตารางที่เราจะพูดถึงตัวเลือกทั้งหมดกัน z 1 , z 2 , z 3 , z 4 เนื่องจากสมการตรรกะแรกมีตัวแปรสี่ตัวแปร ตารางจึงมี 16 แถว (16=2 4) ลบค่าดังกล่าวออกจากตาราง z 4 ซึ่งสมการแรกไม่มีคำตอบ (ขีดฆ่าตัวเลข)

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. วิเคราะห์ตาราง เราสร้างกฎสำหรับการแสดงคู่ของตัวแปร (เช่น คู่ ซี 1 ซี 2 =00 สอดคล้องกันคู่ ซี 3 ซี 4 = 11) .

5. กรอกตารางโดยคำนวณจำนวนคู่ของตัวแปรที่ระบบมีคำตอบ

6. รวมผลลัพธ์ทั้งหมด: 9 + 9 + 9 + 27 = 54
7. คำตอบ: 54.
วิธีการที่ปรับให้เหมาะสมข้างต้นสำหรับการแก้ปัญหา 23 จาก Unified State Exam KIM ช่วยให้นักเรียนได้รับความมั่นใจและแก้ไขปัญหาประเภทนี้ได้สำเร็จ

วรรณกรรม:

1. ฟิปี. คำแนะนำด้านระเบียบวิธีสำหรับครู ซึ่งจัดทำขึ้นบนพื้นฐานของการวิเคราะห์ข้อผิดพลาดทั่วไปของผู้เข้าร่วมในการสอบ Unified State ประจำปี 2558 ในสาขาวิทยาศาสตร์สารสนเทศและไอซีที โหมดการเข้าถึง: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. ก.ย. โปลยาคอฟ, M.A. รอยต์เบิร์ก.ระบบสมการลอจิก: การแก้ปัญหาโดยใช้สตริงบิต วารสารสารสนเทศ ฉบับที่ 12, 2014, หน้า. 4-12.สำนักพิมพ์ "First of September", มอสโก
3. อี.เอ. มิรอนชิค วิธีการแสดงนิตยสาร สารสนเทศ ฉบับที่ 10, 2013, น. 18-26. สำนักพิมพ์ "First of September", มอสโก

การแก้ระบบสมการลอจิกโดยการเปลี่ยนตัวแปร

วิธีการทดแทนตัวแปรจะใช้หากตัวแปรบางตัวรวมอยู่ในสมการเฉพาะในรูปแบบของนิพจน์เฉพาะเท่านั้น และไม่มีอะไรอื่นอีก จากนั้นนิพจน์นี้สามารถแสดงด้วยตัวแปรใหม่ได้

ตัวอย่างที่ 1

มีชุดค่าต่างๆ ของตัวแปรลอจิคัล x1, x2, x3, x4, x5, x6, x7, x8 กี่ชุดที่ตรงตามเงื่อนไขทั้งหมดที่แสดงด้านล่าง

(x1 → x2) → (x3→ x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

คำตอบไม่จำเป็นต้องแสดงรายการชุดค่าต่าง ๆ ทั้งหมดของตัวแปร x1, x2, x3, x4, x5, x6, x7, x8 ซึ่งเป็นไปตามระบบความเท่าเทียมกันนี้ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว

สารละลาย:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4

จากนั้นเราสามารถเขียนระบบเป็นสมการเดียวได้:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1 การร่วมคือ 1 (จริง) เมื่อแต่ละตัวถูกดำเนินการรับค่า 1 นั่นคือ แต่ละนัยจะต้องเป็นจริงและเป็นจริงสำหรับทุกค่ายกเว้น (1 → 0) เหล่านั้น. ในตารางค่าของตัวแปร y1, y2, y3, y4 ไม่ควรอยู่ทางด้านซ้ายของศูนย์:

เหล่านั้น. เป็นไปตามเงื่อนไข 5 ชุด y1-y4

เพราะ y1 = x1 → x2 ดังนั้นค่า y1 = 0 จะได้รับจากชุดเดียว x1, x2: (1, 0) และค่า y1 = 1 – ในสามชุด x1, x2: (0,0) , (0 ,1), (1.1) ในทำนองเดียวกันสำหรับ y2, y3, y4

เนื่องจากแต่ละชุด (x1,x2) สำหรับตัวแปร y1 ถูกรวมเข้ากับแต่ละชุด (x3,x4) สำหรับตัวแปร y2 เป็นต้น จำนวนชุดของตัวแปร x จะถูกคูณ:

				จำนวนชุดต่อ x1…x8

ลองบวกจำนวนชุดกัน: 1 + 3 + 9 + 27 + 81 = 121

คำตอบ: 121

ตัวอย่างที่ 2

มีชุดค่าที่แตกต่างกันของตัวแปรลอจิคัล x1, x2, ... x9, y1, y2, ... y9 กี่ชุดที่ตรงตามเงื่อนไขทั้งหมดที่ระบุไว้ด้านล่าง

(ฌ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(ฌ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(ฌ (x8 ≡ y8)) ≡ (x9 ≡ y9)

ในการตอบสนอง ไม่จำเป็นแสดงรายการชุดค่าต่าง ๆ ทั้งหมดของตัวแปร x1, x2, ... x9, y1, y2, ... y9 ซึ่งเป็นไปตามระบบความเท่าเทียมกันที่กำหนด คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว

สารละลาย:

มาทำการเปลี่ยนแปลงตัวแปรกัน:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

ระบบสามารถเขียนเป็นสมการเดียวได้:

(‚ z1 ≡ z2) ∧ (‚ z2 ≡ z3) ∧ …..∧ (‚ z8 ≡ z9)

ความเท่าเทียมกันเป็นจริงก็ต่อเมื่อตัวถูกดำเนินการทั้งสองมีค่าเท่ากัน สมการนี้มีวิธีแก้สองชุด:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

เพราะ zi = (xi ≡ yi) ดังนั้นค่า zi = 0 สอดคล้องกับสองชุด (xi,yi): (0,1) และ (1,0) และค่า zi = 1 สอดคล้องกับสองชุด (xi,yi) ): (0 ,0) และ (1,1)

จากนั้นเซตแรก z1, z2,…, z9 สอดคล้องกับ 2 9 เซต (x1,y1), (x2,y2),…, (x9,y9)

หมายเลขเดียวกันตรงกับชุดที่สอง z1, z2,…, z9 แล้วมีทั้งหมด 2 9 +2 9 = 1024 ชุด

คำตอบ: 1024

การแก้ระบบสมการตรรกะโดยใช้วิธีการหาค่าการเรียกซ้ำด้วยภาพ

วิธีการนี้ใช้หากระบบสมการค่อนข้างง่ายและลำดับการเพิ่มจำนวนชุดเมื่อบวกตัวแปรชัดเจน

ตัวอย่างที่ 3

ระบบสมการมีคำตอบที่แตกต่างกันกี่ข้อ?

ฌx9 ∨ x10 = 1,

โดยที่ x1, x2, … x10 เป็นตัวแปรเชิงตรรกะ?

คำตอบไม่จำเป็นต้องแสดงรายการชุดค่าต่าง ๆ ทั้งหมด x1, x2, ... x10 ซึ่งเป็นไปตามระบบความเท่าเทียมกันนี้ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว

สารละลาย:

มาแก้สมการแรกกัน การแตกแยกจะเท่ากับ 1 ถ้าตัวถูกดำเนินการอย่างน้อยหนึ่งตัวมีค่าเท่ากับ 1 นั่นคือ วิธีแก้ปัญหาคือชุด:

สำหรับ x1=0 มีสองค่าของ x2 (0 และ 1) และสำหรับ x1=1 มีเพียงค่าเดียวของ x2 (1) โดยที่เซต (x1,x2) จะเป็นคำตอบของสมการ . มีทั้งหมด 3 ชุด

ลองบวกตัวแปร x3 แล้วพิจารณาสมการที่สอง มันคล้ายกับค่าแรกซึ่งหมายความว่าสำหรับ x2=0 มีสองค่าของ x3 (0 และ 1) และสำหรับ x2=1 มีเพียงค่าเดียวเท่านั้น x3 (1) เพื่อให้เซต (x2) ,x3) คือคำตอบของสมการ มีทั้งหมด 4 ชุด

จะสังเกตง่ายๆ ว่าเมื่อเพิ่มตัวแปรอีกชุดหนึ่งก็จะถูกเพิ่มเข้าไป เหล่านั้น. สูตรเรียกซ้ำสำหรับจำนวนชุดของตัวแปร (i+1):

N i +1 = N i + 1 จากนั้นสำหรับตัวแปร 10 ตัว เราจะได้ 11 ชุด

คำตอบ: 11

การแก้ระบบสมการตรรกะประเภทต่างๆ

ตัวอย่างที่ 4

มีชุดค่าที่แตกต่างกันของตัวแปรลอจิคัล x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 กี่ชุดที่ตรงตามเงื่อนไขทั้งหมดที่ระบุไว้ด้านล่าง ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(ปี 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

ในการตอบสนอง ไม่จำเป็นแสดงรายการชุดค่าต่าง ๆ ทั้งหมดของตัวแปร x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 ที่ระบบความเท่าเทียมกันนี้พอใจ

คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว

สารละลาย:

โปรดทราบว่าสมการทั้งสามของระบบเหมือนกันกับชุดตัวแปรอิสระที่ต่างกัน

ลองดูสมการแรกกัน การรวมเป็นจริง (เท่ากับ 1) ก็ต่อเมื่อตัวถูกดำเนินการทั้งหมดเป็นจริง (เท่ากับ 1) ความหมายคือ 1 ในทุกสิ่งอันดับ ยกเว้น (1,0) ซึ่งหมายความว่าคำตอบของสมการแรกจะเป็นเซตต่อไปนี้ x1, x2, x3, x4 โดยที่ 1 ไม่ได้อยู่ทางด้านซ้ายของ 0 (5 ชุด):

ในทำนองเดียวกัน การแก้สมการที่สองและสมการที่สามจะเป็นเซต y1,…,y4 และ z1,…, z4 ที่เหมือนกันทุกประการ

ทีนี้มาวิเคราะห์สมการที่สี่ของระบบ: x ​​4 ∧ y 4 ∧ z 4 = 0 ผลเฉลยจะเป็นเซต x4, y4, z4 ทั้งหมด โดยที่ตัวแปรอย่างน้อยหนึ่งตัวมีค่าเท่ากับ 0

เหล่านั้น. สำหรับ x4 = 0 เซตที่เป็นไปได้ทั้งหมด (y4, z4) เหมาะสม และสำหรับ x4 = 1 เซต (y4, z4) เหมาะสม โดยมีศูนย์อย่างน้อยหนึ่งตัว: (0, 0), (0,1 ) , (1, 0)

				จำนวนชุด

จำนวนเซ็ตทั้งหมดคือ 25 + 4*9 = 25 + 36 = 61

คำตอบ: 61

การแก้ระบบสมการตรรกะโดยการสร้างสูตรที่เกิดซ้ำ

วิธีสร้างสูตรที่เกิดซ้ำใช้ในการแก้ระบบที่ซับซ้อนซึ่งลำดับการเพิ่มจำนวนชุดไม่ชัดเจน และการสร้างแผนภูมิเป็นไปไม่ได้เนื่องจากปริมาตร

ตัวอย่างที่ 5

มีชุดค่าที่แตกต่างกันของตัวแปรลอจิคัล x1, x2, ... x7, y1, y2, ... y7 ที่ตรงตามเงื่อนไขทั้งหมดที่ระบุไว้ด้านล่างกี่ชุด?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

คำตอบไม่จำเป็นต้องแสดงรายการชุดค่าต่าง ๆ ทั้งหมดของตัวแปร x1, x2, ..., x7, y1, y2, ..., y7 ที่ระบบความเท่าเทียมกันนี้พอใจ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว

สารละลาย:

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

เรามาแสดงว่า:

จำนวนสิ่งอันดับ (0,0) บนตัวแปร (x1,y1) ถึง A 1

จำนวนสิ่งอันดับ (0,1) บนตัวแปร (x1,y1) ถึง B 1

จำนวนสิ่งอันดับ (1,0) บนตัวแปร (x1,y1) ถึง C 1

จำนวนสิ่งอันดับ (1,1) บนตัวแปร (x1,y1) ถึง D 1

จำนวนสิ่งอันดับ (0,0) บนตัวแปร (x2,y2) ถึง A 2

จำนวนสิ่งอันดับ (0,1) บนตัวแปร (x2,y2) ถึง B 2

จำนวนสิ่งอันดับ (1,0) บนตัวแปร (x2,y2) ถึง C 2

จำนวนสิ่งอันดับ (1,1) บนตัวแปร (x2,y2) ถึง D 2

จากแผนผังการตัดสินใจเราจะเห็นว่า

ก 1 =0, ข 1 =1, ค 1 =1, ง 1 =1

โปรดทราบว่าเซต (0,0) ของตัวแปร (x2,y2) ได้มาจากเซต (0,1), (1,0) และ (1,1) ของตัวแปร (x1,y1) เหล่านั้น. ก 2 =ข 1 +ค 1 +ง 1

เซต (0,1) ของตัวแปร (x2,y2) ได้มาจากเซต (0,1), (1,0) และ (1,1) ของตัวแปร (x1,y1) เหล่านั้น. ข 2 =ข 1 +ค 1 +ง 1

เมื่อโต้แย้งในทำนองเดียวกัน เราสังเกตว่า C 2 =B 1 +C 1 +D 1 ด2 = ดี1

ดังนั้นเราจึงได้สูตรที่เกิดซ้ำ:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

มาจัดโต๊ะกันเถอะ

ชุด	การกำหนด.	สูตร	จำนวนชุด
			ผม=1	ผม=2	ผม=3	ผม=4	ผม=5	ผม=6	ผม=7
(0,0)	ฉัน	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	บี ฉัน	ข i+1 =ข ฉัน +C ฉัน +D ฉัน	1	3	7	15	31	63	127
(1,0)	ซี ฉัน	C ผม+1 =B ผม +C ผม +D ผม	1	3	7	15	31	63	127
(1,1)	ฉัน	ดี ไอ+1 = ดี ไอ	1	1	1	1	1	1	1

สมการสุดท้าย (x7 ∨ y7) = 1 เป็นไปตามสมการทุกเซต ยกเว้นเซตที่มี x7=0 และ y7=0 ในตารางของเราจำนวนชุดดังกล่าวคือ A 7

จากนั้นจำนวนเซตทั้งหมดคือ B 7 + C 7 + D 7 = 127+127+1 = 255

คำตอบ: 255

วิธีการแก้ระบบสมการเชิงตรรกะ

Kirgizova E.V., Nemkova A.E.

สถาบันสอนการสอน Lesosibirsk –

สาขามหาวิทยาลัยสหพันธ์ไซบีเรีย ประเทศรัสเซีย

ความสามารถในการคิดอย่างสม่ำเสมอ ให้เหตุผลอย่างน่าเชื่อถือ สร้างสมมติฐาน และหักล้างข้อสรุปเชิงลบไม่ได้เกิดขึ้นเอง ทักษะนี้ได้รับการพัฒนาโดยศาสตร์แห่งตรรกะ ตรรกะเป็นศาสตร์ที่ศึกษาวิธีการสร้างความจริงหรือเท็จของข้อความบางข้อความบนพื้นฐานของความจริงหรือเท็จของข้อความอื่นๆ

การเรียนรู้พื้นฐานของวิทยาศาสตร์นี้เป็นไปไม่ได้หากปราศจากการแก้ปัญหาเชิงตรรกะ การทดสอบการพัฒนาทักษะเพื่อนำความรู้ไปใช้ในสถานการณ์ใหม่นั้นดำเนินการผ่านการผ่าน โดยเฉพาะอย่างยิ่งนี่คือความสามารถในการแก้ไขปัญหาเชิงตรรกะ งาน B15 ในการสอบ Unified State เป็นงานที่มีความซับซ้อนเพิ่มขึ้นเนื่องจากมีระบบสมการตรรกะ มีหลายวิธีในการแก้ระบบสมการเชิงตรรกะ เช่น การลดลงเหลือเพียงสมการเดียว การสร้างตารางความจริง การสลายตัว การแก้สมการตามลำดับ เป็นต้น

งาน:แก้ระบบสมการตรรกะ:

ลองพิจารณาดู วิธีการลดให้เป็นสมการเดียว - วิธีนี้เกี่ยวข้องกับการเปลี่ยนสมการเชิงตรรกะเพื่อให้ด้านขวามือมีค่าเท่ากับค่าความจริง (นั่นคือ 1) เมื่อต้องการทำเช่นนี้ ให้ใช้การดำเนินการปฏิเสธเชิงตรรกะ จากนั้น หากสมการมีการดำเนินการเชิงตรรกะที่ซับซ้อน เราจะแทนที่ด้วยการดำเนินการพื้นฐาน: "AND", "OR", "NOT" ขั้นตอนต่อไปคือการรวมสมการให้เป็นหนึ่งเดียว ซึ่งเทียบเท่ากับระบบ โดยใช้การดำเนินการเชิงตรรกะ "AND" หลังจากนี้ คุณควรแปลงสมการผลลัพธ์ตามกฎของพีชคณิตเชิงตรรกะและรับวิธีแก้ปัญหาเฉพาะของระบบ

โซลูชันที่ 1:ใช้การผกผันกับทั้งสองด้านของสมการแรก:

ลองจินตนาการถึงความหมายผ่านการดำเนินการพื้นฐาน "OR" และ "NOT":

เนื่องจากด้านซ้ายมือของสมการมีค่าเท่ากับ 1 เราจึงสามารถรวมพวกมันเข้าด้วยกันโดยใช้การดำเนินการ "AND" ให้เป็นสมการเดียวที่เทียบเท่ากับระบบดั้งเดิม:

เราเปิดวงเล็บแรกตามกฎของ De Morgan และแปลงผลลัพธ์ที่ได้รับ:

สมการผลลัพธ์มีวิธีแก้ปัญหาเดียว:ก= 0, B =0 และ C =1

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

โซลูชันที่ 2:มาสร้างตารางความจริงสำหรับระบบกัน:

0	0	1	1	0	1

บรรทัดที่ตรงตามเงื่อนไขของงานจะถูกเน้นด้วยตัวหนา ดังนั้น A =0, B =0 และ C =1

ทาง การสลายตัว . แนวคิดก็คือการแก้ไขค่าของตัวแปรตัวใดตัวหนึ่ง (ตั้งค่าให้เท่ากับ 0 หรือ 1) และทำให้สมการง่ายขึ้น จากนั้นคุณสามารถแก้ไขค่าของตัวแปรตัวที่สองและอื่นๆ ได้

โซลูชันที่ 3:อนุญาต A = 0 จากนั้น:

จากสมการแรกที่เราได้รับบี =0 และจากวินาที – C=1 คำตอบของระบบ: A = 0, B = 0 และ C = 1

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

สมการแรกของระบบขึ้นอยู่กับ A และ B เท่านั้น และสมการที่สองบน A และ C ตัวแปร A สามารถรับได้ 2 ค่า 0 และ 1:

จากสมการแรกเป็นไปตามนั้น ดังนั้นเมื่อใด A = 0 และเราได้ B = 0 และสำหรับ A = 1 เรามี B = 1 ดังนั้น สมการแรกจึงมีคำตอบสองข้อที่เกี่ยวข้องกับตัวแปร A และ B

ให้เราพรรณนาสมการที่สองซึ่งเรากำหนดค่าของ C สำหรับแต่ละตัวเลือก เมื่อ A =1 ความหมายจะเป็นเท็จไม่ได้ กล่าวคือ กิ่งที่สองของต้นไม้ไม่มีวิธีแก้ปัญหา ที่ก= 0 เราได้รับทางออกเดียวค= 1 :

ดังนั้นเราจึงได้คำตอบของระบบ: A = 0, B = 0 และ C = 1

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

งาน:สมการนี้มีคำตอบกี่ข้อ (ก → ข ) + (ค → ง ) = 1? โดยที่ A, B, C, D เป็นตัวแปรเชิงตรรกะ

สารละลาย:มาแนะนำตัวแปรใหม่กัน: X = A → B และ Y = C → D - เมื่อคำนึงถึงตัวแปรใหม่ สมการจะถูกเขียนเป็น: X + Y = 1

การแยกส่วนเป็นจริงในสามกรณี: (0;1), (1;0) และ (1;1) ในขณะที่ X และ Y เป็นนัยคือเป็นจริงในสามกรณีและเท็จในกรณีเดียว ดังนั้น กรณี (0;1) จะสอดคล้องกับชุดพารามิเตอร์ที่เป็นไปได้สามชุด กรณี (1;1) – จะสอดคล้องกับชุดพารามิเตอร์ที่เป็นไปได้เก้าชุดของสมการดั้งเดิม ซึ่งหมายความว่าผลรวมที่เป็นไปได้ของสมการนี้คือ 3+9=15

วิธีต่อไปในการกำหนดจำนวนคำตอบของระบบสมการตรรกะคือ ต้นไม้ไบนารี- ลองดูวิธีนี้โดยใช้ตัวอย่าง

งาน:ระบบสมการตรรกะมีคำตอบที่แตกต่างกันกี่ข้อ:

ระบบสมการที่กำหนดนั้นเทียบเท่ากับสมการ:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x ม -1 → x ม) = 1.

เรามาแกล้งทำเป็นว่าx 1 – เป็นจริง จากนั้นเราจะได้สมการแรกจากสมการแรกx 2 ก็จริงเช่นกันตั้งแต่วินาที -x 3 =1 และต่อๆ ไปจนกระทั่ง x ม= 1. ดังนั้นเซต (1; 1; …; 1) ของม หน่วยคือคำตอบของระบบ ปล่อยให้มันตอนนี้x 1 =0 จากนั้นจากสมการแรกที่เรามีx 2 =0 หรือ x 2 =1.

เมื่อไร x 2 จริง เราพบว่าตัวแปรที่เหลือก็เป็นจริงเช่นกัน กล่าวคือ เซต (0; 1; ...; 1) เป็นคำตอบของระบบ ที่x 2 =0 เราเข้าใจแล้ว x 3 =0 หรือ x 3 = และอื่นๆ จากตัวแปรตัวสุดท้าย เราจะพบว่าคำตอบของสมการคือชุดของตัวแปรต่อไปนี้ (ม โซลูชัน +1 ในแต่ละโซลูชันม ค่าตัวแปร):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

วิธีการนี้แสดงให้เห็นได้ดีโดยการสร้างต้นไม้ไบนารี จำนวนวิธีแก้ไขที่เป็นไปได้คือจำนวนกิ่งก้านที่แตกต่างกันของต้นไม้ที่สร้างขึ้น มันง่ายที่จะเห็นว่ามันเท่าเทียมกันม. +1

ตัวแปร	ต้นไม้	จำนวนโซลูชั่น
x1
x2
x3

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

ลองเขียนระบบสมการใหม่ในรูปแบบ:

และมาสร้างตารางความจริงแยกกันสำหรับสมการเดียว:

x1	x2	(x 1 → x 2)

มาสร้างตารางความจริงสำหรับสองสมการกัน:

x1	x2	x3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

ต่อไป คุณจะเห็นว่าสมการหนึ่งเป็นจริงในสามกรณีต่อไปนี้: (0; 0), (0; 1), (1; 1) ระบบสองสมการเป็นจริงในสี่กรณี (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1) ในกรณีนี้เป็นที่ชัดเจนทันทีว่ามีวิธีแก้ปัญหาที่ประกอบด้วยศูนย์เท่านั้นและมากกว่านั้น มโซลูชันที่เพิ่มทีละหน่วย เริ่มจากตำแหน่งสุดท้ายจนกระทั่งเต็มทุกตำแหน่งที่เป็นไปได้ สามารถสันนิษฐานได้ว่าวิธีแก้ปัญหาทั่วไปจะมีรูปแบบเดียวกัน แต่สำหรับแนวทางดังกล่าวที่จะกลายเป็นวิธีแก้ปัญหา จำเป็นต้องมีการพิสูจน์ว่าสมมติฐานนั้นถูกต้อง

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

วรรณกรรม:

1. ปัญหาเชิงตรรกะ / อ.บ. โบโกโมลอฟ – ฉบับที่ 2 – ม.: บินอม. ห้องปฏิบัติการความรู้, 2549. – 271 หน้า: ป่วย.

2. Polyakov K.Yu. ระบบสมการตรรกะ / หนังสือพิมพ์การศึกษาและระเบียบวิธีสำหรับครูวิทยาการคอมพิวเตอร์: สารสนเทศ ฉบับที่ 14, 2554.

เมื่อสิ้นปีปรากฏว่ามีเพียงหนึ่งในสามสมมติฐานเท่านั้นที่เป็นจริง หน่วยงานไหนทำกำไรสิ้นปี?

สารละลาย. ให้เราเขียนสมมติฐานจากเงื่อนไขของปัญหาในรูปแบบของข้อความเชิงตรรกะ: “การรับผลกำไรจากแผนก B ไม่ใช่เงื่อนไขที่จำเป็นสำหรับการได้รับ

กำไรตามแผนก A ":F 1 (A, B, C) = A → B

“การได้กำไรจากดิวิชั่น B และ C อย่างน้อยหนึ่งรายการไม่เพียงพอสำหรับดิวิชั่น A ที่จะทำกำไร”: F 2 (A, B, C) = (B + C) → A

“ดิวิชั่น A และ B จะไม่ทำกำไรในเวลาเดียวกัน”: F 3 (A, B, C) = A B

จากเงื่อนไขเป็นที่รู้กันว่าสมมติฐานเพียงหนึ่งในสามข้อเท่านั้นที่เป็นจริง ซึ่งหมายความว่าเราต้องค้นหาว่านิพจน์เชิงตรรกะใดในสามนิพจน์ต่อไปนี้ไม่เป็นเท็จเหมือนกัน:

1) ฉ 1F 2F 3

2) ฉ 1F 2F 3

3) ฉ 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

ด้วยเหตุนี้ เมื่อสิ้นปี ข้อสันนิษฐานที่สองก็เป็นจริง และข้อสันนิษฐานข้อแรกและข้อสามก็เป็นเท็จ

									ก=0
	F1 F2 F3 = ABC= 1
									ถ้าหากว่า B = 0
									ค=1

ดังนั้นดิวิชั่น C จะได้รับผลกำไร แต่ดิวิชั่น A และ B จะไม่ได้รับผลกำไร

การแก้สมการลอจิก

ในข้อความของการทดสอบแบบรวมศูนย์ของรัฐมีงาน (A8) ซึ่งขอให้ค้นหารากของสมการเชิงตรรกะ ลองดูวิธีแก้ปัญหาดังกล่าวโดยใช้ตัวอย่าง

ค้นหารากของสมการตรรกะ: (A + B)(X AB) = B + X → A

วิธีแก้ปัญหาแรกคือการสร้างตารางความจริง มาสร้างตารางความจริงสำหรับด้านขวาและด้านซ้ายของสมการแล้วดูว่า X ค่าใดในคอลัมน์สุดท้ายของตารางเหล่านี้ตรงกัน

F1 (A, B, X) = (A+ B)(X AB)

					เอ+บี	(เอ+ ข)(X เอบี)	ฉ 1 (ก ,บี ,เอ็กซ์ )

F2 (A, B, X) = B+ X→ A

			X → ก							ฉ 2 (ก ,บี ,เอ็กซ์ )
					X → ก			X → ก

ลองเปรียบเทียบตารางความจริงที่ได้และเลือกแถวที่มีค่า F 1 (A, B, X) และ F 2 (A, B, X) ตรงกัน

			ฉ 1 (ก ,บี ,เอ็กซ์ )	ฉ 2 (ก ,บี ,เอ็กซ์ )

มาเขียนใหม่เฉพาะแถวที่เลือก เหลือเพียงคอลัมน์อาร์กิวเมนต์ ลองดูที่ตัวแปร X ที่เป็นฟังก์ชันของ A และ B

แน่นอน X = B → A

วิธีที่สองคือการแทนที่เครื่องหมายเท่ากับในสมการด้วยเครื่องหมายที่เทียบเท่ากัน จากนั้นจึงทำให้สมการตรรกะที่ได้ออกมาเป็นแบบง่ายขึ้น

เพื่อความสะดวกในการทำงานต่อไป ก่อนอื่นมาลดความซับซ้อนของด้านขวาและด้านซ้ายของสมการตรรกะแล้วค้นหาการปฏิเสธ:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

ลองแทนที่เครื่องหมายเท่ากับในสมการเชิงตรรกะของเราด้วยเครื่องหมายสมมูล:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

ลองจัดเรียงเงื่อนไขตรรกะของนิพจน์นี้ใหม่ โดยนำตัวประกอบ X และ X ออกจากวงเล็บ

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

ให้เราแสดงว่า T = A B แล้ว

XT+ XT= X↔ ต.

ดังนั้น เพื่อให้สมการลอจิกมีคำตอบ: X = A B = B + A = B → A

องค์ประกอบทางตรรกะของคอมพิวเตอร์ การสร้างไดอะแกรมการทำงาน

ด้วยการพัฒนาเทคโนโลยีคอมพิวเตอร์ ตรรกะทางคณิตศาสตร์มีความเกี่ยวข้องอย่างใกล้ชิดกับประเด็นการออกแบบและการเขียนโปรแกรมเทคโนโลยีคอมพิวเตอร์ พีชคณิตของตรรกะพบการประยุกต์ใช้อย่างกว้างขวางในช่วงเริ่มต้นในการพัฒนา หน้าสัมผัสรีเลย์แผนงาน การวิจัยพื้นฐานครั้งแรกที่ดึงดูดความสนใจของวิศวกรที่เกี่ยวข้องกับการออกแบบคอมพิวเตอร์ถึงความเป็นไปได้ในการวิเคราะห์วงจรไฟฟ้าโดยใช้พีชคณิตแบบบูล ได้รับการตีพิมพ์ในเดือนธันวาคม พ.ศ. 2481 โดย American Claude Shannon เรื่อง "การวิเคราะห์เชิงสัญลักษณ์ของวงจรแลดเดอร์" หลังจากบทความนี้ การออกแบบคอมพิวเตอร์ไม่สามารถทำได้หากไม่มีการใช้พีชคณิตแบบบูล

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

การเชื่อมต่อแบบอนุกรมของผู้ติดต่อ

การเชื่อมต่อแบบขนานของผู้ติดต่อ

มารวบรวมตารางการขึ้นต่อกันของสถานะของวงจรกับสถานะที่เป็นไปได้ทั้งหมดของหน้าสัมผัส ให้เราแนะนำสัญลักษณ์ต่อไปนี้: 1 – หน้าสัมผัสปิดอยู่ มีกระแสอยู่ในวงจร; 0 - หน้าสัมผัสเปิดอยู่ ไม่มีกระแสไฟฟ้าในวงจร

		สภาพวงจร	สภาพวงจรขนานกัน
		การเชื่อมต่อแบบอนุกรม	การเชื่อมต่อ

อย่างที่คุณเห็นวงจรที่มีการเชื่อมต่อแบบอนุกรมสอดคล้องกับการดำเนินการเชิงตรรกะของการเชื่อมต่อเนื่องจากกระแสไฟฟ้าในวงจรจะปรากฏเฉพาะเมื่อปิดหน้าสัมผัส A และ B พร้อมกัน วงจรที่มีการเชื่อมต่อแบบขนานสอดคล้องกับการดำเนินการเชิงตรรกะของการแยกเนื่องจากไม่มีกระแสไฟฟ้าในวงจรเฉพาะในขณะที่เปิดหน้าสัมผัสทั้งสองเท่านั้น

การดำเนินการเชิงตรรกะของการผกผันจะดำเนินการผ่านวงจรหน้าสัมผัสของรีเลย์แม่เหล็กไฟฟ้าซึ่งมีการศึกษาหลักการในหลักสูตรฟิสิกส์ของโรงเรียน ติดต่อ x เปิดเมื่อ x ปิดและในทางกลับกัน

การใช้องค์ประกอบหน้าสัมผัสรีเลย์เพื่อสร้างวงจรลอจิคัลของคอมพิวเตอร์ไม่ได้พิสูจน์ตัวเองเนื่องจากความน่าเชื่อถือต่ำ ขนาดใหญ่ การใช้พลังงานสูง และประสิทธิภาพต่ำ การถือกำเนิดของอุปกรณ์อิเล็กทรอนิกส์ (สุญญากาศและเซมิคอนดักเตอร์) ได้สร้างความเป็นไปได้ในการสร้างองค์ประกอบลอจิกด้วยความเร็ว 1 ล้านสวิตช์ต่อวินาทีและสูงกว่า องค์ประกอบตรรกะของเซมิคอนดักเตอร์ทำงานในโหมดสวิตช์คล้ายกับรีเลย์แม่เหล็กไฟฟ้า ทฤษฎีทั้งหมดที่นำเสนอสำหรับวงจรหน้าสัมผัสจะถูกถ่ายโอนไปยังองค์ประกอบเซมิคอนดักเตอร์ องค์ประกอบลอจิกในเซมิคอนดักเตอร์นั้นไม่ได้มีลักษณะเฉพาะโดยสถานะของหน้าสัมผัส แต่โดยการมีอยู่ของสัญญาณที่อินพุตและเอาต์พุต

ลองพิจารณาองค์ประกอบเชิงตรรกะที่ใช้การดำเนินการเชิงตรรกะขั้นพื้นฐาน:

อินเวอร์เตอร์ - ดำเนินการดำเนินการของการปฏิเสธหรือการผกผัน ยู

อินเวอร์เตอร์มี 1 อินพุทและเอาท์พุท 1 อัน สัญญาณเอาท์พุตปรากฏขึ้น

เมื่อไม่มีอินพุต และในทางกลับกัน

คอนจังเตอร์ -

X1 X2 ... Xn

ดำเนินการดำเนินการร่วม

ที่จุดเชื่อมต่อ

ทางออกหนึ่งทางและทางเข้าอย่างน้อยสองทาง สัญญาณเปิดอยู่

ปรากฏในเอาต์พุตหากและหากเท่านั้น

อินพุตทั้งหมดจะถูกส่งสัญญาณ

X2 + ... Xn

Disjunctor - ดำเนินการดำเนินการแยกส่วน ยู

disjunctor มีทางออกหนึ่งทางและอย่างน้อยสองทาง

สัญญาณเอาท์พุตจะไม่ปรากฏก็ต่อเมื่อเท่านั้น

เมื่อไม่มีการจ่ายสัญญาณให้กับอินพุตทั้งหมด

	สร้าง	การทำงาน
F(X, Y, Z) = X(Y+ Z)
			เอ็กซ์+ซ

แผนภาพที่สอดคล้องกับฟังก์ชัน:

&F(X, Y, Z)

การแก้ปัญหาโดยใช้การเชื่อมแบบปกติ

และ ไม่ต่อเนื่องกัน-ปกติแบบฟอร์ม

ใน หนังสือปัญหาลอจิกมักมีปัญหามาตรฐานซึ่งคุณต้องเขียนฟังก์ชันที่นำไปปฏิบัติแผนภาพแลดเดอร์ ลดความซับซ้อนและสร้างตารางความจริงสำหรับฟังก์ชันนี้ วิธีแก้ปัญหาผกผัน? เมื่อพิจารณาตารางความจริงตามอำเภอใจ คุณจะต้องสร้างไดอะแกรมการทำงานหรือไดอะแกรมรีเลย์ เราจะจัดการกับปัญหานี้ในวันนี้

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

minterm คือฟังก์ชันที่เกิดจากการรวมตัวแปรจำนวนหนึ่งหรือการปฏิเสธของตัวแปรเหล่านั้น Minterm รับค่า 1 สำหรับชุดที่เป็นไปได้เพียงชุดเดียว

อาร์กิวเมนต์ และค่า 0 สำหรับอาร์กิวเมนต์อื่นๆ ทั้งหมด ตัวอย่าง: x 1 x 2 x 3 x 4 .

maxterm คือฟังก์ชันที่เกิดจากการแยกตัวแปรจำนวนหนึ่งหรือการปฏิเสธของตัวแปรเหล่านั้น Maxterm รับค่า 0 ในชุดที่เป็นไปได้ชุดใดชุดหนึ่ง และ 1 ในชุดอื่นๆ ทั้งหมด

ตัวอย่าง: x 1 + x 2 + x 3

ฟังก์ชั่นใน รูปแบบปกติที่ไม่ต่อเนื่องกัน(DNF) คือผลรวมเชิงตรรกะของ minterms

ตัวอย่าง: x 1x 2+ x 1x 2+ x 1x 2x 3

แบบฟอร์มปกติที่เชื่อมต่อกัน(CNF) เป็นผลคูณเชิงตรรกะของการแยกทางเบื้องต้น (maxterms)

ตัวอย่าง: (x 1+ x 2+ x 3) (x 1+ x 2)

รูปแบบปกติที่ไม่ต่อเนื่องที่สมบูรณ์แบบ เรียกว่า DNF ในแต่ละ minterm ซึ่งมีตัวแปรทั้งหมดหรือการปฏิเสธอยู่

ตัวอย่าง: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

รูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบ เรียกว่า CNF ในแต่ละเทอมสูงสุดซึ่งมีตัวแปรทั้งหมดหรือการปฏิเสธอยู่

ตัวอย่าง: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

การเขียนฟังก์ชันลอจิคัลจากตาราง

ฟังก์ชันลอจิคัลใดๆ สามารถแสดงเป็น SDNF หรือ SCNF ได้ เป็นตัวอย่าง ให้พิจารณาฟังก์ชัน f ที่แสดงในตาราง

			ฉ(x1 , x2 , x3 )

ฟังก์ชัน G0, G1, G4, G5, G7 คือ minterms (ดูคำจำกัดความ) แต่ละฟังก์ชันเป็นผลคูณของตัวแปรสามตัวหรือค่าผกผัน และรับค่า 1 ในสถานการณ์เดียวเท่านั้น จะเห็นได้ว่าในการที่จะได้รับ 1 ในค่าของฟังก์ชัน f จำเป็นต้องมีหนึ่ง minterm ดังนั้น จำนวน minterm ที่ประกอบเป็น SDNF ของฟังก์ชันนี้จึงเท่ากับจำนวนหน่วยในค่าฟังก์ชัน: f= G0+G1+G4+G5+G7 ดังนั้น SDNF จึงมีรูปแบบ:

ฉ (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

ในทำนองเดียวกัน คุณสามารถสร้าง SKNF ได้ จำนวนปัจจัยเท่ากับจำนวนศูนย์ในค่าฟังก์ชัน:

ฉ (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

ดังนั้นฟังก์ชันลอจิคัลใดๆ ที่กำหนดในรูปแบบของตารางจึงสามารถเขียนเป็นสูตรได้

อัลกอริทึมสำหรับการสร้าง SDNF โดยใช้ตารางความจริง

มีการกำหนดตารางความจริงของฟังก์ชันบางอย่าง หากต้องการสร้าง SDNF คุณต้องดำเนินการตามลำดับขั้นตอนต่อไปนี้:

1. เลือกแถวตารางทั้งหมดที่ฟังก์ชันรับค่า 1

2. สำหรับแต่ละบรรทัดดังกล่าว ให้กำหนดการรวมกันของอาร์กิวเมนต์ทั้งหมดหรือการกลับกัน (minterm) ในกรณีนี้ อาร์กิวเมนต์ที่ใช้ค่า 0 จะรวมอยู่ใน minterm ที่มีการปฏิเสธ และค่า 1 จะรวมอยู่โดยไม่มีการปฏิเสธ

3. ในที่สุด เราก็สร้างการแยกตัวของ minterms ที่ได้รับทั้งหมด จำนวน minterms ต้องตรงกับจำนวนหน่วยของฟังก์ชันลอจิคัล

อัลกอริทึมสำหรับการสร้าง SCNF โดยใช้ตารางความจริง

มีการกำหนดตารางความจริงของฟังก์ชันบางอย่าง ในการสร้าง SKNF คุณต้องดำเนินการตามลำดับขั้นตอนต่อไปนี้:

1. เลือกแถวทั้งหมดของตารางที่ฟังก์ชันรับค่า 0

2. แต่ละบรรทัดดังกล่าวจะต้องเชื่อมโยงกับการแยกอาร์กิวเมนต์ทั้งหมดหรือการกลับกัน (maxterm) ในกรณีนี้ อาร์กิวเมนต์ที่ใช้ค่า 1 จะรวมอยู่ในค่าสูงสุดที่มีการปฏิเสธ และค่า 1 จะรวมอยู่ในค่าที่ไม่มีการปฏิเสธ

3. ในที่สุด เราก็สร้างจุดร่วมของเงื่อนไขสูงสุดที่ได้รับทั้งหมด จำนวน maxterms ต้องตรงกับจำนวนศูนย์ของฟังก์ชันลอจิคัล

หากเราตกลงจากสองรูปแบบ (SDNF หรือ SKNF) เพื่อให้ความสำคัญกับรูปแบบที่มีตัวอักษรน้อยกว่า SDNF จะดีกว่าหากมีค่าน้อยกว่าในค่าของฟังก์ชันตารางความจริง SKNF - หากมีศูนย์น้อยกว่า

ตัวอย่าง. ตารางความจริงของฟังก์ชันลอจิคัลของตัวแปรทั้งสามถูกกำหนดไว้ สร้างสูตรตรรกะที่ใช้ฟังก์ชันนี้

			ฉ(เอ บี ซี)

ให้เราเลือกแถวเหล่านั้นในตารางความจริงนี้ซึ่งค่าฟังก์ชันเป็น 0

F(A, B, C) = (A+ B+ C) (A+ B+ C)

ลองตรวจสอบฟังก์ชันที่ได้รับโดยการสร้างตารางความจริง

โดยการเปรียบเทียบตารางความจริงเริ่มต้นและตารางสุดท้าย เราสามารถสรุปได้ว่าฟังก์ชันลอจิคัลถูกสร้างขึ้นอย่างถูกต้อง

การแก้ปัญหา

1. ครูสามคนเลือกปัญหาสำหรับการแข่งขันกีฬาโอลิมปิก มีหลายงานให้เลือก สำหรับแต่ละงาน ครูแต่ละคนแสดงความคิดเห็น: งานง่าย (0) หรืองานยาก (1) งานจะรวมอยู่ในงานโอลิมปิกถ้าครูอย่างน้อยสองคนทำเครื่องหมายว่ายาก แต่ถ้าครูทั้งสามคนเห็นว่ายาก งานดังกล่าวจะไม่รวมอยู่ในงานโอลิมปิกว่ายากเกินไป สร้างไดอะแกรมลอจิคัลของอุปกรณ์ที่จะส่งออกเป็น 1 หากงานนั้นรวมอยู่ในงาน Olympiad และ 0 หากไม่ได้รวมไว้ด้วย

มาสร้างตารางความจริงสำหรับฟังก์ชันที่ต้องการกันดีกว่า เรามีตัวแปรอินพุตสามตัว (ครูสามคน) ดังนั้นฟังก์ชันที่ต้องการจะเป็นฟังก์ชันของตัวแปรสามตัว

การวิเคราะห์สภาพปัญหา เราได้รับตารางความจริงดังต่อไปนี้:

เรากำลังสร้าง SDNF F(A, B, C) = เอบีซี+ เอบีซี+ เอบีซี

ตอนนี้เราสร้างไดอะแกรมเชิงตรรกะของฟังก์ชันนี้

B&1F(เอ,บี,ซี)

2. โอลิมปิกเมือง สาขาวิชาวิทยาการคอมพิวเตอร์ขั้นพื้นฐาน 2550สร้างแผนภาพวงจรไฟฟ้าสำหรับทางเข้าบ้านสามชั้นโดยให้สวิตช์บนชั้นใดก็ได้สามารถเปิดหรือปิดไฟทั่วทั้งบ้านได้

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

จากนั้น F(A, B, C) = ABC+ ABC+ ABC+ ABC

	3. เปลี่ยนสภาพ			ค่าฟังก์ชันลอจิคัล			F(เอ, บี, ค) = ค→		เอ+บี
	การเปลี่ยนข้อโต้แย้ง B และ C พร้อมกันเท่ากับ:
		เอ → (Bค)						(Bค) → ก
					เอ(บีค)
	4) (Bค) → ก				เอ → (Bค)

บันทึก. เพื่อแก้ไขปัญหานี้ให้สำเร็จ โปรดจำสูตรตรรกะต่อไปนี้:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

เราได้รับฟังก์ชันลอจิคัลของตัวแปรสามตัว F 1 (A, B, C) = C → A + B = C + A B

มาเปลี่ยนตัวแปร B และ C พร้อมกัน: F 2 (A, B, C) = F 1 (A, B, C) = C + A B มาสร้างตารางความจริงสำหรับฟังก์ชันทั้งสองนี้กันดีกว่า:

มาวิเคราะห์ตารางผลลัพธ์กัน จากแปดแถวของตาราง มีเพียงสองแถว (ที่ 2 และ 3) เท่านั้นที่ฟังก์ชันจะไม่เปลี่ยนค่า โปรดสังเกตว่าในบรรทัดเหล่านี้ ตัวแปร A จะไม่กลับค่าของมัน แต่ตัวแปร B และ C กลับด้าน

เราสร้างฟังก์ชัน SKNF โดยใช้บรรทัดเหล่านี้:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C=

A+ (B↔ C) = A+ B C= (B C) → A

ดังนั้นคำตอบที่ต้องการคือ 4

4. เงื่อนไขสำหรับการเปลี่ยนแปลงค่าของฟังก์ชันลอจิคัล F (A, B, C) = C + AB ในขณะที่เปลี่ยนอาร์กิวเมนต์ A และ B พร้อมกันจะเท่ากับ:

1) C+ (เอบี)

C+(เอบี)

แท็กซี่)

4) ค(เอบี)

ค → (เอบี)

ฉ 1 (ก ,บี ,ค )=

ซี+เอบี

ฉ 2 (ก ,บี ,ค )= ฉ 1 (

ค )= ก

เราสร้างตารางความจริง

มาวิเคราะห์ตารางผลลัพธ์กัน จากแปดแถวของตาราง มีเพียงสองแถว (ที่ 1 และ 7) เท่านั้นที่ฟังก์ชันจะเปลี่ยนค่า โปรดทราบว่าในบรรทัดเหล่านี้ ตัวแปร C จะไม่เปลี่ยนค่า แต่ตัวแปร A และ B เปลี่ยนแปลง

เราสร้างฟังก์ชัน SDNF โดยใช้บรรทัดเหล่านี้:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

ดังนั้นคำตอบที่ต้องการคือ 2

อ้างอิง

1. ชาปิโร เอส.ไอ. การแก้ปัญหาเชิงตรรกะและการเล่นเกม(การศึกษาเชิงตรรกะและจิตวิทยา) – อ.: วิทยุและการสื่อสาร, 2527. – 152 น.

2. โชโลมอฟ แอล.เอ. ความรู้พื้นฐานของทฤษฎีอุปกรณ์ลอจิคัลและคอมพิวเตอร์แบบแยกส่วน – ม.: วิทยาศาสตร์. ช. เอ็ด ทางกายภาพ - เสื่อ สว่าง., 1980. - 400 น.

3. Pukhalsky G.I. , Novoseltseva T.Ya. การออกแบบอุปกรณ์แยกส่วนบนวงจรรวม: คู่มือ – อ.: วิทยุและการสื่อสาร, 2533.