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].
