Үл хамаарах зүйлийг шингээх, наалдуулах хуулиуд. Алгебрийн логикийн үндэс. Де Морганы хуулиудын үгийн томъёолол

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

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

Тэмдэглэгээ хийхэд хялбар болгох үүднээс бид хоёр логик хувьсагчийн логик алгебрийн үндсэн хуулиудыг танилцуулж байна АТэгээд IN.Эдгээр хуулиуд нь бусад логик хувьсагчдад мөн хамаарна.

1. Зөрчилдөөний хууль:

2. Хасах дундын тухай хууль:

3. Давхар үгүйсгэх хууль:

4. Де Морганы хуулиуд:

5. Давталтын хуулиуд: A&A=A; A v A = A; B & B = B; V v V = V.

6. Шингээх хуулиуд: А? (A & B) = A; A & (A ? B) = A.

7. Тогтмолуудыг арилгах хуулиуд: А? 1 = 1; А? 0 = A; A&1=A; A&0=0; Б? 1 = 1; Б? 0 = B; B&1=B; B & 0 = 0.

8. Наалт хийх хууль:

9. Эсрэг заалтын хууль: (A ? B) = (B ? A).

Логик хувьсагчийн хувьд математикийн ерөнхий хуулиуд бас хүчинтэй. Тэмдэглэгээ хийхэд хялбар болгох үүднээс бид гурван логик хувьсагчийн математикийн ерөнхий хуулиудыг танилцуулж байна A, B, C:

1. Солих хууль: A&B = B&A; А? B = B? А.

2. Холбооны хууль: A & (B & C) = (A & B) & C; А? (B ? C) = (A ? B) ? C.

3. Түгээлтийн хууль: A & (B ? C) = (A & B) ? (A & C).

Өмнө дурьдсанчлан, логик алгебрийн хуулиудыг ашиглан логик илэрхийллийг хялбарчлахын тулд ижил төстэй хувиргалтыг хийх боломжтой. Логикийн алгебр дээр хүлээн зөвшөөрөгдсөн конвенцид үндэслэн логик үйлдлүүдийг гүйцэтгэх дараах дүрмийг (тэргүүлэх чиглэл) тогтоодог: хаалтанд хийсэн үйлдлүүдийг эхлээд, дараа нь дараах дарааллаар гүйцэтгэнэ: урвуу (үгүйсгэх), холболт (&), салгах. (v), далд утга (?), эквивалент (?)

Жишээлбэл, логик функцийг хувиргацгаая

логик алгебрийн зохих хуулиудыг хэрэглэх замаар.

Алгебрын логикийн хичээлийн хуулиуд

илэрхийллийг хялбарчлахын тулд логик алгебрийн хуулиудыг хэрэглэж сурах;
логик сэтгэлгээг хөгжүүлэх;
сэтгэлгээг төлөвшүүлэх

Логикийн алгебрийн хуулиудын судалгаа (самбар дээр).

Бид тэдгээрийн хамгийн чухалыг жагсаав:

X X таних тухай хууль.
Зөрчилдөөний хууль
Оруулсан дундын хууль
Давхар үгүйсгэлийн хууль
Идпотентын хуулиуд: X X X, X X C
Хөрвөх чадварын хуулиуд (хөлжих чадвар): X Y Y X, X Y Y X
Холбооны хууль (хослол): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
Хуваарилалтын хууль (тархалт): X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
Де Морганы хуулиуд,
X 1 X, X 0 X
X 0 0, X 1 1

1-р хуульЭртний Грекийн гүн ухаантан Аристотель томъёолсон. Тодорхой байдлын тухай хуульд тодорхой мэдэгдэлд агуулагдах бодол нь энэ мэдэгдэл гарч ирсэн бүх аргументийн туршид өөрчлөгдөөгүй хэвээр байна гэж заасан байдаг.

Зөрчилдөөний хуульЯмар ч өгүүлбэр нь түүнийг үгүйсгэхтэй зэрэгцэн үнэн байж чадахгүй гэж хэлдэг. "Энэ алим боловсорч гүйцсэн", "Энэ алим болоогүй байна."

Оруулсан дундын хуульЭнэ мэдэгдэл нь үнэн эсвэл худал гэсэн хоёр л боломж байдаг гэж хэлсэн. Гурав дахь нь байхгүй. "Өнөөдөр би 5 авах болно, эсвэл авахгүй." Санал нь үнэн эсвэл үгүйсгэх юм.

Давхар үгүйсгэх хууль.Мэдэгдэлийн үгүйсгэлийг үгүйсгэх нь энэ мэдэгдлийг батлахтай адил юм.

“2*24 гэдэг нь худлаа”

Эрх мэдэлгүй байдлын хуулиуд.Логикийн алгебрт илтгэгч ба коэффициент гэж байдаггүй. Ижил "хүчин зүйлс" -ийн нэгдэл нь тэдгээрийн аль нэгтэй тэнцэнэ.

Солилцоо ба нэгдлийн хуулиуд.Холболт ба салгах нь ижил нэртэй үржүүлэх, нэмэх тэмдэгтэй төстэй.

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

Де Морганы хуулиудын утга учир(Augustus de Morgan (1806-1871) - Шотландын математикч, логикч) -ийг товч аман томъёогоор илэрхийлж болно.

- логик бүтээгдэхүүний үгүйсгэл нь хүчин зүйлсийн үгүйсгэлийн логик нийлбэртэй тэнцүү байна.

- логик нийлбэрийг үгүйсгэх нь нэр томьёоны үгүйсгэлийн логик үржвэртэй тэнцүү байна.

1. Мэдэгдэл нь тэнцүү эсэхийг тодорхойлно.

3. Үнэний хүснэгтийг ашиглан шингээлт, наалдацын хуулийг батал.

I. Шинэ материал ирүүлэх.

Шингээлтийн хууль: X (X Y) X, X (X Y) X
Наалт хийх хууль: (X Y) (Y) Y, (X Y) (Y) Y

Та логикийн хуулиудыг баталж чадна:

үнэний хүснэгтийг ашиглах;
эквивалентыг ашиглах.

Наалдамхай ба шингээлтийн хуулиудыг эквивалент ашиглан баталцгаая.

(X Y) (Y) (X+Y) *(+Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y(+1) ) Y холболт
X (X Y) X*X+X*Y X+X*Y X(1+Y) X шингээлт

P. Практик хэсэг

1. Томьёог хялбарчлах.

Жишээ 1. Томьёог хялбарчлах (A+B) * (A+C)

(A + B) * (A + C) A * A + A * C + B * A + B * C хаалтуудыг нээцгээе.
Идпотентын хуулийн дагуу A*A A , тиймээс A*A + A*C + B*A + B*C A + A*C + B*A + B*C
A ба A*C өгүүлбэрт бид А-г хаалтнаас гаргаж, A+1 1 шинж чанарыг ашиглан A+A*C+ B*A + B*C A*(1 + C) + B*A + B*-г авна. CA + B* A+B*C
3-р цэгтэй төстэй. Хаалтаас А мэдэгдлийг авч үзье.
A + B*A + B*C A (1 + B) + B C A + B*C

2. "Шингээлт" ба "холбох" өөрчлөлтүүд

Жишээ 2. A+ A*B илэрхийллийг хялбарчлах

Шийдэл. A+A*B A (1 + B) A - шингээлт

Жишээ 3. A*B+A* илэрхийллийг хялбарчлах

Шийдэл . A*B + A* A (B + ) A - наалт

3. Аливаа томьёог нийлмэл өгүүлбэрийн үгүйсгэл байхгүй байхаар өөрчилж болно - бүх үгүйсгэлт нь зөвхөн энгийн өгүүлбэрт хамаарна.

Жишээ 4. Нарийн төвөгтэй хэллэгийг үгүйсгэхгүй байхаар томьёог өөрчил.

Де Морганы томъёог ашиглаад дараахь зүйлийг олж авцгаая.
Илэрхийллийн хувьд бид де Морганы томъёог дахин ашиглавал бид дараахь зүйлийг авна.

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

логик нэмэх тэмдэг;
логик үржүүлэх тэмдэг,
ашиглагдах болно:
үгүйсгэх ба логик үржүүлэх тэмдэг
үгүйсгэх, логик нэмэх шинж тэмдэг.

Жишээ 5. Томьёог логик нэмэх тэмдэг ашиглахгүй байхаар хувирга.

Шийдэл. Давхар үгүйсгэх хуулийг, дараа нь Де Морганы томъёог ашиглая.

Дүгнэлт: Логикийн алгебрт аливаа логик функцийг бусад логик функцээр илэрхийлж болох боловч хамгийн багадаа 2 үйлдэл байх ёстой бөгөөд тэдгээрийн нэг нь үгүйсгэх байх ёстой.

Бүх үйлдлийг холбох ба үгүйсгэх, салгах ба үгүйсгэх, импликация ба үгүйсгэх зэргээр илэрхийлж болно. Бусад үйлдлүүдийг эквивалент ба үгүйсгэх замаар илэрхийлэх боломжгүй.

Дасгал 1.Мэдэгдэлийн үнэн зөвийг тогтооно уу.
Даалгавар 2Энэ мэдэгдэл нь тавтологи эсэхийг тодорхойлох уу?
Даалгавар 3.Мэдэгдэл нь тэнцүү эсэхийг тодорхойлох.

1. Логик нэмэлтийг арилгаснаар эдгээр мэдэгдлийн томъёог ижил утгатай болгон хувирга.

2. Логик үржүүлгийг арилгаснаар эдгээр мэдэгдлийн томьёог ижил утгатай болгон хувирга.

lunina.21205s09.edusite.ru

ЛОГИКИЙН ЕРТӨНЦ

Логикийн алгебрийн хууль, логик илэрхийллийг хувиргах дүрэм

Логик томъёоны эквивалент хувиргалт нь энгийн алгебрийн томъёоны хувиргалттай ижил зорилготой. Эдгээр нь логик алгебрийн үндсэн хуулиудыг ашиглан томъёог хялбарчлах эсвэл тодорхой хэлбэрт оруулахад үйлчилдэг.

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

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

Хууль

Томъёо

1. Баримтлалын хууль

Мэдэгдэл бүр өөртэйгөө адилхан байдаг.

2. хасагдсан дунд шатны хууль

Мэдэгдэл нь үнэн эсвэл худал байж болно, гуравдахь сонголт байхгүй. Иймээс мэдэгдэл, түүнийг үгүйсгэх логик нэмэлтийн үр дүн нь үргэлж "үнэн" гэсэн утгыг авдаг.

3. Зөрчилгүй байдлын хууль

Мэдэгдэл нь үнэн, худал аль аль нь байж болохгүй. Хэрэв X мэдэгдэл үнэн бол түүний үгүйсгэх БИШ X нь худал байх ёстой. Тиймээс мэдэгдэл ба түүнийг үгүйсгэх логик үржвэр нь худал байх ёстой.

4. Давхар сөрөгийн хууль

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

5. Аяллын (коммутатив) хууль

6. Хосолсон (ассоциатив) хууль

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

5. Хуваарилах (тараах) хууль

(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)

(X /\ Y) \/ Z = (X \/ Z) /\ (Y \/ Z)

Ерөнхий мэдэгдлийг хаалтнаас гаргах дүрмийг тодорхойлно.

7. Ерөнхий урвуу хууль Де Морганы хууль

Ерөнхий урвуу байдлын хууль.

8. Эквивалентийн хууль (идемпотенци)

Латин үгнээс idem - ижил ба potens - хүчтэй

Шингээлтийн алгебр логикийн хуулиуд

Сэдэв 3. Математик логикийн үндэс 1. Логик илэрхийлэл ба логик үйлдлүүд.
2. Үнэний хүснэгт ба логик функцийг байгуулах.
3. Логикийн хуулиуд ба логик илэрхийллийн хувиргалт.
Лабораторийн ажил No3. Математик логикийн үндэс.

3. Логикийн хуулиуд, логик илэрхийллийг хувиргах дүрэм

Давхар үгүйсгэлийн хууль (давхар үгүйсгэх нь үгүйсгэлийг арилгадаг):

А = = Ú

Эрх чөлөөний тухай хууль (Латин үгнээс idem - ижил ба potens - хүчтэй; шууд утгаараа - дүйцэхүйц):

логик нэмэхийн тулд: А У А = А ;

логик үржүүлэхийн тулд: A & A = A .

Хууль гэдэг нь илтгэгчгүй гэсэн үг.

логик үржүүлэхийн тулд: A&1=A, A&0=0 .

A&=0 .

Зөрчилтэй мэдэгдэл нэгэн зэрэг үнэн байх боломжгүй.

A Ú = 1 .

Нэг сэдвийн талаархи хоёр зөрчилтэй мэдэгдлийн нэг нь үргэлж үнэн, хоёр дахь нь худал, гурав дахь нь байдаггүй.

логик үржүүлэхийн тулд: A & (A Ú B) = A .

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

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

Логикийн хуулиудыг зөрчих нь логик алдаа, үүнээс үүдэлтэй зөрчилдөөнд хүргэдэг.

Жишээ 1. Томьёог хялбарчлах (A Ú B) ба (A Ú C) .

Өмнөх догол мөртэй адил мэдэгдлийг хаалтнаас хасъя А .
A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C .

Ийнхүү бид хуваарилалтын хуулийг батлав.

Аливаа томьёог нарийн төвөгтэй мэдэгдлийн үгүйсгэлийг агуулаагүйн тулд өөрчилж болно - бүх үгүйсгэлт нь зөвхөн энгийн мэдэгдлүүдэд хамаарна.

Жишээ 2. Үүссэн томьёо нь нарийн төвөгтэй мэдэгдлийн үгүйсгэлийг агуулаагүй байхаар илэрхийллийг хялбарчлаарай.

Шийдэл:

Санал алгебрийн хуулиуд

Санал алгебр (логикийн алгебр) нь өгүүлбэр дээрх логик үйлдлүүд болон нарийн төвөгтэй мэдэгдлийг хувиргах дүрмийг судалдаг математик логикийн хэсэг юм.

Олон асуудлыг шийдэхэд логик асуудлуудНөхцөлүүдийг нь албан ёсны болгох замаар олж авсан томъёог хялбарчлах нь ихэвчлэн шаардлагатай байдаг. Санал алгебр дахь томъёог хялбарчлах нь үндсэн логик хуулиудад суурилсан эквивалент хувиргалт дээр суурилдаг.

Санал алгебрын хуулиуд (логикийн алгебр) - Эдгээр нь тавтологи юм.

Заримдаа эдгээр хуулиудыг теорем гэж нэрлэдэг.

Санал алгебрт логик хуулиудыг эквивалент томъёоны тэгш байдлын хэлбэрээр илэрхийлдэг. Хуулиудын дотроос нэг хувьсагч агуулсан хууль бусдаас ялгардаг.

Доорх эхний дөрвөн хууль нь саналын алгебрын үндсэн хуулиуд юм.

Баримтлалын хууль:

A=A

Үзэл баримтлал, шүүлт бүр өөртэйгөө ижил байдаг.

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

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

Үндэслэлд: Хөдөлгөөн бол мөнхийн. Сургууль руу алхах нь хөдөлгөөн юм. Тиймээс, үүрд сургуульд явахдаа "хөдөлгөөн" гэдэг үгийг хоёр өөр утгаар ашигладаг (эхнийх нь - философийн утгаараа - материйн шинж чанар, хоёр дахь нь - өдөр тутмын утгаар - орон зайд шилжих үйл ажиллагаа). энэ нь буруу дүгнэлтэд хүргэдэг.

Зөрчилгүй байдлын хууль :

Яг тэр мөчид мэдэгдэл нь үнэн эсвэл худал байж болно, гуравдахь сонголт байхгүй. А нь үнэн эсвэл үгүй A. Хасах дундын хуулийг биелүүлэх жишээ:

1. 12345 тоо тэгш эсвэл сондгой, гуравдахь сонголт байхгүй.

2. Компани нь алдагдалтай буюу алдагдалтай ажилладаг.

3. Энэ шингэн нь хүчил байж болно, үгүй ч байж болно.

Хасагдсан дундын хууль нь бүх логикчид хүлээн зөвшөөрсөн хууль биш бөгөөд логикийн бүх нийтийн хууль юм. Энэ хууль нь танин мэдэхүй нь "эсвэл - эсвэл", "үнэн-худал" гэсэн хатуу нөхцөл байдлыг шийдвэрлэхэд хамаарна. Тодорхойгүй байдал үүссэн тохиолдолд (жишээ нь, ирээдүйн талаар бодоход) хасагдсан дундын хуулийг хэрэглэх боломжгүй байдаг.

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

Энэ жишээн дэх парадокс (грек. paradoxos - гэнэтийн, хачирхалтай) нь өгүүлбэр нь өөртэйгөө холбоотой байдгаас үүдэлтэй. Өөр нэг алдартай парадокс бол үсчинтэй холбоотой асуудал юм: Нэг хотод үсчин өөрөө үсээ засдаг хүмүүсээс бусад бүх оршин суугчдын үсийг тайрдаг. Үсчний үсийг хэн тайрдаг вэ? Логикийн хувьд албан ёсны байдлаасаа болоод ийм өөрт нь хандсан мэдэгдлийн хэлбэрийг олж авах боломжгүй юм. Энэ нь логикийн алгебрын тусламжтайгаар бүх боломжит бодол санаа, аргументуудыг илэрхийлэх боломжгүй гэсэн санааг дахин баталж байна. Саналын эквивалентийн тодорхойлолт дээр үндэслэн саналын алгебрийн үлдсэн хуулиудыг хэрхэн олж авч болохыг харцгаая.

Жишээ нь, А нь юутай тэнцэх (тэнцэх) болохыг тодорхойлъё (А-г давхар үгүйсгэх, өөрөөр хэлбэл, А-г үгүйсгэхийг үгүйсгэх). Үүний тулд бид үнэний хүснэгтийг байгуулна:

Эквивалентийн тодорхойлолтоор бид утгууд нь А баганын утгатай давхцах баганыг олох ёстой. Энэ нь А багана болно.

Тиймээс бид давхар үгүйсгэлийн хуулийг томъёолж болно:

Хэрэв та мэдэгдлийг хоёр удаа үгүйсгэвэл үр дүн нь анхны мэдэгдэл болно. Жишээлбэл, мэдэгдэл A = Матроскин - муурнь А мэдэгдэлтэй тэнцүү байна = Матроскин бол муур биш гэдэг нь худлаа.

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

Тогтмолуудын шинж чанарууд:

Эрх мэдлийн хуулиуд:

Зурагт асаалттай, эсвэл зурагт асаалттай, эсвэл зурагт асаалттай гээд хичнээн ч удаа давтсан ч гэсэн үгийн утга өөрчлөгдөхгүй. Үүний нэгэн адил давтан хэлэхэд гадаа дулаахан, гадаа дулаахан, ... нэг хэмээр дулаарахгүй.

Солих хуулиуд:

A v B = B v A

A & B = B & A

Дизюнкц болон коньюнкцийн үйлдлээр А ба В операндуудыг сольж болно.

Холбооны хуулиуд:

A v(B v C) = (A v B) v C;

A & (B & C) = (A & B) & C.

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

Хуваарилалтын хуулиуд:

A v (B ба C) = (A v B) &(A v C)

(дизьюнкцийн тархалт
холболттой холбоотой)

A & (B v C) = (A & B) v (A & C)

(холбооны тархалт
салгах тухай)

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

Шингээх хууль:

A v (A & B) = A

A & (A v B) = A

Шингээлтийн хуулиудыг өөрөө батал.

Де Морганы хуулиуд:

Де Морганы хуулиудын үг хэллэг:

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

Де Морганы хуулийн хэрэгжилтийн жишээ:

1) Би араб, хятад хэл мэддэг гэсэн нь худлаа байна, би араб хэл мэдэхгүй, хятад хэл мэдэхгүй гэсэнтэй ижил байна.

2) Би хичээл сурсан, муу дүн авсан гэдэг нь худлаа байна. Би хичээл сураагүй, эсвэл муу дүн аваагүй гэсэн үгтэй ижил байна.

Дэгдэлт ба эквивалентийн үйлдлүүдийг орлуулах

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

Тиймээс далд үйлдлийг дараах дүрмийн дагуу сольж болно.

Эквивалент үйлдлийг солих хоёр дүрэм байдаг:

Хоёр таних тэмдгийн баруун болон зүүн талд үнэний хүснэгтийг байгуулах замаар эдгээр томъёоны үнэн зөвийг шалгахад хялбар байдаг.

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

Дараах жишээг авч үзье.

Мэдэгдэл өгье:

E = Тэмцээнд түрүүлбэл шагнал авна гэдэг худлаа.

Болъё A = Би тэмцээнд түрүүлнэ,

B = Би шагнал авах болно.

Дараа нь

Эндээс, E = Би тэмцээнд түрүүлнэ, гэхдээ би шагнал авахгүй.

Логик алгебрийн таван хууль байдаг:

1. Нэг элементийн хууль

1 * X = X
0 * X = 0
1 + X = 1
0 + X = X

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

Дээд хоёр илэрхийлэл нь шилжүүлэгчийг барихад хэрэг болно, учир нь "2I" элементийн оролтын аль нэгэнд логик тэг эсвэл нэгийг оруулснаар та гаралт руу дохио дамжуулах эсвэл гаралт дээр тэг потенциал үүсгэх боломжтой.

Эдгээр илэрхийллийг ашиглах хоёр дахь сонголт бол олон оронтой тооны тодорхой цифрүүдийг сонгон тэглэх боломж юм. "AND" үйлдлийг битээр гүйцэтгэхдээ та битийн өмнөх утгыг орхиж эсвэл харгалзах битүүдэд нэгж эсвэл тэг потенциалыг ашигласнаар битийн өмнөх утгыг тэг болгож болно. Жишээлбэл, та 6, 3, 1-ийн цифрүүдийг дахин тохируулах хэрэгтэй. Дараа нь:

Логик алгебрын хуулиудыг ашиглах өгөгдсөн жишээн дээр масканд шаардлагатай цифрүүдийг (доод тоо) дахин тохируулахын тулд харгалзах цифрүүдийн оронд тэгийг, үлдсэн цифрүүдэд нэгийг бичсэн нь тодорхой харагдаж байна. Анхны тоонд (дээд тоо) 6 ба 1-р оронгийн оронд нэг тоо байна. "AND" үйлдлийг хийсний дараа эдгээр газруудад тэг гарч ирнэ. Анхны дугаарын гурав дахь оронгийн оронд тэг байна. Үүссэн тоо нь мөн энэ газарт тэгийг агуулна. Асуудлын нөхцлийн дагуу үлдсэн цифрүүд өөрчлөгдөөгүй.

Үүний нэгэн адил логик алгебрийн үндсэн хуулиудын нэг болох нэг элементийн хуулийг ашиглан нэгжийг өөрт хэрэгтэй цифрээр бичиж болно. Энэ тохиолдолд нэг элементийн хуулийн доод хоёр илэрхийллийг ашиглах шаардлагатай. “OR” үйлдлийг битээр гүйцэтгэхдээ та битийн өмнөх утгыг орхиж эсвэл харгалзах битүүдэд тэг эсвэл нэг потенциал тавьж тэг болгож болно. Та тооны 7 ба 6-р битүүдэд нэгж бичихийг хүсч байна гэж бодъё. Дараа нь:

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

Ганц хаалганы тухай хуулийн эхний ба сүүлчийн илэрхийлэл нь олон тооны оролттой, цөөн тооны оролттой логик хаалга болгон ашиглах боломжийг олгодог. Үүнийг хийхийн тулд AND хэлхээний ашиглагдаагүй оролтыг 1-р зурагт үзүүлсэн шиг тэжээлийн эх үүсвэрт холбох ёстой.

Зураг 1. "3I-NOT" логик элемент дээр хэрэгжсэн "2I-NOT" хэлхээ

Үүний зэрэгцээ OR хэлхээнд ашиглагдаагүй оролтууд нь дан элементийн хуулийн дагуу 2-р зурагт үзүүлсэн шиг хэлхээний нийтлэг утсанд холбогдсон байх ёстой.

Зураг 2. “2I-NOT” элемент дээр хэрэгжсэн “БИШ” хэлхээ

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

2. Үгүйсгэх хуулиуд

а. Нэмэлт элементүүдийн тухай хууль

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

Логик алгебрийн өөр нэг өргөн хэрэглэгддэг хууль бол давхар үгүйсгэлийн хууль юм.

б. Хоёр удаа үгүй

Давхар үгүйсгэх хуулийг логик илэрхийллийг хялбарчлах (мөн үүний үр дүнд дижитал комбинаторын хэлхээний зардлыг хялбарчлах, багасгах), "2 БА-БИШ" ба "2 ЭСВЭЛ-БИШ" гэх мэт логик элементүүдийн дараа дохионы урвуу байдлыг арилгахад ашигладаг. . Энэ тохиолдолд логик алгебрийн хуулиуд нь хязгаарлагдмал логик элементүүдийг ашиглан өгөгдсөн тоон хэлхээг хэрэгжүүлэх боломжийг олгодог.

в. Сөрөг логикийн хууль

Сөрөг логикийн хууль нь олон тооны хувьсагчдад хүчинтэй. Логик алгебрийн энэхүү хууль нь логик элементүүдийг ашиглан "OR"-ыг хэрэгжүүлэх боломжийг олгодог ба эсрэгээр: "AND" логик элементүүдийг ашиглан "OR" логик функцийг хэрэгжүүлэх. Энэ нь ялангуяа TTL хэлхээнд ашигтай байдаг, учир нь "AND" логик хаалгыг хэрэгжүүлэхэд хялбар байдаг ч "OR" логик хаалгыг хэрэгжүүлэхэд нэлээд хэцүү байдаг. Сөрөг логикийн хуулийн ачаар "AND" логик элементүүд дээр "OR" элементүүдийг хэрэгжүүлэх боломжтой болсон. Зураг 3-т "2OR" логик элементийн хэрэгжилтийг " " элемент болон хоёр инвертер дээр харуулав.

Зураг 3. "2I-NOT" элемент болон хоёр инвертер дээр хэрэгжсэн "2OR" логик элемент.

"OR" хэлхээний утаснуудын талаар ижил зүйлийг хэлж болно. Шаардлагатай бол энэ хэлхээний оролт гаралт дээр инвертер ашиглан угсрах "БА" болгон хувиргаж болно.

3. Хосолсон хуулиуд

Логик алгебрийн хослолын хуулиуд нь ердийн алгебрийн хослолын хуулиудтай ихээхэн нийцдэг боловч бас ялгаа байдаг.

а. Тавтологийн хууль (олон давталт)

X + X + X + X = X
X * X * X * X = X

Логик алгебрийн энэхүү хууль илүү олон оролттой логик хаалгануудыг цөөн оролттой логик хаалга болгон ашиглах боломжийг олгодог. Жишээлбэл, та хоёр оролттой "2I" хэлхээг "3I" логик элемент дээр Зураг 4-т үзүүлсэн шиг хэрэгжүүлж болно.

Зураг 4. “3I-БИШ” логик элемент дээр хэрэгжсэн “2I-NOT” хэлхээ

эсвэл "2 БА-БИШ" хэлхээг 5-р зурагт үзүүлсэн шиг ердийн инвертер болгон ашиглах:

Зураг 5. "2I-NOT" логик элемент дээр хэрэгжсэн "БИШ" хэлхээ.

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

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

Логик алгебрийн хуулиудыг үргэлжлүүлэн авч үзье.

б. хөдөлгөөний хууль

A + B + C + D = A + C + B + D

в. хослолын хууль

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

г. хуваарилалтын хууль

X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /бид үүнийг хаалт нээж нотлох болно/ =
= X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3

4. Шингээх дүрэм (нэг хувьсагч бусдыг шингээдэг)

X1 + X1X2X3 =X1(1 + X2X3) = X1

5. Наалт хийх дүрэм (зөвхөн нэг хувьсагчийг гүйцэтгэдэг)

Энгийн математикийн нэгэн адил логикийн алгебрт үйлдлүүдийн тэргүүлэх чиглэл байдаг. Энэ тохиолдолд хамгийн түрүүнд хийх зүйл бол:

Хаалтанд хийсэн үйлдэл
Нэг операнд бүхий үйлдэл (нэг байрлалтай үйлдэл) - "БИШ"
Холбоос - "Ба"
Салгах - "OR"
Модули хоёр нийлбэр.

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

Уран зохиол:

"Логикийн алгебрийн хуулиуд" нийтлэлийн хамт уншина уу:

Санах ойгүй аливаа логик хэлхээг үнэний хүснэгтээр бүрэн дүрсэлсэн байдаг... Үнэний хүснэгтийг хэрэгжүүлэхийн тулд зөвхөн тэдгээр мөрүүдийг авч үзэхэд хангалттай...
http://site/digital/SintSxem.php

Декодерууд (декодерууд) нь зарим төрлийн хоёртын кодыг бусад руу хөрвүүлэх боломжийг олгодог. Жишээлбэл...
http://site/digital/DC.php

Ихэнх тохиолдолд дижитал тоног төхөөрөмж хөгжүүлэгчид эсрэгээрээ асуудалтай тулгардаг. Та наймтын эсвэл аравтын тооллын шугаман кодыг хөрвүүлэх хэрэгтэй...
http://site/digital/Coder.php

Мультиплексор нь олон оролтыг нэг гаралтад холбох боломжийг олгодог төхөөрөмжүүд юм...
http://site/digital/MS.php

Демултиплексорууд нь төхөөрөмжүүд... Мультиплексороос мэдэгдэхүйц ялгаа нь...
http://site/digital/DMS.php

Дискрет математик: Математик логик

Лекц 8

Булийн функцийг багасгах. Квин-Мак-Класки арга

Булийн алгебрийн хуулиуд

Математик логикт логик үржүүлэх, логик нэмэх, үгүйсгэх (  , +, -) үйлдлүүдийг агуулсан Буль алгебр хэмээх тусгай алгебрийг тодорхойлсон бөгөөд энэ нь логик илэрхийллийг адилхан хувиргах боломжийг олгодог. Эдгээр хуулиудад

Бие даасан байдлын хууль (ижил байдал)

Орлуулалтын хууль

a  b = b a

Холбооны хууль

a + (b + c) = (a + b) + c

a  (b  c) = (a  b)  c

Тархалтын хуулиуд

Дизьюнкцтэй харьцуулахад холболтын тархалт

A  (b + c) = a  b + a  c

Холбогчтой харьцуулахад дизьюнкцийн тархалт

A + b  c = (a + b)  (a + c)

давхар үгүйсгэх хууль

Де Морганы хуулиуд

Шингээх хуулиуд

a + a  b = a

a  (a + b) = a

0 ба 1 логик тогтмолуудтай үйлдлийг тодорхойлох хуулиуд

a + 0 = a

a  0 = 0

a+1=1

a  1 = a

1 = 0

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

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

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

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

Блэйк-Порецкийн хууль

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

Логик илэрхийллийн эвдрэлийн хууль

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

Логик функцуудыг хялбарчлах

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

Даалгаврууд.

SDNF-ийг дараах функцээр хялбарчлах:

1. (а б)  в

2. (а б)  в

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

SDNF =

Цаашид хялбарчлах боломжгүй.

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

SDNF =
5.

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

Квин-Мак-Класки арга

Логик функцийг багасгах ажлыг дөрвөн үе шатаас бүрдэх Quine-McCluskey аргыг ашиглан хийж болно.

Функц үнэн байх олонлогуудыг (бүрэлдэхүүнүүдийг) хоёртын эквивалент хэлбэрээр төлөөлүүлье.
Хоёртын эквивалентуудыг шатлал (хоёртын эквивалентийн нэгжийн тоогоор) ба цавуу (харгалзах бүрэлдэхүүн хэсгүүдэд наах дүрмийг хэрэглэнэ) зэрэгт байрлуулж, хамгийн их интервалыг олж авцгаая; Бид наалдсан багц бүрийг тэмдэглэнэ. Зөвхөн эдгээр олонлогууд эсвэл интервалууд нийлдэг бөгөөд тэдгээрийн ялгаа нь зөвхөн нэг оронтой тоонд байна: 001 ба 000, 001- ба 101- гэх мэт.
Баганууд нь функцийн хоёртын үнэний олонлогтой, мөрүүд нь хамгийн их интервалтай тохирч байгаа Квин хүснэгтийг байгуулъя. Хэрэв i-р олонлогийг j-р интервалаар бүрхсэн бол бид харгалзах мөр, баганын огтлолцол дээр 1-ийг тавина, эс тэгвээс бид 0 эсвэл юу ч биш.
Бид Квин хүснэгтийн хамгийн бага хамрах хүрээг олдог бөгөөд энэ нь функц нь үнэн байх бүх залгууруудыг багтаасан (хамрах) хамгийн их интервалуудын хамгийн бага тооноос бүрддэг.

F1 функцийг авч үзье (1, 3, 5, 7, 11, 13, 15). Энэ функцийн төгс салгах хэвийн хэлбэр нь дараахтай тэнцүү байна.

Жинхэнэ олонлогуудын хоёртын эквивалентууд нь:

1	0001
3	0011
5	0101
7	0111
11	1011
13	1101
15	1111

Хоёртын багцуудыг шатлал болгон байрлуулж, аль болох урт наалт хийцгээе

0001  	00-1 	0-1
0011  	0-01 	--11
0101  	-011 	-1-1
0111   	0-11  
1101  	-101 
1011  	01-1  
1111   	11-1 
	-111  
	1-11 

Дараа нь бид Квин хүснэгтийг бүтээдэг:

	0001	0011	0101	0111	1011	1101	1111
0--1	1	1	1	1
--11		1		1	1	1	1
-1-1			1	1		1	1

Манай хүснэгтэд 0001 ба 1011 олонлогуудыг цорын ганц боломжит байдлаар тусгасан тул тэдгээрийг хамарсан хамгийн бага интервалыг гэж нэрлэдэг. заавал байх ёстойболон хэлбэр бүрэх гол, учир нь ямар ч бүрээсэнд орсон байх ёстой. Хүснэгтэд харгалзах нэгжүүдийн доогуур зурсан байна; интервалууд (0- -1,- -11) нь зөвхөн үндсэн хамрах хүрээг бүрдүүлдэг төдийгүй Квин хүснэгтийг бүхэлд нь хамардаг.
Тиймээс бид судалж буй функцийн хамгийн бага хэлбэрийг дараах хэлбэрээр олж авсан.

MDNF = (0 - - 1, - - 1 1) =

Хэд хэдэн жишээг харцгаая.
Даалгаврууд.

1. MDNF функцуудыг олохе1 =

x1 x2 x3 x4
0 0 0 0	0
0 0 0 1	1
0 0 1 0	1
0 0 1 1	1
0 1 0 0	1
0 1 0 1	0
0 1 1 0	0
0 1 1 1	1
1 0 0 0	0
1 0 0 1	1
1 0 1 0	1
1 0 1 1	1
1 1 0 0	0
1 1 0 1	1
1 1 1 0	0
1 1 1 1	1

Судалж буй функцийн төгс DNF нь дараах хэлбэртэй байна.

0001 	00-1 	-0-1
0010 	-001 	-01-
0100	001- 	--11
0011 	-010 	1-1
1010 	0-11 
1001 	-011 
0111 	101- 
1011 	10-1 
1101 	1-01 
1111 	-111 
	1-11 
	11-1 

Эхний баганад ямар ч нэгтгэхэд оролцоогүй олонлог агуулагддаг - энэ нь өөрөө хамгийн их интервал 0100. Гурав дахь баганад дөрвөн дээд интервал нэмж байна: (-0-1, -01-, --11, 1 --1).

Бид Квин хүснэгтийг бүтээдэг:

	0001	0010	0100	0011	1010	1001	0111	1011	1101	1111
0100			1
-0-1	1					1		1	1
-01-		1		1	1			1
--11				1			1	1		1
1--1						1		1	1	1

Заавал хийх интервалуудыг багтаасан хамрах хүрээний үндсэн хэсгийг тодорхойлъё.

(0100, -0-1, -01-, --11). Энэ тохиолдолд хамрах хүрээ нь хүснэгтийг бүхэлд нь хамарна.

Хамгийн бага салалтын хэвийн хэлбэр f1 нь:

2. MDNF функцуудыг ол е 2( x 1, x 2, x 3), 0,2,3,6, 7-р багц дээр нэг утгыг авна.

Үнэний хүснэгтийг бүтээцгээе е2

x1 x2 x3	F2
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	1
1 0 0	0
1 0 1	0
1 1 0	1
1 1 1	1

SDNF =
Хоёртын багцуудыг шатлал болгон байрлуулж, наалт хийцгээе.

000 	0-0 	--0
010 	-00 
100 	-10 
110 	1-0 
111 	11-

Цавуулалтын үр дүнд бид зөвхөн хоёр хамгийн их интервалыг авсан: (11-, --0). Quine хүснэгтийг бүтээхгүйгээр тэд хамгийн бага хамрах хүрээг бүрдүүлдэг нь ойлгомжтой, учир нь Эдгээр интервалын аль нэгийг нь хасвал f2(x1, x2, x3) функц ажиллах олонлог алдагдах болно. ) үнэн. MDNF = x1 x2 +x3.

Уран зохиол

Гусева А.И. Компьютерийн шинжлэх ухааныг сурах: асуудал, тэдгээрийг шийдвэрлэх арга. - М.: DIALOG-MEPhI, 2003.
Горбатов В.А. Дискрет математикийн үндэс. - М .: Шинжлэх ухаан. Физматлит, 1999.-544 он

Логик- сэтгэлгээний хууль, хэлбэрийг судалдаг шинжлэх ухаан; үндэслэл ба нотлох аргын тухай сургаал.

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

Үзэл баримтлал- бие даасан объект эсвэл нэг төрлийн объектын ангиллын чухал шинж чанарыг тусгасан сэтгэлгээний хэлбэр. Хэл дэх ойлголтууд үгээр илэрхийлэгддэг.

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

Дараахь ойлголтуудын харилцааг эзлэхүүнээр нь ялгадаг.

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

Шүүх- энэ бол объект, шинж чанар, тэдгээрийн харилцааны талаар ямар нэг зүйлийг батлах эсвэл үгүйсгэх сэтгэлгээний хэлбэр юм.

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

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

Алгебрын жишээ: натурал тооны алгебр, рационал тооны алгебр, олон гишүүнтийн алгебр, векторын алгебр, матрицын алгебр, олонлогын алгебр гэх мэт. Логикийн алгебр буюу Булийн алгебрын объектууд нь саналууд юм.

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

Мэдэгдэл бүр үнэн эсвэл худал байдаг; Энэ нь хоёулаа нэгэн зэрэг байж болохгүй.

Байгалийн хэлээр мэдэгдэл нь тунхаг өгүүлбэрээр илэрхийлэгддэг. Өгүүлбэр, асуух өгүүлбэр нь мэдэгдэл биш юм.

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

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

Энгийн хэллэгүүдээс бүрдсэн мэдэгдлийг дуудна нийлмэл(төвөгтэй).

Логик алгебр дахь энгийн мэдэгдлүүдийг латин том үсгээр тэмдэглэнэ.
А= (Аристотель - логикийг үндэслэгч),
IN= (Банана алимны мод дээр ургадаг).

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

Үнэн мэдэгдлийг 1, худалыг 0 гэж оноодог. Тиймээс, А = 1, IN = 0.

Логикийн алгебр нь мэдэгдлийн семантик агуулгаас хийсвэрлэгдсэн байдаг. Тэрээр зөвхөн нэг баримтыг сонирхож байна - өгөгдсөн мэдэгдэл үнэн эсвэл худал эсэх нь нийлмэл мэдэгдлийн үнэн эсвэл худал байдлыг алгебрийн аргаар тодорхойлох боломжийг олгодог.

Санал алгебрийн үндсэн үйлдлүүд.

Логик үйлдэл CONJUNCTION(лат. conjunctio - би холбогддог):

байгалийн хэлээр бол холболттой тохирч байна Тэгээд;
тэмдэглэгээ: & ;
Програмчлалын хэл дээрх тэмдэглэгээ нь: болон;
өөр нэр: логик үржүүлэх.

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

Холболтын үнэний хүснэгт:

А	IN	А&IN
0	0	0
0	1	0
1	0	0
1	1	1

DISJUNCTION логик үйлдэл(лат. disjunctio - би ялгаж байна):

Дизюнкц гэдэг нь хоёр энгийн өгүүлбэр бүрийг нийлмэл өгүүлбэртэй холбодог логик үйлдэл бөгөөд эхний өгүүлбэр хоёулаа худал, түүнийг бүрдүүлж буй хоёр мэдэгдлийн ядаж нэг нь үнэн байвал худал болно.

Дизьюнкцийн үнэний хүснэгт:

А	IN	АIN
0	0	0
0	1	1
1	0	1
1	1	1

Логик үйлдэл INVERSION(Латин инверсио - эргүүлэх):

Үгүйсгэх гэдэг нь энгийн өгүүлбэр бүрийг нийлмэл өгүүлбэртэй холбодог логик үйлдэл бөгөөд энэ нь анхны хэллэгийг үгүйсгэж байгаагаас бүрддэг.

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

А	А биш
0	1
1	0

Логик нэмэх функц OR (LogValue1;LogValue2;...) нь ядаж нэг логик аргумент ҮНЭН (1) үед л ҮНЭН (Үнэн) утгыг өгнө.

Логик үгүйсгэх функц NOT (LogValue) нь логик аргумент нь ХУДАЛ (0) үед ҮНЭН (Үнэн) утгыг, харин эсрэгээр логик аргумент нь ҮНЭН (1) үед ХУДАЛ (Худал) утгыг өгдөг.

Логик үйл ажиллагаа(лат. implicatio - нягт холбох):

Нөхцөл (эхний өгүүлбэр) үнэн, үр дагавар (хоёр дахь мэдэгдэл) худал байвал хоёр энгийн өгүүлбэр бүрийг худал нийлмэл өгүүлбэртэй холбодог логик үйлдэл юм.

Үр дагаварын үнэний хүснэгт:

А	IN	АIN
0	0	1
0	1	1
1	0	0
1	1	1

Логик үйлдэл EQUIVALENCE(лат. aequivalens - эквивалент):

байгалийн хэлээр бол ярианы дүрстэй тохирч байна дараа нь, зөвхөн дараа ньТэгээд хэрвээ мөн л бол;
тэмдэглэгээ: ~ ;
өөр нэр: эквивалент.

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

Эквивалент үнэний хүснэгт:

А	IN	А~IN
0	0	1
0	1	0
1	0	0
1	1	1

Логик үйлдлүүд нь дараах тэргүүлэх ач холбогдолтой: хаалтанд хийх үйлдлүүд, урвуу, &, , ~.

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

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

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

хувьсагчийн тоог тоол nлогик илэрхийлэлд;
Хүснэгт дэх мөрийн тоог тодорхойлно м = 2 n ;
томьёоны логик үйлдлүүдийн тоог тоолох;
хаалт, тэргүүлэх чиглэлийг харгалзан логик үйлдлүүдийн дарааллыг тогтоох;
Хүснэгт дэх баганын тоог тодорхойлох: хувьсагчийн тоог нэмсэн үйлдлийн тоо;
0-ээс 2 хүртэлх n битийн хоёртын тоонуудын натурал цувралыг төлөөлж буйг харгалзан оролтын хувьсагчдын багцыг бичих. n -1;
4-р зүйлд заасан дарааллын дагуу логик үйлдлүүдийг хийж, үнэний хүснэгтийн баганыг баганаар дүүргэнэ.

Алдаа гарахаас зайлсхийхийн тулд оролтын хувьсагчийн багцыг дараах байдлаар жагсаахыг зөвлөж байна.
a) оролтын хувьсагчийн багцын тоог тодорхойлох;
б) эхний хувьсагчийн утгын баганыг хагасаар хувааж, баганын дээд хэсгийг 0, доод хэсгийг -1-ээр дүүргэнэ;
в) хоёр дахь хувьсагчийн утгын баганыг дөрвөн хэсэгт хувааж, улирал бүрийг 0 бүлгээс эхлэн 0 эсвэл 1-ийн ээлжлэн бүлгүүдээр дүүргэнэ;
г) дараагийн хувьсагчдын утгын баганыг 8, 16 гэх мэтээр үргэлжлүүлэн хуваах. хэсгүүд болон 0 ба 1-р бүлгүүд нэг тэмдэгтээс бүрдэх хүртэл 0 эсвэл 1-ийн бүлгүүдээр дүүргэнэ.

Жишээ. A&(B C) томьёоны хувьд үнэний хүснэгтийг алгебрийн аргаар болон хүснэгт ашиглан байгуул.

Логик хувьсагчийн тоо 3 тул үнэний хүснэгтийн мөрийн тоо 2 3 = 8 байх ёстой.

Томъёоны логик үйлдлүүдийн тоо 5 тул үнэний хүснэгтийн баганын тоо 3 + 5 = 8 байх ёстой.

А	IN	C	INC	А & (INC)
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Логик (Боолийн) функцфункцийг дуудна F(X 1, X 2, ..., X n), хэний аргументууд X 1, X 2, ..., X n(бие даасан хувьсагч) ба функц өөрөө (хамааралтай хувьсагч) 0 эсвэл 1 утгыг авна.

Логик функц нь түүний аргументуудын утгуудын бүх хослолын хувьд ямар утгыг авахыг харуулсан хүснэгтийг логик функцийн үнэний хүснэгт гэж нэрлэдэг. Логик функцийн үнэний хүснэгт n 2 аргумент агуулсан nшугам, nаргументын утгуудын багана ба функцийн утгын 1 багана.

Логик функцуудыг хүснэгт хэлбэрээр эсвэл аналитик хэлбэрээр - тохирох томъёо хэлбэрээр зааж өгч болно.

Хэрэв логик функцийг салгах, холбогч, урвуу байдлаар дүрсэлсэн бол энэ дүрслэлийн хэлбэрийг гэнэ. хэвийн.

Хоёр хувьсагчийн 16 өөр логик функц байдаг.

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

Логикийн алгебрт логик илэрхийллийг ижил төстэй хувиргах боломжийг олгодог хэд хэдэн хууль байдаг. Эдгээр хуулиудыг тусгасан харилцааг танилцуулъя.

Давхар үгүйсгэлийн хууль:
биш (А биш) = А.
Давхар сөрөг нь сөрөг талыг арилгадаг.
Аялал жуулчлалын хууль:
- логик нэмэхийн тулд:
A B = B A;

A&B = B&A.
Мэдэгдэл дээр хийсэн үйлдлийн үр дүн нь эдгээр мэдэгдлийг авах дарааллаас хамаарахгүй.
Хосолсон (ассоциатив) хууль:
- логик нэмэхийн тулд:
(A B) C = A (B C);
Логик үржүүлэхийн тулд:
(A & B) & C = A & (B & C).
Тэмдгүүд нь ижил байвал хаалтанд дур мэдэн байрлуулж эсвэл бүрмөсөн орхиж болно.
Түгээлтийн хууль:
- логик нэмэхийн тулд:
(A B) & C = (A & C) (B & C);
Логик үржүүлэхийн тулд:
(A & B) C = (A C) & (B C).
Ерөнхий мэдэгдлийг хаалтнаас гаргах дүрмийг тодорхойлно.
Ерөнхий урвуу хууль (де Морганы хуулиуд):
- логик нэмэхийн тулд:
;
Логик үржүүлэхийн тулд:
.
Идемпотентын хууль (Латин үгнээс idem - ижил ба potens - хүчтэй; шууд утгаараа - дүйцэхүйц):
- логик нэмэхийн тулд:
A A = A;
Логик үржүүлэхийн тулд:
A & A = A.
Хууль гэдэг нь илтгэгчгүй гэсэн үг.
Тогтмолуудыг арилгах хуулиуд:
- логик нэмэхийн тулд:
A 1 = 1, A 0 = A;
Логик үржүүлэхийн тулд:
A & 1 = A, A & 0 = 0.
Зөрчилдөөний хууль:
A & (А биш)= 0.
Зөрчилтэй мэдэгдэл нэгэн зэрэг үнэн байх боломжгүй.
Гурав дахь нь хасах тухай хууль:
A (А биш) = 1.
Нэг сэдвийн талаархи хоёр зөрчилтэй мэдэгдлийн нэг нь үргэлж үнэн, хоёр дахь нь худал, гурав дахь нь байдаггүй.
Шингээх хууль:
- логик нэмэхийн тулд:
A(A&B)=A;
Логик үржүүлэхийн тулд:
A & (A B) = A.
Хасагдах хууль (наалт):
- логик нэмэхийн тулд:
(A & B) (& B) = B;
Логик үржүүлэхийн тулд:
(A B) & (B) = B.
Эсрэг заалтын хууль (урвуулах дүрэм):
(AB) = (BA).
Дээрх хуулиудын үнэн зөвийг хүснэгтийн аргаар баталж болно: A ба B утгын бүх багцыг бичиж, тэдгээрт нотлогдсон илэрхийллийн зүүн ба баруун талын утгыг тооцоолж, гарсан баганууд давхцаж байна.

Жишээ.Логик илэрхийллийг хялбарчлах:

Ефимова О., Морозов В., Угринович Н. Компьютерийн шинжлэх ухааны үндэстэй компьютерийн технологийн курс. Зааварахлах сургуулийн хувьд. - М.: "АСТ хэвлэлийн газар" ХХК; ABF, 2000
Компьютерийн шинжлэх ухааны асуудлын ном-семинар. 2 боть / Ed. I. Semakina, E. Henner. - М.: Суурь мэдлэгийн лаборатори, 2001 он.
Угринович Н. Компьютерийн шинжлэх ухаан, мэдээллийн технологи. 10-11-р анги - М.: Суурь мэдлэгийн лаборатори, "Москвагийн сурах бичиг" ХК, 2001 он.

"Албан ёсны логикийн үндэс" сэдэвт асуудал, тестүүд

DBMS логик хандалт - Логик-математик загварууд 10-р анги
Хичээл: 5 Даалгавар: 9 Тест: 1
Математик логик ашиглан логик асуудлыг шийдвэрлэх
Хичээл: 4 Даалгавар: 6 Тест: 1

Эрхэм оюутан!

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

"Компьютерийн харилцаа холбоо. Интернэт" сэдэв сүүлийн үед ихээхэн сонирхол татаж байгаа бөгөөд олон залуучууд бараг бүх чөлөөт цагаа дэлхийн сүлжээнд өнгөрөөдөг. Интернэтийг эзэмшсэн байх нь зөвхөн интернетээр аялах, сонирхолтой "чат"-уудаар үе үе зочлох чадвар төдийгүй дэлхийн сүлжээн дэх мэдээллийг зохион байгуулах зарчмуудыг ойлгох, түүнийг ойлгох чадвар гэдгийг танд сануулмаар байна. бүтэц, протокол, хөтч, шуудангийн программыг тохируулах чадвартай байх, интернетийн ёс зүйг мэдэж, дагаж мөрдөх. Мэдээжийн хэрэг, сүлжээг хамгийн чухал зорилгодоо ашиглах - хүрээгээ тэлэх.

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

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