1. Formulalar. Teng kuchli formulalar. Aynan chin, aynan yolg‘on va bajariluvchi formulalar


Aynan chin, aynan yolg‘on va bajariluvchi formulalar



Download 53,5 Kb.
bet2/5
Sana28.05.2023
Hajmi53,5 Kb.
#945027
1   2   3   4   5
Bog'liq
Diskret tenglamalar

Aynan chin, aynan yolg‘on va bajariluvchi formulalar
Tabiiyki, berilgan formula uning tarkibida qatnashuvchi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlari ucnun turli qiymatlar, jumladan, faqat ch yoki faqat yo qiymat qabul qilishi mumkin.

  1. t a ’ r i f. Tarkibidagi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.

1-jadval

x

y

x  y

x  (x  y)

x  (x  y)  y

yo

yo

ch

yo

ch

yo

ch

ch

yo

ch

ch

yo

yo

yo

ch

ch

ch

ch

ch

ch

Tavtologiya iborasi o‘rnida aynan chin yoki doimo chin formula iborasi ham qo‘llanilishi mumkin. Tavtologiya, ko‘pincha, J yoki 1 bilan belgilanadi. Aynan chin formula, uning tarkibida ishtirok etuvchi o‘zgaruvchilarning qiymatlariga bog‘liq bo‘lmay, faqat bitta (ch) qiymat qabul qiladi.


Berilgan formula tavtologiya bo‘lishi yoki bo‘lmasligi, odatda, uning qiymatlar jadvali vositasida aniqlanadi.
1- m i s o l . D  x  (x  y)  y formula tavtologiyadir. Bu tasdiqning to‘griligini tekshirish uchun 1- jadvalni ( D formulaning qiymatlar jadvalini) tuzamiz. Berilgan D formula uning tarkibida qatnashuvchi x va y elementar mulohazalarning mumkin bo‘lgan hamma qiymatlar satrlarida faqat ch qiymat qabul qilgani uchun, u tavtologiyadir, ya’ni x  (x  y)  y  J . ■
2- m i s o l . Berilgan B  (x  y)  (x  y)  z formulani tekshirish uchun uning chinlik jadvalini tuzamiz
2-jadval

x

y

z

¯x

¯x  y

x  y

(¯x  y)  (x  y)

B

yo

yo

yo

ch

ch

ch

ch

yo

yo

yo

ch

ch

ch

ch

ch

ch

yo

ch

yo

ch

ch

ch

ch

yo

yo

ch

ch

ch

ch

ch

ch

ch

ch

yo

yo

yo

yo

yo

ch

yo

ch

yo

ch

yo

yo

yo

ch

ch

ch

ch

yo

yo

ch

ch

ch

yo

ch

ch

ch

yo

ch

ch

ch

Ch




  1. jadvaldan ko‘rinib turibdiki, (x  y)  (x  y)  J , lekin B J . ■

Aynan chin formulalar mantiqda katta ahamiyatga ega bo‘lib, ular mantiq qonunlarini ifodalaydi. Shu sababli, mantiq algebrasida yechilish muammosi deb yuritiluvchi chekli miqdordagi amal yordamida berilgan ixtiyoriy mantiqiy formulaning aynan chin yoki aynan chin emasligini aniqlash masalasi dolzarb muammo hisoblanadi. Yechilish muammosi faqat mulohazalar algebrasi uchungina emas, balki boshqa mantiqiy sistemalar uchun ham qo‘yilishi mumkin. Yechilish muammosi mulohazalar algebrasi uchun ijobiy hal etiladi (ushbu bobning 5- paragrafiga qarang). Tabiiyki, yechilish muammosini turli usullar yordamida hal qilish mumkin. Bunday usullarni yechuvchi usullar deb ataymiz. Yechuvchi usul iborasi o‘rnida yechish protsedurasi yoki yechish algoritmi iboralari ham qo‘llanilishi mumkin.
Yechish protsedurasi sifatida chinlik jadvalini qo‘llashga asoslangan usulni olish mumkin, chunki chinlik jadvali har bir muayan formula uchun yechilish muammosini to‘liq hal qilish imkonini beradi. Agar berilgan formulaga mos keladigan chinlik jadvalning oxirgi ustunida faqat ch bo‘lsa, u holda bu formula aynan chin, agar oxirgi ustunda hech bo‘lmaganda bitta yo bo‘lgan holda esa formula aynan chin emas bo‘ladi. Tabiiyki, amalda bu usulni har doim ham qo‘llab bo‘lavermaydi, chunki u quyidagi asosiy kamchilikka ega. Agar berilgan formulada n ta elementar o‘zgaruvchi mulohazalar qatnashsa, u holda bu formulaning chinlik jadvali n 2 ta satrga ega bo‘ladi va n ning yetarli katta qiymatlarida bu yechish protsedurasini, hattoki, komp’yuter yordamida ham oxiriga yetkazib bo‘lmaydi. Lekin, prinsip jihatdan olganda, “chinlik jadvalini qo‘llashga asoslangan usul yordamida chekli miqdordagi amallar bajarib yechilish muammosini hal qilish mumkin” degan tasdiq to‘g‘ridir. Ushbu bobning keyingi paragraflarida boshqa bir yechuvchi protsedurani keltiramiz. Bu yechuvchi protsedura berilgan formulani normal shaklga keltirish usuliga asoslangan. Normal shakllar matematik mantiqning boshqa masalalarida ham ishlatiladi.
Aynan yolg‘on formulalar. Formula uning tarkibida ishtirok etuvchi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlari ucnun faqat yo qiymat qabul qilishi ham mumkin.

  1. t a ’ r i f. Tarkibidagi elementar mulohazalarning mumkin bo‘lgan barcha qiymatlar satrlarida faqat yo qiymat qabul qiluvchi formula aynan yolg‘on (doimo yolg‘on) yoki bajarilmaydigan formula deb ataladi.

  1. va 2- ta’riflardan yaqqol ko‘rinib turibdiki, aynan yolg‘on formula tavtologiyaning inkoridir, va, aksincha, tavtologiya aynan yolg‘on formulaning inkoridir. Shuning ucnun aynan yolg‘on formulani J yoki 0 bilan belgilash joizdir.

Aynan yolg‘on formula ham, aynan chin formula kabi, o‘z tarkibida ishtirok etuvchi o‘zgaruvchilarning qiymatlariga bog‘liq emas, u faqat bitta (yo) qiymat qabul qiladi. Berilgan formulaning bajarilmaydigan formula bo‘lishi yoki bo‘lmasligi ham, odatda, uning qiymatlar jadvali yordamida aniqlanadi.

  1. t a ’ r i f. Agar А va В formulalar uchun А  В formula tavtologiya bo‘lsa, u holda В formula А formulaning mantiqiy xulosasi deb ataladi.

4- t a ’ r i f. Agar А va В formulalar uchun А  В formula tavtologiya bo‘lsa, u holda berilgan formulalar mantiqiy ekvivalent formulalar deb ataladi.
1-t e o r e m a . Agar А va А  В formulalarning har biri tavtologiya bo‘lsa, u holda В formula ham tavtologiya bo‘ladi.
I s b o t i . А va А  В formulalarning har biri tavtalogiya bo‘lsin. Teorema tasdig‘ining teskarisini, ya’ni А va В formulalar tarkibiga kiruvchi o‘zgaruvchilarning hech bo‘lmaganda bitta qiymatlar satrida В formula yo qiymat qabul qilsin deb faraz qilamiz. U holda, А formula tavtologiya bo‘lganligi uchun, o‘zgaruvchilarning o‘sha qiymatlar satr(lar)ida А ch qiymat qabul qiladi. Shu sababli А  В formula yo qiymat qabul qiladi. Bu esa А  В formula tavtologiyadir degan tasdiqqa qarama-qarshidir. Demak, В tavtologiyadir. ■
2-t e o r e m a . Agar А1 formula tarkibiga bir yoki ko‘p marta kirgan А formula o‘rniga В formulani qo‘yish natijasida В1 formula hosil qilinsa, u holda ( ) ( ) А  В  А1  В1 formula tavtologiya bo‘ladi.
I s b o t i . Agar tarkibidagi o‘zgaruvchilarning biror qiymatlar satrida А va В formulalar turli qiymatlarga ega bo‘lsa, u holda o‘sha qiymatlar satrida А  В formulaning qiymati yo bo‘ladi va, natijada, А1  В1 formulaning qiymati qanday bo‘lishidan qat’iy nazar, ( ) ( ) А  В  А1  В1 formula ch qiymat qabul qiladi.
Agar tarkibidagi o‘zgaruvchilarning qandaydir qiymatlar satrida А va В formulalar bir xil qiymat qabul qilsa, u holda o‘sha qiymatlar satrida А1 va В1 formulalar ham bir xil qiymat qabul qiladi, chunki teoremaning shartiga asosan В1 formula А1 formuladan А formulaning o‘rniga В formulani qo‘yish natijasida hosil qilingan. Demak, bu holda А  В va А1  В1 formulalarning ikkalasi ham ch qiymat qabul qiladi. Shuning uchun ( ) ( ) А  В  А1  В1 formula ham ch qiymat qabul qiladi.
Shunday qilib, yuqorida qaralgan mumkin bo‘lgan ikkala holda ham ( ) ( ) А  В  А1  В1 formula ch qiymat qabul qiladi. Demak, ( ) ( ) А  В  А1  В1 formula tavtologiya bo‘ladi. ■
2- teoremaga ko’ra, agar А1 formula tarkibiga bir yoki ko‘p marta kirgan А formula o‘rniga В formulani qo‘yish natijasida В1 formula hosil qilinsa, u holda А va В formulalarning mantiqiy ekvivalentligidan А1 va В1 formulalarning ham mantiqiy ekvivalentligi chiqadi.



Download 53,5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish