Өтініштерді есепке алу нысандары. Логикалық есептерді шешудің алгоритмдік жолдары

1.2 Өтініштерді есепке алу нысандары. Логикалық есептерді шешудің алгоритмдік жолдары

1.2.1 Мәлімдеменің логикалық формулалары және олардың қасиеттері

А, В, С, т.б. болсын . - айнымалылар, олардың орнына осы айнымалылар мен логика таңбаларының көмегімен кез келген элементар мәлімдемелерді ауыстыруға болады, кез келген мәлімдемені формализациялауға болады, яғни оның логикалық құрылымын білдіретін формуламен алмастыруға болады.

Мысалы,: «Егер 20 саны 2-ге және 5-ке бөлінетін болса, онда 20 саны 10-ға бөлінеді» деген мәлімдеме ретінде ресімделеді . Сол формула сөйлемге сәйкес келеді: «егер төртбұрышта қарама-қарсы екі қабырға тең және параллель болса, онда бұл төртбұрыш параллелограмм болады»

Болжамдық логикалық формула ұғымын нақтылайық. Ол үшін алдымен алфавитті, яғни пропозициялық логикада қолдануға болатын белгілер жиынтығын анықтаймыз.

1. 
   A, B, C және т. - айтылымға арналған белгілер;
   
2. 
   1 және 0 – «ақиқат», «жалған» логикалық тұрақтыларды белгілейтін символдар;
   
3. 
   - символдар, логикалық операциялар;
   
4. 
   ( , ) – амалдардың орындалу ретін көрсету үшін қолданылатын жақшалар, көмекші белгілер.
   

Ұсыныс логикалық формуласының қатаң анықтамасын берейік .

1. 
   Әрбір мәлімдеме формула болып табылады;
   
2. 
   1, 0 символдары – формулалар;
   
3. 
   Егер А формула болса, онда А да формула болады;
   
4. 
   Егер A ₁ және A ₂ - формулалар, содан кейін
   

5. 
   - формулалар;
   

6. 
   Пропозициялық логикада басқа формулалар жоқ.
   

1. 
   Қарапайым мәлімдемелерді айнымалылармен ауыстырамыз;
   
2. 
   Логикалық жалғауларды сәйкес белгілермен ауыстырамыз;
   
3. 
   Көмекші белгілерді, жақшаларды: ( , ) осы сөйлемнің мағынасына сәйкес орналастырамыз.
   

Мәлімдеменің ақиқаты немесе жалғандығы, ақиқат кестесін орнатамыз.

Ақиқат кестелері келесі ереже бойынша құрастырылады:

Алдымен сіз мәлімдемелердің барлық мүмкін жиындарын жазуыңыз керек, сонымен қатар , мәлімдемелердің әрқайсысы екі күйдің біріне ( 0 немесе 1) енгізе алады. Содан кейін орындалу ретіне сәйкес ретімен логикалық амалдар, әрбір логикалық операцияның астына жазу керек шынайы құндылықтар. Формулада p бар-жоғына назар аударыңыз ұсыныстар болса, онда ақиқат кестесінде жолдар болады.

Кестелерді құрастыру кезінде сақ болу керек тәртіпті шатастырыңыз. Кестені толтыру кезінде «іштен сыртқа», яғни қарапайым формулалардан күрделірек формулаларға көшу керек. Толтырылатын соңғы баған бастапқы формуланың мәндерін қамтиды /4/.

Операциялардың орындалу реті жақша арқылы анықталады. Жақша болмаған жағдайда алдымен терістеу амалы орындалады, одан кейін конъюнктура, содан кейін дизъюнкция, содан кейін реттілікпен, импликация, теңдік т.б.

2-мысал: функцияның мәнін есептеңіз:

Алгебралық өрнектер сияқты, үлкен күрделі логикалық формулалар да көп жағдайда жеңілдетілуі мүмкін, яғни эквивалент.

, егер олардың ақиқат кестелері бірдей болса, эквивалентті (A=B немесе ) деп аталады . Егер соңғы (нәтиже) бағандары бірдей болса , екі ақиқат кестесін бірдей деп қарастырамыз .

Мысалы:

Ұсыныс логикасында біз балама формулалар бір ұсынысты анықтайды деп есептейміз. Ақиқат кестесінің соңғы бағанында тек бір немесе нөл бар екені белгілі болуы мүмкін. Мұндай тұжырымды бірдей ақиқат (таутология) сәйкесінше бірдей жалған (қайшылық) деп атаймыз және 1 мен 0-ді белгілейміз. Анықтамадан формулалардың эквиваленттігін тексеру үшін олардың ақиқат кестелерін құру және салыстыру қажет екендігі шығады.

Логикалық мәлімдемелерді жеңілдету үшін келесі эквиваленттіктерді (қасиеттерді) пайдалануға болады:

1. 
   Ауыстыру (орын ауыстыру) заңдары
   

2. 
   Ассоциативті (ассоциативті) заңдар
   

3. 
   Бөлу (тарату) заңдары
   

4. 
   Абсорбция заңдары
   

5. 
   Желімдеу заңдылықтары
   

Теріс қасиеттер

1. 
   Де Морган заңдары
   
2. 
   Қос теріске шығару заңы ;
   
3. 
   Қарама-қайшылық заңы ;
   
4. 
   Үшіншіні алып тастау заңы .
   

Логикалық тұрақтылары бар қасиеттер

1. 
   , ;
   
2. 
   
   
3. 
   
   
4. 
   
   

Логикалық операциялар арасындағы байланыс

1. 
   ;
   
2. 
   , ;
   
3. 
   , ;
   
4. 
   ;
   
5.