Компьютерийн шинжлэх ухаан дахь тэгшитгэл. Компьютерийн шинжлэх ухааны улсын нэгдсэн шалгалтын бодлого дахь логик тэгшитгэлийн системүүд

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

Энэхүү техник нь үнэний хүснэгтийг ашиглахад үндэслэсэн бөгөөд логик илэрхийллийг хэрхэн хувиргах талаар мэддэг оюутнуудад зориулагдсан болно. Хэрэв оюутнууд эдгээр аргуудыг сайн эзэмшээгүй бол тэдгээрийг ямар ч өөрчлөлтгүйгээр ашиглаж болно. (Бид хувиргалтыг ашиглах болно). Энэхүү шийдлийн аргыг эзэмшихийн тулд үндсэн логик үйлдлүүдийн шинж чанаруудыг мэдэх шаардлагатай: коньюнкц, дизъюнкц, урвуу, импликация, эквивалент.

Энэ аргыг ашиглан тэгшитгэлийн системийг шийдэх алгоритм:

Логик тэгшитгэлийг хувиргаж, хялбарчил.

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

Эхний (эсвэл сүүлчийн) хувьсагчийн анхны утгыг тохируулах боломжтой хувьсагчдын хүснэгтийг байгуул.

Дараахь хувьсагчийн боломжит хувилбаруудыг байнга бичнэ үү хүн бүрэхнийх нь утга.

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

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

Жишээ 1.

¬ X1 ˅ X2=1

¬ X2 ˅ X3=1

¬ X3 ˅ X4=1

¬ X9 ˅ X10=1

X1-ээс эхэлж, энэ хувьсагч ямар утгыг авч болохыг харцгаая: 0 ба 1.

Дараа нь эдгээр утгууд тус бүрийг авч үзээд X2 гэж юу болохыг харцгаая.

Хариулт: 11 шийдэл

Жишээ 2.

( X1˄X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1

( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1

(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0

Томьёог ашиглан хувиргацгаая (А˄ Б)˅ (¬ А ˄ ¬ Б)= А↔ Б

Бид авах:

( X1↔ X2) ˅ (X1↔ X3) =1

( X2↔ X3) ˅ (X2↔ X4) =1

( X8↔ X9 (X8↔ X10) =0

X1 =0 - 8 шийдлийн хувьд

X1=1 гэж аваад X2 ямар утгыг авч болохыг харцгаая. Одоо X2 бүрийн хувьд бид X3 ямар утгыг авч болох гэх мэтийг авч үзэх болно.

X1=1 – 8 шийдлийн хувьд

Нийт 8+8=16 шийдэл

Хариулах. 16 шийдэл

Жишээ 3 .

¬ ( X1↔ X2) ˄ ( X1 ˅X3) ˄ (¬X1˅¬X3 )=0

¬ ( X2↔ X3) ˄ (X2 ˅X4) ˄ (¬X2˅¬X4)=0

….

¬ ( X8↔ X9 (X8˅X10) ˄ (¬X8˅¬X10)=0

Өөрчлөлтийн дараа (А˅ Б) ˄(¬ А ˅¬ Б)= ¬( А ↔ Б)

бид авах:

¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0

¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0

…..

¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0

X1=0 гэж аваад X2 ямар утгыг авч болохыг харцгаая. Одоо X2 бүрийн хувьд бид X3 ямар утгыг авч болох гэх мэтийг авч үзэх болно.

Бид X1=0-ийн 10 шийдлийг авсан

X1=1-ийн хувьд ижил зүйлийг хийцгээе. Бид бас 10 шийдлийг авдаг

Нийт:10+10=20

Хариулт: 20 шийдэл.

Жишээ 4.

(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1

(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Томъёо ашиглан хөрвүүлье. (А˄ Б)˅ (¬ А ˄ ¬ Б)= А↔ Б. Бид авах:

(X1↔ X2) ˅ (X2↔ X3)=1

(X2↔ X3) ˅ (X3↔ X4)=1

(X3↔ X4) ˅ (X4↔ X5)=1

(X4↔ X5) ˅ (X5↔ X6)=1

(X5↔ X6) ˅ (X6↔ X7)=1

(X6↔ X7) ˅ (X7↔ X8)=1

(X7↔ X8) ˅ (X8↔ X9)=1

(X8↔ X9) ˅ (X9↔ X10)=0

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

X10=0, дараа нь X9=1, X8=0, X7=0, X6=0, дараах хувьсагчдыг авч болно. өөр өөр утгатай. Бид тус бүрийг авч үзэх болно.

X10=0-ийн нийт 21 шийдэл

Одоо X10=1 гэж бод. Мөн бид 21 шийдлийг авдаг

Нийт: 21+21=42

Хариулт: 42 шийдэл

Жишээ 5.

( X1 ˄X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3 ˄X4) ˅ (X3 ˄ ¬X4)=1

( X3 ˄X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5 ˄X6) ˅ (X5˄¬X6)=1

( X5 ˄X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8) ˅ (X7 ˄ ¬X8)=1

( X7˄X8) ˅ (¬X7 ˄ ¬X8) ˅ (¬ X9X10) ˅ (X9˄¬X10) =1

Томъёоны дагуу хувиргацгаая.(¬ А ˄ Б) ˅ ( А ˄ ¬ Б)= А↔ ¬ Б

( А˄ Б)˅ (¬ А ˄ ¬ Б)= А↔ Б

( X1↔ X2) ˅ (X3 ↔ ¬X4)=1

( X3↔ X4) ˅ (X5 ↔ ¬X6)=1

( X5↔ X6) ˅ (X7 ↔ ¬X8)=1

( X7↔ X8) ˅ (X9 ↔ ¬X10)=1

X1 ба X2 ямар утгыг авч болохыг авч үзье: (0,0), (0,1), (1,0), (1,1).

Сонголт бүрийг авч үзээд X3, X4 ямар утгыг авч болохыг харцгаая.

X7, X8-аас эхлэн бид шийдлүүдийн тоог нэн даруй бичих болно, учир нь утгууд ижил (1,1) ба (0,0) байвал дараах хувьсагчид 4 шийдэлтэй болох нь нэн даруй тодорхой болно. ба тэдгээр нь ялгаатай үед (0,1) ба (1 ,0) – 2 шийдэл.

Нийт: 80+80+32=192

Хариулт: 192 шийдэл

Жишээ 6.

(X1↔X2) ˅ (X2 ↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4 ↔X5)=1

….

(X8↔X9) ˅ (X9 ↔X10)=1

X1=0 гэж аваад X2 ямар утгыг авч болохыг харцгаая. Одоо X2 бүрийн хувьд бид X3 ямар утгыг авч болох гэх мэтийг авч үзэх болно.

Бид тодорхой загварыг харж байна: Дараагийн шийдлүүдийн тоо нь өмнөх хоёрын нийлбэртэй тэнцүү байна.

X1=1-ийн хувьд бид 89 шийдлийг авна

Нийт: 89+89=178 шийдэл

Хариулт: 178 шийдэл

Үүнийг дахиад нэг аргаар шийдье

(X1↔X2) ˅ (X2 ↔X3)=1

(X2↔X3) ˅ (X3↔X4)=1

(X3↔X4) ˅ (X4 ↔X5)=1

….

(X8↔X9) ˅ (X9 ↔X10)=1

Орлуулахыг танилцуулъя:

Т 1 =(X1↔X2)

Т 2 =(X2↔X3)

Т 3 =(X3↔X4)

Т 4 =(X4↔X5)

Т 5 =(X5↔X6)

Т 6 =(X6↔X7)

Т 7 =(X7↔X8)

Т 8 =(X8↔X9)

Т 9 =(X9↔X10)

Бид авах:

Т1 ˅Т2=1

Т2 ˅Т3=1

Т3˅Т4=1

Т4 ˅Т5=1

Т5˅Т6=1

Т6˅Т7=1

Т7˅Т8=1

Т8˅Т9=1

Т9Т10=1

АвцгааяТ1=1 ба дизьюнкцийн шинж чанарыг ашиглана:

ГЭХДЭЭ үүнийг санацгаая

Т 1 =(X1↔X2)

Т 2 =(X2↔X3) гэх мэт.

Эквивалент шинж чанарыг ашиглаад хүснэгтээс харахад үүнийг шалгацгаая

T = 1 байх үед хоёр шийдэл гарна. Мөн =0 үед нэг шийдэл байна.

Тиймээс бид нэгийн тоог тоолж, тэгийн тоог 2+-аар үржүүлж болно. Тоолох, мөн загвар ашиглан.

Нэгийн тоо = өмнөх шийдүүдийн T нийт тоо, тэгийн тоо нь өмнөх нэгийн тоотой тэнцүү байна.

Тэгэхээр. Бид авах болно. Нэг нь хоёр шийдийг өгдөг тул нэгээс 34 * 2 = 68 шийдэл + 0-ээс 21 шийдэл гарна.

T=1-ийн нийт 89 шийдэл. Үүнтэй ижил аргаар бид T=0-ийн 89 шийдлийг олж авдаг

Нийт 89+89=178

Хариулт: 178 шийдэл

Жишээ 7.

(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅ ¬(X3↔ X4)=1

(X3 ↔ X4) ˅ (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅ ¬(X5↔ X6)=1

(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅ ¬(X7↔ X8)=1

(X7 ↔ X8) ˅ (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅ ¬(X9↔ X10)=1

Орлуулахыг танилцуулъя:

Т1=(X1 ↔ X2)

Т2=(X3↔ X4)

Т3=(X5↔ X6)

Т4=(X7 ↔ X8)

Т5=(X9↔ X10)

Бид авах:

(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1

(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1

(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1

(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1

Ц нь юу байж болохыг авч үзье.

T1

T2

T3

T4

T5

Нийт

0

1

0

1

0

32

1

0

1

0

1

32

Т К ≠Т K+1 Би Т К =Т K+2

Бид авна: 2 5 =32 Т

Нийт: 32+32=64

Хариулт: 64 шийдэл.

Тэгшитгэлийн шийдэл 1. Үгүйсгэх тэмдгийг ¬-ээр сольж тэгшитгэл бичих угтвар хэлбэр рүү очно 2. Тусгай төрлийн үнэний хүснэгтийн гарчгийг байгуулна 3. Үнэний хүснэгтийн мөрүүдийг бүх хослолыг бөглөнө. X-ийн оронд 0 эсвэл 1-ийг орлуулах A ба B. 4. X = F (A,B)-ийн үнэний хүснэгтийг үүсгэнэ 5. Үнэний хүснэгтийг ашиглан SCNF байгуулах аргуудыг ашиглан шаардлагатай бол X функцийн төрлийг тодорхойлно. болон SDNF, үүнийг доор авч үзэх болно.

Тусгай хэлбэрийн үнэний хүснэгтийг байгуулах ¬((A+B)·(X A·B))=¬(B+¬(X A))

Үнэний хүснэгт X=F(A, B) ABX A ХАРИУЛТ дахь B далдлыг үгүйсгэхэд тохирно:

Логик төхөөрөмжүүдийн хосолсон хэлхээ Үндсэн элементүүд (ГОСТ): 1 A B Дизьюнкц A B Эквивалент & A B холболт M2 A B XOR

Логик төхөөрөмжүүдийн хосолсон хэлхээ Үндсэн элементүүд (ГОСТ): 1 A B Implication & A B Schaeffer элемент & A B Coimplication 1 A B Webb элемент

Жишээ хэлхээ F 1 & 1 & & 1M2 B A

Хэлхээ шийдвэрлэх 1 Сонголт - хэлхээг нарийн төвөгтэй логик илэрхийлэл болгон хувиргаж, дараа нь логикийн хуулиудын дагуу хялбарчлах. Сонголт 2 – үнэний хүснэгтийг барьж, шаардлагатай бол SKNF эсвэл SDNF-ээр дамжуулан барих (доороос үзнэ үү). Хоёрдахь сонголтыг авч үзье, учир нь энэ нь илүү энгийн бөгөөд ойлгомжтой байдаг.

Үнэний хүснэгт байгуулах AB A + B + · B B · A + A B A + · ·

Үнэний хүснэгт F(A, B) ABX A ХАРИУЛТ дахь В далдлыг үгүйсгэхэд тохирно:

SDNF ба SKNF (тодорхойлолтууд) Элементар холболт гэдэг нь үгүйсгэхтэй эсвэл үгүйсгэлгүйгээр авсан хэд хэдэн хувьсагчийн холболт бөгөөд хувьсагчдын дунд ижил хувьсагч байж болно хувьсагчдын дунд ижилхэн байж болно. Элементар холболтын аливаа дизьюнкцийг дизьюнктив хэвийн хэлбэр (DNF) гэж нэрлэе.

SDNF ба SCNF (тодорхойлолт) Төгс салгагч хэвийн хэлбэрийг (PDNF) DNF гэж нэрлэдэг бөгөөд үүнд ижил элементар холболт байхгүй бөгөөд бүх холболтууд нь хувьсагч бүр зөвхөн нэг удаа гарч ирдэг (магадгүй үгүйсгэлтэй) хувьсагчдаас бүрддэг. Төгс коньюнктив хэвийн хэлбэр (PCNF) нь ижил энгийн дизъюнкц байхгүй, бүх дизьюнкцүүд нь хувьсагч бүр зөвхөн нэг удаа гарч ирдэг (магадгүй үгүйсгэсэн) хувьсагчдаас бүрддэг CNF юм.

Үнэний хүснэгтээс SDNF авах алгоритм 1. Үнэний хүснэгтийн хамгийн сүүлийн баганад 1 байгаа мөрүүдийг тэмдэглэ. 2. Тэмдэглэгдсэн мөр бүрт бүх хувьсагчийн холболтыг дараах байдлаар бичнэ: хэрэв хувьсагчийн утга Өгөгдсөн мөр нь 1 бол энэ хувьсагчийг холболтонд оруулна, хэрэв 0-тэй тэнцүү бол түүнийг үгүйсгэнэ. 3. Үүссэн бүх холбоосыг салгах холбоо болгон холбоно.

Үнэний хүснэгтээс SCNF-ийг авах алгоритм 1. Үнэний хүснэгтийн сүүлийн баганад 0 байгаа мөрүүдийг тэмдэглэ. 2. Тэмдэглэгдсэн мөр бүрт бүх хувьсагчийн дизьюнкцийг дараах байдлаар бичнэ: хэрэв хувьсагчийн утга өгөгдсөн мөр нь 0 бол энэ хувьсагчийг холболтонд оруулаарай, хэрэв 1-тэй тэнцүү бол түүнийг үгүйсгэнэ. 3. Үүссэн бүх салалтуудыг холбогч холбоо болгон холбоно.

SKNF XY F(X,Y) байгуулах жишээ Тэгээр тэмдэглэ 2. Дизюнкц: X + Y 3. Холболт: (X + Y) · (X + Y)

Компьютерийн шинжлэх ухааны шалгалтын А, В хэсгийн зарим асуудлыг хэрхэн шийдвэрлэх талаар

Хичээл №3. Логик. Логик функцууд. Тэгшитгэл шийдвэрлэх

1. Улсын нэгдсэн шалгалтын олон тооны асуудал нь саналын логикт зориулагдсан болно. Тэдгээрийн ихэнхийг шийдвэрлэхийн тулд саналын логикийн үндсэн хуулиудыг, нэг ба хоёр хувьсагчийн логик функцүүдийн үнэний хүснэгтийн талаархи мэдлэгийг мэдэхэд хангалттай. Би саналын логикийн үндсэн хуулиудыг өгөх болно.
   Дизюнкц ба коньюнкцийн шилжих чадвар:
   a ˅ b ≡ b ˅ a
2. a^b ≡ b^a
   Дизюнкц ба коньюнкцийн талаарх хуваарилалтын хууль:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
3. Үгүйсгэхийг үгүйсгэх:
   ¬(¬a) ≡ a
4. Тохиромжтой байдал:
   a ^ ¬а ≡ худал
5. Онцгой гурав дахь:
   a ˅ ¬а ≡ үнэн
6. Де Морганы хуулиуд:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Хялбарчлал:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ үнэн ≡ a
   a ˄ худал ≡ худал
8. Шингээлт:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Далд утгыг солих
   a → b ≡ ¬a ˅ b
10. Баримт бичгийг солих
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Логик функцүүдийн төлөөлөл

n хувьсагчийн аливаа логик функц - F(x 1, x 2, ... x n)-ийг үнэний хүснэгтээр тодорхойлж болно. Ийм хүснэгтэд 2n олонлог хувьсагч агуулагддаг бөгөөд тус бүрд нь энэ олонлог дээрх функцийн утгыг зааж өгсөн болно. Хувьсагчийн тоо харьцангуй бага үед энэ арга сайн. Аль хэдийн n > 5-ын хувьд дүрслэл муу харагдах болно.

Өөр нэг арга бол функцийг хангалттай мэдэгдэж байгаа томъёогоор тодорхойлох явдал юм энгийн функцууд. Аливаа логик функцийг зөвхөн f i функц агуулсан томьёогоор илэрхийлэх боломжтой бол функцүүдийн системийг (f 1, f 2, ... f k) бүрэн гэж нэрлэдэг.

Функцийн систем (¬, ˄, ˅) дууссан. 9 ба 10-р хууль нь үгүйсгэх, коньюнкц, салгах замаар далд утга, ижил төстэй байдлыг хэрхэн илэрхийлж байгааг харуулсан жишээ юм.

Үнэн хэрэгтээ үгүйсгэх ба холбогч эсвэл үгүйсгэх ба салгах гэсэн хоёр функцээс бүрдсэн систем мөн бүрэн дүүрэн байдаг. Де Морганы хуулиас үгүйсгэх, салгах замаар холболтыг илэрхийлэх, үүний дагуу үгүйсгэх, салгах замаар салгах санааг илэрхийлэх санаануудыг дагаж мөрддөг.

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

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

Програмчлалын хэлний үндсэн функцууд нь ихэвчлэн таних, үгүйсгэх, холбох, салгах зэрэг орно. Улсын нэгдсэн шалгалтын асуудалд эдгээр чиг үүргүүдийн зэрэгцээ үр дагавар нь ихэвчлэн олддог.

Цөөн хэдэн зүйлийг харцгаая энгийн даалгаваруудлогик функцтэй холбоотой.

Асуудал 15:

Үнэний хүснэгтийн фрагментийг өгөв. Өгөгдсөн гурван функцийн аль нь энэ фрагментэд тохирох вэ?

X 1	X 2	X 3	X 4	Ф
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функцийн дугаар 3.

Асуудлыг шийдэхийн тулд та үндсэн функцүүдийн үнэний хүснэгтийг мэдэж, үйл ажиллагааны тэргүүлэх чиглэлийг санах хэрэгтэй. Холбогч (логик үржүүлэх) нь дизюнкцаас (логик нэмэх) илүү давуу эрхтэй бөгөөд эрт гүйцэтгэдэг гэдгийг сануулъя. Тооцооллын явцад гурав дахь багц дахь 1 ба 2 тоотой функцууд нь 1 утгатай бөгөөд энэ шалтгааны улмаас фрагменттэй тохирохгүй байгааг анзаарахад хялбар байдаг.

Асуудал 16:

Өгөгдсөн тоонуудын аль нь нөхцөлийг хангаж байна:

(хамгийн чухал цифрээс эхэлсэн цифрүүд буурах дарааллаар байна) → (тоо - тэгш) ˄ (бага орон - тэгш) ˄ (өндөр орон - сондгой)

Хэрэв хэд хэдэн ийм тоо байгаа бол хамгийн томыг нь зааж өгнө үү.

1. 13579
2. 97531
3. 24678
4. 15386

Нөхцөл 4-ийн тоогоор хангагдсан байна.

Эхний хоёр тоо нь хамгийн бага орон сондгой байх нөхцөлийг хангахгүй байна. Холболтын нөхцлийн аль нэг нь худал байвал нөхцлийн холбоо худал болно. Гурав дахь тооны хувьд хамгийн өндөр оронтой байх нөхцөл хангагдаагүй байна. Дөрөв дэх тооны хувьд тухайн тооны бага, өндөр оронтой тоонд тавигдах нөхцөлийг хангасан. Энд байгаа нөхцөл байдал нь худал бол далд утга нь үнэн тул холболтын эхний гишүүн мөн үнэн юм.

Асуудал 17: Хоёр гэрч дараах мэдүүлэг өгсөн.

Нэгдүгээр гэрч: А нь буруутай бол Б нь бүр ч буруутай, С нь гэм буруугүй.

Хоёр дахь гэрч: Хоёр нь буруутай. Үлдсэн хүмүүсийн нэг нь гарцаагүй буруутай, буруутай, гэхдээ яг хэн гэдгийг хэлж чадахгүй байна.

Мэдүүлгээс А, Б, С нарын гэм буруугийн талаар ямар дүгнэлт хийж болох вэ?

Хариулт: Мэдүүлгээс харахад А, Б буруутай, С нь гэм буруугүй.

Шийдэл: Мэдээжийн хариултыг эрүүл ухаанд тулгуурлан хэлж болно. Гэхдээ үүнийг хэрхэн хатуу, албан ёсоор хийж болохыг харцгаая.

Хамгийн эхний хийх зүйл бол мэдэгдлийг албан ёсны болгох явдал юм. Хэрэв холбогдох сэжигтэн гэм буруутай бол үнэн (1) гэсэн утгатай A, B, C гэсэн гурван логик хувьсагчийг оруулъя. Дараа нь анхны гэрчийн мэдүүлгийг дараах томъёогоор өгнө.

A → (B ˄ ¬C)

Хоёр дахь гэрчийн мэдүүлгийг дараах томъёогоор өгнө.

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Хоёр гэрчийн мэдүүлгийг үнэн гэж тооцож, харгалзах томъёоны холболтыг илэрхийлнэ.

Эдгээр уншилтын үнэний хүснэгтийг байгуулцгаая.

А	Б	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Товч нотлох баримт нь зөвхөн нэг тохиолдолд үнэн бөгөөд тодорхой хариулт өгөхөд хүргэдэг - А, Б буруутай, С нь гэм буруугүй.

Энэ хүснэгтийн дүн шинжилгээнээс харахад хоёр дахь гэрчийн мэдүүлэг илүү мэдээлэлтэй байна. Түүний гэрчлэлийн үнэнээс зөвхөн хоёр зүйл л гардаг: боломжит сонголтууд- А, Б буруутай, С буруугүй, эсвэл А, С буруугүй, Б буруугүй. Эхний гэрчийн мэдүүлэг нь мэдээлэл багатай - 5 байна янз бүрийн сонголтууд, түүний гэрчлэлтэй тохирч байна. Хоёр гэрчийн мэдүүлэг нийлээд сэжигтнүүдийн гэм буруугийн талаар тодорхой хариулт өгдөг.

Логик тэгшитгэл ба тэгшитгэлийн систем

F(x 1, x 2, …x n) нь n хувьсагчийн логик функц байг. Логик тэгшитгэл нь дараах байдлаар харагдаж байна.

F(x 1, x 2, …x n) = C,

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

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

F(x 1 , x 2 , …x n) = 1

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

F(x 1, x 2, …x n) = 0

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

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

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

Ф = F 1 ˄ F 2 ˄ … F k

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

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

Шалгалтанд санал болгож буй асуудлын шийдэл нь ихэвчлэн тэгшитгэлийн системийн онцлогийг харгалзан үздэг. Би давтан хэлье, олон тооны хувьсагчийн бүх сонголтыг туршиж үзэхээс гадна асуудлыг шийдэх ерөнхий арга байхгүй. Шийдэл нь системийн онцлогт тулгуурлан бүтээгдсэн байх ёстой. Мэдэгдэж буй логик хуулиудыг ашиглан тэгшитгэлийн системийг урьдчилан хялбарчлах нь ихэвчлэн ашигтай байдаг. Энэ асуудлыг шийдэх өөр нэг ашигтай арга бол дараах байдалтай байна. Бид бүх олонлогийг сонирхдоггүй, зөвхөн Ф функц нь 1 гэсэн утгатай байх болно. Бид бүрэн үнэний хүснэгтийг бүтээхийн оронд түүний аналог буюу хоёртын шийдвэрийн модыг бүтээх болно. Энэ модны мөчир бүр нь нэг шийдэлтэй тохирч, Ф функц 1 гэсэн утгатай олонлогийг зааж өгдөг. Шийдвэрлэх модны мөчрүүдийн тоо нь тэгшитгэлийн системийн шийдүүдийн тоотой давхцдаг.

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

Асуудал 18

Хоёр тэгшитгэлийн системийг хангадаг x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 логик хувьсагчдын утгын хэдэн өөр багц байдаг вэ?

Хариулт: Систем нь 36 өөр шийдэлтэй.

Шийдэл: Тэгшитгэлийн системд хоёр тэгшитгэл багтана. x 1, x 2, ...x 5 гэсэн 5 хувьсагчаас хамаарч эхний тэгшитгэлийн шийдийн тоог олъё. Эхний тэгшитгэлийг эргээд 5 тэгшитгэлийн систем гэж үзэж болно. Дээр дурдсанчлан тэгшитгэлийн систем нь логик функцүүдийн нэгдлийг илэрхийлдэг. Үүний эсрэгээр нь бас үнэн: нөхцлийн холболтыг тэгшитгэлийн систем гэж үзэж болно.

Анхны тэгшитгэл гэж үзэж болох холболтын эхний гишүүн (x1→ x2)-д зориулсан шийдвэрийн модыг байгуулъя. Энэ модны график дүрслэл дараах байдалтай байна.

Мод нь тооны дагуу хоёр түвшнээс бүрдэнэ тэгшитгэлийн хувьсагчид. Эхний түвшин нь эхний хувьсагч X 1-ийг тодорхойлдог. Энэ түвшний хоёр салбар нь энэ хувьсагчийн боломжит утгуудыг тусгадаг - 1 ба 0. Хоёр дахь түвшинд модны мөчрүүд нь зөвхөн тэгшитгэл үнэн болох X 2 хувьсагчийн боломжит утгуудыг тусгасан болно. Тэгшитгэл нь далд санааг зааж байгаа тул X 1 нь 1 утгатай салбар нь тухайн салбар дээр X 2 нь 1 утгатай байхыг шаарддаг. X 1 нь 0 утгатай салбар нь X 2 утгатай хоёр салбар үүсгэдэг. 0 ба 1-тэй тэнцүү Баригдсан мод нь гурван шийдлийг тодорхойлдог бөгөөд үүнд X 1 → X 2 утга нь 1 гэсэн утгыг авдаг. Салбар бүр дээр хувьсах утгуудын харгалзах багцыг бичиж, тэгшитгэлийн шийдийг өгдөг.

Эдгээр багцууд нь: ((1, 1), (0, 1), (0, 0))

Дараахь X 2 → X 3 гэсэн утгатай дараах тэгшитгэлийг нэмж шийдвэрийн модыг үргэлжлүүлэн байгуулъя. Манай тэгшитгэлийн системийн онцлог нь системийн шинэ тэгшитгэл болгонд өмнөх тэгшитгэлийн нэг хувьсагчийг ашиглаж, нэг шинэ хувьсагчийг нэмдэгт оршино. X 2 хувьсагч нь модонд аль хэдийн утгуудтай байдаг тул X 2 хувьсагч нь 1 утгатай бүх салбарууд дээр X 3 хувьсагч нь мөн 1 утгатай байх болно. Ийм салбаруудын хувьд модыг барих дараагийн түвшинд хүртэл үргэлжлэх боловч шинэ салбарууд гарч ирэхгүй байна. X 2 хувьсагч нь 0 утгатай ганц салбар нь X 3 хувьсагч 0 ба 1 утгыг хүлээн авах хоёр салбар болж салбарлана. Тиймээс шинэ тэгшитгэлийн нэмэлт болгонд өөрийн онцлогийг харгалзан нэг шийд нэмнэ. Анхны анхны тэгшитгэл:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6 шийдэлтэй. Энэ тэгшитгэлийн бүрэн шийдвэрийн мод дараах байдалтай байна.

Манай системийн хоёр дахь тэгшитгэл нь эхнийхтэй төстэй:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Ганц ялгаа нь тэгшитгэл нь Y хувьсагчийг ашигладаг. X i хувьсагчийн шийдэл бүрийг Y j хувьсагчийн шийдэл бүртэй нэгтгэж болох тул нийт тоо 36 шийдэл байдаг.

Баригдсан шийдвэрийн мод нь зөвхөн шийдлүүдийн тоог (салбарын тоогоор) төдийгүй модны мөчир тус бүр дээр бичсэн шийдлүүдийг өөрөө өгдөг гэдгийг анхаарна уу.

Асуудал 19

X1, x2, x3, x4, x5, y1, y2, y3, y4, y5 гэсэн логик хувьсагчдын утгын хэдэн өөр багц доор жагсаасан бүх нөхцлийг хангасан бэ?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Энэ даалгавар нь өмнөх даалгаврын өөрчлөлт юм. Үүний ялгаа нь X ба Y хувьсагчдыг холбосон өөр нэг тэгшитгэл нэмэгдсэнд оршино.

X 1 → Y 1 тэгшитгэлээс харахад X 1 нь 1 утгатай байхад (ийм нэг шийдэл байгаа) Y 1 нь мөн 1 утгатай байна. Тиймээс X 1 ба Y 1 нь утгыг агуулсан нэг олонлог байна. 1. X 1 нь 0-тэй тэнцэх үед Y 1 нь 0 ба 1 гэсэн ямар ч утгатай байж болно. Тиймээс X 1-тэй олонлог бүр 0-тэй тэнцүү бөгөөд ийм 5 олонлог байдаг нь Y хувьсагчтай бүх 6 олонлогтой тохирч байна. Тиймээс нийт шийдлийн тоо 31 байна.

Асуудал 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Шийдэл: Үндсэн тэгшитгэлийг санаж, тэгшитгэлээ дараах байдлаар бичнэ.

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Цикл нөлөөллийн гинжин хэлхээ нь хувьсагчид ижил байна гэсэн үг тул бидний тэгшитгэл нь тэгшитгэлтэй тэнцүү байна:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Бүх X i нь 1 эсвэл 0 байх үед энэ тэгшитгэл нь хоёр шийдэлтэй байна.

Асуудал 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Шийдэл: 20-р асуудлын нэгэн адил бид мөчлөгийн үр дагавраас ижил төстэй байдал руу шилжиж, тэгшитгэлийг дараах хэлбэрээр дахин бичнэ.

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Энэ тэгшитгэлийн шийдвэрийн модыг байгуулъя:

Асуудал 22

Дараах тэгшитгэлийн систем хэдэн шийдэлтэй вэ?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Хариулт: 64

Шийдэл: Дараах хувьсагчийн өөрчлөлтийг оруулан 10 хувьсагчаас 5 хувьсагч руу шилжье.

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Дараа нь эхний тэгшитгэл нь дараах хэлбэртэй болно.

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Тэгшитгэлийг дараах байдлаар бичих замаар хялбарчилж болно.

(Y 1 ≡ Y 2) = 0

Уламжлалт хэлбэрт шилжсэнээр бид системийг хялбаршуулсаны дараа дараах хэлбэрээр бичнэ.

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

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

Анхны X хувьсагчид руу буцахдаа Y хувьсагчийн утга тус бүрийн хувьд X хувьсагчийн 2 утга байгаа тул Y хувьсагчийн шийдэл бүр X хувьсагчид 2 5 шийдлийг үүсгэдэг болохыг анхаарна уу 5 шийдэлтэй тул нийт шийдлийн тоо 64 байна.

Таны харж байгаагаар тэгшитгэлийн системийг шийдвэрлэх асуудал бүр өөрийн гэсэн арга барилыг шаарддаг. Ерөнхий хүлээн авалттэгшитгэлийг хялбарчлах эквивалент хувиргалт хийх явдал юм. Нийтлэг арга бол шийдвэрийн модыг барих явдал юм. Ашигласан арга нь хувьсагчийн боломжит утгуудын бүх багцыг бүтээгээгүй, зөвхөн функц 1 (үнэн) утгыг авдаг онцлогтой нь үнэний хүснэгтийг байгуулахыг хэсэгчлэн санагдуулдаг. Санал болгож буй асуудлуудад ихэнхдээ шийдвэрийн модыг бүрэн бүтээх шаардлагагүй байдаг, учир нь эхний шатанд, жишээлбэл, 18-р асуудалд хийсэн шиг дараагийн түвшин бүрт шинэ мөчрүүдийн харагдах хэв маягийг тогтоох боломжтой байдаг. .

Ерөнхийдөө логик тэгшитгэлийн системийн шийдлийг олохтой холбоотой асуудлууд нь математикийн сайн дасгалууд юм.

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

Ийм программ бичих нь тийм ч хэцүү биш юм. Ийм хөтөлбөр нь улсын нэгдсэн шалгалтанд санал болгож буй бүх даалгаврыг амархан даван туулах болно.

Хачирхалтай нь, логик тэгшитгэлийн системийн шийдлийг олох ажил нь компьютерт хэцүү байдаг бөгөөд компьютерт өөрийн гэсэн хязгаар байдаг. Компьютер нь 20-30 хувьсагчийн тоотой асуудлуудыг амархан даван туулж чаддаг ч том хэмжээтэй асуудлуудыг удаан хугацаанд бодож эхэлдэг. Баримт нь олонлогийн тоог тодорхойлдог 2 n функц нь n нэмэгдэх тусам хурдацтай өсдөг экспоненциал юм. Өдөрт 40 хувьсагчтай даалгаврыг энгийн персонал компьютер даван туулах чадваргүй тийм хурдан байдаг.

Логик тэгшитгэлийг шийдвэрлэх C# хэл дээрх програм

Логик тэгшитгэлийг шийдвэрлэх програм бичих нь зөвхөн Улсын нэгдсэн шалгалтын тестийн асуудлыг өөрийн шийдлийн зөв эсэхийг шалгахад ашиглаж болох юм бол олон шалтгааны улмаас ашигтай байдаг. Өөр нэг шалтгаан нь ийм хөтөлбөр нь Улсын нэгдсэн шалгалтын С ангиллын даалгаварт тавигдах шаардлагыг хангасан програмчлалын даалгаврын маш сайн жишээ юм.

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

Ийм программ дээр та олонлогийн тоонд тулгуурлан гогцоо бүтээх хэрэгтэй бөгөөд давталтын биед багцын дугаарыг ашиглан олонлогийг өөрөө бүрдүүлж, энэ олонлог дээрх функцийн утгыг тооцоолох, хэрэв энэ нь утга нь 1 бол олонлог нь тэгшитгэлийн шийдийг өгнө.

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

Бидний асуудлыг шийдэж буй C# хэл дээрх функц иймэрхүү харагдаж байна:

///

/// шийдлийн тоог тоолох програм

/// логик тэгшитгэл (тэгшитгэлийн систем)

///

///

/// логик функц - арга,

/// түүний гарын үсгийг ХС-ийн төлөөлөгч тодорхойлсон

///

/// хувьсагчийн тоо

/// шийдлийн тоо

статик int Шийдэх тэгшитгэлүүд(DF хөгжилтэй, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); // багцын тоо

int p = 0, q = 0, k = 0;

//Багцын тоогоор хайлтыг гүйцээнэ

хувьд (int i = 0; i< m; i++)

//Дараагийн багцыг бүрдүүлэх - багц,

//i тооны хоёртын дүрслэлээр тодорхойлогддог

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Олонлог дээрх функцын утгыг тооцоол

Хөтөлбөрийг ойлгохын тулд хөтөлбөрийн санааны тайлбар, текст дэх тайлбар нь хангалттай байх гэж найдаж байна. Би зөвхөн өгөгдсөн функцийн гарчгийг тайлбарлахад анхаарлаа хандуулах болно. SolveEquations функц нь хоёр оролтын параметртэй. Хөгжилтэй параметр нь шийдэж буй тэгшитгэл эсвэл тэгшитгэлийн системд тохирох логик функцийг тодорхойлдог. n параметр нь тоог зааж өгдөг функцын хувьсагчидхөгжилтэй. Үүний үр дүнд SolveEquations функц нь логик функцийн шийдүүдийн тоог, өөрөөр хэлбэл функц үнэн гэж үнэлдэг олонлогуудын тоог буцаана.

Зарим F(x) функц нь арифметик, мөр эсвэл логик төрлийн хувьсагч x оролтын параметртэй байх нь сургуулийн сурагчдад түгээмэл байдаг. Манай тохиолдолд илүү хүчирхэг загварыг ашигладаг. SolveEquations функц нь параметрүүд нь зөвхөн энгийн хувьсагчаас гадна функц байж болох F(f) төрлийн функцуудыг хэлдэг.

SolveEquations функцэд параметр болгон дамжуулж болох функцүүдийн ангиллыг дараах байдлаар тодорхойлно.

delegate bool DF(bool vars);

Энэ анги нь vars массиваар тодорхойлсон логик хувьсагчийн утгуудын багцыг параметр болгон дамжуулсан бүх функцийг эзэмшдэг. Үр дүн нь энэ олонлог дээрх функцийн утгыг илэрхийлэх логик утга юм.

Эцэст нь, хэд хэдэн логик тэгшитгэлийн системийг шийдвэрлэхийн тулд SolveEquations функцийг ашигладаг програмыг энд оруулав. SolveEquations функц нь доорх ProgramCommon ангийн нэг хэсэг юм:

ангийн програм Нийтлэг

delegate bool DF(bool vars);

статик хүчингүй Үндсэн(string args)

Console.WriteLine("Ба функцууд - " +

Шийдэх тэгшитгэл(Зөөлөн ба, 2));

Console.WriteLine("Функц нь 51 шийдэлтэй - " +

Шийдэх тэгшитгэл(Хөгжилтэй51, 5));

Console.WriteLine("Функц нь 53 шийдэлтэй - " +

Шийдэх тэгшитгэл(Хөгжилтэй53, 10));

статик bool FunAnd(bool vars)

буцаах vars && vars;

статик bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

статик bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Энэ програмын шийдлийн үр дүн дараах байдалтай байна.

Бие даасан ажилд зориулсан 10 даалгавар

1. Гурван функцийн аль нь тэнцүү вэ:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Үнэний хүснэгтийн фрагментийг өгөв.

X 1	X 2	X 3	X 4	Ф
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Энэ хэсэг нь гурван функцийн алинд нь тохирох вэ:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Шүүгчдийн бүрэлдэхүүн гурван хүний ​​бүрэлдэхүүнтэй. Тангарагтны шүүгчдийн нэгээс доошгүй гишүүн дэмжсэнээр тангарагтны дарга санал өгсөн тохиолдолд шийдвэр гарна. Үгүй бол шийдвэр гарахгүй. Шийдвэр гаргах үйл явцыг албан ёсны болгох логик функцийг байгуул.
5. Дөрвөн зоос шидэхэд гурван удаа толгой цохиход X нь Y-г хожно. X-ийн өгөөжийг тодорхойлсон логик функцийг тодорхойлно уу.
6. Өгүүлбэр дэх үгсийг нэгээс эхлэн дугаарлана. Дараах дүрмийг хангасан тохиолдолд өгүүлбэрийг зөв зохиосон гэж үзнэ.
   1. Тэгш тоотой үг эгшгээр төгсдөг бол дараагийн үг байгаа бол эгшгээр эхлэх ёстой.
   2. Хэрэв сондгой тоотой үг гийгүүлэгчээр төгссөн бол дараагийн үг байгаа бол гийгүүлэгчээр эхэлж, эгшгээр төгсөх ёстой.
      Дараах өгүүлбэрүүдийн аль нь зөв зохиогдсон бэ?
   3. Ээж Машаг савангаар угаав.
   4. Удирдагч хүн үргэлж үлгэр жишээ байдаг.
   5. Үнэн бол сайн, гэхдээ аз жаргал илүү дээр.
7. Тэгшитгэл хэдэн шийдэлтэй вэ:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Тэгшитгэлийн бүх шийдлийг жагсаа:
   (a → b) → c = 0
9. Дараахь тэгшитгэлийн систем хэдэн шийдэлтэй вэ?
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Тэгшитгэл хэдэн шийдэлтэй вэ:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Асуудлын хариултууд:

1. b ба c функцүүд нь тэнцүү байна.
2. Фрагмент нь b функцтэй тохирч байна.
3. Шүүгчдийн зөвлөлийн дарга шийдвэрт санал өгөхөд P логик хувьсагч 1-ийн утгыг ав. M 1 ба M 2 хувьсагч нь тангарагтны гишүүдийн санал бодлыг илэрхийлдэг. Эерэг шийдвэр гаргах логик функцийг дараах байдлаар бичиж болно.
   P ˄ (M 1 ˅ M 2)
4. i-р зоос толгой дээр буухад P i логик хувьсагч 1 утгыг авъя. X өгөөжийг тодорхойлдог логик функцийг дараах байдлаар бичиж болно.
   ¬((¬P 1 ˄ (¬P 2 ¬ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Өгүүлбэр b.
6. Тэгшитгэл нь 3 шийдэлтэй: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Тэгшитгэлийн хэрэглээ бидний амьдралд өргөн тархсан. Тэдгээрийг олон тооны тооцоолол, барилга байгууламж барих, тэр ч байтугай спортод ашигладаг. Эрт дээр үед хүн тэгшитгэлийг ашигладаг байсан бөгөөд түүнээс хойш тэдний хэрэглээ улам бүр нэмэгдсээр байна. Математикийн хувьд саналын логиктой холбоотой тодорхой асуудлууд байдаг. Энэ төрлийн тэгшитгэлийг шийдэхийн тулд та тодорхой хэмжээний мэдлэгтэй байх хэрэгтэй: саналын логикийн хуулиудын мэдлэг, 1 эсвэл 2 хувьсагчийн логик функцүүдийн үнэний хүснэгтүүдийн мэдлэг, логик илэрхийллийг хөрвүүлэх аргууд. Нэмж дурдахад та логик үйлдлүүдийн дараах шинж чанаруудыг мэдэх хэрэгтэй: коньюнкц, дизъюнкц, урвуу, импликация, эквивалент.

\variables - \-ийн аливаа логик функцийг үнэний хүснэгтээр тодорхойлж болно.

Хэд хэдэн логик тэгшитгэлийг шийдье:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Шийдвэрийг \[X1\]-ээр эхлүүлж, энэ хувьсагч ямар утгыг авч болохыг тодорхойлъё: 0 ба 1. Дараа нь дээрх утгууд тус бүрийг авч үзээд \[X2.\] гэж юу болохыг харна.

Хүснэгтээс харахад бидний логик тэгшитгэл 11 шийдэлтэй байна.

Логик тэгшитгэлийг онлайнаар хаанаас шийдэж болох вэ?

Та манай https://site сайтаас тэгшитгэлийг шийдэж болно. Үнэгүй онлайн шийдүүлэгч нь танд ямар ч төвөгтэй онлайн тэгшитгэлийг хэдхэн секундын дотор шийдэх боломжийг олгоно. Таны хийх ёстой зүйл бол зүгээр л шийдвэрлэгч рүү өгөгдлөө оруулах явдал юм. Та мөн видео зааварчилгааг үзэж, тэгшитгэлийг хэрхэн шийдвэрлэх талаар манай вэбсайтаас сурах боломжтой. Хэрэв танд асуулт байгаа бол манай ВКонтакте групп http://vk.com/pocketteacher дээрээс асууж болно. Манай группт нэгдээрэй, бид танд туслахдаа үргэлж баяртай байх болно.

Энэхүү материал нь компьютерийн шинжлэх ухааны улсын нэгдсэн шалгалтын В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-ийн ижил утгуудын хувьд A  B нь ойлгомжтой. 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, [Цахим нөөц].