1§. Мулоҳазалар алгебраси

Мулоҳазалар алгебрасида ечилиш проблемаси.

нормал формалар

Биз юқорида кўрдикки, мулоҳазалар алгебрасининг ҳар қандай фомуласи ё айнан рост (тавтология), ё айнан ёлғон (зиддиятли), ё бажарилувчи бўлар экан.

Берилган формуланинг юқорида айтилган синфлардан қай бирига тегишли бўлишини аниқлаш масаласи муҳим аҳамиятга эга бўлиб, бу масала мулоҳазалар алгебрасида ечилиш проблемаси номи билан аталади.

Биз юқорида ҳар қандай формула учун бу масалани ҳал қилиш усулларидан бири бўлган жадвал усули билан танишдик. Бу усул жуда содда ва равшан бўлишига қарамай, айрим ноқулайликларга эгадир. Масалан, тўрт пропозиционал ўзгарувчили формулани текшириш учун 2⁴ яъни 16 сатрга эга бўлган жадвал тузишга, n ўзгарувчили формулани текшириш учун эса, 2ⁿ сатрга эга бўлган жадвал тузишга тўғри келади. Бундай жадвални тузиб, натижани аниқлаш, амалий жиҳатдан равшанки бир мунча қийинчилик туғдиради. Табиий, шу муносабат билан бу масалани ҳал этишни бошқа, аввалги усулидан фарқли усули бормикан деган савол туғилади. +уйида бу саволга формулаларнинг «нормал формаси» тушунчаси жавоб беради.

Келтирилган формула.

1-таъриф: Агар формуланинг таркибида мантиқий амаллардан фақат конъюнкция, дизъюнкция ва инкор амалларигина қатнашган бўлиб, инкор амали фақат пропозиционал ўзгарувчиларгагина тегишли бўлса, бундай формула келтирилган формула дейилади.

Дизъюнктив ва конъюнктив нормал формалар

Бундан кейин, ёзувни янада соддалаштириш мақсадида, мулоҳазанинг қиймати ростлигини ифодаловчи р ўрнига 1 рақамидан, ёлғон қийматини ифодаловчи Ё ўрнига 0 рақамидан фойдаланамиз. Баъзи ҳолларда эса, A B фoрмулани AB кўринишда ёзамиз, ҳамда A, A формулалар учун ушбу белгилашни киритамиз:

яъни, деб ҳисоблаймиз.