Исчисления высказываний классической логики. Гуров С.И. - 27 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

2
n
n
A T F
R ϕ
A |A|
ϕ
A = ¬ (p
¡
¢
r)
¡
¢
((q
¡
¢
r)
¡
¢
(p ∨ q
¡
¢
r))
¬ p
¡
¢
r
¡
¢
q
¡
¢
r
¡
¢
(p ∨ q
¡
¢
r)
2
3. Õàðàêòåðèçàöèÿ ôîðìóë àëãåáðû âûñêàçûâàíèé                            27


   Ïðîáëåìà õàðàêòåðèçàöèè äëÿ àëãåáðû ëîãèêè ðåøàåòñÿ ïîëîæè-
òåëüíî: èçâåñòíû íåñêîëüêî ïîäõîäîâ, íà îñíîâå êîòîðûõ ìîãóò áûòü
ïðåäëîæåíû ñîîòâåòñòâóþùèå àëãîðèòìû. Çàìåòèì, ÷òî ðàññìàòðèâàå-
ìàÿ çàäà÷à ÿâëÿåòñÿ ïåðåáîðíîé. Ýòî îçíà÷àåò íåîáõîäèìîñòü ðàññìîò-
ðåíèÿ â õóäøåì ñëó÷àå âñåõ 2n ýëåìåíòàðíûõ âàðèàíòîâ îöåíîê, åñëè
èññëåäóåìàÿ ôîðìóëà ñîäåðæèò n ïåðåìåííûõ. Ïîýòîìó íà ïðàêòè-
êå ïîèñê îòâåòà íà ïîñòàâëåííûé âîïðîñ ìîæåò ïîòðåáîâàòü áîëüøîé
âû÷èñëèòåëüíîé ðàáîòû.
   Íèæå ðàññìàòðèâàþòñÿ íåêîòîðûå àëãîðèòìû õàðàêòåðèçàöèè ôîð-
ìóë àëãåáðû ëîãèêè. Â ñâÿçè ñ âûøåñêàçàííûì ÿñíî, ÷òî îäíè ìåòîäû
ìîãóò îêàçàòüñÿ ýôôåêòèâíåå äðóãèõ ëèøü â íåêîòîðûõ ÷àñòíûõ ñëó-
ֈ؛.

Ìåòîä èñòèííîñòíûõ òàáëèö.         Äàííûé ìåòîä, ÿâëÿþùèéñÿ òðè-
âèàëüíûì àëãîðèòìîì ïðîâåðêè ïðèíàäëåæíîñòè A ê êëàññàì T, F,
R, ñâîäèòñÿ ê ïåðåáîðó èíòåðïðåòàöèé ϕ ïðîïîçèöèîíàëüíûõ ïåðåìåí-
íûõ, âõîäÿùèõ â ôîðìóëó A è àíàëèçó çíà÷åíèé |A|ϕ 17 .
Ïðèìåð 1.7. Äëÿ ïðîâåðêè, ÿâëÿåòñÿ ëè ôîðìóëà
                          ¡    ¡    ¡    ¡       ¡
                 A = ¬ (p ¢ r) ¢((q ¢ r) ¢(p ∨ q ¢ r))

òàâòîëîãèåé, ñîñòàâèì å¼ èñòèííîñòíóþ òàáëèöó:
            ¡      ¡¢      ¡     ¡¢        ¡
    ¬ (p ¢ r)        ( (q ¢ r )     (p ∨ q ¢ r)        )
     0    010       1     010      1     00010
     0    011       1     011      1     00011
     0    010       1     100      1     01100
     0    011       1     111      1     01111
     1    100       0     010      0     11000
     0    111       1     011      1     11011
     1    100       1     100      1     11100
     0    111       1     111      1     11111
     2      1       7       3       6      4    5
   Ñòðîêè òàáëèöû ñîîòâåòñòâóþò âñåâîçìîæíûì èíåòåðïðåòàöèÿì
äàííîé ôîðìóëû. Ñòîëáöû ïîä ñèìâîëàìè ïðîïîçèöèîíàëüíûõ ïåðå-
ìåííûõ ñîäåðæàò èõ èñòèííîñòíûå çíà÷åíèé â äàííîé èíòåðïðåòàöèè.
Ñòîëáöû ïîä ñèìâîëàìè ëîãè÷åñêèõ ñâÿçîê ñîäåðæàò ðåçóëüòàòû ñîîò-
âåòñòâóþùèõ ëîãè÷åñêèõ îïåðàöèé.  ïîñëåäíåé ñòðîêå óêàçàí ïîðÿäîê
âûïîëíåíèÿ îïåðàöèé. Ñòîëáåö ïîä ñèìâîëîì ãëàâíîé ñâÿçêè ôîðìóëû
  17 Ýòà ïðîöåäóðà ïðåäëîæåíà Ïîñòîì â 1921 ã. äëÿ óñòàíîâëåíèÿ âûâîäèìîñòè
ôîðìóëû ïîñëå óñòàíîâëåíèÿ ïîëíîòû (ò.å. ñîâïàäåíèÿ ìíîæåñòâ âûâîäèìûõ ôîð-
ìóë è òàâòîëîãèé) èñ÷èñëåíèÿ âûñêàçûâàíèé, ôîðìàëèçóþùåãî C2 . Îá èñ÷èñëåíèè
âûñêàçûâàíèé ñì. ðàçäåë 1 ãëàâû 2.

Страницы