Пропозициялық логиканы пайдаланып логикалық есептерді шешу

1.2.3 Пропозициялық логиканы пайдаланып логикалық есептерді шешу

1. 
   Кодтау: логикалық айнымалылардың көмегімен қалағанды белгілеу (0, 1 мәндерін алу) және осы айнымалылардың мазмұнын сипаттау.
   
2. 
   Шартты логикалық теңдеулер жүйесі түрінде жазу, оның оң жақ бөлігінде бірліктері бар.
   

3. 
   Жүйенің сол жақ бөліктерінің жалғаулығын құрастыру және оны бірлікке теңеу. Алынған теңдеу сипаттамалық деп аталады. Ол бастапқы теңдеулер жүйесіне тең: жүйенің әрбір шешімі сипаттамалық теңдеудің шешімі болып табылады және керісінше.
   

Керісінше де дұрыс – сипаттамалық теңдеудің әрбір шешімі (ол конъюнктураны біреуге айналдырады) конъюнктураның барлық мүшелерін біріне айналдырады, сондықтан теңдеулер жүйесін қанағаттандырады.

4. 
   Сипаттамалық теңдеудің сол жағын DNF-ге келтіру (атап айтқанда, SDNF-ке).
   

5. 
   SDNF әрбір мүшесін басқаларына қарамастан біреуге теңестіру және теңдеулерден (сол жақ бөліктері айнымалылардың қосылыстары немесе оларды теріске шығару) айнымалылардың мәндерін шығару. Олардың әрбір жиынтығы мәселенің шешімі болып табылады.
   

Түсініктеме. Егер оңайлатылғаннан кейін DNF-де бір термин қалса, мәселенің бірегей шешімі, егер біреуден көп болса, бірнеше шешімі болады. Сипаттамалық теңдеудің сол жағындағы барлық мүшелер жойылған жағдайда есептің шешімі болмайды (деректер сәйкес емес).

Мәселені шешу үшін осы алгоритмді қолданайық.

Тапсырма. (Кім теледидар көреді?)

Отбасы бес адамнан тұрады: Алексей (А), Вера (С), Глеб (Г), Даша (Д), Евгений (Е).

1. 
   Егер А теледидар көріп отырса, онда В да қарайды;
   
2. 
   D немесе E немесе екеуін бірге қараңыз;
   
3. 
   C немесе D қараңыз, бірақ бірге емес;
   
4. 
   E мен D не бірге қарайды, не мүлде қарамайды;
   
5. 
   егер E қарап отырса, онда A және D қарап отыр.
   

Шешім:

2. 
   Логикалық теңдеулер жүйесі түрінде жазамыз:
   

3. 
   Сипаттамалық теңдеуге түрлендірейік:
   

4. 
   SDNF-ге сипаттамалық теңдеудің сол жағын келтіреміз:
   

5. 
   Бізде бір термин бар, сондықтан мәселенің бірегей шешімі бар. SDNF әрбір мүшесін біреуге теңестіру және теңдеуден айнымалылардың мәнін шығару.
   

Осылайша, біз жауап алдық: Глеб пен Даша теледидар көріп отыр.