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

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

Бүүлийн алгебр

энгийн логик илэрхийлэл, хоорондоо холбоотой үйлдлүүд нь цогц илэрхийлэл бий болгох, дээр тулгуурлан логик алгебр. гэж Бүүлийн алгебр хоёр хоёртын үйл ажиллагааг бүрдэнэ Тайлбар: нэмэх ба үржүүлэх (уялдуулан болон disjunction тус тус); нь unary - Урвуу. Бүх энгийн илэрхийлэл (цогцолбор логик үзэл бодлоо илэрхийлэх эрх элемент) хоёр утгын нэг нь авч: "1" буюу "0", "үнэн", эсвэл "худал", "+" эсвэл "-" тус тус.

логик алгебр хэдэн харьцангуй энгийн Аксиом дээр суурилсан байна:

• associativity;
• коммутатив юм;
• шингээх;
• distributivity;
• нэмэгдэл.

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

хүснэгтийг дээр зураг зурах журам

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

зөв логик хүснэгтийг болгохын тулд, энэ нь мөрийн тоог тодорхойлох эхлэх шаардлагатай байна. Хэрхэн үүнийг хийх вэ? цогц илэрхийлэл бүрдүүлдэг хувьсагчийн тоог тоолох бөгөөд энгийн томъёог ашиглана: эрчим хүч N нь A = 2. Тэгээд - Энэ үнэний эмхэтгэсэн хүснэгт дэх мөрийн тоо, N - цогц логик үзэл бодлоо илэрхийлэх нэг хэсэг юм хувьсагчдын тоо юм.

Жишээ нь: комплекс илэрхийлэл гурван хувьсагчуудыг (A, В, С), дараа нь муу тэмдэг гурав дахь зэргийг барьж байх ёстой байдаг. B үнэн хүснэгт бид найман мөрийг байх болно юм. баганын гарчиг нэг мөрийг нэмнэ.

Дараа нь бид үзэл бодлоо чөлөөтэй илэрхийлэх нь эргэж, гүйцэтгэсэн үйл ажиллагааны дарааллыг тодорхойлно. өөрсдөө сайн захиалга харандаа тэмдэг (нэг, хоёр, гэх мэт).

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

Дараа нь та бидний хүснэгтийн малгайгаа бөглөх хэрэгтэй. Та доор энэ жишээг үзнэ үү.

Одоо аль болох хослолын дүүргэлтийн үргэлжлүүлье. Хоёр хувьсагчийн, тэд нь дараах байдалтай байна: 00, 01, 10, 11. гурван хувьд хувьсагчид: 000, 001, 010, 011, 100, 101, 110, 111.

дээр дурдсан бүх зүйлс үлдсэн эс болон үр дүнд хүснэгтийг бөглөх тооцоолох үргэлжлүүлэх болно дараа.

жишээ нь

A + B * А Урвуу: логик үзэл бодлоо илэрхийлэх эрх нь хүснэгтийг байгуулах жишээ нь үнэн юм Бид одоо үзэх

1. 2. шугамын тоо: 4 + 1 = 5 хувьсагчуудыг тоолно.
2. үйл ажиллагааны гүйцэтгэл зэрэг: Эхний Урвуу, хоёр дахь Холбоос, disjunction гурав.
3. Баганы тоо: 3 + 2 = 5.
4. нь дагах авах болон хүснэгтийг бөглөх.

"F = 1 хослол зүйлдээ", "хэдэн хослолууд хангасан F = 0" эсвэл: Дүрмээр бол, ажил энэ мэт сонсогдож байна. 1, хоёр дахь - - 00, 01, 11-Эхний асуултын хариулт байна.

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

• үгүйсгэх,
• үржүүлэх;
• нэмэлт.

ажил

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

1), 7 2) 6, 3), 5, 4) 4. тэдний зарим нь тайлан "Урвуу (жижиг A 6) + (5-аас бага A)" худал нь: А дөрвөн утгыг харгалзан?

Бидний Эхний багана нь утгын 7, 6, 5, 4-энэ дарааллаар шаардлагатай дүүрэн байх болно. Дараагийн баганад бид асуултанд хариулах ёстой: "? 6-аас бага" асуултын адил, зөвхөн одоо хариуд дүүрэн гурав дахь багана нь: "? 5-аас бага"

Бид үйл ажиллагааны дарааллыг тодорхойлно. үгүйсгэх disjunction давуу авдаг гэдгийг санаарай. Тиймээс бид нөхцөлд таарах утгын бөглөх дараагийн багана (A 6-аас бага) биш юм. Дөрөв дэх нь бидний асуудлын гол асуултанд хариулах болно. Та доорх хүснэгтийг бөглөх жишээг үзнэ үү.

Бид хариу тоо гэдгийг анхаарна уу, хуурамч илэрхийлэл А = 5 гэсэн утга нь энэ хариулт нь гурав дахь хувилбар юм.