Логик тэгшитгэлийн системийг шийдвэрлэх арга. Компьютерийн шинжлэх ухааны USE бодлого дахь логик тэгшитгэлийн системүүд Логик тэгшитгэлийн янз бүрийн шийдлүүдийн тоо
Даалгаврын каталог.
Логик тэгшитгэл
Эдгээр даалгаврууд дээр шалгалт өгнө үү
Даалгаврын каталог руу буцах
MS Word дээр хэвлэх, хуулах хувилбар
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, энд J, K, L, M, N нь логик хувьсагч мөн үү?
Шийдэл.
(N ∨ ¬N) илэрхийлэл нь дурын N-ийн хувьд үнэн юм
J ∧ ¬K ∧ L ∧ ¬M = 0.
Логик тэгшитгэлийн хоёр талд үгүйсгэхийг хэрэглэж, Де Морганы хуулийг ¬ (A ∧ B) = ¬ A ∨ ¬ B. Бид ¬J ∨ K ∨ ¬L ∨ M = 1 болно.
Логик нийлбэр нь 1-тэй тэнцүү байна. Хэрэв түүний бүрдүүлэгч мэдэгдлүүдийн дор хаяж нэг нь 1-тэй тэнцүү бол үүссэн тэгшитгэл нь тэгшитгэлд орсон бүх хэмжигдэхүүнүүд 0-тэй тэнцүү байхаас бусад тохиолдолд логик хувьсагчийн дурын хослолоор хангагдана. 4 хувьсагч нь 1 эсвэл 0-тэй тэнцүү байж болох тул бүх боломжит хослолууд нь 2·2·2·2 = 16. Тиймээс тэгшитгэл нь 16 −1 = 15 шийдтэй байна.
Олдсон 15 шийдэл нь N логик хувьсагчийн хоёр боломжит утгын аль нэгэнд тохирч байгаа тул анхны тэгшитгэл нь 30 шийдэлтэй байна.
Хариулт: 30
Хэдэн ширхэг янз бүрийн шийдэлтэгшитгэлтэй байна
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
J, K, L, M, N нь логик хувьсагч вэ?
Хариулт нь J, K, L, M, N-ийн өөр өөр утгуудыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл.
Бид A → B = ¬A ∨ B ба ¬(A ∨ B) = ¬A ∧ ¬B томъёог ашигладаг.
Эхний дэд томъёог авч үзье.
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Хоёрдахь дэд томъёог авч үзье
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Гурав дахь дэд томъёог авч үзье
1) M → J = 1 тиймээс,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Нэгтгэцгээе:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 тул 4 шийдэл байна.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Нэгтгэцгээе:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L тул 4 шийдэл байна.
в) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Хариулт: 4 + 4 = 8.
Хариулт: 8
Тэгшитгэл хэдэн өөр шийдэлтэй вэ?
((K ∨ L) → (L ∧ M ∧ N)) = 0
Энд K, L, M, N логик хувьсагчууд вэ? Хариулт нь энэ тэгш байдлыг хангах K, L, M ба N утгын бүх багцыг жагсаах шаардлагагүй. Хариултын хувьд та ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл.
Үйлдлийн энгийн тэмдэглэгээг ашиглан тэгшитгэлийг дахин бичье.
((K + L) → (L M N)) = 0
1) "далд" үйлдлийн үнэний хүснэгтээс (эхний асуудлыг үзнэ үү) энэ тэгш байдал нь зөвхөн нэгэн зэрэг үнэн болно гэсэн үг юм.
K + L = 1 ба L M N = 0
2) эхний тэгшитгэлээс K эсвэл L хувьсагчийн дор хаяж нэг нь 1-тэй тэнцүү байна (эсвэл хоёулаа хамтдаа); Тиймээс гурван тохиолдлыг авч үзье
3) хэрэв K = 1 ба L = 0 бол хоёр дахь тэгш байдал нь дурын M ба N-д тохирно; Хоёр Булийн хувьсагчийн 4 хослол (00, 01, 10, 11) байгаа тул бидэнд 4 өөр шийдэл байна.
4) хэрэв K = 1 ба L = 1 бол хоёр дахь тэгш байдал нь M · N = 0-д тохирно; Ийм 3 хослол байдаг (00, 01 ба 10), бидэнд өөр 3 шийдэл байна
5) хэрэв K = 0 бол L = 1 (эхний тэгшитгэлээс); энэ тохиолдолд M · N = 0 үед хоёр дахь тэгш байдал хангагдана; Ийм 3 хослол байдаг (00, 01 ба 10), бидэнд өөр 3 шийдэл байна
6) нийтдээ бид 4 + 3 + 3 = 10 шийдлийг авна.
Хариулт: 10
Тэгшитгэл хэдэн өөр шийдэлтэй вэ?
(K ∧ L) ∨ (M ∧ N) = 1
Энд K, L, M, N логик хувьсагчууд вэ? Хариулт нь энэ тэгш байдлыг хангах K, L, M, N утгуудын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та зөвхөн ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл.
(K ∧ L) ба (M ∧ N) нь 01, 11, 10-тай тэнцүү байх гурван тохиолдолд илэрхийлэл үнэн байна.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N нь 1-тэй тэнцүү, K ба L нь нэгэн зэрэг 1-ээс бусад бүх зүйл. Тиймээс 3 шийдэл байна.
Логик тэгшитгэлийн системийг шийдэх янз бүрийн арга байдаг. Энэ нь нэг тэгшитгэл рүү буулгах, үнэний хүснэгт байгуулах, задлах явдал юм.
Даалгавар:Логик тэгшитгэлийн системийг шийд:
Ингээд авч үзье нэг тэгшитгэл болгон бууруулах арга . Энэ арга нь логик тэгшитгэлийг баруун гар тал нь үнэний утгатай (өөрөөр хэлбэл 1) тэнцүү байхаар хувиргах явдал юм. Үүнийг хийхийн тулд логик үгүйсгэх үйлдлийг ашиглана. Дараа нь тэгшитгэлүүд нь нарийн төвөгтэй логик үйлдлүүдийг агуулж байвал бид тэдгээрийг үндсэн зүйлээр солино: "AND", "OR", "NOT". Дараагийн алхам бол тэгшитгэлүүдийг системтэй дүйцэхүйц нэг болгон нэгтгэх явдал юм логик ажиллагаа"БА". Үүний дараа та логик алгебрийн хуулиуд дээр үндэслэн үүссэн тэгшитгэлийг хувиргаж, системийн тодорхой шийдлийг олж авах хэрэгтэй.
Шийдэл 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) |
Хотын төсөв боловсролын байгууллага
"Дундаж иж бүрэн сургууль№18"
Бүгд Найрамдах Башкортостан Улсын Салават хотын хотын дүүрэг
Логик тэгшитгэлийн системүүд
В Улсын нэгдсэн шалгалтын даалгаваркомпьютерийн шинжлэх ухаанд
"Логик алгебрийн үндэс" хэсэг Улсын нэгдсэн шалгалтын даалгавархамгийн хэцүү, тааруу шийдэгдээгүйн нэг гэж тооцогддог. Энэ сэдвээр гүйцэтгэсэн ажлын дундаж хувь хамгийн бага буюу 43.2 байна.
| Курсын хэсэг | Ажлын хэсгүүдийн гүйцэтгэлийн дундаж хувь |
| Мэдээллийг кодлох, түүний хэмжээг хэмжих | |
| Мэдээллийн загварчлал | |
| Тооны систем | |
| Логик алгебрийн үндэс | |
| Алгоритмчлал ба програмчлал | |
| Мэдээлэл, харилцаа холбооны технологийн үндэс |
2018 оны KIM-ийн тодорхойлолтод үндэслэн энэхүү блок нь янз бүрийн хүндрэлийн түвшний дөрвөн ажлыг багтаасан болно.
| № даалгавар | Баталгаажуулах боломжтой агуулгын элементүүд | Даалгаврын хүндрэлийн түвшин |
| Үнэний хүснэгт, логик хэлхээ байгуулах чадвар | ||
| Интернетээс мэдээлэл хайх чадвар | ||
| Үндсэн ойлголт, хууль тогтоомжийн талаархи мэдлэг математик логик | ||
| Логик илэрхийлэл бүтээх, хувиргах чадвар |
Даалгавар 23 нь хүндрэлийн түвшин өндөр тул гүйцэтгэлийн хамгийн бага хувьтай байна. Бэлтгэлтэй төгсөгчдийн дунд (81-100 оноо) 49.8% нь дунд зэргийн бэлтгэлтэй төгсөгчид (61-80 оноо) 13.7% нь энэ даалгаврыг биелүүлээгүй;
Логик тэгшитгэлийн системийг шийдвэрлэх амжилт нь логикийн хуулиудын мэдлэг, системийг шийдвэрлэх аргуудыг нарийн ашиглахаас хамаарна.
Логик тэгшитгэлийн системийг зураглалын аргыг ашиглан шийдвэрлэх талаар авч үзье.
(23.154 Поляков К.Ю.) Тэгшитгэлийн систем хэдэн өөр шийдэлтэй вэ?
((x1 y1 ) (х2 y2 )) (х1 x2 ) (ж1 y2 ) =1
((x2 y2 ) (х3 y3 )) (х2 x3 ) (ж2 y3 ) =1
((x7 y7 ) (x8 y8 )) (x7 x8 ) (y7 y8 ) =1
Хаана x1 , x2 ,…, x8, цагт1 , у2 ,…,y8 - логик хувьсагч? Хариулт нь энэ тэгш байдлыг хангах хувьсагчийн утгуудын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл. Системд орсон бүх тэгшитгэлүүд нь ижил төрлийнх бөгөөд тэгшитгэл бүрд дөрвөн хувьсагч багтдаг. x1 ба y1-ийг мэдсэнээр бид эхний тэгшитгэлийг хангасан x2 ба y2-ийн бүх боломжит утгуудыг олж чадна. Үүнтэй адил үндэслэлээр бид мэдэгдэж буй x2 ба y2-аас хоёр дахь тэгшитгэлийг хангасан x3, y3-ийг олж чадна. Өөрөөр хэлбэл (x1, y1) хосыг мэдэж, (x2, y2) хосын утгыг тодорхойлсноор бид (x3, y3) хосыг олох бөгөөд энэ нь эргээд (x4, y4) хосыг бий болгоно. гэх мэт.
Эхний тэгшитгэлийн бүх шийдлийг олъё. Үүнийг хоёр аргаар хийж болно: үндэслэл, логикийн хуулиудыг хэрэгжүүлэх замаар үнэний хүснэгт байгуулах.
Үнэний хүснэгт:
| x 1 y 1 | x 2 y 2 | (x 1 y 1) (x2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Үнэний хүснэгтийг бүтээх нь маш их хөдөлмөр, цаг хугацаа бага шаарддаг тул бид хоёр дахь аргыг ашигладаг - логик үндэслэл. Хэрэв хүчин зүйл бүр 1-тэй тэнцүү байвал үржвэр нь 1-тэй тэнцүү байна.
(x1 y1 ) (x2 y2 ))=1
(x1 x2 ) =1
(y1 y2 ) =1
Эхний тэгшитгэлийг харцгаая. 0 0, 0 1, 1 1 үед үр дагавар нь 1-тэй тэнцүү бөгөөд энэ нь (01), (10)-д (x1 y1)=0, дараа нь хос гэсэн үг юм. (x2 y2 ) дурын (00), (01), (10), (11) байж болох ба (x1 y1) = 1 байх үед (00) ба (11) хос (x2 y2) = 1 нь ижил утгатай (00) ба (11). Хоёр ба гурав дахь тэгшитгэл нь худал, өөрөөр хэлбэл x1=1, x2=0, y1=1, y2=0 гэсэн хосуудыг энэ шийдлээс хасъя.
| (x1 , y1 ) | (x2 , y2 ) |
Нийт хосын тоо 1+1+1+22= 25
2) (23.160 Поляков К.Ю.) Логик тэгшитгэлийн систем хэдэн өөр шийдэлтэй вэ?
(х 1 (х 2 y 2 )) (ж 1 y 2 ) = 1
(х 2 (х 3 y 3 )) (ж 2 y 3 ) = 1
...
( x 6 ( x 7 y 7 )) ( y 6 y 7 ) = 1
x 7 y 7 = 1
Шийдэл. 1) Тэгшитгэлүүд нь ижил төрлийнх тул үндэслэлийг ашиглан эхний тэгшитгэлийн бүх боломжит хосуудыг (x1,y1), (x2,y2) олох болно.
(x1 (x2 y2 ))=1
(y1 y2 ) = 1
Хоёр дахь тэгшитгэлийн шийдэл нь (00), (01), (11) хосууд юм.
Эхний тэгшитгэлийн шийдлүүдийг олцгооё. Хэрэв x1=0 бол x2, y2 - дурын, хэрэв x1=1 бол x2, y2 нь (11) утгыг авна.
(x1, y1) болон (x2, y2) хосуудын хооронд холболт хийцгээе.
| (x1 , y1 ) | (x2 , y2 ) |
Үе шат бүрт хосуудын тоог тооцоолох хүснэгтийг үүсгэцгээе.
| 0 |
|||||||
Сүүлийн тэгшитгэлийн шийдлүүдийг харгалзан үзэх x 7 y 7 = 1, (10) хосыг хасъя. Бид олдог нийт тоошийдлүүд 1+7+0+34=42
3)(23.180) Логик тэгшитгэлийн систем хэдэн өөр шийдэлтэй вэ?
(x1 x2 ) (x3 x4 ) = 1
(x3 x4 ) (x5 x6 ) = 1
(x5 x6 ) (x7 x8 ) = 1
(x7 x8 ) (x9 x10 ) = 1
x1 x3 x5 x7 x9 = 1
Шийдэл. 1) Тэгшитгэлүүд нь ижил төрлийнх тул үндэслэлийг ашиглан эхний тэгшитгэлийн бүх боломжит хосуудыг (x1,x2), (x3,x4) олох болно.
(x1 x2 ) (x3 x4 ) = 1
Дараалалд 0 (1 0) өгдөг хосуудыг шийдээс хасъя, эдгээр нь (01, 00, 11) ба (10) хосууд юм.
(x1,x2), (x3,x4) хосуудын хооронд холболт хийцгээе.
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
Дараах тэгшитгэлийн систем хэдэн шийдэлтэй вэ?
Энэхүү материал нь компьютерийн шинжлэх ухааны улсын нэгдсэн шалгалтын В15 (2015 оны № 23) даалгаварт логик тэгшитгэл, логик тэгшитгэлийн системийг шийдвэрлэх аргуудыг харуулсан танилцуулгыг агуулдаг. Энэ даалгавар нь Улсын нэгдсэн шалгалтын даалгавруудын дунд хамгийн хэцүү нь гэдгийг мэддэг. Энэхүү танилцуулга нь төрөлжсөн ангиудад "Логик" сэдвээр хичээл заахад, мөн улсын нэгдсэн шалгалтанд бэлтгэхэд хэрэг болно.
Татаж авах:
Урьдчилан үзэх:
Үзүүлэнг урьдчилан үзэхийг ашиглахын тулд өөртөө бүртгэл үүсгэнэ үү ( данс) Google болон нэвтэрнэ үү: https://accounts.google.com
Слайдын тайлбар:
В15 даалгаврын шийдэл (логик тэгшитгэлийн системүүд) Вишневская М.П., МАОУ “Гимнази №3” 2013 оны 11-р сарын 18, Саратов.
В15 даалгавар бол компьютерийн шинжлэх ухааны улсын нэгдсэн шалгалтын хамгийн хэцүү даалгавар юм!!! Дараах ур чадваруудыг шалгана: логик хувьсагч агуулсан илэрхийллийг хөрвүүлэх; өгөгдсөн логик хувьсагчийн багц үнэн болох логик хувьсагчийн утгуудын багцыг байгалийн хэлээр тайлбарлах; Өгөгдсөн нөхцөлийг хангасан хоёртын олонлогийн тоог тоол. Хамгийн хэцүү зүйл бол... Үүнийг хэрхэн хийх талаар албан ёсны дүрэм байхгүй, энэ нь таавар шаарддаг.
Та юугүйгээр хийж чадахгүй вэ!
Та юугүйгээр хийж чадахгүй вэ!
Тэмдгийн холболт: A /\ B , A B , AB , A &B, A and B disjunction: A \ / B , A + B , A | B , A эсвэл B үгүйсгэх: A , A, A биш эквивалент: A B, A B, A B онцгой “эсвэл”: A B , A xor B
Хувьсагчийг солих арга: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5) ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ¬(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\'(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Хариулт нь x1, x2, …, x9, x10 гэсэн бүх өөр олонлогуудыг жагсаах шаардлагагүй. Энэ тэгш байдлын тогтолцоо бий. Хариулт нь та ийм багцын тоог зааж өгөх ёстой (демо хувилбар 2012)
Шийдлийн алхам 1. t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 хувьсагчдыг өөрчлөх замаар хялбарчлах: (t1 \/ t2) /\ (¬t1 \/ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬ t4 \/ ¬ t5) =1 Тэгшитгэлийн аль нэгийг авч үзье: (t1 \/ t2) /\ (¬t1 \/¬ t2) =1 Мэдээжийн хэрэг, хувьсагчийн аль нэг нь 0, нөгөө нь 1 байвал энэ нь =1 байх нь ойлгомжтой. XOR үйлдлийг холбогч ба дизьюнкцээр илэрхийлэх томъёог ашиглая: (t1 \/ t2) /\ (¬t1 \/¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Алхам 2. Системийн шинжилгээ ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 01 .Хэнд. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), тэгвэл tk-ийн утга бүр нь x2k-1 ба x2k гэсэн хоёр хос утгатай тохирч байна, жишээлбэл: tk =0 нь хоёр хостой тохирч байна - (0) ,1) ба (1, 0) , мөн tk =1 – хос (0,0) ба (1,1).
Алхам 3. Шийдлийн тоог тоолж байна. t тус бүр 2 шийдэлтэй, ts-ийн тоо 5. Тиймээс. t хувьсагчдын хувьд 2 5 = 32 шийдэл байна. Гэхдээ t бүрийн хувьд x шийдлийн хос тохирно, өөрөөр хэлбэл. анхны систем нь 2*32 = 64 шийдэлтэй. Хариулт: 64
Шийдлийн зарим хэсгийг арилгах арга. Доор жагсаасан бүх нөхцлийг хангасан x1, x2, ..., x5, y1,y2,..., y5 логик хувьсагчдын утгын хэдэн багц байдаг вэ: (x1→ x2) )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. Хариулт нь энэ тэгш байдлын системд хамаарах x1, x2, ..., x5, y 1, y2, ... , y5 олонлогуудыг жагсаах шаардлагагүй. Хариулт нь ийм багцын тоог зааж өгөх ёстой.
Шийдэл. 1-р алхам. Тэгшитгэлийн дараалсан шийдэл x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Эхний тэгшитгэл нь 1-тэй тэнцүү хэд хэдэн далд үйлдлүүдийн нэгдэл юм. үр дагавар бүр нь үнэн юм. 1 0 тохиолдолд бусад бүх тохиолдолд (0 0, 0 1, 1 1) үйлдэл 1-ийг буцаана. Үүнийг хүснэгт хэлбэрээр бичье.
1-р алхам. Тэгшитгэлийн дараалсан шийдэл T.o. x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111) -ийн 6 багц уусмалыг авсан. Үүнтэй адил үндэслэлээр бид y1, y2, y3, y4, y5-ийн хувьд ижил шийдлүүд байна гэсэн дүгнэлтэд хүрнэ. Учир нь эдгээр тэгшитгэлүүд нь бие даасан, өөрөөр хэлбэл. Тэдэнд нийтлэг хувьсагч байхгүй бол энэ тэгшитгэлийн системийн шийдэл (гурав дахь тэгшитгэлийг тооцохгүйгээр) 6 * 6 = 36 хос "X" ба "Y" болно. Гурав дахь тэгшитгэлийг авч үзье: y5→ x5 =1 Шийдэл нь хосууд: 0 0 0 1 1 1 Хос нь шийдэл биш: 1 0
y5 =1, x5=0 тохиромжгүй тохиолдолд олж авсан шийдлүүдийг харьцуулж үзье. Ийм 5 хос системтэй шийдлийн тоо: 36-5= 31. Хариулт: 31 Комбинаторик хэрэгтэй байсан!!!
Динамик програмчлалын арга x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 логик тэгшитгэл нь хэдэн өөр шийдэлтэй вэ, энд x 1, x 2, …, x 6 нь логик хувьсагч юм? Хариулт нь энэ тэгш байдлыг хангах хувьсагчийн утгуудын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын хэмжээг зааж өгөх хэрэгтэй.
Шийдэл 1. Нөхцөл байдлын шинжилгээ Тэгшитгэлийн зүүн талд далд үйлдлүүд дарааллаар бичигдсэн бөгөөд тэргүүлэх чиглэл нь ижил байна. Дахин бичье: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Дараагийн хувьсагч бүр өмнөхөөсөө хамаарахгүй, харин өмнөх нөлөөллийн үр дүнгээс хамаарна!
Алхам 2. Загварыг илчлэх нь X 1 → X 2 гэсэн эхний санааг авч үзье. Үнэний хүснэгт: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 0-ээс бид 2 нэгж, 1-ээс авсан. Бид нэг 0, нэг 1 авсан. Зөвхөн нэг 0, гурван 1 байна, энэ бол эхний үйлдлийн үр дүн юм.
Алхам 2. Загварыг илчлэх Анхны үйлдлийн үр дүнд x 3-ыг холбосноор бид дараахийг олж авна: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Хоёр 0-оос хоёр 1, тус бүрээс 1 (3 байгаа) нэг 0, нэг 1 (3+3)
Алхам 3. Томьёог гарган авах T.o. i хувьсагчтай тэгшитгэлийн хувьд N i тэгийн тоо ба нэгийн тоог E i тооцоолох томъёог үүсгэж болно: ,
Алхам 4. Хүснэгтийг бөглөх Хүснэгтийг зүүнээс баруун тийш i = 6-д зориулж, тэг болон нэгийн тоог дээрх томьёог ашиглан тооцоолж бичье; Хүснэгтэд өмнөх баганаас дараагийн багана хэрхэн бүтээгдсэнийг харуулав: хувьсагчийн тоо 1 2 3 4 5 6 Тэгийн тоо N i 1 1 3 5 11 21 Нэгийн тоо E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Хариулт: 43
Логик хэллэгийг хялбарчлах арга.Тэгшитгэл нь хэдэн өөр шийдэлтэй вэ ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 энд J, K, L, M, N нь логик хувьсагч вэ? Хариулт нь J, K, L, M, N-ийн өөр өөр утгуудыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын тоог зааж өгөх хэрэгтэй.
Шийдэл J → K = ¬ J K гэдгийг анхаарна уу. Хувьсагчийн өөрчлөлтийг оруулъя: J → K=A, M N L =B Өөрчлөлтийг харгалзан тэгшитгэлийг дахин бичье: (A → B) (B →) A) (M → J)=1 4. (A B) (M → J)= 1 5. Мэдээжийн хэрэг, A B үед ижил утгатайА ба В 6. Сүүлчийн утга санааг авч үзье M → J =1 Энэ нь дараах тохиолдолд боломжтой: M=J=0 M=0, J=1 M=J=1
Шийдэл Учир нь A B, дараа нь M=J=0 үед бид 1 + K=0 болно. Шийдэл байхгүй. M=0, J=1 үед бид 0 + K=0, K=0, N ба L нь дурын 4 шийд гарна: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1
Шийдэл 10. M=J=1 үед 0+K=1 *N * L, эсвэл K=N*L, 4 шийд гарна: 11. Нийт 4+4=8 шийдэлтэй Хариу: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1
Мэдээллийн эх сурвалж: О.Б. Богомолова, Д.Ю. Усенков. В15: шинэ даалгавар, шинэ шийдэл // Мэдээлэл зүй, № 6, 2012, х. 35 – 39. К.Ю. Поляков. Логик тэгшитгэл // Мэдээлэл зүй, No14, 2011, х. 30-35. http://ege-go.ru/zadania/grb/b15/, [Цахим нөөц]. http://kpolyakov.narod.ru/school/ege.htm, [Цахим нөөц].