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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A (∗)
ϕ
U
A
⇔
A = ¬ B [A] = [¬ B] = [B]
[A] ∈ U ⇔ [B] ∈ U
F 3,F 6
⇔ [B] 6∈ U ⇔ |B| = ⇔ |A| = .
A = B
¡
¢
C [A] = [B] ∪ [C]
[A] ∈ U ⇔ [B] ∪ [C] ∈ U
F 4
⇔ [B] ∈ U [C] ∈ U ⇔
⇔ |B| = |C| = ⇔ |B
¡
¢
C| = ⇔ |A| = .
(∗) ¤
ϕ
U
L
∗
2
E
ϕ
E
x = y = ϕ
E
E E
x y
H
²
2
A ⇒ `
H
A
0
H
A ⇒ 2
2
A
0
H
A L
∗
[A] 6= T [A] 6= F
[A] U
ϕ
U
|A|ϕ
U
= A
2
2
A ¤
70          Ãëàâà 2. Èñ÷èñëåíèÿ âûñêàçûâàíèé. Ãèëüáåðòîâñêèå ÈÂ


   Åñëè A  ïðîïîçèöèîíàëüíàÿ ïåðåìåííàÿ è óñëîâèå (∗) âûïîëíÿ-
åòñÿ ïî îïðåäåëåíèþ èíòåðïðåòàöèè ϕU .
   Èíà÷å, ðàññìîòðèì âîçìîæíûå ïîäñëó÷àè ñòðîåíèÿ ôîðìóëû A.
                       (èíä)
Íèæå ýêâèâàëåíòíîñòè    ⇔      ñïðàâåäëèâû ïî èíäóêòèâíîìó ïðåäïî-
ëîæåíèþ.
A = ¬ B.    Èìååì [A] = [¬ B] = [B], îòêóäà
                            F 3,F 6              (èíä)
        [A] ∈ U ⇔ [B] ∈ U      ⇔      [B] 6∈ U    ⇔ |B| = 0 ⇔ |A| = 1.
      ¡
A = B ¢C.     Ïî (2.2) èìååì [A] = [B] ∪ [C], îòêóäà:

                                   F4                        (èíä)
       [A] ∈ U ⇔ [B] ∪ [C] ∈ U ⇔ [B] ∈ U èëè [C] ∈ U ⇔
                                             ¡
                ⇔ |B| = 0 èëè |C| = 1 ⇔ |B ¢ C| = 1 ⇔ |A| = 1.

Òàêèì îáðàçîì, â îáîèõ ñëó÷àÿõ ïîëó÷åíî ñîîòíîøåíèå (∗).                 ¤

   Çàìåòèì, ÷òî ϕU îñóùåñòâëÿåò áóëåâ ãîìîìîðôèçì àëãåáðû Ëèí-
äåíáàóìàÒàðñêîãî L∗ â äâîè÷íóþ àëãåáðó âûñêàçûâàíèé 2.
Ïðèìåð 2.5.  ïðåäûäóùåì ïðèìåðå óëüòðàôèëüòð E çàäà¼ò èíòåð-
ïðåòàöèþ ϕE ïðè êîòîðîé x = 0, y = 1. Ëåãêî ïðîâåðèòü, ÷òî ϕE
âåðèôèöèðóåò ëþáóþ ôîðìóëó èç âñåõ êëàññîâ ýêâèâàëåíòíîñòè, ñî-
ñòàâëÿþùèõ E è òîëüêî èõ. Íà äèàãðàììå Õàññå óëüòðàôèëüòðà E
íà ðèñ. 2.1 êëàññàì ôîðìóë ñîïîñòàâëåíû âåêòîðû èñòèííîñòíûõ çíà-
÷åíèé ñîîòâåòñòâóþùèõ ôóíêöèé (ïîäðàçóìåâàåòñÿ óïîðÿäî÷åíèå íà-
áîðîâ çíà÷åíèé ïåðåìåííûõ ñíà÷àëà ïî x, çàòåì ïî y ).
   Äàííàÿ ëåììà ïîçâîëÿåò ëåãêî äîêàçàòü ñåìàíòè÷åñêóþ ïîëíîòó
èñ÷èñëåíèÿ H .
Òåîðåìà 2.7 (Î ñåìàíòè÷åñêîé ïîëíîòå È H ).               ² C 2 A ⇒ ` H A.
Äîêàçàòåëüñòâî. Ïîêàæåì ñïðàâåäëèâîñòü ýêâèâàëåíòíîãî òðåáóåìî-
ìó ñëåäîâàíèÿ 0H A ⇒ 2C2 A.
   Ïóñòü 0H A. Òîãäà â àëãåáðå ËèíäåíáàóìàÒàðñêîãî L∗ ïîëó÷èì
[A] 6= T . Ðàññìîòðèì ýëåìåíò [A] 6= F è îáðàçóåì ãëàâíûé ôèëüòð,
ïîðîæä¼ííûé [A]. Âñåãäà íàéä¼òñÿ åãî ñîäåðæàùèé óëüòðàôèëüòð U ,
êîòîðûé çàäàñò èíòåðïðåòàöèþ ϕU ïî óêàçàííîìó âûøå ïðàâèëó. Ñî-
ãëàñíî ëåììå 2.3 ïîëó÷èì |A|ϕU = 0, ò.å. A íå ÿâëÿåòñÿ òàâòîëîãèåé,
÷òî è çàïèñûâàþò êàê 2C2 A.                                      ¤

     çàêëþ÷åíèå äàííîãî ïàðàãðàôà äàäèì îïðåäåëåíèå êîððåêòíîñòè
è ñåìàíòè÷åñêîé ïîëíîòû ôîðìàëüíîé òåîðèè îòíîñèòåëüíî íåêîòîðîãî
ñâîéñòâà.

Страницы