Анықтама.формуласынформулаларының коньюнкциясы деп атайды және оны
арқылы белгілейді. Егер жоғарыдағы коньюнкциядағыформулалары әріп немесе әріптің терістеуі болса, онда бұл формула элементар коньюнкция деп аталады.
Дизъюнкция үшін жоғарыдағы келісім бойынша
арқылы белгілесек, элементар дизьюнкцияны да жоғарыдағыдай анықтаймыз. Яғни, жоғарыдағы дизьюнкциядағыформулалары әріп немесе әріптің терістеуі болса, онда ол формула элементар дизьюнкция деп аталады. Енді дизъюнктивті нормаланған форма (ДНФ) және коньюнктивті нормаланған форманың(КНФ) анықтамаларын берелік.
Анықтама.
- Элементар коньюнкциялардың ақырлы дизьюнкциясын дизьюнктивті нормаланған форма (ДНФ) деп атаймыз.
- Элементар дизьюнкциялардың ақырлы коньюнкциясын коньюнктивті нормаланған форма (КНФ) деп атаймыз.
Теорема 2.1 Пікірлер логикасының әрбір формуласына эквивалентті дизьюнктивті нормаланған форма табылады.
Дәлелдеуі.формуласында кездесетін әріптердің тізімі болсын. Егерформуласына сәйкес логикалық функция болса, ондаболады. Алдыменформуласының ақиқаттық кестесін құрайық.
| … | … | ||||||
| … | |||||||
| -ші жол | а | ж | … | ж | … | а | а |
| … | … | … |
формуласының құрамында n әріп кездесетіндіктен, оның ақиқаттық кестесіжолдан тұрады, яғни . Әрбір жолғаақиқаттық функциясы сәйкес келеді. Әрбірфункциясына (жолына)формуласын сәйкес қоямыз. Мұндағыконьюнктивті мүшелерін төмендег шартпен анықтаймыз.
формуласын келесі тәртіппен құралық. Әрбір -ші жолға сәйкесформуласылогикалық функциясы үшінболатындай, алболған жағдайдаболатындай етіп таңдалады. Атап айтқанда, кестеде келтірілген -ші жолға сәйкесформуласы келесі түрде құрылады: . Ендіформуласынформуласы ақиқат мәндер қабылдайтын жолдарға сәйкесформулаларының дизьюнкциясы –ретінде алайық.формулалары элементар коньюнкциялар болғандықтан,– дизьюнктивті нормаланған форма жәнеформулаларының анықтамасынан кез келгенүшін () = () немесеТеорема дәлелденді.
Жоғарыдағы теореманыңдәлелдеу жолынан мынандай қорытындыға келеміз: егер әрбір формулаға ақиқаттық кесте сәйкес келсе, керісінше әрбір ақиқаттық кестеге қандай да бір формула сәйкес келеді. Бірақ, берілген ақиқаттық кестеге сәйкес формула біреу ғана болмайды. Дегенмен жоғарыдағы теоремадан берілген ақиқаттық кестеге сәйкес кез келген екі формуланың өзара логикалық эквиалентті формулалар болатынын көреміз.
Мысалы, төмендегі ақиқаттық кестеге сәйкес формула құрайық.
| а | а | ж | |
| а | ж | А | |
| ж | а | ж | |
| ж | ж | А |
Жоғарыдағы алгоритм бойынша, бұл кестеге
формуласы сәйкес келеді.
Ескерту. Егер j тавтология болса, онда j ~болады да, j қайшылық болғанда j ~ . Бұлар әрі ДНФ, әрі КНФ түріндегі формулалар. Жалпы жағдайда, кез келген элементар конъюнкция мен элементар дизъюнкция әрі ДНФ, әрі КНФ түріндегі формулалар болады.
Келтірілген теореманың дәлелдеуіндегі ж мәнін а мәніне, конъюнкцияны дизъюнкцияға және дизъюнкцияны конъюнкцияға алмастырып, дәлелденген теоремаға қосалқы теореманы аламыз.
Теорема 2.2 (КНФ туралы) Пікірлер логикасының әрбір формуласына логикалық эквивалентті коньюнктивті нормаланған форма табылады.
Енді жоғарыда келтірілген логика заңдарын логикалық есептерді шығаруға қолданып көрейік. Ол үшін келесі мысалдарды пікірлер логикасының формулаларын құру арқылы шешеміз.
1 мысал. Мен үйге барып, бақшада жұмыс істеймін (A) немесе кафедрада қалып іс қағаздарымды реттеймін (B). Егер үйге барып бақшада жұмыс істесем әйелімнің алдында ұпайым көбейеді (C). Ал егер іс қағаздарымды ретке келтірсем бүгін тыныш ұйықтайтын боламын (D). Демек мен бүгін ұпайымды көбейтемін немесе тыныш ұйықтаймын. Осы ұйғарымның мінсіздігін дәлелде.
Алғышарттары:
Қорытынды:
Шешуі:
Ол үшін логика заңдарын қолданамыз.
Сонымен берілген алғышарттарданформуласы қорытылды. Бұл біздің тұжырымымыздың мінсіздігін көрсетеді.
2 мысал. Алты мехматтың студенті – Асқар, Берік, Ғалым, Дархан, Еркін және Санжар математикадан олимпиадаға қатысты. Олардың екеуі барлық есепті шығарды. Оларға жанкүйер болып жүрген бес қыздан «Кім барлық есепті шығарды?» деген сұраққа келесі жауаптар алынды:
1) Асқар мен Дархан; 2) Берік пен Еркін; 3) Еркін мен Асқар; 4) Берік пен Ғалым;
5) Санжар мен Асқар. Осы жауаптың төртеуінде жауаптардың бір бөлігі ақиқат, екінші бөлігі жалған. Біреуінде екі бөлігі де жалған. Кім барлық есепті шығарды?
Келесі пікірлерді белгілейік.
A:= Асқар барлық есепті шығарды;
B:= Берік барлық есепті шығарды;
G:= Ғалым барлық есепті шығарды;
D:= Дархан барлық есепті шығарды;
Е:= Еркін барлық есепті шығарды;
S:= Санжар барлық есепті шығарды.
Бір жауаптың екі бөлігі де (екі коньюнкт те) жалған, ал қалған жауаптардың бір ғана бөлігі (бір конъюнкті) ғана жалған болғандықтан, барлық мүмкін жағдайларды төмендегі бес формула сипаттайды:
- AÙDÙ(BÙЕÚBÙЕ)Ù(ЕÙAÚЕÙA)Ù(BÙGÚBÙG)Ù
Ù(SÙA Ú SÙA);
- BÙЕÙ(AÙDÚAÙD)Ù(ЕÙAÚЕÙA)Ù(BÙGÚBÙG)Ù
Ù(SÙAÚSÙA);
- EÙAÙ(AÙDÚAÙD)Ù(BÙЕÚBÙЕ)Ù(BÙGÚBÙG)Ù (SÙAÚSÙA);
- BÙGÙ(AÙDÚAÙD)Ù(BÙЕÚBÙЕ)Ù(ЕÙAÚЕÙA)Ù(SÙAÚSÙA);
- SÙAÙ(AÙDÚAÙD)Ù(BÙЕÚBÙЕ)Ù(ЕÙAÚЕÙA)Ù(BÙGÚBÙG).
Егер A =а және D =а болса, онда бірінші формула келесі түрде жазылады:
AÙDÙ (BÙЕÚ BÙЕ) ÙЕÙAÙ (BÙGÚBÙG) Ù SÙA,
өәткені үшінші жауап бойынша ЕÙA =ж.
Егер B = а және Е= а болса, онда екінші формула келесі түрде жазылады:
BÙЕÙ (AÙDÚAÙD) ÙЕÙAÙBÙG Ù (SÙAÚ SÙA),
өйткені ЕÙA = ж және BÙG = ж.
Егер Е= а және A = а болса, онда үшінші формула келесі түрде жазылады:
ЕÙAÙAÙDÙBÙЕÙ (BÙGÚBÙG) ÙSÙA,
өйткені AÙD =0, BÙЕ=0, и SÙA =0.
Егер B = а және G = а болса, онда төртінші формула келесі түрде жазылады:
BÙGÙ (AÙDÚAÙ D) ÙBÙЕÙ (ЕÙAÚЕÙA) Ù (SÙAÚSÙA),
өйткені BÙЕ=0.
Егер С = а және A = а болса, онда бесінші формула келесі түрде жазылады:
SÙAÙAÙDÙ (BÙЕÚBÙЕ) ÙЕÙAÙ (BÙG ÚBÙG),
өйткені AÙD =0.
Енді үлестірімділік, идемпотенттілік және сіңіру заңдарын жоғарыдағы формулаларға қолдансақ, келесі формулаларды аламыз:
- AÙDÙBÙЕÙGÙS;
- BÙЕÙDÙSÙAÙG;
- ЕÙAÙGÙDÙSÙB;
- BÙGÙAÙDÙЕÙS;
- SÙAÙBÙDÙЕÙG.
Есеп шарты бойынша барлық есепті тек екі оқушы ғана шығарған. Сондықтан элементар конъюнкцияда терістеусіз үш әріп кездесетін формулалар есеп шартын қанағаттандырмайды. Демек, тек BÙЕÙDÙSÙAÙG формуласы ғана есеп шартына сай келеді. Ендеше барлықолимпиада есептерін Асқар (A) мен Ғалым (G) шығарған.
Енді осы нәтижелерді логика алгебрасының тұрғысынан талдап көрейік.