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

Логик тэгшитгэлийн системийг шийдэх янз бүрийн арга байдаг. Энэ нь нэг тэгшитгэл рүү буулгах, үнэний хүснэгт байгуулах, задлах явдал юм.

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

Ингээд авч үзье нэг тэгшитгэл болгон бууруулах арга . Энэ арга нь логик тэгшитгэлийг баруун гар тал нь үнэний утгатай (өөрөөр хэлбэл 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-тэй тэнцүү байгааг харахад хялбар байдаг.

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

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

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

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

Хотын төсвийн боловсролын байгууллага

"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) хосыг бий болгоно. гэх мэт.

Эхний тэгшитгэлийн бүх шийдлийг олъё. Үүнийг хоёр аргаар хийж болно: үндэслэл, логикийн хуулиудыг хэрэгжүүлэх замаар үнэний хүснэгт байгуулах.

Үнэний хүснэгт:

Үнэний хүснэгтийг бүтээх нь маш их хөдөлмөр, цаг хугацаа бага шаарддаг тул бид хоёр дахь аргыг ашигладаг - логик үндэслэл. Хэрэв хүчин зүйл бүр 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 гэсэн хосуудыг энэ шийдлээс хасъя.

Нийт хосын тоо 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) хосуудын хооронд холболт хийцгээе.

Үе шат бүрт хосуудын тоог тооцоолох хүснэгтийг үүсгэцгээе.

Сүүлийн тэгшитгэлийн шийдлүүдийг харгалзан үзэх 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) хосуудын хооронд холболт хийцгээе.

Хичээлийн сэдэв: Логик тэгшитгэлийг шийдвэрлэх

Хөгжлийн - оюутнуудын танин мэдэхүйн сонирхлыг хөгжүүлэх нөхцлийг бүрдүүлэх, санах ой, анхаарал, логик сэтгэлгээг хөгжүүлэх;

Боловсролын : бусдын санаа бодлыг сонсох чадварыг хөгжүүлэх,эцсийн үр дүнд хүрэх хүсэл зориг, тэсвэр тэвчээрийг төлөвшүүлэх.

Хичээлийн төрөл: хосолсон хичээл

Тоног төхөөрөмж: компьютер, мультимедиа проектор, танилцуулга 6.

Хичээлийн явц

Үндсэн мэдлэгийг давтах, шинэчлэх. Гэрийн даалгавраа шалгах (10 минут)

Өмнөх хичээлүүдээр бид логик алгебрийн үндсэн хуулиудтай танилцаж, эдгээр хуулиудыг логик илэрхийллийг хялбарчлахад ашиглаж сурсан.

Логик илэрхийллийг хялбарчлах гэрийн даалгавраа шалгацгаая.

1. Дараах үгсийн аль нь логик нөхцөлийг хангаж байна вэ?

(эхний үсэг гийгүүлэгч→хоёр дахь үсэг гийгүүлэгч)٨ (сүүлийн үсэг эгшиг → төгсгөлийн өмнөх үсэг эгшиг)? Хэрэв хэд хэдэн ийм үг байгаа бол тэдгээрийн хамгийн жижигийг нь зааж өгнө үү.

1) АННА 2) МАРИА 3) ОЛЕГ 4) Степан

Дараах тэмдэглэгээг танилцуулъя.

A - эхний үсэг гийгүүлэгч

B - хоёр дахь үсэг гийгүүлэгч

S - сүүлчийн үсэг эгшиг

D – эцсийн өмнөх эгшиг үсэг

Нэг илэрхийлэл хийцгээе:

Хүснэгт хийцгээе:

2. Илэрхийлэлтэй ямар логик илэрхийлэл тэнцэж байгааг заана уу

Анхны илэрхийлэл болон санал болгож буй хувилбаруудын бичлэгийг хялбаршуулж үзье.

3. F илэрхийллийн үнэний хүснэгтийн фрагмент өгөгдсөн:

Аргументуудын заасан утгуудын хувьд эдгээр илэрхийллийн утгыг тодорхойлъё.

Хичээлийн сэдвийн танилцуулга, шинэ материалын танилцуулга (30 минут)

Бид логикийн үндсийг үргэлжлүүлэн судалж байгаа бөгөөд өнөөдрийн хичээлийн сэдэв нь "Логик тэгшитгэлийг шийдвэрлэх" юм. Энэ сэдвийг судалсны дараа та логик тэгшитгэлийг шийдвэрлэх үндсэн аргуудыг сурч, логик алгебрийн хэлээр эдгээр тэгшитгэлийг шийдвэрлэх чадвар, үнэний хүснэгтийг ашиглан логик илэрхийлэл зохиох чадварыг эзэмшинэ.

1. Логик тэгшитгэлийг шийд

(¬К М) → (¬Л М N) =0

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

Шийдэл:

Илэрхийлэлийг өөрчилье(¬К  М) → (¬Л  М  N)

Хоёр нэр томьёо худал байвал илэрхийлэл худал байна. M =0, N =0, L =1 бол хоёр дахь гишүүн нь 0-тэй тэнцүү байна. Эхний гишүүнд K = 0, учир нь M = 0, ба
.

Хариулт: 0100

2. Тэгшитгэлд хэдэн шийдэл байгаа вэ (хариултанд зөвхөн тоог заана уу)?

Шийдэл: илэрхийллийг хувиргах

(A +B )*(C +D )=1

A +B =1 ба C +D =1

Арга 2: үнэний хүснэгтийг зурах

Анхны илэрхийлэлийг хувиргаж, холболтын салангид хэсгүүдийг олж авахын тулд хаалтуудыг нээцгээе.

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Холболтуудыг гүйцээхийн тулд (бүх аргументуудын үржвэр) холбоосыг нэмж оруулъя, хаалт нээнэ үү:

Үүнтэй ижил холболтуудыг авч үзье:

Үүний үр дүнд бид 9 холболт агуулсан SDNF-ийг олж авдаг. Иймд энэ функцийн үнэний хүснэгт нь 2 4 =16 багц хувьсагчийн утгын 9 мөрөнд 1 гэсэн утгатай байна.

3. Тэгшитгэлд хэдэн шийдэл байгаа вэ (хариултанд зөвхөн тоог заана уу)?

Илэрхийлэлийг хялбаршуулж үзье:

,

3 арга зам: SDNF барих

Үүнтэй ижил холболтуудыг авч үзье:

Үүний үр дүнд бид 5 холболт агуулсан SDNF-ийг олж авдаг. Иймд энэ функцийн үнэний хүснэгт нь 2 4 =16 багц хувьсагчийн утгын 5 мөрөнд 1 гэсэн утгатай байна.

Үнэний хүснэгтийг ашиглан логик илэрхийлэл бүтээх:

1-ийг агуулсан үнэний хүснэгтийн мөр бүрт бид аргументуудын үржвэр зохиох ба 0-тэй тэнцэх хувьсагчдыг үгүйсгэх үржвэрт, 1-тэй тэнцүү хувьсагчдыг үгүйсгэхгүйгээр оруулна. Хүссэн F илэрхийлэл нь үүссэн бүтээгдэхүүний нийлбэрээс бүрдэнэ. Дараа нь боломжтой бол энэ илэрхийллийг хялбарчлах хэрэгтэй.

Жишээ нь: илэрхийллийн үнэний хүснэгт өгөгдсөн. Логик илэрхийлэл бүтээ.

3. Гэрийн даалгавар (5 минут)

Тэгшитгэлийг шийд:

Тэгшитгэлд хэдэн шийдэл байгаа вэ (хариултанд зөвхөн тоог заана уу)?

Өгөгдсөн үнэний хүснэгтийг ашиглан логик илэрхийлэл байгуулж,

хялбарчлах.

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

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

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 үндэс.

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

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

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

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

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

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

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

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

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

Ингээд авч үзье нэг тэгшитгэл болгон бууруулах арга . Энэ арга нь логик тэгшитгэлийг баруун гар тал нь үнэний утгатай (өөрөөр хэлбэл 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.