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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

F
q
1
, . . . , q
n
A
0
1
, . . . , A
0
n
B
0
1
, . . . , B
0
n
F (q
1
, . . . , q
n
k A
0
1
, . . . , A
0
n
) ∈ T F (q
1
, . . . , q
n
k B
0
1
, . . . , B
0
n
) ∈ F.
F F
0
F
q
i
7→ α
i
q
i
7→ β
i
q
1
, . . . , q
n
(α
1
, . . . , α
n
)
(β
1
, . . . , β
n
)
A
i
α
i
=
α
i
= i = 1, . . . , n
x
¡
¢
x ¬(x
¡
¢
x)
F
0
B
i
β
i
= [ ], i = 1, . . . , n F
0
¤
|A|
ϕ
= |B |
ϕ
ϕ
A B
A ∼ B A ∼ B
(A ≡ B) ∈ T
≡ ∼
A ∼ B
A B
x
¡
¢
y ∼ (¬ x ∨ y) N(z ∨ ¬ z)
x ∨ ¬ x ∼ y ∨ ¬ y
2. Áèíàðíûå îòíîøåíèÿ íà ìíîæåñòâå ôîðìóë                                                    19


Ëåììà 1.1 (Î ïîäñòàíîâêå â íåéòðàëüíóþ ôîðìóëó). Ïóñòü
íåéòðàëüíàÿ ôîðìóëà F çàâèñèò îò ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ
q1 , . . . , qn è òîëüêî îò íèõ. Òîãäà íàéäóòñÿ ôîðìóëû A01 , . . . , A0n è
B10 , . . . , Bn0 òàêèå, ÷òî

F (q1 , . . . , qn k A01 , . . . , A0n ) ∈ T   è   F (q1 , . . . , qn k B10 , . . . , Bn0 ) ∈ F.

Äîêàçàòåëüñòâî. Ðåçóëüòàò ñîîòâåòñòâóþùåé ïîäñòàíîâêè â ôîðìó-
ëó F áóäåì îáîçíà÷àòü F 0 . Ïîñêîëüêó F  íåéòðàëüíàÿ ôîðìóëà,
òî äëÿ íå¼ ñóùåñòâóþò è ìîäåëü, è êîíòðìîäåëü. Ïóñòü îíè îïðåäåëÿ-
þòñÿ ñîîòâåòñòâåííî îòîáðàæåíèÿìè qi 7→ αi è qi 7→ βi ïðîïîçèöèî-
íàëüíûõ ïåðåìåííûõ q1 , . . . , qn â èñòèííîñòíûå íàáîðû (α1 , . . . , αn )
è (β1 , . . . , βn ).
    Âîçüì¼ì â êà÷åñòâå Ai ïðè αi = 1 ïðîèçâîëüíóþ òàâòîëîãèþ, à ïðè
αi = 0  ïðîèçâîëüíîå ïðîòèâîðå÷èå, i = 1, . . . , n. Íàïðèìåð, ìîæíî
               ¡       ¡
áðàòü x ¢ x èëè ¬(x ¢ x) ñîîòâåòñòâåííî. Òîãäà ÿñíî, ÷òî ôîðìóëà
  0
F  òàâòîëîãèÿ.
    Àíàëîãè÷íî, åñëè â êà÷åñòâå Bi , áðàòü ïðîèçâîëüíûå òàâòîëîãèè
[ïðîòèâîðå÷èÿ], åñëè βi = 1 [0], i = 1, . . . , n , òî ôîðìóëà F 0  ïðî-
òèâîðå÷èå.                                                               ¤



2.2 Ëîãè÷åñêàÿ ýêâèâàëåíòíîñòü

   Íàïîìíèì, ÷òî ýêâèâàëåíòíîñòüþ íàçûâàþò ðåôëåêñèâíîå, ñèììåò-
ðè÷íîå è òðàíçèòèâíîå áèíàðíîå îòíîøåíèå íà íåêîòîðîì ìíîæåñòâå.
   Åñëè |A|ϕ = |B|ϕ ïðè ëþáîé èíòåðïðåòàöèè ϕ, òî ãîâîðÿò, ÷òî
ôîðìóëû àëãåáðû ëîãèêè A è B ëîãè÷åñêè ýêâèâàëåíòíû èëè ðàâ-
íîñèëüíû , ÷òî áóäåì çàïèñûâàòü êàê A ∼ B . Ïîíÿòíî, ÷òî A ∼ B
îçíà÷àåò (A ≡ B) ∈ T.
   Ëþáàÿ òàâòîëîãèÿ ëèáî ÿâëÿåòñÿ òîæäåñòâîì, ëèáî ìîæåò áûòü
ïðèâåäåíà ê òàêîìó âèäó c èñïîëüçîâàíèåì çàêîíîâ óòâåðæäåíèÿ èëè
îòðèöàíèÿ (ñì. ïï. 2 è 3 â ïðèìåðå 1.4). Ïîñëå òàêîãî ïðèâåäåíèÿ â
òàâòîëîãèÿõ çíàê ãëàâíîé ñâÿçêè ≡ ìîæíî çàìåíèòü íà ∼, ïîëó÷èâ
óòâåðæäåíèÿ î ðàâíîñèëüíîñòè ñîîòâåòñòâóþùèõ ôîðìóë. ×àñòî ëî-
ãè÷åñêèå çàêîíû çàïèñûâàþò èìåííî â ôîðìå ýêâèâàëåíòíîñòåé, à íå
òàâòîëîãèé.
   Ëîãè÷åñêàÿ ýêâèâàëåíòíîñòü A ∼ B âûðàæàåò ñåìàíòè÷åñêîå ðà-
âåíñòâî ôîðìóë A è B . ßñíî, ÷òî ñèíòàêñè÷åñêîå ðàâåíñòâî ôîðìóë
âëå÷¼ò èõ ñåìàíòè÷åñêîå ðàâåíñòâî, íî íå íàîáîðîò. Áîëåå òîãî, ýêâè-
âàëåíòíûå ôîðìóëû ìîãóò çàâèñåòü îò ðàçíîãî ÷èñëà ïðîïîçèöèîíàëü-
                               ¡
íûõ ïåðåìåííûõ (íàïðèìåð, x ¢ y ∼ (¬ x ∨ y) N(z ∨ ¬ z) ) è âîîáùå
íå èìåòü îáùèõ ïåðåìåííûõ (íàïðèìåð, x ∨ ¬ x ∼ y ∨ ¬ y ). Ëåãêî

Страницы