นอสกิน อันเดรย์ นิโคลาวิช
ครูสอนวิทยาศาสตร์คอมพิวเตอร์
หมวดหมู่คุณสมบัติสูงสุด
ผู้สมัครสาขาวิชาวิทยาศาสตร์การทหาร, รองศาสตราจารย์
GBOU Lyceum หมายเลข 1575 มอสโก
วิธีการทำแผนที่ที่ปรับให้เหมาะสมสำหรับการแก้ปัญหา 23 จาก KIM Unified State Examination ในสาขาวิทยาการคอมพิวเตอร์และ ICT
หนึ่งในงานที่ยากที่สุดใน Unified State Exam KIM คือปัญหา 23 ซึ่งคุณต้องค้นหาจำนวนชุดค่าต่างๆ ของตัวแปรลอจิคัลที่ตรงตามเงื่อนไขที่ระบุ
งานนี้อาจจะมากที่สุด งานที่ยากลำบากการสอบ KIM Unified State ในด้านสารสนเทศและ ICT ตามกฎแล้วผู้สอบไม่เกิน 5% สามารถรับมือกับมันได้ (1)
นักเรียนส่วนน้อยที่ทำภารกิจนี้สำเร็จจะอธิบายได้ดังต่อไปนี้:
- นักเรียนอาจสับสน (ลืม) สัญญาณของการดำเนินการเชิงตรรกะ
- ข้อผิดพลาดทางคณิตศาสตร์ในกระบวนการคำนวณ
- ข้อผิดพลาดในการให้เหตุผลเมื่อค้นหาวิธีแก้ไข
- ข้อผิดพลาดในกระบวนการลดความซับซ้อนของนิพจน์เชิงตรรกะ
- ครูแนะนำให้แก้ไขปัญหานี้หลังจากทำงานทั้งหมดเสร็จแล้วเนื่องจากมีความน่าจะเป็น
ข้อผิดพลาดมีขนาดใหญ่มากและ “น้ำหนัก” ของงานเป็นเพียงจุดหลักจุดเดียวเท่านั้น
นอกจากนี้ ครูบางคนเองก็มีปัญหาในการแก้ปัญหาประเภทนี้ จึงพยายามแก้ไขปัญหาที่ง่ายกว่ากับเด็กๆ
สถานการณ์ที่ซับซ้อนก็คือว่าในบล็อกนี้มี จำนวนมากงานต่างๆ และไม่สามารถเลือกโซลูชันเทมเพลตได้
เพื่อแก้ไขสถานการณ์นี้ ชุมชนการสอนกำลังสรุปวิธีการหลักสองวิธีในการแก้ปัญหา ประเภทนี้: วิธีแก้ปัญหาโดยใช้บิตเชน (2) และวิธีการแมป (3)
ความจำเป็นในการปรับแต่ง (เพิ่มประสิทธิภาพ) วิธีการเหล่านี้เกิดจากการที่งานมีการเปลี่ยนแปลงตลอดเวลาทั้งในโครงสร้างและจำนวนตัวแปร (ตัวแปร X เพียงประเภทเดียว, ตัวแปร X และ Y สองประเภท, สามประเภท: X, Y , ซี)
ความยากลำบากในการฝึกฝนวิธีการเหล่านี้ในการแก้ปัญหาได้รับการยืนยันจากข้อเท็จจริงที่ว่าบนเว็บไซต์ของ K.Yu Polyakov มีการวิเคราะห์ปัญหาประเภทนี้ 38 รายการ (4) การวิเคราะห์บางอย่างมีวิธีแก้ไขปัญหามากกว่าหนึ่งประเภท
เมื่อเร็วๆ นี้ในการสอบ KIM Unified State ในวิทยาการคอมพิวเตอร์ มีปัญหากับตัวแปร X และ Y สองประเภท
ฉันได้ปรับวิธีการแสดงผลให้เหมาะสมแล้ว และสนับสนุนให้นักเรียนใช้วิธีการปรับปรุงนี้
สิ่งนี้ให้ผลลัพธ์ เปอร์เซ็นต์ของนักเรียนของฉันที่สามารถรับมือกับงานนี้แตกต่างกันไปมากถึง 43% ของผู้ที่สอบผ่าน ตามกฎแล้วทุกปีจาก 25 ถึง 33 คนจากเกรด 11 ทั้งหมดจะเข้าสอบ Unified State ในสาขาวิทยาการคอมพิวเตอร์
ก่อนที่จะเกิดปัญหากับตัวแปรสองประเภท นักเรียนใช้วิธีการทำแผนที่ได้สำเร็จมาก แต่หลังจากการปรากฏตัวของ Y ในนิพจน์เชิงตรรกะ ฉันเริ่มสังเกตเห็นว่าคำตอบของเด็กไม่ตรงกับการทดสอบอีกต่อไป ปรากฎว่าพวกเขายังไม่ชัดเจนเกี่ยวกับวิธีการสร้างตารางการแมปด้วยตัวแปรประเภทใหม่ จากนั้นฉันก็เกิดความคิดขึ้นมาว่าเพื่อความสะดวกควรลดการแสดงออกทั้งหมดให้เป็นตัวแปรประเภทเดียวตามความสะดวกสำหรับเด็ก
ฉันจะให้เทคนิคนี้โดยละเอียดยิ่งขึ้น เพื่อความสะดวกผมจะพิจารณาโดยใช้ตัวอย่างระบบนิพจน์เชิงตรรกะที่ให้ไว้ใน (4)
เท่าไหร่ โซลูชั่นต่างๆมีระบบ สมการเชิงตรรกะ
(x1 ^ ใช่ 1)=(€x2 วี ¬
ย 2
)
(x2 ^ ใช่ 2)= (¬
x 3
วี ¬
ย 3
)
...
(x5 ^ ใช่ 5)
= (¬
x 6
วี ¬
ย 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)) ∨ (ฌ(X1 ≡ X2) ∧ ฌ(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (ฌ(X3 ≡ X4) ∧ ฌ(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (ฌ(X5 ≡ X6) ∧ ฌ(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (ฌ(X7 ≡ X8) ∧ ฌ(X9 ≡ X10)) = 0
สารละลาย:
ขอแนะนำตัวแปรใหม่: A=(X1≡ X2); B=(X3 ≡ X4); ซ=(X5 ≡ X6); ง=(X7 ≡ X8); อี=(X9 ≡ X10)
(โปรดทราบ! ตัวแปรแต่ละตัว x1, x2, ..., x10 จะต้องรวมอยู่ในตัวแปรใหม่เพียงตัวเดียวเท่านั้น ตัวแปร A, B, C, D, E, เช่น. ตัวแปรใหม่จะเป็นอิสระจากกัน)
จากนั้นระบบสมการจะเป็นดังนี้:
(A ∧ B) ∨ (ฌA ∧ ฌB)=0
(B ∧ C) ∨ (ฌB ∧ ฌC)=0
(ค ∧ ง) ∨ (ฌC ∧ ฌD)=0
(ด ∧ จ) ∨ (ฌD ∧ ฌE)=0
มาสร้างแผนผังการตัดสินใจสำหรับระบบผลลัพธ์กันดีกว่า:
พิจารณาสมการ A=0 เช่น (X1≡ X2)=0 มี 2 ราก:
X1 ≡ X2 |
||
จากตารางเดียวกันจะเห็นว่าสมการ A=1 มี 2 รากเช่นกัน ลองจัดเรียงจำนวนรากบนแผนผังการตัดสินใจ:
หากต้องการค้นหาจำนวนโซลูชันของสาขาหนึ่ง คุณต้องคูณจำนวนโซลูชันในแต่ละระดับ สาขาด้านซ้ายมี 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 โซลูชั่น; สาขาที่ถูกต้องก็มี 32 โซลูชั่นเช่นกัน เหล่านั้น. ทั้งระบบมีคำตอบ 32+32=64 ข้อ
คำตอบ: 64.
2. วิธีการให้เหตุผล
ความยากในการแก้ระบบสมการเชิงตรรกะอยู่ที่ความยุ่งยากของแผนผังการตัดสินใจที่สมบูรณ์ วิธีการให้เหตุผลช่วยให้คุณไม่ต้องสร้างต้นไม้ทั้งต้น แต่เพื่อให้เข้าใจว่าต้นไม้จะมีกี่กิ่ง ลองดูวิธีนี้โดยใช้ตัวอย่างเฉพาะ
ตัวอย่างที่ 1 มีค่าที่แตกต่างกันกี่ชุดของตัวแปรลอจิคัล x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ที่ตรงตามเงื่อนไขทั้งหมดที่ระบุไว้ด้านล่างนี้
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
คำตอบไม่จำเป็นต้องแสดงรายการชุดค่าต่าง ๆ ทั้งหมดของตัวแปร x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ที่ระบบความเท่าเทียมกันนี้พอใจ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว
สารละลาย :
สมการที่หนึ่งและที่สองประกอบด้วยตัวแปรอิสระที่เกี่ยวข้องกับเงื่อนไขที่สาม มาสร้างแผนผังคำตอบสำหรับสมการที่หนึ่งและที่สองกัน
ในการแทนแผนผังคำตอบสำหรับระบบสมการที่หนึ่งและสอง แต่ละสาขาของแผนภูมิแรกจะต้องต่อด้วยต้นไม้สำหรับตัวแปรที่ - ต้นไม้ที่สร้างในลักษณะนี้จะมีกิ่งก้าน 36 กิ่ง สาขาเหล่านี้บางสาขาไม่เป็นไปตามสมการที่สามของระบบ เรามาทำเครื่องหมายจำนวนกิ่งก้านของต้นไม้บนต้นไม้ต้นแรกกัน"ย" ซึ่งเป็นไปตามสมการที่สาม:
ให้เราอธิบาย: เพื่อให้ตรงตามเงื่อนไขที่สาม เมื่อ x1=0 จะต้องมี y1=1 กล่าวคือ กิ่งก้านทั้งหมดของต้นไม้"เอ็กซ์" โดยที่ x1=0 สามารถต่อยอดได้เพียงกิ่งเดียวจากแผนผัง"ย" - และสำหรับกิ่งก้านของต้นไม้เพียงกิ่งเดียวเท่านั้น"เอ็กซ์" (ขวา) กิ่งก้านของต้นไม้พอดี"ย" ดังนั้น ต้นไม้ทั้งระบบจึงมีกิ่งก้าน 11 กิ่ง แต่ละสาขาแทนคำตอบเดียวของระบบสมการดั้งเดิม ซึ่งหมายความว่าทั้งระบบมี 11 โซลูชัน
คำตอบ: 11.
ตัวอย่างที่ 2 ระบบสมการมีคำตอบที่แตกต่างกันกี่ข้อ?
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (ฌX1 ∧ ฌ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (ฌX2 ∧ ฌ X10)= 1
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (ฌX9 ∧ ฌ X10)= 1
(X1 ≡ X10) = 0
โดยที่ x1, x2, …, x10 เป็นตัวแปรเชิงตรรกะ? คำตอบไม่จำเป็นต้องแสดงรายการชุดตัวแปรต่างๆ ทั้งหมดที่มีความเท่าเทียมกันนี้ คำตอบคือคุณต้องระบุจำนวนชุดดังกล่าว
สารละลาย : มาทำให้ระบบง่ายขึ้น เรามาสร้างตารางความจริงสำหรับส่วนหนึ่งของสมการแรกกัน:
X1 ∧ X10 | ฌX1 ∧ ฌX10 | (X1 ∧ X10) ∨ (ฌX1 ∧ ฌ X10) |
||
ให้ความสนใจกับคอลัมน์สุดท้ายซึ่งตรงกับผลลัพธ์ของการกระทำ X1 ≡ X10
X1 ≡ X10 |
หลังจากการทำให้เข้าใจง่ายเราได้รับ:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
พิจารณาสมการสุดท้าย:(X1 ≡ X10) = 0 เช่น x1 ไม่ควรตรงกับ x10 เพื่อให้สมการแรกเท่ากับ 1 ความเท่าเทียมกันจะต้องเป็นจริง(X1 ≡ X2)=1 เช่น x1 ต้องตรงกับ x2
มาสร้างแผนผังคำตอบสำหรับสมการแรกกัน:
พิจารณาสมการที่สอง: สำหรับ x10=1 และสำหรับ x2=0 วงเล็บเหลี่ยมต้องเท่ากับ 1 (เช่น x2 ตรงกับ x3) สำหรับ x10=0 และสำหรับ x2=1 วงเล็บเหลี่ยม(X2 ≡ X10)=0 ซึ่งหมายถึงวงเล็บ (X2 ≡ X3) ควรเท่ากับ 1 (เช่น x2 ตรงกับ x3):
การใช้เหตุผลในลักษณะนี้ เราสร้างแผนผังการตัดสินใจสำหรับสมการทั้งหมด:
ดังนั้น ระบบสมการจึงมีคำตอบเพียง 2 ข้อเท่านั้น
คำตอบ: 2.
ตัวอย่างที่ 3
มีชุดค่าที่แตกต่างกันกี่ชุดของตัวแปรลอจิคัล x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 ที่ตรงตามเงื่อนไขทั้งหมดที่ระบุไว้ด้านล่างนี้
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(ฌx1 /\ y1 /\ z1) \/ (x1 /\ ‚y1 /\ z1) \/ (x1 /\ y1 /\ ñz1) = 1
(ฌx2 /\ y2 /\ z2) \/ (x2 /\ ây2 /\ z2) \/ (x2 /\ y2 /\ ñz2) = 1
(ฌx3 /\ y3 /\ z3) \/ (x3 /\ ây3 /\ z3) \/ (x3 /\ y3 /\ ñz3) = 1
(ฌx4 /\ y4 /\ z4) \/ (x4 /\ ây4 /\ z4) \/ (x4 /\ y4 /\ ñz4) = 1
สารละลาย:
มาสร้างแผนผังคำตอบสำหรับสมการที่ 1 กัน:
พิจารณาสมการที่สอง:
- เมื่อ x1=0 : วงเล็บที่สองและสามจะเท่ากับ 0; สำหรับวงเล็บแรกจะเท่ากับ 1, y1=1, z1=1 (เช่นในกรณีนี้ - 1 วิธีแก้ปัญหา)
- เมื่อ x1=1 : วงเล็บแรกจะเท่ากับ 0; ที่สองหรือ วงเล็บที่สามต้องเท่ากับ 1; วงเล็บที่สองจะเท่ากับ 1 เมื่อ y1=0 และ z1=1; วงเล็บที่สามจะเท่ากับ 1 เมื่อ y1=1 และ z1=0 (เช่นในกรณีนี้ - 2 วิธีแก้ปัญหา)
ในทำนองเดียวกันสำหรับสมการที่เหลือ ให้เราสังเกตจำนวนผลลัพธ์ของการแก้ปัญหาสำหรับแต่ละโหนดต้นไม้:
หากต้องการทราบจำนวนคำตอบสำหรับแต่ละสาขา ให้คูณตัวเลขผลลัพธ์แยกกันสำหรับแต่ละสาขา (จากซ้ายไปขวา)
1 สาขา: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 วิธีแก้ปัญหา
สาขา 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 โซลูชั่น
สาขาที่ 3: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 โซลูชั่น
สาขาที่ 4: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 โซลูชั่น
สาขาที่ 5: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 โซลูชั่น
มาบวกตัวเลขผลลัพธ์กัน: มีทั้งหมด 31 คำตอบ
คำตอบ: 31.
3. เพิ่มจำนวนรากตามธรรมชาติ
ในบางระบบ จำนวนรากของสมการถัดไปจะขึ้นอยู่กับจำนวนรากของสมการก่อนหน้า
ตัวอย่างที่ 1 มีชุดค่าต่างๆ ของตัวแปรลอจิคัล x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 ที่ตรงตามเงื่อนไขทั้งหมดด้านล่างนี้กี่ชุด?
ฌ(x1 ≡ x2) ∧ ((x1 ∧ ฌx3) ∨ (ฌx1 ∧ x3)) = 0
ฌ(x2 ≡ x3) ∧ ((x2 ∧ ฌx4) ∨ (ฌx2 ∧ x4)) = 0
ฌ(x8 ≡ x9) ∧ ((x8 ∧ ฌx10) ∨ (ฌx8 ∧ x10)) = 0
มาลดความซับซ้อนกัน สมการแรก:(x1 ∧ ฌx3) ∨ (ฌx1 ∧ x3)=x1 ⊕ x3=ฌ(x1 ≡ x3) จากนั้นระบบจะอยู่ในรูปแบบ:
ฌ(x1 ≡ x2) ∧ ฌ(x1 ≡ x3) = 0
ฌ(x2 ≡ x3) ∧ ฌ(x2 ≡ x4)= 0
ฌ(x8 ≡ x9) ∧ ฌ(x8 ≡ x10) = 0
ฯลฯ
สมการถัดไปแต่ละสมการจะมีรากมากกว่าสมการก่อนหน้า 2 อัน
สมการที่ 4 มี 12 ราก
สมการที่ 5 มี 14 ราก
สมการที่ 8 มี 20 ราก
คำตอบ: 20 ราก
บางครั้งจำนวนรากก็เพิ่มขึ้นตามกฎฟีโบนัชชี
การแก้ระบบสมการตรรกะต้องใช้แนวทางที่สร้างสรรค์
การแก้ระบบสมการลอจิกโดยการเปลี่ยนตัวแปร
วิธีการทดแทนตัวแปรจะใช้หากตัวแปรบางตัวรวมอยู่ในสมการเฉพาะในรูปแบบของนิพจน์เฉพาะเท่านั้น และไม่มีอะไรอื่นอีก จากนั้นนิพจน์นี้สามารถกำหนดให้เป็นตัวแปรใหม่ได้
ตัวอย่างที่ 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
การใช้สมการแพร่หลายในชีวิตของเรา ใช้ในการคำนวณ การสร้างโครงสร้าง และแม้กระทั่งการกีฬา มนุษย์ใช้สมการในสมัยโบราณ และตั้งแต่นั้นมาการใช้สมการก็เพิ่มขึ้นเท่านั้น ในทางคณิตศาสตร์ มีปัญหาบางอย่างที่เกี่ยวข้องกับตรรกะเชิงประพจน์ ในการแก้สมการประเภทนี้ คุณต้องมีความรู้จำนวนหนึ่ง เช่น ความรู้เกี่ยวกับกฎของตรรกศาสตร์เชิงประพจน์ ความรู้เกี่ยวกับตารางความจริงของฟังก์ชันเชิงตรรกะของตัวแปร 1 หรือ 2 ตัว วิธีการแปลงนิพจน์เชิงตรรกะ นอกจากนี้ คุณจำเป็นต้องทราบคุณสมบัติของการดำเนินการเชิงตรรกะดังต่อไปนี้: การร่วม การแตกแยก การผกผัน การอนุมาน และความเท่าเทียมกัน
ฟังก์ชันเชิงตรรกะใดๆ ของ \variables - \can สามารถระบุได้ด้วยตารางความจริง
ลองแก้สมการเชิงตรรกะหลายสมการ:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\ขวาฉมวกดาวน์ X9\vee X10=1\]
มาเริ่มวิธีแก้ปัญหาด้วย \[X1\] และพิจารณาว่าตัวแปรนี้สามารถรับค่าใดได้: 0 และ 1 ต่อไป เราจะพิจารณาแต่ละค่าข้างต้นและดูว่า \[X2.\] เป็นค่าใดได้บ้าง
ดังที่เห็นจากตาราง สมการเชิงตรรกะของเรามีคำตอบ 11 ข้อ
ฉันจะแก้สมการตรรกะออนไลน์ได้ที่ไหน
คุณสามารถแก้สมการได้บนเว็บไซต์ของเรา https://site. ฟรี แก้ปัญหาออนไลน์จะช่วยให้คุณสามารถแก้สมการออนไลน์ที่ซับซ้อนได้ภายในไม่กี่วินาที สิ่งที่คุณต้องทำคือเพียงป้อนข้อมูลของคุณลงในตัวแก้ปัญหา คุณยังสามารถชมวิดีโอคำแนะนำและเรียนรู้วิธีแก้สมการบนเว็บไซต์ของเรา และหากคุณยังมีคำถาม คุณสามารถถามพวกเขาได้ในกลุ่ม VKontakte ของเรา http://vk.com/pocketteacher เข้าร่วมกลุ่มของเรา เรายินดีช่วยเหลือคุณเสมอ
หัวข้อบทเรียน: การแก้สมการลอจิก
ทางการศึกษา – ศึกษาวิธีการแก้สมการเชิงตรรกะ การพัฒนาทักษะการแก้สมการเชิงตรรกะ และการสร้างนิพจน์เชิงตรรกะโดยใช้ตารางความจริงพัฒนาการ - สร้างเงื่อนไขในการพัฒนา ความสนใจทางปัญญานักเรียนส่งเสริมการพัฒนาความจำความสนใจ การคิดเชิงตรรกะ;
ทางการศึกษา : ส่งเสริมความสามารถในการรับฟังความคิดเห็นของผู้อื่นการบำรุงเลี้ยงความตั้งใจและความเพียรพยายามเพื่อให้บรรลุ ผลลัพธ์สุดท้าย.
ประเภทบทเรียน: บทเรียนรวม
อุปกรณ์: คอมพิวเตอร์ เครื่องฉายมัลติมีเดีย การนำเสนอ 6.
ความคืบหน้าของบทเรียน
การทำซ้ำและการปรับปรุงความรู้พื้นฐาน การตรวจสอบ การบ้าน(10 นาที)
ในบทเรียนที่แล้ว เราคุ้นเคยกับกฎพื้นฐานของพีชคณิตเชิงตรรกะ และเรียนรู้ที่จะใช้กฎเหล่านี้เพื่อทำให้นิพจน์เชิงตรรกะง่ายขึ้น
มาตรวจสอบการบ้านของเราเกี่ยวกับการลดความซับซ้อนของนิพจน์เชิงตรรกะ:
1. คำใดต่อไปนี้ตรงตามเงื่อนไขตรรกะ:
(พยัญชนะอักษรตัวแรก → พยัญชนะอักษรตัวที่สอง)٨ (สระตัวอักษรตัวสุดท้าย → สระอักษรตัวสุดท้าย)? หากมีคำดังกล่าวหลายคำ ให้ระบุคำที่เล็กที่สุด
1) แอนนา 2) มาเรีย 3) โอเลก 4) สเตฟาน
ให้เราแนะนำสัญกรณ์ต่อไปนี้:
ก – พยัญชนะอักษรตัวแรก
B – พยัญชนะอักษรตัวที่สอง
S – สระอักษรตัวสุดท้าย
D – สระเสียงสุดท้าย
เรามาสร้างการแสดงออกกัน:
มาทำตารางกันเถอะ:
2. ระบุว่านิพจน์เชิงตรรกะใดเทียบเท่ากับนิพจน์
มาทำให้การบันทึกนิพจน์ดั้งเดิมและตัวเลือกที่เสนอง่ายขึ้น:
3. ให้ส่วนหนึ่งของตารางความจริงของนิพจน์ F:
นิพจน์ใดตรงกับ F
ให้เรากำหนดค่าของนิพจน์เหล่านี้สำหรับค่าที่ระบุของอาร์กิวเมนต์:
ความรู้เบื้องต้นเกี่ยวกับหัวข้อของบทเรียน การนำเสนอเนื้อหาใหม่ (30 นาที)
เราศึกษาพื้นฐานของตรรกะต่อไป และหัวข้อของบทเรียนวันนี้คือ "การแก้สมการเชิงตรรกะ" หลังจากศึกษาหัวข้อนี้ คุณจะได้เรียนรู้วิธีการพื้นฐานในการแก้สมการเชิงตรรกะ เพิ่มทักษะในการแก้สมการเหล่านี้โดยใช้ภาษาพีชคณิตเชิงตรรกะ และความสามารถในการเขียนนิพจน์เชิงตรรกะโดยใช้ตารางความจริง
1. แก้สมการตรรกะ
(ฌเค ม) → (ฌล ม น) =0
เขียนคำตอบของคุณเป็นสตริงสี่อักขระ: ค่าของตัวแปร K, L, M และ N (ตามลำดับ) ตัวอย่างเช่น บรรทัดที่ 1101 สอดคล้องกับข้อเท็จจริงที่ว่า K=1, L=1, M=0, N=1
สารละลาย:
มาแปลงนิพจน์กันเถอะ(ฌเค ม) → (ฌล ม ยังไม่มี)
นิพจน์เป็นเท็จเมื่อทั้งสองคำเป็นเท็จ เทอมที่สองจะเท่ากับ 0 ถ้า M =0, N =0, L =1 ในเทอมแรก K = 0 เนื่องจาก M = 0 และ 
.
คำตอบ: 0100
2. สมการนี้มีคำตอบกี่ข้อ (ระบุเฉพาะตัวเลขในคำตอบของคุณ)
วิธีแก้ไข: แปลงนิพจน์
(A +B )*(ค +D )=1
A +B =1 และ C +D =1
วิธีที่ 2: วาดตารางความจริง
3 ทาง: การสร้าง SDNF - รูปแบบปกติที่แยกออกจากกันที่สมบูรณ์แบบสำหรับฟังก์ชัน - การแยกตัวของคำสันธานพื้นฐานปกติที่สมบูรณ์มาแปลงนิพจน์ดั้งเดิมโดยเปิดวงเล็บเพื่อให้ได้คำสันธานที่แยกจากกัน:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
เรามาเสริมคำสันธานเพื่อทำให้คำสันธานสมบูรณ์ (ผลคูณของอาร์กิวเมนต์ทั้งหมด) เปิดวงเล็บ:
พิจารณาคำสันธานเดียวกัน:
เป็นผลให้เราได้รับ SDNF ที่มีคำสันธาน 9 คำ ดังนั้นตารางความจริงของฟังก์ชันนี้จึงมีค่า 1 ใน 9 แถว จำนวน 2 ชุด 4 =16 ชุดของค่าตัวแปร
3. สมการนี้มีคำตอบกี่ข้อ (ระบุเฉพาะตัวเลขในคำตอบของคุณ)
มาทำให้นิพจน์ง่ายขึ้น:
,
3 ทาง: การก่อสร้าง SDNF
พิจารณาคำสันธานเดียวกัน:
เป็นผลให้เราได้รับ SDNF ที่มีคำสันธาน 5 คำ ดังนั้น ตารางความจริงของฟังก์ชันนี้จึงมีค่า 1 ใน 5 แถว โดย 2 ชุด 4 =16 ชุดของค่าตัวแปร
การสร้างนิพจน์เชิงตรรกะโดยใช้ตารางความจริง:
สำหรับแต่ละแถวของตารางความจริงที่มี 1 เราจะเขียนผลคูณของอาร์กิวเมนต์ และตัวแปรเท่ากับ 0 จะรวมอยู่ในผลคูณที่มีการปฏิเสธ และตัวแปรเท่ากับ 1 จะรวมไว้โดยไม่มีการปฏิเสธ นิพจน์ที่ต้องการ F จะประกอบด้วยผลรวมของผลิตภัณฑ์ผลลัพธ์ ถ้าเป็นไปได้ ควรทำให้นิพจน์นี้ง่ายขึ้น
ตัวอย่าง: ให้ตารางความจริงของนิพจน์ สร้างนิพจน์เชิงตรรกะ
สารละลาย:3. การบ้าน (5 นาที)
แก้สมการ:
สมการนี้มีคำตอบกี่ข้อ (ระบุเฉพาะตัวเลขในคำตอบของคุณ)
ใช้ตารางความจริงที่กำหนด สร้างนิพจน์เชิงตรรกะและ
ทำให้ง่ายขึ้น
