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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

N
Γ `
N
Γ `
H
B
0
N ¬ B
0
Γ ` H
Γ ²
2
A ⇒ Γ `
H
A
N
N
r Rl(N)
{Rl(N) r r}
N
(+ N). |A N B| =
(− N). |A N B| = B |x N B| = A
(+ ∨). |A ∨ B| = B |A ∨ B| = A
(− ∨). |A ∨ B| =
(+
¡
¢
). |A
¡
¢
B| =
(−
¡
¢
). |A
¡
¢
B| =
(−¬). {0, 1, 2}
1. Èñ÷èñëåíèå N íàòóðàëüíîãî òèïà                              109


   Â ï. 2 ýêâèâàëåíòíîñòü âûâîäèìîñòåé ñåêâåíöèé Γ     `N è
Γ `H B 0 N ¬ B 0 ñëåäóåò èç çàêîíà ïðîòèâîðå÷èÿ è ïðàâèëà DS
(ïîñêîëüêó çàïèñü Γ ` â ÈÂ H íå îïðåäåëåíà).

  Â ñèëó ñëåäñòâèÿ 1.4 òåîðåìû 3.6 àíàëîã å¼ ï. 3.6 ñïðàâåäëèâ è â
ÈÂ H, ãäå ñïðàâåäëèâà ñëåäóþùàÿ

Òåîðåìà 3.7 (Îá îáîáù¼ííîé ñåìàíòè÷åñêîé ïîëíîòå ÈÑ H ).
  Γ ²C2 A ⇒ Γ `H A.


Íåçàâèñèìîñòü. Ïîñêîëüêó â N âñåãî îäíà ñõåìà àêñèîì, òî îíà
òðèâèàëüíî íåçàâèñèìà.
   Ïðàâèëî âûâîäà íàçûâàåòñÿ íåçàâèñèìûì â èñ÷èñëåíèè , åñëè îíî
íå ÿâëÿåòñÿ äîïóñòèìûì â èñ÷èñëåíèè áåç ýòîãî ïðàâèëà.

Òåîðåìà 3.8. Ëþáîå ïðàâèëî âûâîäà ÈÑ N íåçàâèñèìî îò ñîâîêóï-
íîñòè îñòàëüíûõ.

Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà íåçàâèñèìîñòè äîñòàòî÷íî äëÿ
êàæäîãî ïðàâèëà r èç Rl(N ) íàéòè õàðàêòåðíîå ñâîéñòâî, êîòîðûì îá-
ëàäàþò âñå ñåêâåíöèè, äîêàçóåìûå ïðè ïîìîùè ïðàâèë èç {Rl(N ) r r},
è êîòîðûì íåêîòîðûå äîêàçóåìûå â ÈÑ N ñåêâåíöèè íå îáëàäàþò.
   Áóäåì ïîëüçîâàòüñÿ ãëàâíîé èíòåðïðåòàöèåé. Íîâûå îïðåäåëåíèÿ
ëîãè÷åñêèõ îïåðàöèé äëÿ óêàçàííûõ âûøå ïðàâèë (îñòàëüíûå îïåðàöèè
ïðè ýòîì èìåþò îáû÷íûå îïðåäåëåíèÿ) ñóòü ñëåäóþùèå:

(+ N). |A N B| = 0 (ò.å. êîíúþíêöèÿ îïðåäåëÿåòñÿ êàê òîæäåñòâåííî
      ëîæíàÿ ôóíêöèÿ).
(− N). |A N B| = B è |x N B| = A äëÿ ïåðâîãî è âòîðîãî ïðàâèëà
      ñîîòâåòñòâåííî.
(+ ∨). |A ∨ B| = B è |A ∨ B| = A äëÿ ïåðâîãî è âòîðîãî ïðàâèëà
      ñîîòâåòñòâåííî.
(− ∨). |A ∨ B| = 1 (ò.å. äèçúþíêöèÿ îïðåäåëÿåòñÿ êàê òîæäåñòâåííî
      èñòèííàÿ ôóíêöèÿ);
    ¡¢       ¡
(+ ). |A ¢ B| = 0.
    ¡        ¡
(− ¢). |A ¢ B| = 1.
(−¬). Äëÿ ìíîæåñòâà èñòèííîñòíûõ çíà÷åíèé {0, 1, 2} êîíúþíêöèþ
      îïðåäåëèì êàê ìèíèìóì äâóõ çíà÷åíèé, äèçúþíêöèþ  êàê ìàê-
      ñèìóì, à îòðèöàíèå è èìïëèêàöèþ  ñëåäóþùèì îáðàçîì:

Страницы