MULOHAZALAR ALGEBRASI ASOSIY TUSHUNCHALARINING
GRAMMATIK TA’RIFI
II-bobda, mantiqiy formula tarkiblari va uning grammatik ta’rifi berilgan,
mantiqiy ifodalarni tarkibiy qismlarga ajratish va ularni komputer xotirasida saqlash
uchun ma’lu
m
otlar strukturasini tanlash va ularni qayta ishlash algoritmlari berilgan.
Ma’lumotlarni ifodalanish uchun ma’lumotlar strukturasini tanlash uchun tavsiyalar
berilgan.
Mantiqiy formulaning grammatik ta’rifi.
Mantiqiy o’zgaruvchi deb shunday o’zgaruvchiga aytiladiki, u faqat ikki xil
mantiqiy ifodani qabul qiladi, ya’ni
FALSE
yoki
TRUE.
Mantiqiy funksiya
f(x
1,
...,x
n
)
quyidagicha tasvirlanadi:
f:{FALSE,TRUE}
n
{FALSE,TRUE}[8].
Mantiqiy funksiya berilishining yana bir usuli—bu mantiqiy formulalarni
metalingvistik formulalar ko’rinishida yozilishidir. Mantiqiy formulalarning grammatik
yozilish tili quyidagi ko’rinishda bo’ladi:
{::=
kon‘yunksiya/kon‘yunksiya OR }
kon‘yunksiya::={
AND kon‘yunksiya}
::={true/false/o’zgaruvchi/not
o’zgaruvchi/not
/
and kon‘yunksiya/ and mantiqiy-formula1
o’zgaruvchi
::=harf/harf butun son
harf::=a /b/c/…A/B/C/…
butun son::=raqam/ raqam/ butun son
Ikki mantiqiy formula ekvivalent deyiladi, agar ixtiyoriy qiymatlar to’plami
uchun,ularning chinlik to’plamimos kelsa, ya’ni agar ular bir xil mantiqiy funksiyani
ifodalasa.
7
—berilganmantiqiy formula
,
ning inkori.
—mantiqiy-formula
mantiqiy formulaning qismiy formulasi deyiladi, agar u
quyidagi shartlardan hech bo’lmaganda bittasini qanoatlantirsa:
a)
;
b)
=
OR
, bu yerda
-formula,
- mantiqiy formula,
-
yoki
larning birining
qismiy formulasi;
c)
=
AND
, bu yerda
- ko’paytuvchi,
- esa kon‘yunksiya,
-
yoki
ning qismiy
formulasi;
d)
=(
),
- esa
- formulaning qismiy formulasi;
e)
=
NOT
, bu yerda
- ko’paytuvchi,
- formula esa
- ko’paytuvchining qismiy
formulasini.
Mantiqiy funksiyalarni berilishining yana bir usuli—bu ularni diz’yunktiv normal
shakl (DNSh) deb nomlanuvchi ko’rinishda yozilishidir. DNShning grammatik ta’rifi
quyidagicha yoziladi:
DNSh::={FALSE //OR DNSh}
::={/
ko’paytuvchi>AND }
::={/NOT }
o’zgaruvchi::=harf/harf butun son
harf::=a /b/c/…A/B/C/…
butun son::=raqam/< raqam>/< butun son>
Kengaytirilgan
(mantiqiy)
formulalarning
sintaktik
ta’rifimantiqiy
formulalarning qo’shimcha sintaktik qoidalari bilan ifodalanishi:
::={/
formula>{
=
+//}}
va qo’shimcha ko’paytirish qoidasi orqali ko’paytuvchining ifodalanishi:
::={NOT /TRUE /FALSE
()
8
Shunday qilib,
NOT, AND
va
OR
operatsiyalariga nisbatan
, = va + mantiqiy
amallarning barilish tartibi pastroq, ya’ni ular qavs ichidagi operatsiyalardan keyin
bajariladi. Bu operatsiyalarni hisoblash qoidasi quyidagicha:
(
)=(
V
), (
=
)=(
&
)V(
&
) va
+
=(
&
)V(
&
)
- mantiqiy formulalarning ifodalanish qoidasini bildiradi, bu yerda
,
- bir-
biriga teng bo’lmagan mantiqiy formulalar.
ga asosan
-mantiqiy formula
ga
qismiy formula bo’lsa,
-
ga akslantiriladi. Agar
,
formula tarkibida bo’lmasa, u
holda ,
ga tegishli emas.
Qoidalar to’plami cheksiz qoidalar to’plamini kompakt yozish uchun qo’llaniladi.
Qoidalar to’plamida o’zgaruvchilar bilan birga mavjud sintaktik tushunchalar:
mantiqiy-formula, kon‘yunksiya, dizyunksiya, o’zgaruvchi nomlari yoziladi. Shunday
qilib, masalan: <
kon‘yunksiya> AND
qoidalar
sxemasi cheksiz qoidalar to’plamini bildiradi, bu sxemalar yordamida kon‘yunksiyani
umumlashtirib, boshqa bir qandaydir kon‘yunksiyani hosil qilish mumkin, ya’ni bu
qoidalar to’plami quyidagilarni o’z ichida saqlaydi:
TRUE AND TRUE
TRUE X AND X-^X, (X OR Y) AND (X OR Y)
(X OR Y).
Oddiy mantiqiy ifoda tushunchasining sintaktik ta’rifi quyidagi Grammatik qoida
yordamida yoziladi:
::={/< ifoda>
{V}
NOT ()}
::={/
< ifoda>}
::={// ()}
::={TRUE
FALSE}
::={//< identifikator-raqam>}
Oddiy ifoda daraxtini quyidagicha qurish mumkin:
1). Oddiy ifoda
=
ko’rinishda bo’lsa, uning sintaktik daraxti-
daraxt
bo’ladi.buda
- bu “V” yoki “
”,
- ifoda,
- esa oddiy ifoda;
- daraxtning ildizi.
9
2). agar
,
=
ko’rinishda bo’lsava
- (*) amal belgisi,
- ko’paytuvchi,
- esa
ifoda bo’lsa, unda
- daraxtning ildizi
- amal belgisi bilan belgilangan uch bo’ladi,
uning chap tomoni—
- ko’paytuvchi, o’ng tomoni esa —
- ifoda (term) bo’ladi[8].
|
