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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

H
A ' B ⇒ A ∼ B
A B
' ∼
'
H
⇒ ⇔
h P, v i
P v
a v b a b
a v b a 6= b a @ b
a v b x a @ x x @ b
a b
a
b a b a
b
v
h B, t, u,
−
, o, ι i
a v b ⇔ a t b = b a v b ⇔ a u b = a
B
h B, ∪, ∩,
−
, v, o, ι i
a v b ⇔ a u b
0
= o ⇔ a
0
t b = ι .
66           Ãëàâà 2. Èñ÷èñëåíèÿ âûñêàçûâàíèé. Ãèëüáåðòîâñêèå ÈÂ


3.2 Ñåìàíòè÷åñêàÿ ïîëíîòà

    Äîêàçàòåëüñòâî ñåìàíòè÷åñêîé ïîëíîòû È H çíà÷èòåëüíî ñëîæ-
íåå äîêàçàòåëüñòâà åãî êîððåêòíîñòè. ×òî çäåñü ÿñíî ñðàçó, òàê ýòî
ñïðàâåäëèâîñòü ñëåäîâàíèÿ A ' B ⇒ A ∼ B äëÿ ëþáûõ ôîðìóë
A è B : óêàçàííîå ñîîòíîøåíèå ñëåäóåò èç îïðåäåëåíèé ëîãè÷åñêîé è
äåäóêòèâíîé ýêâèâàëåíòíîñòåé â ñèëó êîððåêòíîñòè. Ïîýòîìó ýêâèâà-
ëåíòíîñòü ' ñîäåðæèòñÿ â ýêâèâàëåíòíîñòè ∼ è â îäèí ñìåæíûé êëàññ
ïî ' ïîïàäóò ôîðìóëû, ðåàëèçóþùèå îäíó è òó æå áóëåâó ôóíêöèþ,
íî, âîçìîæíî, íå âñå. Ñåìàíòè÷åñêàÿ ïîëíîòà È H è áóäåò îçíà÷àòü,
÷òî ⇒ â âûøåïðèâåä¼ííîì ñîîòíîøåíèè ìîæíî çàìåíèòü íà ⇔. Äîêà-
çàòåëüñòâî âîçìîæíîñòè äàííîé çàìåíû áóäåò ñóùåñòâåííî îïèðàòüñÿ
íà ñâîéñòâà äåäóêòèâíîé ýêâèâàëåíòíîñòè è ïîíÿòèå óëüòðàôèëüòðà
áóëåâîé ñòðóêòóðû.

Áóëåâà ñòðóêòóðà. Ôèëüòðû è óëüòðàôèëüòðû.            Ïàðó h P, v i,
ãäå P  ìíîæåñòâî, à v  ÷àñòè÷íûé ïîðÿäîê íà í¼ì, íàçûâà-
þò ÷àñòè÷íî óïîðÿäî÷åííûì ìíîæåñòâîì (ñîêðàù¼ííî ¾÷.ó. ìíîæå-
ñòâîì ¿).
    Ïðè a v b ãîâîðÿò, ÷òî a ïðåäøåñòâóåò (èëè ñîäåðæèòñÿ â) b. Åñ-
ëè a v b è a 6= b, òî ïèøóò a @ b  ýòî îòíîøåíèå ñòðîãîãî ïîðÿäêà.
Ïðè a v b, åñëè íå ñóùåñòâóåò òàêîãî x, ÷òî a @ x è x @ b, ãîâîðÿò,
÷òî a íåïîñðåäñòâåííî ïðåäøåñòâóåò b. Äëÿ íàãëÿäíîãî ïðåäñòàâ-
ëåíèÿ êîíå÷íûõ ÷.ó. ìíîæåñòâ, èìåþùèõ íåáîëüøîå ÷èñëî ýëåìåíòîâ,
èñïîëüçóþò äèàãðàììû Õàññå . Íà ýòèõ äèàãðàììàõ èçîáðàæàþò ýëå-
ìåíòû ÷.ó. ìíîæåñòâ, ïðè÷¼ì åñëè ýëåìåíò a ïðåäøåñòâóåò ýëåìåíòó
b, òî a ðèñóþò íèæå b è ñîåäèíÿþò èõ îòðåçêîì, åñëè a íåïîñðåä-
ñòâåííî ïðåäøåñòâóåò b.
    Ëåãêî ïðîâåðèòü, ÷òî îòíîøåíèå v, çàäàííîå íà ýëåìåíòàõ áóëåâîé
àëãåáðû h B, t, u, − , o, ι i ïî ïðàâèëó
 avb ⇔ atb = b         èëè, ýêâèâàëåíòíî,     a v b ⇔ a u b = a (2.1)
åñòü îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêà. Ðàññìàòðèâàÿ äàííîå îòíî-
øåíèå êàê îñíîâíîå íà ìíîæåñòâå B , ïîëó÷èì áóëåâó ñòðóêòóðó
h B, ∪, ∩, − , v, o, ι i. Ïîíÿòíî, ÷òî áóëåâà ñòðóêòóðà åñòü ÷.ó. ìíîæå-
ñòâî.
   Íà áóëåâîé ñòðóêòóðå êðîìå çàêîíîâ, ïðèâåä¼ííûõ â ï. 1.2 ãëàâû 1
ñïðàâåäëèâû, â ÷àñòíîñòè, ñîîòíîøåíèÿ
                  a v b ⇔ a u b0 = o ⇔ a0 t b = ι.
Ïîñêîëüêó óêàçàííûì ñïîñîáîì ëþáàÿ áóëåâà àëãåáðà ïðåâðàùàåòñÿ â
áóëåâó ñòðóêòóðó, òî ýòè ïîíÿòèÿ ìîæíî íå ðàçëè÷àòü.

Страницы