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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A
∨ ↔ N A
0
↔ ¬ A
0
A
0
≈ M
m ∈ M [m]
≈
m [m]
A
[A] = [B] ⇔ (A ≡ B) ∈ T
A /∼
−
∪
∩
[A]
def
= [¬ A], [A] ∪ [B]
def
= [A ∨ B], [A] ∩ [B]
def
= [A N B]
[A] A ∼
T F A /∼
∪ ∩
[A] ∪ F = [A] ∩ T = [A]
[A] ∪ [A] = T [A] ∩ [A] = F
Φ = h A /∼, ∪, ∩,
−
, F, T i
F T
A
n
n
A
n
A
n
/∼
22                             Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


ëèøü îò îáú¼ìà âõîäÿùèõ â íåãî ïîíÿòèé, íî íå îò èõ ñîäåðæàíèÿ. Âû-
ñêàçûâàíèÿ, çàâèñÿùèå îò ñîäåðæàíèÿ, íàçûâàþò èíòåíñèîíàëüíûìè
(îñòàëüíûå äâà âûñêàçûâàíèÿ â ïðåäûäóùåì ïðèìåðå).
    Ëåãêî âèäåòü, ÷òî äëÿ ôîðìóë àëãåáðû âûñêàçûâàíèé A ñïðàâåä-
ëèâ ïðèíöèï äâîéñòâåííîñòè : åñëè â íåêîòîðîé íå ñîäåðæàùåé ñèìâî-
ëà èìïëèêàöèè ôîðìóëå ïðîèçâåñòè çàìåíû ∨ ↔ N è A0 ↔ ¬ A0 , ãäå
A0  ýëåìåíòàðíîå âûñêàçûâàíèå, òî ïîëó÷åííàÿ ôîðìóëà áóäåò ýê-
âèâàëåíòíà îòðèöàíèþ èñõîäíîé (ñì., íàïðèìåð, [5]). Â òîæå âðåìÿ, îò
çíàêà èìïëèêàöèè ìîæíî ëåãêî èçáàâèòüñÿ, èñïîëüçóÿ ðàâíîñèëüíîñòè
(3) ëåììû 1.2 è ïðàâèëî çàìåíû ýêâèâàëåíòíûõ.
    Íàïîìíèì, ÷òî äëÿ äàííîé ýêâèâàëåíòíîñòè ≈ íà ìíîæåñòâå M
êàæäîìó m ∈ M ìîæíî ñîïîñòàâèòü ìíîæåñòâî [m]≈ ýêâèâàëåíò-
íûõ åìó ýëåìåíòîâ  êëàññîâ ýêâèâàëåíòíîñòè èëè ñìåæíûõ êëàñ-
ñîâ. Åñëè ýêâèâàëåíòíîñòü ôèêñèðîâàíà, òî ñìåæíûé êëàññ ýëåìåíòà
m îáîçíà÷àåì [m]. Ïîíÿòíî, ÷òî ïðè ýòîì êàæäûé ýëåìåíò ïîïàäàåò â
îäèí è òîëüêî îäèí êëàññ ýêâèâàëåíòíîñòè è êëàññû ýêâèâàëåíòíîñòè
èëè ñîâïàäàþò, èëè íå ïåðåñåêàþòñÿ, ò.å. îáðàçóþò ðàçáèåíèå èñõîäíîãî
ìíîæåñòâà.
    ßñíî, ÷òî ðàâíîñèëüíîñòü åñòü îòíîøåíèå ýêâèâàëåíòíîñòè íà ìíî-
æåñòâå A, è ñîîòâåòñòâóþùèå êëàññû ýêâèâàëåíòíîñòè ñîäåðæàò ôîð-
ìóëû, ðåàëèçóþùèå îäíó è òó æå áóëåâó ôóíêöèþ. Èç îïðåäåëåíèé
ñëåäóåò, ÷òî íàïðèìåð, [A] = [B] ⇔ (A ≡ B) ∈ T.
    Íà ìíîæåñòâå A / ∼ êëàññîâ ýêâèâàëåíòíîñòè âñåõ ôîðìóë àëãåáðû
ëîãèêè çàäàäèì îïåðàöèè äîïîëíåíèÿ (− ), îáúåäèíåíèÿ (∪) è ïåðåñå-
÷åíèÿ (∩) ïî ïðàâèëàì
           def                 def                   def
       [A] = [¬ A],   [A] ∪ [B] = [A ∨ B],   [A] ∩ [B] = [A N B]

( [A] îáîçíà÷àåò ñìåæíûé êëàññ ôîðìóëû A ïî ýêâèâàëåíòíîñòè ∼ ).
    Ëåãêî âèäåòü, ÷òî T è F  êëàññû èç A / ∼ è ââåä¼ííûå îïåðàöèè
èìåþò ñëåäóþùèå ñâîéñòâà:
     ˆ îïåðàöèè ∪ è ∩ êîììóòàòèâíû è âçàèìíî äèñòðèáóòèâíû;
     ˆ âûïîëíÿþòñÿ ñîîòíîøåíèÿ [A] ∪ F = [A] ∩ T = [A];
     ˆ ñïðàâåäëèâû çàêîíû [A] ∪ [A] = T è [A] ∩ [A] = F.
Óêàçàííîå îçíà÷àåò, ÷òî ñòðóêòóðà Φ = h A / ∼, ∪, ∩, − , F, T i ÿâëÿ-
åòñÿ áóëåâîé àëãåáðîé ñ íóë¼ì F è åäèíèöåé T. Ýòó ÀÑ ìû íàçîâ¼ì
ôàêòîð-àëãåáðîé ëîãè÷åñêèõ ôîðìóë .
    ×åðåç An áóäåì îáîçíà÷àòü ìíîæåñòâî ôîðìóë àëãåáðû ëîãèêè íàä
n ýëåìåíòàðíûìè âûñêàçûâàíèÿìè. Ââåä¼ííàÿ ôàêòîðèçàöèÿ ïîçâîëÿ-
åò, íàïðèìåð, ðàññìàòðèâàòü âìåñòî áåñêîíå÷íîãî ìíîæåñòâà ôîðìóë
An êîíå÷íîå ìíîæåñòâî An / ∼ èõ êëàññîâ.

Страницы