|
Bog‘lovchi
chaqirdi
boshlang'ich
|
| bet | 4/6 | | Sana | 30.11.2023 | | Hajmi | 30,39 Kb. | | #108899 |
Bog'liq Diskret tuzilmalarBog‘lovchi
chaqirdi
boshlang'ich
agar unga kiritilgan barcha
o'zgaruvchilar boshqacha bo'lsa. Elementar birikma yoki elementar ayirma
tarkibiga kiruvchi harflar soni deyiladi
daraja.
1-raqam 0-darajali elementar birikma hisoblanadi. Oʻzgaruvchi elementar
bogʻlanish yoki 1-darajali elementar dis’yunksiya hisoblanadi. elementar shaklga
keltiriladi va harflarning bir xil to'g'ri bo'lmagan har qanday diszyunksiyasi
elementar shaklga ham keltirilishi mumkin. Buning uchun konyunksiya va
diszyunksiyaning kommutativlik, idempotentlik va assotsiativlik xossalarini
qo`llash zarur.
Mantiqiy algebraning istalgan formulasini , &, amallari yordamida ifodalash
mumkinligi qat’iy isbotlangan. Intuitiv ravishda, bu haqiqat aniq, keling, haqiqat
jadvaliga ko'ra formulani tuzish algoritmini eslaylik. Biroq, biz faqat ushbu
operatsiyalardan foydalanamiz. Belgilanishning bu shakli deyiladi
disjunktiv
normal shakl
(DNF). Bu mantiqiy algebra formulalarini normallashtirish
mexanizmining bir turi.
Ta'rifi:
DNF
Har xil elementar qo‘shma gaplarning diszyunksiyasi (ya’ni, har bir
qo‘shma gap elementar gaplardan yoki ularning inkorlaridan iborat).
CNF xuddi shunday aniqlanadi - kon'yunktiv normal shakl.
Ta'rifi: Agar DNFda barcha elementar birikmalar DNF bog'liq bo'lgan
o'zgaruvchilar soniga teng bir xil darajaga ega bo'lsa, u deyiladi.
mukammal
(SDNF).
Teorema. Xuddi shunday noto'g'ri bo'lmagan har qanday funktsiya uchun noyob
SDNF ham mavjud.
Natija ... Xuddi shunday noto'g'ri bo'lmagan har qanday mantiqiy funktsiya
superpozitsiya sifatida taqdim etilishi mumkin &, , va inkor faqat
o'zgaruvchilarga tegishli.
Ta'rifi: Mantiqiy amallar tizimi, agar ushbu amallar va ushbu tizimning
konstantalaridan foydalanib, mantiqiy algebraning istalgan funksiyasini ifodalash
mumkin bo'lsa, funktsional tugallangan deb ataladi.
Tizimlar (&, , ); (, ); (&, ), (/) - funksional jihatdan tugallangan
(&, ) - funktsional jihatdan to'liq emas.
Biz bu faktlarni isbotsiz qabul qilamiz va masalalarni yechishda istalgan formulani
(&, , ) yordamida ifodalashga harakat qilamiz. Keyinchalik operatsiyalar
tizimining funktsional to'liqligi va to'liq emasligi masalasini batafsilroq ko'rib
chiqamiz.
1.7-mavzu. Mantiqiy ifodalarni soddalashtirish usullari. Mantiqiy masalalarni
yechish usullari.
Keling, mantiqiy masalani yechish misolini ko'rib chiqaylik.
Misol :
Ekspeditsiya ishtirokchilari tarkibini muhokama qilib, ikkita shart bajarilishi kerak
degan qarorga keldi.
Agar Arbuzov ketsa, Bryukvin yoki Vishnevskiy ketishi kerak
Agar Arbuzov va Vishnevskiy ketsa, Bryukvin ketadi
Ramziy shaklda qaror qabul qilishning mantiqiy formulasini tuzing, natijada
olingan formulani soddalashtiring va undan foydalangan holda ekspeditsiyani
shakllantirishning yangi shartini tuzing.
Keling, o'zgaruvchilar va ularga mos keladigan elementar bayonotlarni kiritamiz.
- Arbuzov ketadi
Mantiqiy algebra qonunlari va o'ziga xosliklaridan foydalanib, siz mantiqiy
ifodalarni soddalashtirishingiz mumkin.
Xizmat maqsadi... Onlayn kalkulyator uchun mo'ljallangan
|
| |
