Логик тэгшитгэлийн системийг шийдвэрлэх арга. Логик. Логик функцууд. Тэгшитгэл шийдвэрлэх

Системийг шийдвэрлэх аргууд логик тэгшитгэл

Киргизова Е.В., Немкова А.Е.

Лесосибирскийн сурган хүмүүжүүлэх дээд сургууль -

ОХУ-ын Сибирийн Холбооны Их Сургуулийн салбар

Тогтвортой сэтгэх, үнэмшилтэй үндэслэл гаргах, таамаглал дэвшүүлэх, сөрөг дүгнэлтийг няцаах чадварыг логикийн шинжлэх ухаан өөрөө бий болгодоггүй; Логик бол бусад мэдэгдлийн үнэн эсвэл худал дээр үндэслэн зарим мэдэгдлийн үнэн эсвэл худал байдлыг тогтоох аргуудыг судалдаг шинжлэх ухаан юм.

Энэ шинжлэх ухааны үндсийг эзэмших нь логик асуудлыг шийдэхгүйгээр боломжгүй юм. Мэдлэгээ шинэ нөхцөл байдалд ашиглах чадварыг хөгжүүлэх туршилтыг дамжих замаар явуулдаг. Ялангуяа энэ бол шийдэх чадвар юм логик асуудлууд. Улсын нэгдсэн шалгалтын В15 даалгаврууд нь логик тэгшитгэлийн системийг агуулдаг тул нарийн төвөгтэй ажил юм. Та сонгож болно янз бүрийн арга замуудлогик тэгшитгэлийн системийг шийдвэрлэх. Энэ нь нэг тэгшитгэл болгон бууруулах, үнэний хүснэгт байгуулах, задлах, тэгшитгэлийн дараалсан шийдэл гэх мэт.

Даалгавар:Логик тэгшитгэлийн системийг шийд:

Ингээд авч үзье нэг тэгшитгэл болгон бууруулах арга . Энэ арга нь логик тэгшитгэлийг баруун гар тал нь үнэний утгатай (өөрөөр хэлбэл 1) тэнцүү байхаар хувиргах явдал юм. Үүнийг хийхийн тулд логик үгүйсгэх үйлдлийг ашиглана. Дараа нь тэгшитгэлүүд нь нарийн төвөгтэй логик үйлдлүүдийг агуулж байвал бид тэдгээрийг үндсэн зүйлээр солино: "AND", "OR", "NOT". Дараагийн алхам бол "AND" логик үйлдлийг ашиглан тэгшитгэлүүдийг системтэй тэнцэх нэг болгон нэгтгэх явдал юм. Үүний дараа та логик алгебрийн хуулиуд дээр үндэслэн үүссэн тэгшитгэлийг хувиргаж, системийн тодорхой шийдлийг олж авах хэрэгтэй.

Шийдэл 1:Эхний тэгшитгэлийн хоёр талд урвуу хамаарлыг хэрэглэнэ.

"OR" ба "NOT" гэсэн үндсэн үйлдлүүдийн үр дагаврыг төсөөлье.

Тэгшитгэлийн зүүн тал нь 1-тэй тэнцүү тул бид тэдгээрийг "AND" үйлдлийг ашиглан анхны системтэй тэнцэх нэг тэгшитгэл болгон нэгтгэж болно.

Бид Де Морганы хуулийн дагуу эхний хаалтыг нээж, олж авсан үр дүнг хувиргана.

Үүссэн тэгшитгэл нь нэг шийдэлтэй байна: A= 0, B =0 ба C =1.

Дараагийн арга бол үнэний хүснэгт байгуулах . Логик хэмжигдэхүүн нь зөвхөн хоёр утгатай байдаг тул та бүх хувилбаруудыг үзэж, тэдгээрийн дундаас өгөгдсөн тэгшитгэлийн систем хангагдсаныг олох боломжтой. Өөрөөр хэлбэл, бид системийн бүх тэгшитгэлийн хувьд нэг нийтлэг үнэний хүснэгтийг байгуулж, шаардлагатай утгууд бүхий шугамыг олно.

Шийдэл 2:Системийн үнэний хүснэгтийг байгуулъя:

Даалгаврын нөхцөл хангагдсан мөрийг тодоор тэмдэглэнэ. Тэгэхээр A =0, B =0, C =1.

Арга зам задрал . Гол санаа нь нэг хувьсагчийн утгыг засах (үүнийг 0 эсвэл 1-тэй тэнцүүлэх) бөгөөд ингэснээр тэгшитгэлийг хялбарчлах явдал юм. Дараа нь та хоёр дахь хувьсагчийн утгыг засах боломжтой, гэх мэт.

Шийдэл 3:Болъё A = 0, тэгвэл:

Эхний тэгшитгэлээс бид олж авдагБ =0, хоёр дахь нь - C=1. Системийн шийдэл: A = 0, B = 0 ба C = 1.

Та мөн аргыг ашиглаж болно тэгшитгэлийн дараалсан шийдэл , алхам бүр дээр авч үзэж буй олонлогт нэг хувьсагчийг нэмнэ. Үүнийг хийхийн тулд хувьсагчдыг цагаан толгойн үсгийн дарааллаар оруулахын тулд тэгшитгэлийг хувиргах шаардлагатай. Дараа нь бид шийдвэрийн модыг бий болгож, түүнд хувьсагчдыг дараалан нэмнэ.

Системийн эхний тэгшитгэл нь зөвхөн А ба В-ээс, хоёр дахь тэгшитгэл нь А ба С-ээс хамаарна. А хувьсагч нь 0 ба 1 гэсэн 2 утгыг авч болно:

Эхний тэгшитгэлээс энэ нь дараах байдалтай байна , тийм үед A = 0, бид B = 0, A = 1-ийн хувьд B = 1 байна. Тиймээс эхний тэгшитгэл нь A ба B хувьсагчтай холбоотой хоёр шийдэлтэй байна.

Хоёрдахь тэгшитгэлийг дүрсэлж, сонголт бүрийн хувьд C-ийн утгыг тодорхойлно. A =1 үед далд утга нь худал байж болохгүй, өөрөөр хэлбэл модны хоёр дахь мөчир шийдэлгүй болно. At A= 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. Тиймээс (1; 1; …; 1) олонлогм нэгж нь системийн шийдэл юм. Одоо больёx 1 =0, тэгвэл эхний тэгшитгэлээс бид байнаx 2 =0 эсвэл x 2 =1.

Хэзээ x 2 үнэн бол бид үлдсэн хувьсагчид нь үнэн, өөрөөр хэлбэл олонлог (0; 1; ...; 1) нь системийн шийдэл гэдгийг олж авна. Atx 2 =0 бид үүнийг ойлгож байна x 3 =0 эсвэл x 3 = гэх мэт. Сүүлчийн хувьсагчийг үргэлжлүүлбэл тэгшитгэлийн шийдлүүд нь дараах хувьсагчдын багц болохыг олж мэдэв (м Уусмал бүрт +1 уусмалм хувьсах утгууд):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Энэ аргыг хоёртын мод байгуулах замаар сайн тайлбарласан болно. Боломжит шийдлүүдийн тоо нь барьсан модны янз бүрийн салбаруудын тоо юм. Энэ нь тэнцүү гэдгийг харахад хялбар байдагм +1.

Шийдвэрлэх, шийдвэрийн модыг бий болгоход бэрхшээлтэй байгаа тохиолдолд та үүнийг ашиглан шийдлийг хайж болно үнэний хүснэгтүүд, нэг эсвэл хоёр тэгшитгэлийн хувьд.

Тэгшитгэлийн системийг дараах хэлбэрээр дахин бичье.

Нэг тэгшитгэлийн хувьд үнэний хүснэгтийг тусад нь байгуулъя:

Хоёр тэгшитгэлийн үнэний хүснэгтийг байгуулъя:

Дараа нь (0; 0), (0; 1), (1; 1) гэсэн гурван тохиолдолд нэг тэгшитгэл үнэн болохыг харж болно. Хоёр тэгшитгэлийн систем нь дөрвөн тохиолдолд (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1) үнэн байдаг. Энэ тохиолдолд зөвхөн тэг ба түүнээс дээш тооноос бүрдэх шийдэл байгаа нь шууд тодорхой болно м-ээс эхлэн нэг удаад нэг нэгж нэмэгдэх шийдлүүд сүүлчийн байрлалболомжтой бүх газрыг дүүргэх хүртэл. Ийм гэж таамаглаж болно нийтлэг шийдвэрижил хэлбэртэй байх боловч энэ арга нь шийдэл болохын тулд таамаглал үнэн болохыг нотлох шаардлагатай.

Дээр дурдсан бүх зүйлийг нэгтгэн дүгнэхийн тулд хэлэлцсэн бүх аргууд нь бүх нийтийнх биш гэдгийг би та бүхний анхаарлыг татахыг хүсч байна. Логик тэгшитгэлийн систем бүрийг шийдвэрлэхдээ түүний онцлогийг харгалзан үзэх шаардлагатай бөгөөд үүний үндсэн дээр шийдлийн аргыг сонгох хэрэгтэй.

Уран зохиол:

1. Логик асуудлууд / O.B. Богомолов - 2-р хэвлэл. – М.: БИНОМ. Мэдлэгийн лаборатори, 2006. – 271 х.: өвчтэй.

2. Поляков К.Ю. Логик тэгшитгэлийн системүүд / Информатикийн багш нарт зориулсан сургалт, арга зүйн сонин: Информатик 2011 оны №14.

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) нь 01, 11, 10-тай тэнцүү байх гурван тохиолдолд илэрхийлэл үнэн байна.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N нь 1-тэй тэнцүү, K ба L нь нэгэн зэрэг 1-ээс бусад бүх зүйл. Тиймээс 3 шийдэл байна.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 уусмал.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 шийдэл.

Хариулт: 7.

Хариулт: 7

Тэгшитгэл хэдэн өөр шийдэлтэй вэ?

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0

X, Y, Z, P нь логик хувьсагч юм уу? Хариулт нь энэ тэгш байдлыг хангасан бүх өөр өөр утгыг жагсаах шаардлагагүй. Хариулт нь та зөвхөн ийм багцын тоог зааж өгөх хэрэгтэй.

Тайлбар.

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логик OR нь зөвхөн нэг тохиолдолд худал болно: хоёр илэрхийлэл худал үед.

Тиймээс,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Тиймээс тэгшитгэлийн цорын ганц шийдэл байна.

Хариулт: 1

Тэгшитгэл хэдэн өөр шийдэлтэй вэ?

(K ∨ L) ∧ (M ∨ N) = 1

Энд K, L, M, N логик хувьсагчууд вэ? Хариулт нь энэ тэгш байдлыг хангах K, L, M ба N утгуудын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та зөвхөн ийм багцын тоог зааж өгөх хэрэгтэй.

Тайлбар.

Логик Мөн зөвхөн нэг тохиолдолд үнэн болно: бүх илэрхийлэл үнэн байх үед.

K ∨ L = 1, M ∨ N = 1.

Тэгшитгэл бүр нь 3 шийдлийг өгдөг.

Хэрэв A болон B хоёулаа зөвшөөрвөл A ∧ B = 1 тэгшитгэлийг авч үзье жинхэнэ үнэт зүйлстус бүр гурван тохиолдолд, дараа нь тэгшитгэл нь нийт 9 шийдэлтэй байна.

Тиймээс хариулт нь 9.

Хариулт: 9

Тэгшитгэл хэдэн өөр шийдэлтэй вэ?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

Энд A, B, C, D нь логик хувьсагчууд вэ?

Хариулт нь энэ тэгш байдлыг хангасан A, B, C, D утгын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та ийм багцын тоог зааж өгөх хэрэгтэй.

Тайлбар.

Логик "OR" нь хамгийн багадаа нэг нь үнэн байвал үнэн болно.

(D ∧ ¬D)= дурын D хувьд 0.

Тиймээс,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1 бөгөөд энэ нь D тус бүрийн 3 боломжит шийдлийг бидэнд өгдөг.

(D ∧ ¬ D)= 0 ямар ч D-ийн хувьд энэ нь бидэнд хоёр шийдлийг өгдөг (D = 1, D = 0).

Тиймээс: нийт шийдлүүд 2*3 = 6.

Нийт 6 шийдэл.

Хариулт: 6

Тэгшитгэл хэдэн өөр шийдэлтэй вэ?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

Энд K, L, M, N логик хувьсагчууд вэ? Хариулт нь энэ тэгш байдлыг хангах K, L, M ба N утгуудын бүх багцыг жагсаах шаардлагагүй. Хариулт нь та зөвхөн ийм багцын тоог зааж өгөх хэрэгтэй.

Тайлбар.

Тэгшитгэлийн хоёр талд үгүйсгэлийг хэрэглэцгээе.

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Гурван тохиолдолд логик OR үнэн байна.

Сонголт 1.

K ∧ L ∧ M = 1, дараа нь K, L, M = 1, ¬L ∧ M ∧ N = 0. N нь дурын, өөрөөр хэлбэл 2 шийдэл.

Сонголт 2.

¬L ∧ M ∧ N = 1, дараа нь N, M = 1; L = 0, K ямар ч, өөрөөр хэлбэл 2 шийдэл.

Тиймээс хариулт нь 4.

Хариулт: 4

A, B, C нь мэдэгдэл үнэн байх бүхэл тоо юм

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

A = 45, C = 43 бол B нь хэдтэй тэнцүү вэ?

Тайлбар.

1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);

2) эдгээр энгийн мэдэгдлүүд нь ∧ (AND, холболт) үйлдлээр холбогдсон, өөрөөр хэлбэл тэдгээрийг нэгэн зэрэг гүйцэтгэх ёстой;

3) ¬(A = B)=1-ээс A B гэсэн шууд гарч ирнэ;

4) A > B гэж бодъё, тэгвэл хоёр дахь нөхцлөөс бид 1→(B > C)=1 болно; B > C = 1 тохиолдолд энэ илэрхийлэл үнэн байж болно;

5) тиймээс бидэнд A > B > C байна, зөвхөн 44 тоо энэ нөхцөлтэй тохирч байна;

6) ямар ч тохиолдолд A 0 →(B > C)=1 сонголтыг шалгая;

энэ илэрхийлэл нь ямар ч B-д үнэн; Одоо бидний олж авсан гурав дахь нөхцөлийг хар

Энэ илэрхийлэл нь зөвхөн C > B тохиолдолд л үнэн байж болох бөгөөд энд бид зөрчилтэй байна, учир нь C > B > A гэсэн B тоо байхгүй.

Хариулт: 44.

Хариулт: 44

Логик функцийн үнэний хүснэгтийг байгуул

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

Үүнд А аргументын утгын багана нь 27 тооны хоёртын дүрслэл, В аргументын утгын багана нь 77 тоо, С аргументын утгын багана нь 120 тоо байна. Тоо баганад хамгийн чухалаас хамгийн бага ач холбогдол бүхий (тэг багцыг оруулаад) дээрээс доошоо бичнэ. Үүссэн X функцийн утгуудын хоёртын дүрслэлийг аравтын бутархай тооллын системд хөрвүүлнэ.

Тайлбар.

Үйлдлийн энгийн тэмдэглэгээг ашиглан тэгшитгэлийг бичье.

1) энэ нь гурван хувьсагчтай илэрхийлэл тул үнэний хүснэгтэд мөрүүд байх болно; тиймээс хүснэгтийн A, B, C багануудыг байгуулахад ашигласан тоонуудын хоёртын дүрслэл нь 8 цифрээс бүрдэх ёстой.

2) 27, 77, 120 тоонуудыг хоёртын систем болгон хувиргаж, тоонуудын эхэнд 8 хүртэлх тооны тэгийг нэн даруй нэмнэ.

3) та хослол бүрийн хувьд X функцийн утгыг шууд бичих боломжгүй тул завсрын үр дүнг тооцоолохын тулд хүснэгтэд нэмэлт багана нэмэх нь тохиромжтой (доорх хүснэгтийг үзнэ үү)

4) хүснэгтийн баганыг бөглөнө үү:

утга нь зөвхөн A = B гэсэн мөрөнд 1 байна

B эсвэл C = 1 гэсэн мөрөнд утга нь 1 байна

утга нь зөвхөн A = 1 ба B + C = 0 байгаа мөрөнд 0 байна

утга нь өмнөх баганын урвуу утгатай (0-ийг 1-ээр, 1-ийг 0-ээр сольсон)

X-ийн үр дүн (сүүлийн багана) нь хоёр баганын логик нийлбэр ба

5) хариултыг авахын тулд X баганаас дээрээс доош битүүдийг бичнэ үү.

6) энэ тоог аравтын бутархай систем рүү хөрвүүлнэ:

Хариулт: 171

(10 (X+1)·(X+2)) мэдэгдэл үнэн байх хамгийн том бүхэл X хэд вэ?

Тайлбар.

Тэгшитгэл нь хоёр харилцааны хоорондын хамаарлын үйлдэл юм:

1) Мэдээжийн хэрэг, энд та жишээ 2208-тай ижил аргыг хэрэглэж болно, гэхдээ та шийдэх хэрэгтэй болно. квадрат тэгшитгэл(Би хүсэхгүй байна…);

2) Нөхцөлөөр бид зөвхөн бүхэл тоонуудыг сонирхож байгаа тул эх илэрхийлэлийг ямар нэгэн байдлаар хувиргаж, ижил утгатай мэдэгдлийг олж авах боломжтой гэдгийг анхаарна уу ( тодорхой утгуудБид үндсийг огт сонирхдоггүй!);

3) Тэгш бус байдлыг авч үзье: мэдээжийн хэрэг, энэ нь эерэг эсвэл сөрөг тоо байж болно;

4) Домэйн дэх мэдэгдэл нь бүх бүхэл тоонуудын хувьд үнэн эсэхийг шалгахад хялбар бөгөөд домэйнд - бүх бүхэл тоонуудын хувьд (андуурахгүйн тулд хатуу бус тэгш бус байдлыг ашиглах нь илүү тохиромжтой. ба );

5) Тиймээс бүхэл тоонуудын хувьд үүнийг эквивалент илэрхийллээр сольж болно

6) илэрхийллийн үнэний талбар нь хоёр хязгааргүй интервалын нэгдэл юм;

7) Одоо хоёр дахь тэгш бус байдлыг авч үзье: энэ нь эерэг эсвэл сөрөг тоо байж болох нь ойлгомжтой;

8) Бүс нутагт мэдэгдэл нь бүх бүхэл тоонд үнэн, бүс нутагт - бүх бүхэл тоонд үнэн байдаг тул бүхэл тоонуудын хувьд үүнийг тэнцүү илэрхийллээр сольж болно.

9) илэрхийллийн үнэний талбар нь хаалттай интервал юм;

10) Өгөгдсөн илэрхийлэл нь ба гэсэн хэсгүүдээс бусад газарт үнэн байна;

11) Утга нь тохирохгүй болсныг анхаарна уу, учир нь тэнд ба , өөрөөр хэлбэл 0-ийг өгдөг;

12) Нөхцөлийг хангасан 2, (10 (2+1) · (2+2)), эсвэл 0 → 0-ийг орлуулах үед.

Тэгэхээр хариулт нь 2.

Хариулт: 2

Энэ мэдэгдэл үнэн байх хамгийн том бүхэл X хэд вэ?

(50 (X+1)·(X+1))?

Тайлбар.

Дуудлагын хувиргалтыг хэрэглэж, илэрхийллийг хувиргацгаая:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логик OR нь ядаж нэг логик хэллэг үнэн байвал үнэн байна. Тэгш бус байдлын аль алиныг нь шийдэж, тэдгээрийн дор хаяж нэг нь хангагдсан хамгийн том бүхэл тоо нь 7 байгааг харж байна (зураг дээр хоёр дахь тэгш бус байдлын эерэг шийдийг шараар, эхнийх нь цэнхэр өнгөөр ​​харуулсан).

Хариулт: 7

Логик илэрхийлэл болох K, L, M, N хувьсагчдын утгыг зааж өгнө үү

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

худлаа. Хариултаа 4 тэмдэгтийн мөр болгон бичнэ үү: K, L, M, N хувьсагчдын утгууд (энэ дарааллаар). Жишээлбэл, 1101-р мөр нь K=1, L=1, M=0, N=1 гэсэн утгатай тохирч байна.

Тайлбар.

3584-р даалгаврыг давхардуулж байна.

Хариулт: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Тайлбар.

Дуудлагын хувиргалтыг хэрэгжүүлье:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Тэгшитгэлийн хоёр талд үгүйсгэлийг хэрэглэцгээе.

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Өөрчлүүлье:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Тиймээс, M = 0, N = 0, одоо (¬K ∧ L ∨ M ∧ L) авч үзье.

M = 0, N = 0 гэсэн баримтаас M ∧ L = 0, дараа нь ¬K ∧ L = 1, өөрөөр хэлбэл K = 0, L = 1 байна.

Хариулт: 0100

Логик илэрхийлэл болох K, L, M, N хувьсагчдын утгыг зааж өгнө үү

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

худлаа. Хариултаа дөрвөн тэмдэгтийн мөр болгон бичнэ үү: K, L, M, N хувьсагчдын утгууд (энэ дарааллаар). Жишээлбэл, 1101-р мөр нь K=1, L=1, M=0, N=1 гэсэн утгатай тохирч байна.

Тайлбар.

Үйлдлийн энгийн тэмдэглэгээг ашиглан тэгшитгэлийг бичье ("илэрхийлэл худал" гэсэн нөхцөл нь логик тэгтэй тэнцүү гэсэн үг):

1) нөхцөлийг томъёолсноор илэрхийлэл нь зөвхөн нэг багц хувьсагчийн хувьд худал байх ёстой.

2) "дүр дагавар" үйл ажиллагааны үнэний хүснэгтээс энэ илэрхийлэл нь зөвхөн нэгэн зэрэг худал болохыг харуулж байна.

3) эхний тэгш байдал (логик үржвэр нь 1-тэй тэнцүү) зөвхөн ба тохиолдолд л хангагдсан; үүнээс үүдэн гарч ирдэг (логик нийлбэр нь тэгтэй тэнцүү), энэ нь зөвхөн үед л тохиолдож болно; Тиймээс бид гурван хувьсагчийг аль хэдийн тодорхойлсон

4) хоёр дахь нөхцлөөс, , for болон бид .

Даалгаврыг давхардуулдаг

Хариулт: 1000

Логик илэрхийлэл болох P, Q, S, T логик хувьсагчдын утгыг зааж өгнө үү

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) нь худал.

Хариултыг дөрвөн тэмдэгтийн мөр болгон бичнэ үү: P, Q, S, T хувьсагчдын утгууд (энэ дарааллаар).

Тайлбар.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ T)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Импликацын хувиргалтыг хэрэгжүүлье:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Хариулт: 0100

Логик илэрхийлэл болох K, L, M, N хувьсагчдын утгыг зааж өгнө үү

(K → M) ∨ (L ∧ K) ∨ ¬N

худлаа. Хариултаа дөрвөн тэмдэгтийн мөр болгон бичнэ үү: K, L, M, N хувьсагчдын утгууд (энэ дарааллаар). Жишээлбэл, 1101-р мөр нь K=1, L=1, M=0, N=1 гэсэн утгатай тохирч байна.

Тайлбар.

Логик OR нь хоёр мэдэгдэл худал байвал худал болно.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Эхний илэрхийлэлд далд хувиргалтыг хэрэгжүүлье:

¬K ∨ M = 0 => K = 1, M = 0.

Хоёр дахь илэрхийлэлийг авч үзье:

(L ∧ K) ∨ ¬N = 0 (эхний илэрхийллийн үр дүнг харна уу) => L ∨ ¬N = 0 => L = 0, N = 1.

Хариулт: 1001.

Хариулт: 1001

Логик илэрхийлэл болох K, L, M, N хувьсагчдын утгыг зааж өгнө үү

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

үнэн. Хариултаа дөрвөн тэмдэгтийн мөр болгон бичнэ үү: K, L, M, N хувьсагчдын утгууд (энэ дарааллаар). Жишээлбэл, 1101-р мөр нь K=1, L=1, M=0, N=1 гэсэн утгатай тохирч байна.

Тайлбар.

Логик "AND" нь үнэн бөгөөд хэрэв хоёр мэдэгдэл үнэн бол л үнэн болно.

1) (K → M) = 1 Доорын хувиргалтыг хэрэгжүүл: ¬K ∨ M = 1

2) (K → ¬M) = 1 Импликацын хувиргалтыг хэрэгжүүл: ¬K ∨ ¬M = 1

Эндээс K = 0 байна.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Доорын хувиргалтыг хэрэгжүүл: K ∨ (M ∧ ¬L ∧ N) = 1 K = 0 гэсэн баримтаас бид дараахь зүйлийг олж авна.

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Хариулт: 0011

X, Y, Z бүхэл тоонуудын хувьд дараах мэдэгдэл үнэн болох нь мэдэгдэж байна.

(Z X=25, Y=48 бол Z хэдтэй тэнцүү вэ?

Тайлбар.

Тоонуудыг орлуулсны дараа бид Z = 47 болно.

Энэхүү нарийн төвөгтэй мэдэгдэл нь гурван энгийн мэдэгдлээс бүрддэг болохыг анхаарна уу

1) (Z 2) эдгээр энгийн хэллэгүүд нь ∧ (AND, холболт) үйлдлээр холбогдсон, өөрөөр хэлбэл тэдгээрийг нэгэн зэрэг гүйцэтгэх ёстой.

3) ¬(Z+1 24, ¬(Z+1 47)-аас.

4) -аас (Z Z Хариулт: 47.

Хариулт: 47

A, B, C нь бүхэл тоонуудын хувьд дараах мэдэгдэл үнэн байна.

(C A=45, B=18 бол C-ийн утга хэд вэ?

Тайлбар.

Логик "AND" нь үнэн бөгөөд хэрэв хоёр мэдэгдэл үнэн бол л үнэн болно.

Илэрхийлэлд тоонуудыг орлъё:

1) (C (C 2) ¬(C+1, C ≥ 44).

3) ¬(C+1, C ≥ 17.

2) ба 1)-ээс харахад C

Хариулт: 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

C = 8, B = 18 бол А-ийн утга хэд вэ?

Тайлбар.

Логик "AND" нь үнэн бөгөөд хэрэв хоёр мэдэгдэл үнэн бол л үнэн болно.

1) ¬(A = B) = 1, өөрөөр хэлбэл, A ≠ 18 = 1.

2) ((B A)) Дуудлагын хувиргалтыг хэрэгжүүл: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Дуудлагын хувиргалтыг хэрэгжүүл: (A > 18) ∨ (A > 16) = 1

2) ба 3)-аас (18 > A) ба (A > 16) гэсэн үг, өөрөөр хэлбэл зөрчил үүснэ: A = 17.

Хариулт: 17

A, B, C нь мэдэгдэл үнэн байх бүхэл тоо юм

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

A = 45, C = 18 бол В-ийн утга хэд вэ?

Тайлбар.

Логик "AND" нь зөвхөн бүх мэдэгдэл үнэн байвал үнэн болно.

n хувьсагчийн логик функц байг. Логик тэгшитгэл нь дараах байдалтай байна.

Тогтмол С нь 1 эсвэл 0 утгатай байна.

Логик тэгшитгэл нь 0-ээс өөр шийдэлтэй байж болно. Хэрэв C нь 1-тэй тэнцүү бол F функц нь үнэн (1) утгыг авдаг үнэний хүснэгтээс бүх хувьсагчдын багц шийдэл болно. Үлдсэн олонлогууд нь C нь тэгтэй тэнцүү тэгшитгэлийн шийдэл юм. Та үргэлж дараах хэлбэрийн тэгшитгэлийг авч үзэж болно.

Үнэн хэрэгтээ тэгшитгэлийг өгье:

Энэ тохиолдолд бид ижил тэгшитгэл рүү явж болно:

k логик тэгшитгэлийн системийг авч үзье.

Системийн шийдэл нь системийн бүх тэгшитгэл хангагдсан хувьсагчдын багц юм. Логик функцүүдийн хувьд логик тэгшитгэлийн системийн шийдлийг олж авахын тулд анхны функцүүдийн холболтыг илэрхийлсэн Ф логик функц үнэн байх олонлогийг олох хэрэгтэй.

Хэрэв хувьсагчийн тоо бага, жишээлбэл, 5-аас бага бол функцийн үнэний хүснэгтийг байгуулах нь тийм ч хэцүү биш бөгөөд энэ нь системд хэдэн шийдэлтэй, шийдлийг өгдөг олонлогуудыг хэлэх боломжийг олгодог.

Заримд нь Улсын нэгдсэн шалгалтын асуудаллогик тэгшитгэлийн системийн шийдлийг олохын тулд хувьсагчийн тоо 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:Системийн үнэний хүснэгтийг байгуулъя:

Даалгаврын нөхцөл хангагдсан мөрийг тодоор тэмдэглэнэ. Тэгэхээр 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-тэй тэнцүү байгааг харахад хялбар байдаг.

Үндэслэлд хүндрэлтэй байгаа тохиолдолд судалгаа, барилгыншийдлийг хайж олох боломжтойашиглах үнэний хүснэгтүүд, нэг эсвэл хоёр тэгшитгэлийн хувьд.

Тэгшитгэлийн системийг дараах хэлбэрээр дахин бичье.

Нэг тэгшитгэлийн хувьд үнэний хүснэгтийг тусад нь байгуулъя:

Хоёр тэгшитгэлийн үнэний хүснэгтийг байгуулъя:

Логик тэгшитгэлийн системийг шийдвэрлэх арга

Та логик тэгшитгэлийн системийг шийдэж болно, жишээлбэл, үнэний хүснэгт (хэрэв хувьсагчдын тоо хэт том биш бол) эсвэл шийдвэрийн модыг ашиглан эхлээд тэгшитгэл бүрийг хялбаршуулж болно.

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 үндэстэй:

Үүнтэй ижил хүснэгтээс 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 ≡ 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 үндэс.

Заримдаа үндэс тоо нь Фибоначчийн хуулийн дагуу ургадаг.

Логик тэгшитгэлийн системийг шийдвэрлэх нь бүтээлч хандлагыг шаарддаг.