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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A A
A ∈ T A ∈ R
A ∼ B A B
B A
A
DeM1, 2
Dtr2
A
A
A
A
A
28                          Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


A (7-ÿ îïåðàöèÿ) ñîäåðæèò ñèìâîë ¾ëîæü¿, è, çíà÷èò, ôîðìóëà A íå
åñòü òàâòîëîãèÿ.
   Åñëè ïðè ïðîâåðêå âêëþ÷åíèÿ A ∈ T [ A ∈ R ] ïîä çíàêîì ãëàâíîé
îïåðàöèè îáíàðóæåí 0 [ 1 ], èññëåäîâàíèå ìîæíî ïðåêðàòèòü.

Ìåòîä ïðèâåäåíèÿ ê íîðìàëüíûì ôîðìàì. Ïðîïîçèöèîíàëü-
íûå ïåðåìåííûå è èõ îòðèöàíèÿ íàçûâàþò ëèòåðàëàìè . Ôîðìóëà,
ÿâëÿþùóþñÿ êîíúþíêöèåé ïðîèçâîëüíûõ ëèòåðàëîâ åñòü êîíúþíêò .
Ôîðìóëà, ÿâëÿþùóþñÿ äèçúþíêöèåé êîíúþíêòîâ íàçûâàåòñÿ äèçúþíê-
òèâíîé íîðìàëüíîé ôîðìîé (ÄÍÔ). Äâîéñòâåííî, ôîðìóëà, ÿâëÿþùó-
þñÿ äèçúþíêöèåé ëèòåðàëîâ íàçûâàåòñÿ äèçúþíêòîì , à ôîðìóëà, ÿâ-
ëÿþùóþñÿ êîíúþíêöèåé äèçúþíêòîâ  êîíúþíêòèâíîé íîðìàëüíîé
ôîðìîé (ÊÍÔ).
   Åñëè A ∼ B , A  ïðîèçâîëüíàÿ ôîðìóëà, à B  ÄÍÔ [ÊÍÔ],
òî B íàçûâàþò ïðåäñòàâëåíèåì A â âèäå ÄÍÔ [ÊÍÔ], èëè ïðîñòî
ÄÍÔ [ÊÍÔ] A. Â äèñêðåòíîé ìàòåìàòèêå äîêàçûâàåòñÿ, ÷òî ëþáàÿ
ôîðìóëà èìååò ýêâèâàëåíòíûå åé (âîçìîæíî íå åäèíñòâåííûå) ÄÍÔ
è ÊÍÔ. Ïðèâåä¼ì àëãîðèòì ïðèâåäåíèÿ ïðîèçâîëüíîé ôîðìóëû àë-
ãåáðû ëîãèêè ê ÊÍÔ, èñïîëüçóþùèé ýêâèâàëåíòíîñòè èç ëåììû 1.2 è
ýëåìåíòàðíûå ñâîéñòâà ëîãè÷åñêèõ ôóíêöèé:
 1) âñå èìïëèêàöèè âûðàæàþò ÷åðåç êîíúþíêöèè è îòðèöàíèÿ;
 2) èñïîëüçóÿ çàêîíû Äå Ìîðãàíà (DeM 1, 2) ïåðåíîñÿò âñå îòðèöà-
    íèÿ ê ïåðåìåííûì è ñîêðàùàþò äâîéíûå îòðèöàíèÿ;
 3) èñïîëüçóÿ Dtr2 ïðåîáðàçóþò ôîðìóëó òàê, ÷òîáû âñå äèçúþíê-
    öèè âûïîëíÿëèñü ðàíüøå êîíúþíêöèé.
   Äëÿ õàðàêòåðèçàöèè ìîæíî ïîïûòàòüñÿ ïðèâåñòè èññëåäóåìóþ
ôîðìóëó A ê îäíîé èç óêàçàííûõ íîðìàëüíûõ ôîðì. Ìåòîä îñíîâàí
íà ñëåäóþùèõ äâóõ ýëåìåíòàðíûõ òåîðåìàõ.
Òåîðåìà 1.3. Ôîðìóëà A àëãåáðû ëîãèêè òîæäåñòâåííî èñòèííà,
åñëè è òîëüêî åñëè ëþáàÿ äèçúþíêöèÿ, âõîäÿùàÿ â ÊÍÔ A, ñîäåðæèò
íåêîòîðóþ ïðîïîçèöèîíàëüíóþ ïåðåìåííóþ âìåñòå ñ å¼ îòðèöàíèåì.
   Ìû èñïîëüçîâàëè äàííîå ñâîéñòâî ïðè äîêàçàòåëüñòâå ïðàâèëà 3
ïðèìåðà 1.6.
Òåîðåìà 1.4. Ôîðìóëà A àëãåáðû ëîãèêè òîæäåñòâåííî ëîæíà, åñ-
ëè è òîëüêî åñëè ëþáàÿ êîíúþíêöèÿ, âõîäÿùàÿ â ÄÍÔ A, ñîäåðæèò
íåêîòîðóþ ïðîïîçèöèîíàëüíóþ ïåðåìåííóþ âìåñòå ñ å¼ îòðèöàíèåì.
   Ïðèâåäåíèå ôîðìóëû ê ÄÍÔ ïðîâîäèòñÿ äâîéñòâåííî ïðèâåäåíèþ
ê ÊÍÔ.  ðÿäå ñëó÷àåâ ýòîò ìåòîä ïðèâîäèò ê óñïåõó áûñòðåå, ÷åì
ñîñòàâëåíèå èñòèííîñòíîé òàáëèöû.

Страницы