Хувьсагчдыг өөрчлөх замаар логик тэгшитгэлийн системийг шийдвэрлэх
Хэрэв зарим хувьсагчийг тэгшитгэлд зөвхөн тодорхой илэрхийлэл хэлбэрээр оруулсан бол хувьсагчдыг орлуулах аргыг ашигладаг, өөр юу ч биш. Дараа нь энэ илэрхийллийг шинэ хувьсагчаар тэмдэглэж болно.
Жишээ 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 хувьсагчдын утгын хүснэгтэд нэг нь тэгийн зүүн талд байх ёсгүй:
Тэдгээр. y1-y4 5 багцын нөхцөл хангагдсан байна.
Учир нь y1 = x1 → x2, тэгвэл y1 = 0 утгыг x1, x2: (1, 0) нэг багц дээр, y1 = 1 утгыг x1, x2 гурван багц дээр олж авна: (0,0) , (0) ,1), (1.1). Y2, y3, y4-ийн хувьд мөн адил.
y1 хувьсагчийн багц бүрийг (x1,x2) y2 гэх мэтийн олонлог бүртэй (x3,x4) нэгтгэдэг тул 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. Дараа нь арван хувьсагчийн хувьд бид 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
(y 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,0)-аас бусад бүх залгуурт утга нь 1 байна. Энэ нь эхний тэгшитгэлийн шийдэл нь 0-ийн зүүн талд байрлахгүй (5 багц) дараах x1, x2, x3, x4 олонлогууд байх болно гэсэн үг юм.
Үүний нэгэн адил хоёр ба гурав дахь тэгшитгэлийн шийдлүүд нь y1,…,y4 ба z1,…, z4 олонлогтой яг ижил байх болно.
Одоо системийн дөрөв дэх тэгшитгэлд дүн шинжилгээ хийцгээе: x 4 ∧ y 4 ∧ z 4 = 0. Шийдэл нь хувьсагчдын аль нэг нь 0-тэй тэнцүү байх бүх x4, y4, z4 олонлогууд байх болно.
Тэдгээр. 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 хувьсагчдын утгын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл:
Системийн эхний зургаан тэгшитгэл нь ижил бөгөөд зөвхөн хувьсагчийн багцад ялгаатай гэдгийг анхаарна уу. Эхний тэгшитгэлийг харцгаая. Үүний шийдэл нь дараах хувьсагчдын багц байх болно.
гэж тэмдэглэе:
(x1,y1)-ээс A 1 хүртэлх хувьсагчид дээрх хэлхээний тоо (0,0),
(x1,y1)-ээс B 1 хүртэлх хувьсагчид дээрх хэлхээний тоо (0,1),
(x1,y1)-ээс C 1 хүртэлх хувьсагчид дээрх хэлхээний тоо (1,0),
(x1,y1)-ээс D 1 хүртэлх хувьсагчид (1,1) хэлхээний тоо.
(x2,y2)-аас A 2 хүртэлх хувьсагчид дээрх хэлхээний тоо (0,0),
(x2,y2)-аас B 2 хүртэлх хувьсагчид дээрх хэлхээний тоо (0,1),
(x2,y2)-аас C 2 хүртэлх хувьсагчид дээрх хэлхээний тоо (1,0),
(x2,y2)-аас D 2 хүртэлх хувьсагчдын тоо (1,1) .
Шийдвэрийн модноос бид үүнийг харж байна
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
(x2,y2) хувьсагчдын (0,0) олонлогийг (x1,y1) хувьсагчдын (0,1), (1,0) болон (1,1) олонлогоос олж авсан болохыг анхаарна уу. Тэдгээр. A 2 =B 1 +C 1 +D 1.
(x2,y2) хувьсагчид дээрх (0,1) олонлогийг (x1,y1) хувьсагчдын (0,1), (1,0) болон (1,1) олонлогоос авна. Тэдгээр. B 2 =B 1 +C 1 +D 1.
Үүнтэй адил маргаж, бид C 2 =B 1 +C 1 +D 1 гэдгийг тэмдэглэж байна. D2 = D1.
Тиймээс бид давтагдах томъёог олж авдаг:
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
Ширээ хийцгээе
| Багцууд | Тэмдэглэл. | Томъёо |
Багцын тоо |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | А и | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C би | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D би | D i+1 =D i | 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
Компьютерийн шинжлэх ухааны шалгалтын А, В хэсгийн зарим асуудлыг хэрхэн шийдвэрлэх талаар
Хичээл №3. Логик. Логик функцууд. Тэгшитгэл шийдвэрлэх
Улсын нэгдсэн шалгалтын олон тооны асуудал нь саналын логикт зориулагдсан болно. Тэдгээрийн ихэнхийг шийдвэрлэхийн тулд саналын логикийн үндсэн хуулиудыг, нэг ба хоёр хувьсагчийн логик функцүүдийн үнэний хүснэгтийн талаархи мэдлэгийг мэдэхэд хангалттай. Би саналын логикийн үндсэн хуулиудыг өгөх болно.
- Дизьюнкц ба коньюнкцийн шилжих чадвар:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Дизюнкц ба коньюнкцийн талаарх хуваарилалтын хууль:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Үгүйсгэхийг үгүйсгэх:
¬(¬a) ≡ a - Тохиромжтой байдал:
a ^ ¬a ≡ худал - Онцгой гурав дахь:
a ˅ ¬а ≡ үнэн - Де Морганы хуулиуд:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Хялбарчлал:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ үнэн ≡ a
a ˄ худал ≡ худал - Шингээлт:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Далд утгыг солих
a → b ≡ ¬a ˅ b - Баримт бичгийг солих
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Логик функцүүдийн төлөөлөл
n хувьсагчийн аливаа логик функц - F(x 1, x 2, ... x n)-ийг үнэний хүснэгтээр тодорхойлж болно. Ийм хүснэгтэд 2n олонлог хувьсагч агуулагддаг бөгөөд тус бүрд нь энэ олонлог дээрх функцийн утгыг зааж өгсөн болно. Хувьсагчийн тоо харьцангуй бага үед энэ арга сайн. Аль хэдийн n > 5-ын хувьд дүрслэл муу харагдах болно.
Өөр нэг арга бол мэдэгдэж буй нэлээн энгийн функцуудыг ашиглан ямар нэг томъёогоор функцийг тодорхойлох явдал юм. Хэрэв ямар нэгэн логик функцийг зөвхөн f i функц агуулсан томьёогоор илэрхийлж чадвал функцүүдийн системийг (f 1, f 2, … f k) бүрэн гэж нэрлэдэг.
Функцийн систем (¬, ˄, ˅) дууссан. 9 ба 10-р хууль нь үгүйсгэх, коньюнкц, салгах замаар далд утга, ижил төстэй байдлыг хэрхэн илэрхийлдгийг харуулсан жишээ юм.
Үнэн хэрэгтээ үгүйсгэх ба холбогч эсвэл үгүйсгэх ба салгах гэсэн хоёр функцээс бүрдсэн систем мөн бүрэн дүүрэн байдаг. Де Морганы хуулиас нэгтгэлийг үгүйсгэх, салгах замаар илэрхийлэх, үүний дагуу үгүйсгэх, салгах замаар салгах санааг илэрхийлэх санаануудыг дагаж мөрддөг.
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Хачирхалтай нь, зөвхөн нэг функцээс бүрдэх систем бүрэн дүүрэн байдаг. Хоёр хоёртын функц байдаг - эсрэг холболт ба задралын эсрэг, Peirce сум ба Шефферийн харвалт гэж нэрлэгддэг, хөндий системийг төлөөлдөг.
Програмчлалын хэлний үндсэн функцууд нь ихэвчлэн таних, үгүйсгэх, холбох, салгах зэрэг орно. IN Улсын нэгдсэн шалгалтын даалгаварЭдгээр функцүүдийн зэрэгцээ үр дагавар нь ихэвчлэн олддог.
Цөөн хэдэн зүйлийг харцгаая энгийн даалгаваруудлогик функцтэй холбоотой.
Асуудал 15:
Үнэний хүснэгтийн фрагментийг өгөв. Өгөгдсөн гурван функцийн аль нь энэ фрагменттэй тохирч байна вэ?
| X 1 | X 2 | X 3 | X 4 | Ф |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Функцийн дугаар 3.
Асуудлыг шийдэхийн тулд та үндсэн функцүүдийн үнэний хүснэгтийг мэдэж, үйл ажиллагааны тэргүүлэх чиглэлийг санах хэрэгтэй. Холбогч (логик үржүүлэх) нь дизюнкцаас (логик нэмэх) илүү чухал ач холбогдолтой бөгөөд эрт гүйцэтгэдэг гэдгийг сануулъя. Тооцооллын явцад гурав дахь багц дахь 1 ба 2 тоотой функцууд нь 1 утгатай бөгөөд энэ шалтгааны улмаас фрагменттэй тохирохгүй байгааг анзаарахад хялбар байдаг.
Асуудал 16:
Өгөгдсөн тоонуудын аль нь нөхцөлийг хангаж байна:
(хамгийн чухал цифрээс эхэлсэн цифрүүд буурах дарааллаар байна) → (тоо - тэгш) ˄ (бага орон - тэгш) ˄ (өндөр орон - сондгой)
Хэрэв хэд хэдэн ийм тоо байгаа бол хамгийн томыг нь зааж өгнө үү.
- 13579
- 97531
- 24678
- 15386
Нөхцөл 4-ийн тоогоор хангагдсан байна.
Эхний хоёр тоо нь хамгийн бага орон сондгой байх нөхцөлийг хангахгүй байна. Холболтын нөхцлүүдийн аль нэг нь худал байвал нөхцлийн холбоо худал болно. Гурав дахь тооны хувьд хамгийн өндөр оронтой байх нөхцөл хангагдаагүй байна. Дөрөв дэх тооны хувьд тухайн тооны бага, өндөр оронтой тоонд тавигдах нөхцөлийг хангасан. Энэ тохиолдолд тохиолдох нөхцөл нь худал бол далд утга нь үнэн тул холболтын эхний гишүүн нь мөн үнэн юм.
Асуудал 17: Хоёр гэрч дараах мэдүүлэг өгсөн.
Нэгдүгээр гэрч: Хэрэв А буруутай бол Б нь бүр ч буруутай, С нь гэм буруугүй.
Хоёр дахь гэрч: Хоёр нь буруутай. Үлдсэн хүмүүсийн нэг нь гарцаагүй буруутай, буруутай, гэхдээ яг хэн гэдгийг хэлж чадахгүй байна.
Мэдүүлгээс А, Б, С нарын гэм буруугийн талаар ямар дүгнэлт хийж болох вэ?
Хариулт: Мэдүүлгээс харахад А, Б буруутай, С нь гэм буруугүй.
Шийдэл: Мэдээж эрүүл ухаанд тулгуурлан хариултыг өгч болно. Гэхдээ үүнийг хэрхэн хатуу, албан ёсоор хийж болохыг харцгаая.
Хамгийн эхний хийх зүйл бол мэдэгдлийг албан ёсны болгох явдал юм. Хэрэв холбогдох сэжигтэн гэм буруутай бол үнэн (1) гэсэн утгатай A, B, C гэсэн гурван логик хувьсагчийг оруулъя. Дараа нь анхны гэрчийн мэдүүлгийг дараах томъёогоор өгнө.
A → (B ˄ ¬C)
Хоёр дахь гэрчийн мэдүүлгийг дараах томъёогоор өгнө.
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
Хоёр гэрчийн мэдүүлгийг үнэн гэж тооцож, харгалзах томъёоны холболтыг илэрхийлнэ.
Эдгээр уншилтын үнэний хүснэгтийг байгуулцгаая.
| А | Б | C | F 1 | F 2 | F 1 ˄ F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Товч нотлох баримт нь зөвхөн нэг тохиолдолд үнэн бөгөөд тодорхой хариулт өгөхөд хүргэдэг - А, Б буруутай, С нь гэм буруугүй.
Энэ хүснэгтийн дүн шинжилгээнээс харахад хоёр дахь гэрчийн мэдүүлэг илүү мэдээлэлтэй байна. Түүний гэрчлэлийн үнэнээс зөвхөн хоёр зүйл л гардаг: боломжит сонголтууд- А, Б буруутай, С буруугүй, эсвэл А, С буруугүй, Б буруугүй. Эхний гэрчийн мэдүүлэг нь мэдээлэл багатай - 5 байна янз бүрийн сонголтууд, түүний гэрчлэлтэй тохирч байна. Хоёр гэрчийн мэдүүлэг нийлээд сэжигтнүүдийн гэм буруугийн талаар тодорхой хариулт өгдөг.
Логик тэгшитгэл ба тэгшитгэлийн систем
F(x 1, x 2, …x n) нь n хувьсагчийн логик функц байг. Логик тэгшитгэл нь дараах байдлаар харагдаж байна.
F(x 1, x 2, …x n) = C,
Тогтмол С нь 1 эсвэл 0 утгатай байна.
Логик тэгшитгэл нь 0-ээс 2 n хүртэл өөр шийдэлтэй байж болно. Хэрэв C нь 1-тэй тэнцүү бол F функц нь үнэн (1) утгыг авдаг үнэний хүснэгтээс бүх хувьсагчдын багц шийдэл болно. Үлдсэн олонлогууд нь C нь тэгтэй тэнцүү тэгшитгэлийн шийдлүүд юм. Та үргэлж дараах хэлбэрийн тэгшитгэлийг авч үзэж болно.
F(x 1 , x 2 , …x n) = 1
Үнэн хэрэгтээ тэгшитгэлийг өгье:
F(x 1, x 2, …x n) = 0
Энэ тохиолдолд бид ижил тэгшитгэл рүү явж болно:
¬F(x 1 , x 2 , …x n) = 1
k логик тэгшитгэлийн системийг авч үзье.
F 1 (x 1, x 2, …x n) = 1
F 2 (x 1, x 2, …x n) = 1
F k (x 1 , x 2 , …x n) = 1
Системийн шийдэл нь системийн бүх тэгшитгэл хангагдсан хувьсагчдын багц юм. Логик функцүүдийн хувьд логик тэгшитгэлийн системийн шийдлийг олж авахын тулд анхны F функцүүдийн холболтыг төлөөлсөн Ф логик функц үнэн байх олонлогийг олох хэрэгтэй.
Ф = F 1 ˄ F 2 ˄ … F k
Хэрэв хувьсагчийн тоо бага, жишээлбэл, 5-аас бага бол Ф функцийн үнэний хүснэгтийг байгуулах нь тийм ч хэцүү биш бөгөөд энэ нь системд хэдэн шийдэлтэй, шийдлийг өгдөг олонлогуудыг хэлэх боломжийг олгодог.
Логик тэгшитгэлийн системийн шийдлийг олох зарим USE асуудалд хувьсагчийн тоо 10 хүрдэг. Дараа нь үнэний хүснэгт байгуулах нь бараг боломжгүй ажил болдог. Асуудлыг шийдэх нь өөр арга барилыг шаарддаг. Дурын тэгшитгэлийн системийн хувьд байхгүй ерөнхий арга, харгис хүчнээс ялгаатай нь ийм асуудлыг шийдвэрлэх боломжийг олгодог.
Шалгалтанд санал болгож буй асуудлын шийдэл нь ихэвчлэн тэгшитгэлийн системийн онцлогийг харгалзан үздэг. Би давтан хэлье, олон тооны хувьсагчийн бүх сонголтыг туршиж үзэхээс гадна асуудлыг шийдэх ерөнхий арга байхгүй. Шийдэл нь системийн онцлогт тулгуурлан бүтээгдсэн байх ёстой. Мэдэгдэж буй логик хуулиудыг ашиглан тэгшитгэлийн системийг урьдчилан хялбарчлах нь ихэвчлэн ашигтай байдаг. Өөр ашигтай трикЭнэ асуудлын шийдэл нь дараах байдалтай байна. Бид бүх олонлогийг сонирхдоггүй бөгөөд зөвхөн Φ функц нь 1 гэсэн утгатай байх болно. Барилгын оронд бүрэн ширээүнэн, бид түүний аналогийг бүтээх болно - хоёртын шийдвэрийн мод. Энэ модны мөчир бүр нь нэг шийдэлтэй тохирч, Ф функц 1 гэсэн утгатай олонлогийг зааж өгдөг. Шийдвэрлэх модны мөчрүүдийн тоо нь тэгшитгэлийн системийн шийдүүдийн тоотой давхцдаг.
Би хоёртын шийдвэрийн мод гэж юу болох, түүнийг хэрхэн бүтээх талаар хэд хэдэн асуудлын жишээн дээр тайлбарлах болно.
Асуудал 18
Хоёр тэгшитгэлийн системийг хангадаг x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 логик хувьсагчдын утгын хэдэн өөр багц байдаг вэ?
Хариулт: Систем нь 36 өөр шийдэлтэй.
Шийдэл: Тэгшитгэлийн системд хоёр тэгшитгэл багтана. x 1, x 2, ...x 5 гэсэн 5 хувьсагчаас хамаарч эхний тэгшитгэлийн шийдийн тоог олъё. Эхний тэгшитгэлийг эргээд 5 тэгшитгэлийн систем гэж үзэж болно. Дээр дурдсанчлан тэгшитгэлийн систем нь логик функцүүдийн нэгдлийг илэрхийлдэг. Мөн эсрэгээр нь үнэн юм: нөхцлийн холболтыг тэгшитгэлийн систем гэж үзэж болно.
Анхны тэгшитгэл гэж үзэж болох холболтын эхний гишүүн (x1→ x2)-д зориулсан шийдвэрийн модыг байгуулъя. Энэ модны график дүрслэл дараах байдалтай байна.
Мод нь тэгшитгэл дэх хувьсагчдын тоогоор хоёр түвшнээс бүрдэнэ. Эхний түвшин нь эхний хувьсагч X 1-ийг тодорхойлдог. Энэ түвшний хоёр салбар нь энэ хувьсагчийн боломжит утгуудыг тусгадаг - 1 ба 0. Хоёр дахь түвшинд модны мөчрүүд нь зөвхөн тэгшитгэл үнэн болох X 2 хувьсагчийн боломжит утгуудыг тусгасан болно. Тэгшитгэл нь далд санааг зааж байгаа тул X 1 нь 1 утгатай салбар нь тухайн салбар дээр X 2 нь 1 утгатай байхыг шаарддаг. X 1 нь 0 утгатай салбар нь X 2 утгатай хоёр салбар үүсгэдэг. 0 ба 1-тэй тэнцүү Баригдсан мод нь гурван шийдлийг тодорхойлдог бөгөөд үүнд X 1 → X 2 утга нь 1 гэсэн утгыг авдаг. Салбар бүр дээр хувьсах утгуудын харгалзах багцыг бичиж, тэгшитгэлийн шийдийг өгдөг.
Эдгээр багцууд нь: ((1, 1), (0, 1), (0, 0))
Дараахь X 2 → X 3 гэсэн утгатай дараах тэгшитгэлийг нэмж шийдвэрийн модыг үргэлжлүүлэн байгуулъя. Манай тэгшитгэлийн системийн онцлог нь системийн шинэ тэгшитгэл болгонд өмнөх тэгшитгэлийн нэг хувьсагчийг ашиглаж, нэг шинэ хувьсагчийг нэмдэгт оршино. X 2 хувьсагч нь модонд аль хэдийн утгуудтай байдаг тул X 2 хувьсагч нь 1 утгатай бүх салбарууд дээр X 3 хувьсагч нь мөн 1 утгатай байх болно. Ийм салбаруудын хувьд модыг барих дараагийн түвшинд хүртэл үргэлжлэх боловч шинэ салбарууд гарч ирэхгүй байна. X 2 хувьсагч нь 0 утгатай ганц салбар нь X 3 хувьсагч 0 ба 1 утгыг хүлээн авах хоёр салбар болж салбарлана. Тиймээс шинэ тэгшитгэлийн нэмэлт болгонд өөрийн онцлогийг харгалзан нэг шийд нэмнэ. Анхны анхны тэгшитгэл:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6 шийдэлтэй. Энэ нь иймэрхүү харагдаж байна бүрэн модЭнэ тэгшитгэлийн шийдлүүд:
Манай системийн хоёр дахь тэгшитгэл нь эхнийхтэй төстэй:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Ганц ялгаа нь тэгшитгэл нь Y хувьсагчийг ашигладаг. X i хувьсагчдын шийдэл бүрийг Y j хувьсагчийн шийдэл бүртэй нэгтгэж болох тул нийт тоо 36 шийдэл байдаг.
Баригдсан шийдвэрийн мод нь зөвхөн шийдлүүдийн тоог (салбарын тоогоор) төдийгүй модны мөчир тус бүр дээр бичсэн шийдлүүдийг өөрөө өгдөг гэдгийг анхаарна уу.
Асуудал 19
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
Энэ даалгавар нь өмнөх даалгаврын өөрчлөлт юм. Үүний ялгаа нь X ба Y хувьсагчдыг холбосон өөр нэг тэгшитгэл нэмэгдсэнд оршино.
X 1 → Y 1 тэгшитгэлээс харахад X 1 нь 1 утгатай байхад (ийм нэг шийдэл байгаа) Y 1 нь мөн 1 утгатай байна. Тиймээс X 1 ба Y 1 нь утгыг агуулсан нэг олонлог байна. 1. X 1 нь 0-тэй тэнцүү бол Y 1 нь 0 ба 1 гэсэн ямар ч утгатай байж болно. Тиймээс X 1-тэй олонлог бүр 0-тэй тэнцүү бөгөөд ийм 5 олонлог байдаг нь Y хувьсагчтай бүх 6 олонлогтой тохирч байна. Тиймээс нийт шийдлийн тоо 31 байна.
Асуудал 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Шийдэл: Үндсэн тэгшитгэлийг санаж, тэгшитгэлээ дараах байдлаар бичнэ.
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
Цикл нөлөөллийн гинжин хэлхээ нь хувьсагчид ижил байна гэсэн үг тул бидний тэгшитгэл нь тэгшитгэлтэй тэнцүү байна:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
Бүх X i нь 1 эсвэл 0 байх үед энэ тэгшитгэл нь хоёр шийдэлтэй байна.
Асуудал 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Шийдэл: 20-р асуудлын нэгэн адил бид мөчлөгийн үр дагавраас ижил төстэй байдал руу шилжиж, тэгшитгэлийг дараах хэлбэрээр дахин бичнэ.
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Энэ тэгшитгэлийн шийдвэрийн модыг байгуулъя: 
Асуудал 22
Дараах тэгшитгэлийн систем хэдэн шийдэлтэй вэ?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0
((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0
((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0
((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0
Хариулт: 64
Шийдэл: Дараах хувьсагчийн өөрчлөлтийг оруулан 10 хувьсагчаас 5 хувьсагч руу шилжье.
Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);
Дараа нь эхний тэгшитгэл нь дараах хэлбэртэй болно.
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Тэгшитгэлийг дараах байдлаар бичих замаар хялбарчилж болно.
(Y 1 ≡ Y 2) = 0
Уламжлалт хэлбэрт шилжсэнээр бид системийг хялбаршуулсаны дараа дараах хэлбэрээр бичнэ.
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
Энэ системийн шийдвэрийн мод нь энгийн бөгөөд хувьсах утга бүхий хоёр салбараас бүрдэнэ.
Анхны X хувьсагчид руу буцахдаа Y хувьсагчийн утга тус бүрийн хувьд X хувьсагчийн 2 утга байгаа тул Y хувьсагчийн шийдэл бүр X хувьсагчид 2 5 шийдлийг үүсгэдэг болохыг анхаарна уу 5 шийдэлтэй тул нийт шийдлийн тоо 64 байна.
Таны харж байгаагаар тэгшитгэлийн системийг шийдвэрлэх асуудал бүр өөрийн гэсэн арга барилыг шаарддаг. Түгээмэл арга бол тэгшитгэлийг хялбарчлахын тулд эквивалент хувиргалт хийх явдал юм. Нийтлэг арга бол шийдвэрийн модыг барих явдал юм. Ашигласан арга нь хувьсагчийн боломжит утгуудын бүх багцыг бүтээгээгүй, зөвхөн функц 1 (үнэн) утгыг авдаг онцлогтой нь үнэний хүснэгтийг байгуулахыг хэсэгчлэн санагдуулдаг. Ихэнхдээ санал болгож буй асуудлуудад аль хэдийн шийдвэрийн модыг бүрэн бүтээх шаардлагагүй байдаг эхний шатЖишээлбэл, 18-р асуудалд хийсэн шиг дараагийн түвшин бүрт шинэ салбаруудын харагдах загварыг тогтоох боломжтой.
Ерөнхийдөө логик тэгшитгэлийн системийн шийдлийг олохтой холбоотой асуудлууд нь математикийн сайн дасгалууд юм.
Хэрэв асуудлыг гараар шийдвэрлэхэд хэцүү бол тэгшитгэл, тэгшитгэлийн системийг шийдвэрлэх зохих програм бичиж компьютерт даатгаж болно.
Ийм программ бичих нь тийм ч хэцүү биш юм. Ийм хөтөлбөр нь улсын нэгдсэн шалгалтанд санал болгож буй бүх даалгаврыг амархан даван туулах болно.
Хачирхалтай нь, логик тэгшитгэлийн системийн шийдлийг олох ажил нь компьютерт хэцүү байдаг бөгөөд компьютерт өөрийн гэсэн хязгаар байдаг. Компьютер нь хувьсагчийн тоо 20-30 байдаг даалгавруудыг амархан даван туулж чаддаг ч удаан хугацааны туршид асуудлын талаар бодож эхэлдэг. илүү том хэмжээтэй. Баримт нь олонлогийн тоог тодорхойлдог 2 n функц нь n нэмэгдэх тусам хурдацтай өсдөг экспоненциал юм. Өдөрт 40 хувьсагчтай даалгаврыг энгийн персонал компьютер даван туулах чадваргүй тийм хурдан байдаг.
Логик тэгшитгэлийг шийдвэрлэх C# хэл дээрх програм
Логик тэгшитгэлийг шийдвэрлэх програм бичих нь зөвхөн Улсын нэгдсэн шалгалтын тестийн асуудлыг өөрийн шийдлийн зөв эсэхийг шалгахад ашиглаж болох юм бол олон шалтгааны улмаас ашигтай байдаг. Өөр нэг шалтгаан нь ийм хөтөлбөр нь Улсын нэгдсэн шалгалтын С ангиллын даалгаварт тавигдах шаардлагыг хангасан програмчлалын даалгаврын маш сайн жишээ юм.
Хөтөлбөрийг бүтээх санаа нь энгийн бөгөөд энэ нь хувьсах утгын бүх боломжит багцыг бүрэн хайхад суурилдаг. Өгөгдсөн логик тэгшитгэл эсвэл тэгшитгэлийн системийн хувьд n хувьсагчийн тоо мэдэгдэж байгаа тул олонлогийн тоо бас мэдэгдэж байна - 2 n тэдгээрийг эрэмбэлэх шаардлагатай. Ашиглаж байна үндсэн функцууд C# хэл - үгүйсгэх, салгах, коньюнкц ба адилтгал зэрэг нь өгөгдсөн хувьсагчдын багцад логик тэгшитгэл эсвэл тэгшитгэлийн системд тохирох логик функцийн утгыг тооцоолох програм бичихэд хэцүү биш юм.
Ийм программ дээр та олонлогийн тоонд тулгуурлан гогцоо барьж, олонлогийн тоон дээр тулгуурлан давталтын биед олонлогийг өөрөө бүрдүүлж, энэ багц дээрх функцийн утгыг тооцоолох, хэрэв энэ утга нь 1 бол олонлог нь тэгшитгэлийн шийдийг өгнө.
Хөтөлбөрийг хэрэгжүүлэхэд тулгардаг цорын ганц бэрхшээл нь тогтоосон тоон дээр үндэслэн хувьсах утгуудын багцыг өөрөө бий болгох ажилтай холбоотой юм. Энэ асуудлын гоо үзэсгэлэн нь энэ хэцүү мэт санагдах ажил нь үнэндээ олон удаа үүссэн энгийн асуудал дээр ирдэг. Үнэн хэрэгтээ тэг ба нэгээс бүрдэх i тоотой харгалзах хувьсах утгуудын багц нь i тооны хоёртын дүрслэлийг төлөөлдөг гэдгийг ойлгоход хангалттай. Тэгэхээр хэцүү даалгаварТодорхой тоогоор хувьсах утгуудын багцыг олж авах нь тоог хоёртын систем рүү хөрвүүлэх алдартай асуудал юм.
Бидний асуудлыг шийдэж буй C# хэл дээрх функц иймэрхүү харагдаж байна:
///
/// шийдлийн тоог тоолох програм
/// логик тэгшитгэл (тэгшитгэлийн систем)
///
///
/// логик функц - арга,
/// түүний гарын үсгийг ХС-ийн төлөөлөгч тодорхойлсон
///
/// хувьсагчийн тоо
///
static int SolveEquations(DF хөгжилтэй, int n)
bool set = new bool[n];
int m = (int)Math.Pow(2, n); // багцын тоо
int p = 0, q = 0, k = 0;
//Багцын тоогоор хайлтыг гүйцээнэ
хувьд (int i = 0; i< m; i++)
//Дараагийн багцыг бүрдүүлэх - багц,
//i тооны хоёртын дүрслэлээр тодорхойлогддог
for (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Олонлог дээрх функцын утгыг тооцоол
Хөтөлбөрийг ойлгохын тулд хөтөлбөрийн санаа, тайлбарыг текстэнд нь тайлбарлах нь хангалттай байх гэж найдаж байна. Би зөвхөн өгөгдсөн функцийн гарчгийг тайлбарлахад анхаарлаа хандуулах болно. SolveEquations функц нь хоёр оролтын параметртэй. Хөгжилтэй параметр нь шийдэж буй тэгшитгэл эсвэл тэгшитгэлийн системд тохирох логик функцийг тодорхойлдог. n параметр нь тоог тодорхойлдог функцын хувьсагчидхөгжилтэй. Үүний үр дүнд SolveEquations функц нь логик функцийн шийдүүдийн тоог, өөрөөр хэлбэл функц үнэн гэж үнэлдэг олонлогуудын тоог буцаана.
Зарим F(x) функц нь арифметик, мөр эсвэл логик төрлийн хувьсагч x оролтын параметртэй байх нь сургуулийн сурагчдад түгээмэл байдаг. Манай тохиолдолд илүү хүчирхэг загварыг ашигладаг. SolveEquations функц нь параметрүүд нь зөвхөн энгийн хувьсагчаас гадна функц байж болох F(f) төрлийн функцуудыг хэлдэг.
SolveEquations функцэд параметр болгон дамжуулж болох функцүүдийн ангиллыг дараах байдлаар тодорхойлно.
delegate bool DF(bool vars);
Энэ анги нь vars массиваар тодорхойлсон логик хувьсагчийн утгуудын багцыг параметр болгон дамжуулсан бүх функцийг эзэмшдэг. Үр дүн нь энэ олонлог дээрх функцийн утгыг илэрхийлэх логик утга юм.
Эцэст нь, хэд хэдэн логик тэгшитгэлийн системийг шийдвэрлэхийн тулд SolveEquations функцийг ашигладаг програмыг энд оруулав. SolveEquations функц нь доорх ProgramCommon ангийн нэг хэсэг юм:
ангийн програм Нийтлэг
delegate bool DF(bool vars);
статик хүчингүй Үндсэн(string args)
Console.WriteLine("Ба функцууд - " +
Шийдэх тэгшитгэл(Зөөлөн ба, 2));
Console.WriteLine("Функц нь 51 шийдэлтэй - " +
Шийдэх тэгшитгэл(Хөгжилтэй51, 5));
Console.WriteLine("Функц нь 53 шийдэлтэй - " +
Шийдэх тэгшитгэл(Хөгжилтэй53, 10));
статик bool FunAnd(bool vars)
буцаах vars && vars;
статик bool Fun51(bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
статик bool Fun53(bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Энэ програмын шийдлийн үр дүн дараах байдалтай байна.
Бие даасан ажилд зориулсан 10 даалгавар
- Гурван функцийн аль нь тэнцүү вэ:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄Y
- Үнэний хүснэгтийн фрагментийг өгөв.
| X 1 | X 2 | X 3 | X 4 | Ф |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Энэ хэсэг нь гурван функцийн алинд нь тохирох вэ:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- Шүүгчдийн бүрэлдэхүүн гурван хүний бүрэлдэхүүнтэй. Шүүгчийн гишүүдийн дор хаяж нэг нь дэмжсэн тангарагтны дарга санал өгсөн тохиолдолд шийдвэр гарна. Тэгэхгүй бол шийдвэр гарахгүй. Шийдвэр гаргах үйл явцыг албан ёсны болгох логик функцийг байгуул.
- Дөрвөн зоос шидэхэд гурван удаа толгой цохиход X нь Y-г хожно. X-ийн өгөөжийг тодорхойлсон логик функцийг тодорхойлно уу.
- Өгүүлбэр дэх үгсийг нэгээс эхлэн дугаарлана. Дараах дүрмүүдийг хангасан тохиолдолд өгүүлбэрийг зөв зохиосон гэж үзнэ.
- Тэгш тоотой үг эгшигээр төгссөн бол дараагийн үг, хэрэв байгаа бол эгшгээр эхлэх ёстой.
- Хэрэв сондгой тоотой үг гийгүүлэгчээр төгссөн бол дараагийн үг байгаа бол гийгүүлэгчээр эхэлж, эгшигээр төгсөх ёстой.
Дараах өгүүлбэрүүдийн аль нь зөв зохиогдсон бэ? - Ээж Машаг савангаар угаав.
- Удирдагч хүн үргэлж үлгэр жишээ байдаг.
- Үнэн сайхан ч аз жаргал илүү дээр.
- Тэгшитгэл хэдэн шийдэлтэй вэ:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Тэгшитгэлийн бүх шийдлийг жагсаа:
(a → b) → c = 0 - Дараахь тэгшитгэлийн систем хэдэн шийдэлтэй вэ?
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - Тэгшитгэл хэдэн шийдэлтэй вэ:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Асуудлын хариултууд:
- b ба c функцүүд нь тэнцүү байна.
- Фрагмент нь b функцтэй тохирч байна.
- Шүүгчдийн зөвлөлийн дарга шийдвэрт санал өгөхөд P логик хувьсагч 1-ийн утгыг ав. M 1 ба M 2 хувьсагч нь тангарагтны гишүүдийн санал бодлыг илэрхийлдэг. Эерэг шийдвэр гаргах логик функцийг дараах байдлаар бичиж болно.
P ˄ (M 1 ˅ M 2) - i-р зоос толгой дээр буухад P i логик хувьсагч 1 утгыг авъя. X өгөөжийг тодорхойлдог логик функцийг дараах байдлаар бичиж болно.
¬((¬P 1 ˄ (¬P 2 ¬ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Өгүүлбэр b.
- Тэгшитгэл нь 3 шийдэлтэй: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)
Логик тэгшитгэлийн системийг шийдвэрлэх арга
Та логик тэгшитгэлийн системийг шийдэж болно, жишээлбэл, үнэний хүснэгт (хэрэв хувьсагчдын тоо хэт том биш бол) эсвэл шийдвэрийн модыг ашиглан эхлээд тэгшитгэл бүрийг хялбаршуулж болно.
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); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Анхаар! x1, x2, ..., x10 хувьсагч бүрийг зөвхөн нэг шинэ хувьсагчд оруулах ёстой. хувьсагч A, B, C, D, E, өөрөөр хэлбэл шинэ хувьсагчид бие биенээсээ хамааралгүй).
Дараа нь тэгшитгэлийн систем дараах байдлаар харагдах болно.
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬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 мөчиртэй болно. Эдгээр салбаруудын зарим нь системийн гурав дахь тэгшитгэлийг хангадаггүй. Эхний модон дээр модны мөчрүүдийн тоог тэмдэглэе"y" , гурав дахь тэгшитгэлийг хангадаг:
Тайлбарлая: гурав дахь нөхцлийг хангахын тулд x1 = 0 үед y1 = 1 байх ёстой, өөрөөр хэлбэл модны бүх мөчир байх ёстой."X" , энд x1=0-ийг модноос зөвхөн нэг мөчрөөр үргэлжлүүлж болно"y" . Мөн зөвхөн модны нэг мөчирний хувьд"X" (баруун) модны бүх мөчир таарч байна"y". Тиймээс бүхэл бүтэн системийн бүрэн мод нь 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-тэй тэнцүү байх ёстой; y1=0 ба z1=1 үед хоёр дахь хаалт нь 1-тэй тэнцүү байх болно; y1=1 ба z1=0 үед гурав дахь хаалт нь 1-тэй тэнцүү байх болно (өөрөөр хэлбэл энэ тохиолдолд - 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. Х1, 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 үндэс.
Заримдаа үндэс тоо нь Фибоначчийн хуулийн дагуу ургадаг.
Логик тэгшитгэлийн системийг шийдвэрлэх нь бүтээлч хандлагыг шаарддаг.
n хувьсагчийн логик функц байг. Логик тэгшитгэл нь дараах байдлаар харагдаж байна.
Тогтмол С нь 1 эсвэл 0 утгатай байна.
Логик тэгшитгэл нь 0-ээс өөр шийдэлтэй байж болно. Хэрэв C нь 1-тэй тэнцүү бол F функц нь үнэн (1) утгыг авдаг үнэний хүснэгтээс бүх хувьсагчдын багц шийдэл болно. Үлдсэн олонлогууд нь C нь тэгтэй тэнцүү тэгшитгэлийн шийдлүүд юм. Та үргэлж дараах хэлбэрийн тэгшитгэлийг авч үзэж болно.
Үнэн хэрэгтээ тэгшитгэлийг өгье:
Энэ тохиолдолд бид ижил тэгшитгэл рүү явж болно:
k логик тэгшитгэлийн системийг авч үзье.
Системийн шийдэл нь системийн бүх тэгшитгэл хангагдсан хувьсагчдын багц юм. Логик функцүүдийн хувьд логик тэгшитгэлийн системийн шийдлийг олж авахын тулд анхны функцүүдийн холболтыг илэрхийлсэн Ф логик функц үнэн байх олонлогийг олох хэрэгтэй.
Хэрэв хувьсагчийн тоо бага, жишээ нь 5-аас бага бол уг функцийн үнэний хүснэгтийг байгуулах нь тийм ч хэцүү биш бөгөөд энэ нь системд хэдэн шийдэлтэй, шийдлүүдийг өгдөг олонлогуудыг хэлэх боломжийг олгодог.
Логик тэгшитгэлийн системийн шийдлийг олох зарим USE асуудалд хувьсагчийн тоо 10 хүрдэг. Дараа нь үнэний хүснэгт байгуулах нь бараг боломжгүй ажил болдог. Асуудлыг шийдэх нь өөр арга барилыг шаарддаг. Дурын тэгшитгэлийн системийн хувьд тоолохоос өөр ерөнхий арга байхгүй бөгөөд ийм асуудлыг шийдвэрлэх боломжтой.
Шалгалтанд санал болгож буй асуудлын шийдэл нь ихэвчлэн тэгшитгэлийн системийн онцлогийг харгалзан үздэг. Би давтан хэлье, олон тооны хувьсагчийн бүх сонголтыг туршиж үзэхээс гадна асуудлыг шийдэх ерөнхий арга байхгүй. Шийдэл нь системийн онцлогт тулгуурлан бүтээгдсэн байх ёстой. Мэдэгдэж буй логик хуулиудыг ашиглан тэгшитгэлийн системийг урьдчилан хялбарчлах нь ихэвчлэн ашигтай байдаг. Энэ асуудлыг шийдэх өөр нэг ашигтай арга бол дараах байдалтай байна. Бид бүх багцыг сонирхдоггүй, зөвхөн функц нь 1 гэсэн утгатай байх болно. Бүрэн үнэний хүснэгтийг бүтээхийн оронд бид түүний аналог буюу хоёртын шийдвэрийн модыг бүтээх болно. Энэ модны мөчир бүр нь нэг шийдэлтэй тохирч, функц нь 1 гэсэн утгатай олонлогийг зааж өгдөг. Шийдвэрлэх модны мөчрүүдийн тоо нь тэгшитгэлийн системийн шийдүүдийн тоотой давхцдаг.
Би хоёртын шийдвэрийн мод гэж юу болох, түүнийг хэрхэн бүтээх талаар хэд хэдэн асуудлын жишээн дээр тайлбарлах болно.
Асуудал 18
Хоёр тэгшитгэлийн системийг хангадаг x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 логик хувьсагчдын утгын хэдэн өөр багц байдаг вэ?
Хариулт: Систем нь 36 өөр шийдэлтэй.
Шийдэл: Тэгшитгэлийн системд хоёр тэгшитгэл багтана. 5 хувьсагчаас хамаарч эхний тэгшитгэлийн шийдийн тоог олъё. Эхний тэгшитгэлийг эргээд 5 тэгшитгэлийн систем гэж үзэж болно. Дээр дурдсанчлан тэгшитгэлийн систем нь логик функцүүдийн нэгдлийг илэрхийлдэг. Эсрэг заалт нь бас үнэн юм - нөхцөлүүдийн холболтыг тэгшитгэлийн систем гэж үзэж болно.
Анхны тэгшитгэл гэж үзэж болох холболтын эхний гишүүн () -д зориулсан шийдвэрийн модыг бүтээцгээе. Энэ модны график дүрслэл иймэрхүү харагдаж байна
Мод нь тэгшитгэл дэх хувьсагчдын тоогоор хоёр түвшнээс бүрдэнэ. Эхний түвшин нь эхний хувьсагчийг тодорхойлдог. Энэ түвшний хоёр салбар нь энэ хувьсагчийн боломжит утгуудыг тусгадаг - 1 ба 0. Хоёр дахь түвшинд модны мөчрүүд нь зөвхөн тэгшитгэлийг үнэн гэж үнэлдэг хувьсагчийн боломжит утгуудыг тусгадаг. Тэгшитгэл нь далд санааг зааж байгаа тул 1 утгатай салбар нь энэ салбар дээр 1 гэсэн утгатай байхыг шаарддаг. 0 утгатай салбар нь 0 ба 1-тэй тэнцүү утгатай хоёр салбар үүсгэдэг. мод нь гурван шийдлийг зааж өгсөн бөгөөд тэдгээрийн утга нь 1 гэсэн утгыг авдаг. Салбар бүр дээр хувьсах утгуудын харгалзах багцыг бичиж, тэгшитгэлийн шийдлийг өгдөг.
Эдгээр багцууд нь: ((1, 1), (0, 1), (0, 0))
Дараах тэгшитгэлийг нэмэх замаар шийдвэрийн модыг үргэлжлүүлэн бүтээцгээе. Манай тэгшитгэлийн системийн онцлог нь системийн шинэ тэгшитгэл болгонд өмнөх тэгшитгэлийн нэг хувьсагчийг ашиглаж, нэг шинэ хувьсагчийг нэмдэгт оршино. Хувьсагч нь модонд аль хэдийн утгуудтай байдаг тул хувьсагч нь 1 утгатай бүх салбаруудад хувьсагч нь мөн 1 гэсэн утгатай байх болно. Ийм салбаруудын хувьд модыг бүтээх ажил дараагийн түвшинд, гэхдээ шинэ салбар байхгүй. Хувьсагч нь 0 утгатай нэг салбар нь хувьсагч нь 0 ба 1 гэсэн утгыг хүлээн авах хоёр салбар болж салбарлана. Тиймээс шинэ тэгшитгэлийн нэмэлт болгонд өөрийн онцлогийг харгалзан нэг шийдийг нэмнэ. Анхны анхны тэгшитгэл:
6 шийдэлтэй. Энэ тэгшитгэлийн бүрэн шийдвэрийн мод дараах байдалтай байна.
Манай системийн хоёр дахь тэгшитгэл нь эхнийхтэй төстэй:
Ганц ялгаа нь тэгшитгэл нь Y хувьсагчийг ашигладаг. Хувьсах шийд бүрийг хувьсах шийдэл бүртэй нэгтгэж болох тул нийт шийдлийн тоо 36 байна.
Баригдсан шийдвэрийн мод нь зөвхөн шийдлүүдийн тоог (салбарын тоогоор) төдийгүй модны мөчир тус бүр дээр бичсэн шийдлүүдийг өөрөө өгдөг гэдгийг анхаарна уу.
Асуудал 19
X1, x2, x3, x4, x5, y1, y2, y3, y4, y5 гэсэн логик хувьсагчдын утгын хэдэн өөр багц доор жагсаасан бүх нөхцлийг хангасан бэ?
Энэ даалгавар нь өмнөх даалгаврын өөрчлөлт юм. Үүний ялгаа нь X ба Y хувьсагчдыг холбосон өөр нэг тэгшитгэл нэмэгдсэнд оршино.
Тэгшитгэлээс харахад 1-ийн утгатай байх үед (ийм шийдэл байдаг) 1-ийн утгатай байна. Иймд 1-тэй тэнцүү нэг багц байдаг. 0-тэй тэнцүү үед энэ нь байж болно. 0 ба 1 аль аль нь ямар ч утгатай байна. Иймд 0-тэй тэнцүү, ийм 5 олонлог байгаа нь Y хувьсагчтай бүх 6 олонлогтой тохирч байна. Тиймээс нийт шийдлийн тоо 31 байна.
Асуудал 20
Шийдэл: Үндсэн тэгшитгэлийг санаж, тэгшитгэлээ дараах байдлаар бичнэ.
Цикл нөлөөллийн гинжин хэлхээ нь хувьсагчид ижил байна гэсэн үг тул бидний тэгшитгэл нь тэгшитгэлтэй тэнцүү байна:
Энэ тэгшитгэл нь бүгд 1 эсвэл 0 байх үед хоёр шийдэлтэй байна.
Асуудал 21
Тэгшитгэл хэдэн шийдэлтэй вэ:
Шийдэл: 20-р асуудлын нэгэн адил бид мөчлөгийн үр дагавраас ижил төстэй байдал руу шилжиж, тэгшитгэлийг дараах хэлбэрээр дахин бичнэ.
Энэ тэгшитгэлийн шийдвэрийн модыг байгуулъя:
Асуудал 22
Дараах тэгшитгэлийн систем хэдэн шийдэлтэй вэ?
Та сонгож болно янз бүрийн арга замуудлогик тэгшитгэлийн системийг шийдвэрлэх. Энэ нь нэг тэгшитгэл рүү буулгах, үнэний хүснэгт байгуулах, задлах явдал юм.
Даалгавар:Логик тэгшитгэлийн системийг шийд:
Ингээд авч үзье нэг тэгшитгэл болгон бууруулах арга . Энэ арга нь логик тэгшитгэлийг баруун гар тал нь үнэний утгатай (өөрөөр хэлбэл 1) тэнцүү байхаар хувиргах явдал юм. Үүнийг хийхийн тулд логик үгүйсгэх үйлдлийг ашиглана. Дараа нь тэгшитгэлүүд нь нарийн төвөгтэй логик үйлдлүүдийг агуулж байвал бид тэдгээрийг үндсэн зүйлээр солино: "AND", "OR", "NOT". Дараагийн алхам бол "AND" логик үйлдлийг ашиглан тэгшитгэлүүдийг системтэй тэнцэх нэг болгон нэгтгэх явдал юм. Үүний дараа та логик алгебрийн хуулиуд дээр үндэслэн үүссэн тэгшитгэлийг хувиргаж, системийн тодорхой шийдлийг олж авах хэрэгтэй.
Шийдэл 1:Эхний тэгшитгэлийн хоёр талд урвуу хамаарлыг хэрэглэнэ.
"OR" болон "NOT" гэсэн үндсэн үйлдлүүдийн үр дагаврыг төсөөлье:
Тэгшитгэлийн зүүн тал нь 1-тэй тэнцүү тул бид тэдгээрийг "AND" үйлдлийг ашиглан анхны системтэй тэнцэх нэг тэгшитгэлд нэгтгэж болно.
Бид Де Морганы хуулийн дагуу эхний хаалтыг нээж, олж авсан үр дүнг хувиргана.
Үүссэн тэгшитгэл нь нэг шийдэлтэй: A =0, B=0, C=1.
Дараагийн арга бол үнэний хүснэгт байгуулах . Логик хэмжигдэхүүн нь зөвхөн хоёр утгатай байдаг тул та бүх хувилбаруудыг үзэж, тэдгээрийн дундаас өгөгдсөн тэгшитгэлийн систем хангагдсаныг олох боломжтой. Өөрөөр хэлбэл, бид системийн бүх тэгшитгэлийн хувьд нэг нийтлэг үнэний хүснэгтийг байгуулж, шаардлагатай утгууд бүхий шугамыг олно.
Шийдэл 2:Системийн үнэний хүснэгтийг байгуулъя:
|
0 |
0 |
1 |
1 |
0 |
1 |
Даалгаврын нөхцөл хангагдсан мөрийг тодоор тэмдэглэнэ. Тэгэхээр A=0, B=0, C=1.
Арга зам задрал . Гол санаа нь нэг хувьсагчийн утгыг засах (үүнийг 0 эсвэл 1-тэй тэнцүүлэх) бөгөөд ингэснээр тэгшитгэлийг хялбарчлах явдал юм. Дараа нь та хоёр дахь хувьсагчийн утгыг засах боломжтой, гэх мэт.
Шийдэл 3: A = 0 байвал:
Эхний тэгшитгэлээс бид B = 0, хоёр дахь нь - C = 1 болно. Системийн шийдэл: A = 0, B = 0 ба C = 1.
Компьютерийн шинжлэх ухааны улсын нэгдсэн шалгалтын хувьд логик тэгшитгэлийн системийн шийдлүүдийн тоог тодорхойлох шаардлагатай байдаг бөгөөд үүний тулд тодорхой аргууд байдаг. Логик тэгшитгэлийн системийн шийдлийн тоог олох гол аргахувьсагчдыг орлуулах. Эхлээд та логик алгебрийн хуулиудад үндэслэн тэгшитгэл бүрийг аль болох хялбарчилж, дараа нь тэгшитгэлийн нийлмэл хэсгүүдийг шинэ хувьсагчаар сольж, шийдлийн тоог тодорхойлох хэрэгтэй. шинэ систем. Дараа нь орлуулалт руу буцаж очоод шийдлийн тоог тодорхойлно уу.
Даалгавар:(A →B) + (C →D) = 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 )*…*(х м -1 → х м) = 1.
Ингэж бодъё x 1 - үнэн, тэгвэл эхний тэгшитгэлээс бид үүнийг олж авна x 2 бас үнэн, хоёрдугаарт - x 3 =1 гэх мэт х м= 1. Энэ нь m нэгжийн олонлог (1; 1; …; 1) нь системийн шийдэл гэсэн үг. Одоо больё x 1 =0, тэгвэл эхний тэгшитгэлээс бид байна x 2 =0 эсвэл x 2 =1.
Хэзээ x 2 үнэн бол бид үлдсэн хувьсагчид нь үнэн, өөрөөр хэлбэл олонлог (0; 1; ...; 1) нь системийн шийдэл гэдгийг олж авна. At x 2 =0 бид үүнийг ойлгож байна x 3 =0 эсвэл x 3 = гэх мэт. Сүүлчийн хувьсагчийг үргэлжлүүлбэл тэгшитгэлийн шийдлүүд нь дараах хувьсагчдын багц болохыг олж мэдэв (m +1 шийдэл, шийдэл бүр нь хувьсагчийн m утгыг агуулна):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Энэ аргыг хоёртын мод байгуулах замаар сайн тайлбарласан болно. Боломжит шийдлүүдийн тоо нь барьсан модны янз бүрийн салбаруудын тоо юм. Энэ нь m +1-тэй тэнцүү байгааг харахад хялбар байдаг.
|
Мод |
Шийдлийн тоо |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
Үндэслэлд хүндрэлтэй байгаа тохиолдолд судалгаа, барилгыншийдлийг хайж олох боломжтойашиглах үнэний хүснэгтүүд, нэг эсвэл хоёр тэгшитгэлийн хувьд.
Тэгшитгэлийн системийг дараах хэлбэрээр дахин бичье.
Нэг тэгшитгэлийн хувьд үнэний хүснэгтийг тусад нь байгуулъя:
|
x 1 |
x 2 |
(x 1 → x 2) |
Хоёр тэгшитгэлийн үнэний хүснэгтийг байгуулъя:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |