Asosan: demo Yagona davlat imtihonlari variantlari 2015 yil uchun informatika fanidan Lyudmila Leonidovna Bosova darsligi asosida

Oldingi 1-qismda biz siz bilan Disjunction va Conjunction mantiqiy operatsiyalarini muhokama qildik, biz uchun faqat inversiyani tahlil qilish va Yagona davlat imtihonini hal qilishga o'tish qoladi.

Inversiya

Inversiya- har bir gapni yangi gap bilan bog'laydigan, ma'nosi asliyatiga qarama-qarshi bo'lgan mantiqiy operatsiya.

Inversiya yozish uchun quyidagi belgilar ishlatiladi: NOT, `¯`, ` ¬ `

Inversiya quyidagi haqiqat jadvali bilan aniqlanadi:

Inversiya boshqacha tarzda mantiqiy inkor deb ataladi.

Har qanday murakkab bayonot shaklda yozilishi mumkin mantiqiy ifoda— mantiqiy o‘zgaruvchilar, mantiqiy operator belgilari va qavslarni o‘z ichiga olgan ifodalar. Mantiqiy ifodadagi mantiqiy amallar quyidagi tartibda bajariladi: inversiya, konyunksiya, diszyunksiya. Qavslar yordamida amallar tartibini o'zgartirishingiz mumkin.

Mantiqiy amallar quyidagi ustuvorlikka ega: inversiya, konyunksiya, diszyunksiya.

Shunday qilib, bizning oldimizda 2015 yil informatika bo'yicha Yagona davlat imtihonidan 2-sonli vazifa turibdi

Aleksandra F iborasi uchun haqiqat jadvalini to'ldirayotgan edi. U faqat jadvalning kichik bir qismini to'ldirishga muvaffaq bo'ldi:

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

F qanday ifoda bo'lishi mumkin?

Muammoni hal qilishni ancha osonlashtiradigan narsa F murakkab ifodaning har bir versiyasida faqat bitta mantiqiy amal mavjud: ko'paytirish yoki qo'shish. Ko'paytirish holatida /\ agar kamida bitta o'zgaruvchi nolga teng bo'lsa, u holda butun F ifodaning qiymati ham nolga teng bo'lishi kerak. Va V qo'shilgan taqdirda, agar kamida bitta o'zgaruvchi birga teng bo'lsa, u holda butun F ifodaning qiymati 1 ga teng bo'lishi kerak.

F ifodasining 8 ta o‘zgaruvchisining har biri uchun jadvaldagi ma’lumotlar biz uchun yechish uchun yetarli.

1-sonli ifodani tekshiramiz:

• ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
• jadvalning ikkinchi qatoridan x1=1, x4=0 F ning mumkin ekanligini va boshqa barcha o'zgaruvchilar 1 ga teng bo'lsa = 1 ga teng bo'lishi mumkinligini ko'ramiz (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
• jadvalning uchinchi qatoriga ko'ra x4=1, x8=1 F=0 ekanligini ko'ramiz (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ) va jadvalda bizda F=1 bor va bu birinchi raqamli ifoda biz uchun ekanligini bildiradi ALBATTA MUVOFIQ EMAS.

2-sonli ifodani tekshiramiz:

• jadvalning birinchi qatoridan x2=0, x8=1 F ning mumkin ekanligini va boshqa barcha o'zgaruvchilar 0 ga teng bo'lsa = 0 ga teng bo'lishi mumkinligini ko'ramiz (? V 0 V ? V ? V ? V ? V ? V 0 )
• jadvalning ikkinchi qatoridan x1=1, x4=0 F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
• jadvalning uchinchi qatoriga ko'ra x4=1, x8=1 F mumkin va agar qolgan o'zgaruvchilardan kamida bittasi 1 ga teng bo'lsa = 1 ga teng bo'lishi mumkinligini ko'ramiz ( ? V ? V ? V 0 V ? V ? V ? V 0 )
  

3-sonli ifodani tekshiramiz:

• jadvalning birinchi qatoridan x2=0, x8=1 F=0 ekanligini ko'ramiz (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
• jadvalning ikkinchi qatoridan x1=1, x4=0 F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), va jadvalda biz F=1 ga egamiz va bu uchinchi raqamli ifoda bizga berishini anglatadi ALBATTA MUVOFIQ EMAS.

4-sonli ifodani tekshiramiz:

• jadvalning birinchi qatoridan x2=0, x8=1 F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), va jadvalda biz F=0 ga egamiz va bu to'rtinchi raqamli ifoda bizga berishini anglatadi ALBATTA MUVOFIQ EMAS.

Yagona davlat imtihonida topshiriqni hal qilishda siz xuddi shu narsani qilishingiz kerak: jadvaldagi ma'lumotlarga asoslanib, mutlaqo mos kelmaydigan variantlardan voz keching. Qolgan mumkin bo'lgan variant(bizning holatimizda bo'lgani kabi, 2-variant) to'g'ri javob bo'ladi.

Ifodaning haqiqatini aniqlash muammosi ko'plab fanlar oldida turadi. Har qanday dalil intizomi dalillarning haqiqatligi uchun ba'zi mezonlarga asoslanishi kerak. Ushbu mezonlarni o'rganadigan fan mantiq algebrasi deb ataladi. Mantiq algebrasining asosiy postulati shundan iboratki, har qanday eng bezakli bayonot haqiqat yoki noto'g'riligini aniqlash oson bo'lgan soddaroq bayonotlarning algebraik ifodasi sifatida ifodalanishi mumkin.

Bayonot ustidagi har qanday “algebraik” amal uchun asl bayonotning haqiqat yoki noto‘g‘riligiga asoslangan holda o‘zgartirilgan bayonotning haqiqat yoki noto‘g‘riligini aniqlash qoidasi belgilanadi. Bu qoidalar orqali yozilgan ifoda haqiqat jadvallari. Haqiqat jadvallarini tuzishdan oldin siz mantiq algebrasi bilan ko'proq tanishishingiz kerak.

Mantiqiy ifodalarning algebraik o'zgarishlari

Har qanday mantiqiy ifoda, shuningdek, uning o'zgaruvchilari (bayonotlari) ikkita qiymatni oladi: yolg'on yoki haqiqat. Yolg'on nol bilan, haqiqat esa bitta bilan belgilanadi. Ta'rif sohasini va qabul qilinadigan qiymatlar diapazonini tushunib, biz mantiq algebrasi operatsiyalarini ko'rib chiqishimiz mumkin.

Inkor qilish

Inkor va inversiya- eng oddiy mantiqiy transformatsiya. U "yo'q" zarrachasiga mos keladi. Ushbu o'zgartirish shunchaki bayonotni o'zgartiradi. Shunga ko'ra, bayonotning ma'nosi ham aksincha o'zgaradi. Agar A bayonoti to'g'ri bo'lsa, "A emas" noto'g'ri. Masalan, "to'g'ri burchak to'qson gradusga teng burchakdir" degan gap to'g'ri. Keyin uning "to'g'ri burchak to'qson gradusga teng emas" degan inkori yolg'ondir.

Inkor qilish uchun haqiqat jadvali shunday bo'ladi:

Ajralish

Bu operatsiya bo'lishi mumkin oddiy yoki qattiq, ularning natijalari har xil bo'ladi.

Odatiy diszyunksiya yoki mantiqiy qo‘shilish “yoki” birikmasiga mos keladi. Unga kiritilgan gaplardan kamida bittasi to'g'ri bo'lsa, to'g'ri bo'ladi. Masalan, "Yer dumaloq yoki uchta ustun ustida turadi" iborasi to'g'ri bo'ladi, chunki birinchi bayonot to'g'ri, ikkinchisi noto'g'ri bo'lsa-da, jadvalda u quyidagicha ko'rinadi:

Qattiq disjunksiya yoki modul qo'shish ham deyiladi "eksklyuziv yoki". Bu amal “ikkidan biri: yo... yoki...” grammatik konstruksiya shaklini olishi mumkin. Bu erda mantiqiy ifodaning qiymati, agar unga kiritilgan barcha gaplar bir xil haqiqatga ega bo'lsa, noto'g'ri bo'ladi. Ya'ni, ikkala bayonot birgalikda to'g'ri yoki birgalikda yolg'ondir.

Eksklyuziv jadval yoki

Implication va ekvivalentlik

Buning ma'nosi shundan iborat oqibat va grammatik jihatdan “A dan keyin B” deb ifodalanishi mumkin. Bu yerda A mulohazasi asos, B esa oqibat deb ataladi. Izoh faqat bitta holatda yolg'on bo'lishi mumkin: agar asos to'g'ri bo'lsa va natija noto'g'ri bo'lsa. Ya'ni, yolg'on haqiqatdan kelib chiqmaydi. Boshqa barcha holatlarda, ma'no haqiqatdir. Ikkala bayonot ham bir xil haqiqatga ega bo'lgan variantlar savol tug'dirmaydi. Lekin nima uchun noto'g'ri asosdan haqiqiy natija haqiqatdir? Gap shundaki, har qanday narsa noto'g'ri asosdan kelib chiqishi mumkin. Bu implikatsiyani ekvivalentlikdan ajratib turadigan narsa.

Matematikada (va boshqa ko'rgazmali fanlarda) zaruriy shartni ko'rsatish uchun implikatsiya qo'llaniladi. Masalan, A bayonoti “O nuqta uzluksiz funksiyaning ekstremumidir”, B bayonoti “O nuqtadagi uzluksiz funksiyaning hosilasi nolga aylanadi”. Agar O uzluksiz funksiyaning ekstremum nuqtasi bo'lsa, bu nuqtadagi hosila haqiqatan ham nolga teng bo'ladi. Agar O ekstremum nuqta bo'lmasa, unda bu nuqtadagi hosila nolga teng bo'lishi mumkin yoki bo'lmasligi mumkin. Ya'ni, B A uchun zarur, lekin etarli emas.

Izoh uchun haqiqat jadvali quyida bayon qilinganidek:

Ekvivalentlikning mantiqiy ishlashi mohiyatan o'zaro ta'sir. "A B ga ekvivalent" degani bir vaqtning o'zida "A dan B dan keyin" va "B dan A dan keyin" degan ma'noni anglatadi. Ikkala bayonot ham bir vaqtning o'zida to'g'ri yoki bir vaqtning o'zida yolg'on bo'lsa, ekvivalentlik to'g'ri bo'ladi.

Matematikada ekvivalentlik zarur va yetarli shartni aniqlash uchun ishlatiladi. Masalan, A - "O nuqta uzluksiz funktsiyaning ekstremum nuqtasi", B - "O nuqtada funktsiyaning hosilasi nolga aylanadi va ishorani o'zgartiradi." Bu ikki bayonot ekvivalentdir. B A uchun zarur va etarli shartni o'z ichiga oladi. E'tibor bering, in bu misolda B iboralari aslida ikkita boshqasining birikmasidir: "O nuqtadagi hosila nolga aylanadi" va "O nuqtadagi hosila belgini o'zgartiradi".

Boshqa mantiqiy funktsiyalar

Yuqorida biz tez-tez ishlatiladigan asosiy mantiqiy operatsiyalarni muhokama qildik. Qo'llaniladigan boshqa funktsiyalar mavjud:

• Schaeffer zarbasi yoki mos kelmasligi A va B birikmalarining inkori hisoblanadi
• Pirsning o'qi dis'yunksiyani inkor etishning muvaffaqiyatsizligini anglatadi.

Haqiqat jadvallarini qurish

Har qanday mantiqiy ifoda uchun haqiqat jadvalini tuzish uchun siz algoritmga muvofiq harakat qilishingiz kerak:

1. Ifodani oddiy iboralarga ajrating va har birini o'zgaruvchi sifatida belgilang.
2. Mantiqiy o'zgarishlarni aniqlang.
3. Ushbu o'zgarishlarning tartibini aniqlang.
4. Kelajakdagi jadvaldagi qatorlarni hisoblang. Ularning soni N ning kuchiga ikkiga teng, bu erda N - o'zgaruvchilar soni, shuningdek, jadval sarlavhasi uchun bitta qator.
5. Ustunlar sonini aniqlang. U o'zgaruvchilar soni va harakatlar soni yig'indisiga teng. Agar bu mantiqiy bo'lsa, har bir harakat natijasini yangi o'zgaruvchi sifatida ko'rsatishingiz mumkin.
6. Sarlavha ketma-ket to'ldiriladi, birinchi navbatda barcha o'zgaruvchilar, so'ngra bajarilgan harakatlar natijalari.
7. Jadvalni birinchi o'zgaruvchi bilan to'ldirishni boshlashingiz kerak. Uning uchun chiziqlar soni yarmiga bo'lingan. Yarim yarmi nollar bilan, ikkinchisi esa birlar bilan to'ldirilgan.
8. Har bir keyingi o'zgaruvchi uchun nollar va birliklar ikki baravar tez-tez almashtiriladi.
9. Shu tarzda, barcha o'zgaruvchilar va oxirgi ustunlar to'ldiriladi o'zgaruvchan qiymat har bir satrda o'zgarishlar.
10. Keyin barcha harakatlarning natijalari ketma-ket to'ldiriladi.

Natijada, oxirgi ustunda o'zgaruvchilar qiymatiga qarab butun ifodaning qiymati ko'rsatiladi.

haqida alohida ta'kidlash kerak mantiqiy harakatlar tartibi. Uni qanday aniqlash mumkin? Bu erda, algebrada bo'lgani kabi, harakatlar ketma-ketligini belgilaydigan qoidalar mavjud. Ular quyidagi tartibda amalga oshiriladi:

1. qavs ichidagi ifodalar;
2. inkor qilish yoki inversiya;
3. birikma;
4. qat'iy va odatiy ajratish;
5. imo-ishora;
6. ekvivalentlik.

Misollar

Materialni birlashtirish uchun siz ilgari aytib o'tilgan mantiqiy ifodalar uchun haqiqat jadvalini yaratishga harakat qilishingiz mumkin. Keling, uchta misolni ko'rib chiqaylik:

• Schaeffer insult.
• Pirsning o'qi.
• Ekvivalentlik ta'rifi.

Schaeffer insult

Schaeffer zarbasi mantiqiy ifoda bo'lib, uni "(A va B) emas" deb yozish mumkin. Ikkita o'zgaruvchi va ikkita harakat mavjud. Bog‘lovchi qavs ichida, ya’ni birinchi bo‘lib bajariladi. Jadvalda sarlavha va o'zgarmaydigan qiymatlari bo'lgan to'rtta qator, shuningdek, to'rtta ustun bo'ladi. Keling, jadvalni to'ldiramiz:

Qo‘shma gapning inkori inkorlarning diszyunksiyasiga o‘xshaydi. Buni “A emas yoki B emas” iborasi uchun haqiqat jadvalini tuzish orqali tekshirish mumkin. Buni o'zingiz bajaring va bu erda allaqachon uchta operatsiya bo'lishini unutmang.

Pirsning o'qi

“(A yoki B) emas” dis’yunksiyasining inkorini ifodalovchi Pirs o‘qini hisobga olib, uni “A emas va B emas” inkorlari birikmasi bilan taqqoslaylik. Keling, ikkita jadvalni to'ldiramiz:

Ifodalarning ma'nolari bir-biriga mos tushdi. Bu ikki misolni o‘rganib chiqqanimizdan so‘ng, inkordan keyin qavsni qanday ochish kerakligi haqida xulosa qilishimiz mumkin: inkor qavs ichidagi barcha o‘zgaruvchilarga, qo‘shma o‘zgarishlar dis’yunktsiyaga, dis’yunksiya o‘zgarishi esa bog‘lanishga nisbatan qo‘llaniladi.

Ekvivalentlik ta'rifi

A va B mulohazalar haqida faqat va agar A dan B dan kelib chiqsa va B A dan kelib chiqsa, ular ekvivalent deb aytishimiz mumkin. Keling, buni mantiqiy ifoda sifatida yozamiz va unga haqiqat jadvalini tuzamiz. "(A B ga ekvivalent) (A dan B dan keyin) va (B dan A dan keyin) ga ekvivalentdir.

Ikkita o'zgaruvchi va beshta harakat mavjud. Biz jadval tuzamiz:

Oxirgi ustundagi barcha qiymatlar to'g'ri. Bu shuni anglatadiki, yuqoridagi ekvivalentlik ta'rifi A va B ning har qanday qiymatlari uchun to'g'ri keladi. Bu har doim to'g'ri ekanligini anglatadi. Aynan shunday haqiqat jadvalidan foydalanish har qanday ta'riflar va mantiqiy konstruktsiyalarning to'g'riligini tekshirishingiz mumkin.

Dars davomiyligi: 45 min

Dars turi: birlashtirilgan:

• bilimlarni tekshirish - og'zaki ish;
• yangi material - ma'ruza;
• konsolidatsiya - amaliy mashg'ulotlar;
• bilimlarni tekshirish - mustaqil ish uchun topshiriqlar.

Dars maqsadlari:

• haqiqat jadvali tushunchasini berish;
• "Takliflar algebrasi" oldingi darsdagi materialni mustahkamlash;
• foydalanish axborot texnologiyalari;
• yangi materialni mustaqil izlash ko'nikmalarini shakllantirish;
• qiziqish va tashabbusni rivojlantirish;
• axborot madaniyatini tarbiyalash.

Dars rejasi:

1. Tashkiliy vaqt (2 daqiqa).
2. O‘tgan dars materialini takrorlash (og‘zaki so‘rov) (4 min).
3. Yangi materialni tushuntirish (12 daqiqa).
4. Mustahkamlash

• amaliy ish (5 daqiqa);
• amaliy mashqlar (10 min);
• mustaqil ish uchun topshiriqlar (10 min).

Uskunalar va dasturiy ta'minot materiallari:

• oq taxta;
• multimedia proyektori;
• kompyuterlar;
• MS PowerPoint 2003 taqdimot muharriri;
• tarqatma ma'lumotnoma "Haqiqat jadvallari";
• "Haqiqat jadvali" taqdimoti namoyishi.

Darslar davomida

I. Tashkiliy moment

Biz "Mantiq asoslari" mavzusini o'rganishni davom ettiramiz. Oldingi darslarda biz mantiq kundalik hayotimiz bilan chambarchas bog'liqligini ko'rdik va deyarli har qanday gapni formula sifatida yozish mumkinligini ham ko'rdik.

II. Oldingi dars materialini takrorlash

Keling, asosiy ta'riflar va tushunchalarni eslaylik:

III. Yangi materialni tushuntirish

Oxirgi ikkita misol murakkab gaplarga tegishli. Murakkab gaplarning haqiqatini qanday aniqlash mumkin?

Hisoblanganligini aytdik. Shu maqsadda mantiqda qo`shma (murakkab) gaplarning haqiqatini hisoblash jadvallari mavjud. Bular haqiqat jadvallari deb ataladi.

Demak, dars mavzusi HAQIQAT JADVALLARI.

3.1) Ta'rif. Haqiqat jadvali - bu kiritilgan o'zgaruvchilarning barcha mumkin bo'lgan qiymatlari uchun murakkab bayonotning haqiqatini ko'rsatadigan jadval (1-rasm).

3.2) Keling, har bir mantiqiy operatsiyani uning ta'rifiga muvofiq batafsil ko'rib chiqaylik:

1. Inversiya (inkor) har bir oddiy gapni qo‘shma gap bilan bog‘laydigan mantiqiy amal bo‘lib, dastlabki gapning inkor etilishini bildiradi.

Ushbu operatsiya faqat bitta o'zgaruvchiga tegishli, shuning uchun faqat ikki chiziqlar, chunki bitta o'zgaruvchida bittadan bo'lishi mumkin ikki qiymatlar: 0 yoki 1.

2. Bog‘lanish (ko‘paytirish) mantiqiy amal bo‘lib, har ikki oddiy gapni har ikkala dastlabki gap ham to‘g‘ri bo‘lgandagina rost bo‘ladigan qo‘shma gap bilan bog‘laydi.

Ushbu jadval haqiqatan ham ko'paytirish jadvaliga o'xshashligini ko'rish oson.

3. Dizyunksiya (qo‘shish) mantiqiy amal bo‘lib, har ikki oddiy gapni ikkala boshlang‘ich gap ham yolg‘on bo‘lsa, yolg‘on bo‘lgan qo‘shma gap bilan bog‘laydi.

Jadvalning oxirgi bosqichdan tashqari qo'shimchalar jadvaliga o'xshashligiga ishonch hosil qilishingiz mumkin. Ikkilik sanoq sistemasida 1 + 1 = 10, o‘nlik sanoq sistemasida – 1 + 1 = 2. Mantiqda 2 o‘zgaruvchining qiymati mumkin emas, mantiq nuqtai nazaridan 10 ni ko‘rib chiqamiz: 1 – rost, 0. - yolg'on, ya'ni. 10 bir vaqtning o'zida to'g'ri va noto'g'ri, bu bo'lishi mumkin emas, shuning uchun oxirgi harakat qat'iy ravishda ta'rifga asoslanadi.

4. Implication (quyidagi) mantiqiy amal bo‘lib, har bir ikki oddiy gapni shart rost va oqibat noto‘g‘ri bo‘lganda yolg‘on bo‘lgan qo‘shma gap bilan bog‘laydi.

5. Ekvivalentlik (ekvivalentlik) har ikki oddiy gapni qo‘shma gap bilan bog‘laydigan mantiqiy amal bo‘lib, har ikkala boshlang‘ich mulohazalar bir vaqtda to‘g‘ri yoki yolg‘on bo‘lgandagina rost bo‘ladi.

Oxirgi ikkita operatsiyani biz oldingi darsda muhokama qildik.

3.3) Keling, buni ko'rib chiqaylik Haqiqat jadvali algoritmi murakkab bayonot uchun:

3.4) Murakkab bayonot uchun haqiqat jadvalini tuzish misolini ko'rib chiqing:

Misol. Formula uchun haqiqat jadvalini tuzing: A U B -> ¬A U C.

Yechim (2-rasm)

Misol shuni ko'rsatadiki, haqiqat jadvali butun qaror emas, balki faqat oxirgi harakat (qizil rang bilan belgilangan ustun).

IV. Mustahkamlash.

Materialni mustahkamlash uchun sizdan a, b, c va qo'shimcha ravishda d-g harflari ostidagi misollarni o'zingiz hal qilishingiz so'raladi (3-rasm).

V. Uyga vazifa, materialni umumlashtirish.

Uy vazifasi ham sizga monitor ekranida beriladi (4-rasm)

Materialning qisqacha mazmuni: Bugun darsda biz qo'shma gaplarning haqiqatini qanday aniqlashni bilib oldik, lekin ko'proq matematik nuqtai nazardan, chunki sizga bayonotlarning o'zi emas, balki ularni aks ettiruvchi formulalar berilgan. Keyingi darslarda biz ushbu ko'nikmalarni mustahkamlaymiz va ularni mantiqiy muammolarni hal qilishda qo'llashga harakat qilamiz.

Ta'rif 1

Mantiqiy funktsiya– o‘zgaruvchilari ikkita qiymatdan birini oladigan funksiya: $1$ yoki $0$.

Har qanday mantiqiy funktsiyani haqiqat jadvali yordamida aniqlash mumkin: barcha mumkin bo'lgan argumentlar to'plami jadvalning chap tomonida, mantiqiy funktsiyaning tegishli qiymatlari o'ng tomonida yoziladi.

Ta'rif 2

Haqiqat jadvali- tarkibidagi oddiy ifodalarning barcha mumkin bo'lgan qiymatlari to'plami uchun murakkab ifoda qanday qiymatlarni olishini ko'rsatadigan jadval.

Ta'rif 3

Ekvivalent haqiqat jadvallarining oxirgi ustunlari mos keladigan mantiqiy ifodalar deyiladi. Ekvivalentlik $«=»$ belgisi yordamida ko'rsatiladi.

Haqiqat jadvalini tuzishda quyidagi mantiqiy operatsiyalar tartibini hisobga olish kerak:

1-rasm.

Amallar tartibini bajarishda qavslar ustunlik qiladi.

Mantiqiy funksiyaning haqiqat jadvalini tuzish algoritmi

Qatorlar sonini aniqlang: qatorlar soni= $2^n + 1$ (sarlavha qatori uchun), $n$ – oddiy ifodalar soni. Masalan, ikkita o'zgaruvchining funktsiyalari uchun $2^2 = 4$ o'zgaruvchilar qiymatlari to'plami, uchta o'zgaruvchining funktsiyalari uchun $2^3 = 8$ va boshqalar mavjud.

Ustunlar sonini aniqlang: ustunlar soni = o'zgaruvchilar soni + mantiqiy operatsiyalar soni. Mantiqiy amallar sonini aniqlashda ularni bajarish tartibi ham hisobga olinadi.

Ustunlarni mantiqiy operatsiyalar natijalari bilan to'ldiring asosiy mantiqiy operatsiyalarning haqiqat jadvallarini hisobga olgan holda ma'lum bir ketma-ketlikda.

2-rasm.

1-misol

$D=\bar(A) \vee (B \vee C)$ mantiqiy ifodasi uchun haqiqat jadvalini tuzing.

Yechim:

Keling, qatorlar sonini aniqlaymiz:

qatorlar soni = $2^3 + 1=9$.

O'zgaruvchilar soni - $3$.

1. teskari ($\bar(A)$);
2. ajralish, chunki u qavs ichida ($B \vee C$);

3. disjunction ($\overline(A)\vee \left(B\vee C\right)$) zarur mantiqiy ifodadir.

   Ustunlar soni = $3 + 3=6$.

Mantiqiy amallarning haqiqat jadvallarini hisobga olgan holda jadvalni to'ldiramiz.

3-rasm.

2-misol

Ushbu mantiqiy ifodadan foydalanib, haqiqat jadvalini tuzing:

Yechim:

Keling, qatorlar sonini aniqlaymiz:

Oddiy iboralar soni $n=3$, ya'ni

qatorlar soni = $2^3 + 1=9$.

Ustunlar sonini aniqlaymiz:

O'zgaruvchilar soni - $3$.

Mantiqiy operatsiyalar soni va ularning ketma-ketligi:

1. inkor qilish ($\bar(C)$);
2. ajralish, chunki u qavs ichida ($A \vee B$);
3. birikma ($(A\vee B)\bigwedge \overline(C)$);
4. inkor, biz buni $F_1$ bilan belgilaymiz ($\overline((A\vee B)\bigwedge \overline(C))$);
5. disjunksiya ($A \vee C$);
6. birikma ($(A\vee C)\bigwedge B$);
7. inkor, biz buni $F_2$ bilan belgilaymiz ($\overline((A\vee C)\bigwedge B)$);

8. disjunction - kerakli mantiqiy funktsiya ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Ko'rsatmalar. Klaviaturadan kiritishda quyidagi belgilardan foydalaning: Masalan, abc+ab~c+a~bc mantiqiy ifodasi quyidagicha kiritilishi kerak: a*b*c+a*b=c+a=b*c
Mantiqiy diagramma shaklida ma'lumotlarni kiritish uchun ushbu xizmatdan foydalaning.

Mantiqiy funktsiyani kiritish qoidalari

1. v (ajralish, OR) belgisi o'rniga + belgisidan foydalaning.
2. Mantiqiy funktsiyadan oldin funktsiya belgilanishini belgilashning hojati yo'q. Masalan, F(x,y)=(x|y)=(x^y) o'rniga (x|y)=(x^y) ni kiritish kifoya.
3. O'zgaruvchilarning maksimal soni - 10 ta.

Kompyuterning mantiqiy sxemalarini loyihalash va tahlil qilish matematikaning maxsus bo'limi - mantiq algebrasi yordamida amalga oshiriladi. Mantiq algebrasida uchta asosiy mantiqiy funktsiyani ajratish mumkin: "EMAS" (inkor), "VA" (birlashma), "OR" (dizyunksiya).
Har qanday mantiqiy qurilmani yaratish uchun chiqish o'zgaruvchilarning har birining mavjud kirish o'zgaruvchilarga bog'liqligini aniqlash kerak, bu bog'liqlik kommutatsiya funktsiyasi yoki mantiqiy algebra funktsiyasi deb ataladi.
Mantiqiy algebra funktsiyasi, agar uning barcha 2n qiymatlari berilgan bo'lsa, to'liq aniqlangan deb ataladi, bu erda n - chiqish o'zgaruvchilari soni.
Agar barcha qiymatlar aniqlanmagan bo'lsa, funktsiya qisman aniqlangan deb ataladi.
Qurilmaning holati mantiqiy algebra funktsiyasi yordamida tasvirlangan bo'lsa, u mantiqiy deb ataladi.
Mantiqiy algebra funksiyasini ifodalash uchun quyidagi usullardan foydalaniladi:

• og'zaki tavsif - dastlabki loyihalash bosqichida qo'llaniladigan va shartli tasvirga ega bo'lgan shakl.
• mantiqiy algebra funksiyasining haqiqat jadvali ko'rinishida tavsifi.
• mantiqiy algebra funktsiyasini algebraik ifoda ko'rinishida tavsiflash: FAL ning ikkita algebraik shakli qo'llaniladi:
  A) DNF - disjunktiv normal shakl elementar mantiqiy mahsulotlarning mantiqiy yig'indisidir. DNF quyidagi algoritm yoki qoida yordamida haqiqat jadvalidan olinadi:
  1) jadvalda chiqish funktsiyasi =1 bo'lgan o'zgaruvchilar qatorlari tanlangan.
  2) o'zgaruvchilarning har bir qatori uchun mantiqiy ko'paytma yoziladi; Bundan tashqari, =0 o'zgaruvchilar inversiya bilan yoziladi.
  3) hosil bo'lgan mahsulot mantiqiy ravishda umumlashtiriladi.
  Fdnf= X 1 *X 2 *X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
  Agar barcha o'zgaruvchilar bir xil daraja yoki tartibda bo'lsa, DNF mukammal deyiladi, ya'ni. Har bir ish to'g'ridan-to'g'ri yoki teskari shakldagi barcha o'zgaruvchilarni o'z ichiga olishi kerak.
  b) CNF - kon'yunktiv normal shakl elementar mantiqiy yig‘indilarning mantiqiy hosilasidir.
  CNF ni quyidagi algoritm yordamida haqiqat jadvalidan olish mumkin:
  1) chiqish funktsiyasi =0 bo'lgan o'zgaruvchilar to'plamini tanlang
  2) har bir o'zgaruvchilar to'plami uchun elementar mantiqiy yig'indi yozamiz va =1 o'zgaruvchilar inversiya bilan yoziladi.
  3) olingan miqdorlar mantiqiy ravishda ko'paytiriladi.
  Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  CNF mukammal deb ataladi, agar barcha o'zgaruvchilar bir xil darajaga ega bo'lsa.

1-rasm - Mantiqiy qurilma diagrammasi

Mantiq algebrasining barcha amallari aniqlangan haqiqat jadvallari qiymatlar. Haqiqat jadvali operatsiya natijasini aniqlaydi hamma mumkin x asl bayonotlarning mantiqiy qiymatlari. Amallarni qo'llash natijasini aks ettiruvchi variantlar soni mantiqiy ifodadagi gaplar soniga bog'liq bo'ladi. Agar mantiqiy ifodadagi gaplar soni N bo'lsa, u holda haqiqat jadvali 2 N qatorni o'z ichiga oladi, chunki mumkin bo'lgan argument qiymatlarining 2 N xil kombinatsiyasi mavjud.

NO operatsiyasi - mantiqiy inkor (inversiya)

• agar asl ifoda rost bo'lsa, uni inkor qilish natijasi noto'g'ri bo'ladi;
• agar asl ifoda noto'g'ri bo'lsa, uni inkor qilish natijasi to'g'ri bo'ladi.

OR operatsiyasi - mantiqiy qo'shish (ajralish, birlashma)

AND operatsiyasi - mantiqiy ko'paytirish (bog'lanish)

"IF-THEN" operatsiyasi - mantiqiy natija (ma'no)

"A, agar va faqat B" operatsiyasi (ekvivalentlik, ekvivalentlik)

"Qo'shimcha moduli 2" operatsiyasi (XOR, eksklyuziv yoki qat'iy ajratish)

Mantiqiy operatsiyalarning ustuvorligi

• Qavslar ichidagi amallar
• Inversiya
• Bog'lovchi (&)
• Disjunction (V), Exclusive OR (XOR), yig'indisi moduli 2
• Izoh (→)
• Ekvivalentlik (↔)

Mukammal disjunktiv normal shakl

1. Formulaning har bir mantiqiy atamasi F(x 1,x 2,...x n) funksiyaga kiritilgan barcha o‘zgaruvchilarni o‘z ichiga oladi.
2. Formulaning barcha mantiqiy shartlari boshqacha.
3. Birorta ham mantiqiy atama o'zgaruvchini va uning inkorini o'z ichiga olmaydi.
4. Formuladagi hech qanday mantiqiy atama bir xil o'zgaruvchini ikki marta o'z ichiga olmaydi.

Mukammal kon'yunktiv normal shakl

1. Barcha elementar disjunksiyalar F(x 1 ,x 2 ,...x n) funksiyaga kiritilgan barcha oʻzgaruvchilarni oʻz ichiga oladi.
2. Barcha elementar disjunctionlar har xil.
3. Har bir elementar dis'yunktsiya bir marta o'zgaruvchini o'z ichiga oladi.
4. Birorta elementar dis'yunksiyada o'zgaruvchi va uning inkori mavjud emas.