Таран Т.А. Основы дискретной математики
Подождите немного. Документ загружается.
160 161Áóëåâà àëãåáðàÃëàâà 9
Îáû÷íî îòíîøåíèå ïîðÿäêà íà íàáîðàõ áóëåâûõ ïåðåìåííûõ
îïðåäåëÿåòñÿ òàê. Ðàññìîòðèì äâà íàáîðà: A = (α
1
,..., α
i
, ..., α
n
)
èB=(β
1
,..., β
i
,..., β
n
). Åñëè äëÿ âñåõ i (i= 1, ..., n) α
i
≤β
i
, è ñóùåñòâóåò
õîòÿ áû îäíî òàêîå j, ïðè êîòîðîì α
j
<β
j
, òî íàáîð A ïðåäøåñòâóåò
(ìåíüøå) íàáîðó B. Ýòî îáîçíà÷àåòñÿ: A≤B. Åñëè äëÿ íåêîòîðûõ
i α
i
≤β
i
è ñóùåñòâóåò òàêîå j, ÷òî α
i
>β
i
, òî íàáîðû A è B íåñðàâíèìû.
Íàïðèìåð: íàáîðû (0101) è (0010) íåñðàâíèìû, à íàáîð (0101)
ïðåäøåñòâóåò íàáîðó (0111).
Îïðåäåëåíèå 9.17. Áóëåâà ôóíêöèÿ f íàçûâàåòñÿ ìîíîòîííîé,
åñëè äëÿ ëþáûõ äâóõ íàáîðîâ A è B èç åå îáëàñòè îïðåäåëåíèÿ,
òàêèõ, ÷òî A≤B, f(A)≤f(B). Åñëè õîòÿ áû äëÿ îäíîé ïàðû
íàáîðîâ, òàêèõ, ÷òî A≤B, f(A)>f(B), òî ôóíêöèÿ íåìîíîòîííà.
Ñðåäè áóëåâûõ ôóíêöèé îäíîé è äâóõ ïåðåìåííûõ êîíúþíêöèÿ,
äèçúþíêöèÿ, êîíñòàíòû 0 è 1 ìîíîòîííû, à ôóíêöèè îòðèöàíèÿ,
èìïëèêàöèè, ýêâèâàëåíòíîñòè, øòðèõ Øåôôåðà, ñòðåëêà Ïèðñà
íåìîíîòîííû. Íàïðèìåð, èìïëèêàöèÿ íà íàáîðå (00) ðàâíà 1, à íà
íàáîðå (10) 0, à ïîñêîëüêó (00) ≤ (10), òî ïîëó÷àåì, ÷òî
f(0,0)>f(1,0), ò.å. ñâîéñòâî ìîíîòîííîñòè íå âûïîëíåíî.
Îïðåäåëåíèå 9.18. Áóëåâà ôóíêöèÿ íàçûâàåòñÿ ôóíêöèåé,
ñîõðàíÿþùåé íóëü, åñëè íà íóëåâîì íàáîðå îíà ðàâíà íóëþ, ò.å.
f(0,,0)= 0.
Íåòðóäíî óáåäèòüñÿ, ÷òî ôóíêöèè 0, x, x∧y, x ∨ y, x ⊕ y ñîõðà-
íÿþò 0, à ôóíêöèè 1, ¬x, x≡y íå ñîõðàíÿþò 0.
Îïðåäåëåíèå 9.19. Áóëåâà ôóíêöèÿ íàçûâàåòñÿ ôóíêöèåé,
ñîõðàíÿþùåé åäèíèöó, åñëè íà åäèíè÷íîì íàáîðå îíà ðàâíà åäè-
íèöå, ò.å. f(1,,1)= 1.
Íàïðèìåð, ôóíêöèè 1, x, x∧y, x ∨ y ñîõðàíÿþò 1, à 0, ¬x,
x⊕y íåò.
9.7. Ôóíêöèîíàëüíî çàìêíóòûå êëàññû
áóëåâûõ ôóíêöèé
Îïðåäåëåíèå 9.20. Êëàññ ôóíêöèé íàçûâàåòñÿ ôóíêöèîíàëüíî
çàìêíóòûì, åñëè ñóïåðïîçèöèÿ ýòèõ ôóíêöèé ïðèíàäëåæèò äàí-
íîìó êëàññó.
Òåîðåìà 9.8. Ñóïåðïîçèöèÿ ëèíåéíûõ ôóíêöèé åñòü ôóíêöèÿ
ëèíåéíàÿ.
Äîêàçàòåëüñòâî. Åñëè â ëèíåéíûé ïîëèíîì Æåãàëêèíà íà ìåñòî
êàêîé-ëèáî ïåðåìåííîé ïîäñòàâèòü ëèíåéíóþ ôóíêöèþ, òî âíîâü
ïîëó÷åííûé ïîëèíîì áóäåò òàêæå ëèíåéíûì. Âîçüìåì ïîëèíîì:
α
1
x
1
⊕ ⊕ α
i
x
i
⊕ ⊕ α
n
x
n
⊕ γ. Ïîäñòàâèì âìåñòî x
1
ëèíåéíûé
ïîëèíîì Σβ
i
y
i
⊕ξ. Ïîëó÷èì ëèíåéíûé ïîëèíîì: α
1
β
1
y
1
⊕ ⊕ α
1
β
i
y
i
⊕
⊕ ⊕ α
1
β
m
y
m
⊕α
1
ξ⊕⊕α
n
x
n
⊕γ. Ñëåäîâàòåëüíî, êëàññ ëèíåéíûõ
ôóíêöèé ôóíêöèîíàëüíî çàìêíóò.
Òåîðåìà 9.9. Ñóïåðïîçèöèÿ ìîíîòîííûõ ôóíêöèé åñòü ôóíêöèÿ
ìîíîòîííàÿ. Ñëåäîâàòåëüíî, êëàññ ìîíîòîííûõ ôóíêöèé ÿâëÿ-
åòñÿ ôóíêöèîíàëüíî çàìêíóòûì.
Äîêàçàòåëüñòâî. Ïóñòü ôóíêöèè f(x
1
,, x
n
), g
1
(y
1
, , y
k
), ,
g
n
(y
1
,, y
k
) ìîíîòîííû. Ñîñòàâèì ñóïåðïîçèöèþ ôóíêöèé
ϕ=f(g
1
,, g
n
). Ïóñòü α è β äâà íàáîðà çíà÷åíèé ïåðåìåííûõ
y
1
,, y
k
, ïðè÷åì α ≤ β.  ñèëó ìîíîòîííîñòè ôóíêöèé g
1
, , g
n
g
1
(α)≤g
1
(β), , g
n
(α)≤g
n
(β),
ïîýòîìó íàáîðû çíà÷åíèé ôóíêöèé óïîðÿäî÷åíû:
(g
1
(α), , g
n
(α))≤(g
1
(β), , g
n
(β)),
à â ñèëó ìîíîòîííîñòè ôóíêöèè f
f(g
1
(α), , g
n
(α)) ≤ f(g
1
(β), , g
n
(β)).
Îòñþäà ïîëó÷àåì ϕ(α) ≤ ϕ(β).
Òåîðåìà 9.10. Êëàññ ôóíêöèé, ñîõðàíÿþùèõ íóëü, ÿâëÿåòñÿ
ôóíêöèîíàëüíî çàìêíóòûì.
Äîêàçàòåëüñòâî. Ïóñòü ôóíêöèè f(x
1
,, x
n
), g
1
(y
1
, , y
k
), ,
g
n
(y
1
,, y
k
) ñîõðàíÿþò íóëü. Ñîñòàâèì ñóïåðïîçèöèþ ôóíêöèé
ϕ=f(g
1
, , g
n
). Òîãäà
ϕ(0, , 0) = f(g
1
(0, , 0), , g
n
(0, , 0)) = f(0, , 0) = 0.
Òåîðåìà 9.11. Êëàññ ôóíêöèé, ñîõðàíÿþùèõ åäèíèöó, ÿâëÿåòñÿ
ôóíêöèîíàëüíî çàìêíóòûì.
Äîêàçûâàåòñÿ äâîéñòâåííî òåîðåìå 9.10.
Òåîðåìà 9.12. Êëàññ ñàìîäâîéñòâåííûõ ôóíêöèé ÿâëÿåòñÿ
ôóíêöèîíàëüíî çàìêíóòûì.
Äîêàçàòåëüñòâî. Ïóñòü ôóíêöèè f(x
1
,, x
n
), g
1
(y
1
, , y
k
), ,
g
n
(y
1
,, y
k
) ñàìîäâîéñòâåííû. Ñîñòàâèì ñóïåðïîçèöèþ ôóíêöèé
ϕ= f(g
1
, , g
n
). Òîãäà
ϕ* = f*(g
1
*, , g
n
*) = f(g
1
, , g
n
) = ϕ.
9.8. Ôóíêöèîíàëüíàÿ ïîëíîòà
ñèñòåì áóëåâûõ ôóíêöèé
Îïðåäåëåíèå 9.21. Ñèñòåìà áóëåâûõ ôóíêöèé íàçûâàåòñÿ
ôóíêöèîíàëüíî ïîëíîé, åñëè ëþáàÿ áóëåâà ôóíêöèÿ ìîæåò áûòü
ïðåäñòàâëåíà êàê ñóïåðïîçèöèÿ ôóíêöèé èç ýòîé ñèñòåìû.
Îáîçíà÷èì: T
0
êëàññ ôóíêöèé, ñîõðàíÿþùèõ 0; T
1
êëàññ
ôóíêöèé, ñîõðàíÿþùèõ 1; S êëàññ ñàìîäâîéñòâåííûõ ôóíêöèé;
M êëàññ ìîíîòîííûõ ôóíêöèé; L êëàññ ëèíåéíûõ ôóíêöèé.
162 163Áóëåâà àëãåáðàÃëàâà 9
Òåîðåìà 9.13 (Ïîñòà). Äëÿ òîãî, ÷òîáû ñèñòåìà ôóíêöèé áûëà
ïîëíà, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû îíà ñîäåðæàëà õîòÿ áû
îäíó íåìîíîòîííóþ, õîòÿ áû îäíó íåëèíåéíóþ, õîòÿ áû îäíó
íåñàìîäâîéñòâåííóþ, õîòÿ áû îäíó, íå ñîõðàíÿþùóþ íóëü, è
õîòÿ áû îäíó, íå ñîõðàíÿþùóþ åäèíèöó, ôóíêöèþ.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü óñëîâèé òåîðåìû ñëåäóåò èç
ôóíêöèîíàëüíîé çàìêíóòîñòè è íåïîëíîòû êëàññîâ ìîíîòîííûõ,
ëèíåéíûõ, ñîõðàíÿþùèõ 0, ñîõðàíÿþùèõ 1 è ñàìîäâîéñòâåííûõ
ôóíêöèé. Äîêàçàíî (òåîðåìû 9.9 9.12), ÷òî ôóíêöèÿ, íå ïðèíàä-
ëåæàùàÿ äàííîìó ôóíêöèîíàëüíî çàìêíóòîìó êëàññó, íå ìîæåò
áûòü ïîñòðîåíà ïóòåì ñóïåðïîçèöèè ôóíêöèé ýòîãî êëàññà.
Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íîñòè ïîêàæåì, ÷òî ñ ïîìîùüþ
ôóíêöèé, íå ïðèíàäëåæàùèõ íåêîòîðûì èç êëàññîâ T
0
, T
1
, S, M, L,
ìîæíî ïîñòðîèòü íåêîòîðóþ ïîëíóþ ñèñòåìó ôóíêöèé. Òàêîé
(ïîëíîé) ñèñòåìîé ÿâëÿåòñÿ, íàïðèìåð, îòðèöàíèå è êîíúþíêöèÿ.
Äåéñòâèòåëüíî, ëþáàÿ áóëåâà ôóíêöèÿ ïðåäñòàâèìà â âèäå ÑÄÍÔ,
ò.å. êàê ñóïåðïîçèöèÿ ¬, ∧, ∨. Ñëåäîâàòåëüíî, ñèñòåìà {¬, ∧, ∨}
ôóíêöèîíàëüíî ïîëíà. Ìîæíî èñêëþ÷èòü èç íåå ∨, òàê îíà
ïðåäñòàâèìà êàê ñóïåðïîçèöèÿ ¬ è ∧: x ∨ y = ¬(¬x∧ ¬y).
Ñíà÷àëà ïîñòðîèì êîíñòàíòû. Åñëè ôóíêöèÿ f(x
1
,, x
n
) íåñà-
ìîäâîéñòâåííà, òî ïîäñòàíîâêîé â íåå x è ¬x ìîæíî ïîëó÷èòü êîí-
ñòàíòó. Äåéñòâèòåëüíî, ââèäó íåñàìîäâîéñòâåííîñòè f(x
1
,, x
n
)
ñóùåñòâóåò òàêîé íàáîð (α
1
,..., α
n
), ÷òî f(α
1
,..., α
n
) = f(¬α
1
,..., ¬α
n
).
Òîãäà ôóíêöèÿ ϕ(x) = f(x
α1
,, x
n
αn
) ÿâëÿåòñÿ êîíñòàíòîé, òàê êàê
ϕ(0) = f(0
α1
,, 0
αn
) = f((¬α
1
, ..., ¬α
n
) = f(α
1
, ..., α
n
) = f(1
α1
,, 1
αn
)=ϕ(1).
Êîíñòàíòó 1 ìîæíî ïîñòðîèòü ñ ïîìîùüþ ôóíêöèè, íå ñîõðàíÿ-
þùåé 0 è ñîõðàíÿþùåé 1, ò.å. íåñàìîäâîéñòâåííîé. Äåéñòâèòåëüíî,
ïóñòü f íå ñîõðàíÿåò 0. Òîãäà ϕ(0) = f(0,,0) = 1, à åñëè ïðè ýòîì
f ñîõðàíÿåò 1, òî ϕ(1) = f(1,,1) = 1, ò.å. êîíñòàíòà 1 ïîñòðîåíà.
Äâîéñòâåííî, ïóñòü f
1
íå ñîõðàíÿåò 1. Òîãäà ψ(x)=f
1
(ϕ(x),,ϕ(x))=
= f
1
(1,,1)) = 0, ò.å. ψ(x) åñòü êîíñòàíòà 0.
Åñëè æå f(1,,1)) = 0, òî ϕ(x) = ¬x, òàê êàê ϕ(0) = 1 ïî îïðåäå-
ëåíèþ f, à ϕ(1) = 0. Òîãäà, åñëè âçÿòü íåñàìîäâîéñòâåííóþ ôóíêöèþ
f
2
, òî, ïîäñòàâëÿÿ â íåå x è ¬x, òàêæå ìîæíî ïîëó÷èòü êîíñòàíòó, à
ñ ïîìîùüþ åùå îäíîãî îòðèöàíèÿ, ïîëó÷èòü äðóãóþ êîíñòàíòó.
Òàêèì îáðàçîì, ñ ïîìîùüþ ôóíêöèé, íå ñîõðàíÿþùèõ 0, íå ñîõðàíÿ-
þùèõ 1 è íåñàìîäâîéñòâåííûõ, ìîæíî ïîñòðîèòü êîíñòàíòû 0, 1.
Ñ ïîìîùüþ íåìîíîòîííîé ôóíêöèè ïîäñòàíîâêîé â íåå êîí-
ñòàíò ìîæíî ïîëó÷èòü îòðèöàíèå. Äåéñòâèòåëüíî, ïóñòü f íåìîíî-
òîííà. Òîãäà ñóùåñòâóþò íàáîðû α è β, òàêèå, ÷òî α≤β, f(α) = 1,
f(β) = 0. Ïîñêîëüêó α ≤ β, òî â α åñòü íåñêîëüêî, íàïðèìåð, k
ýëåìåíòîâ, êîòîðûå ðàâíû 0, â òî âðåìÿ êàê â β ýòè æå ýëåìåíòû
ðàâíû 1. Âîçüìåì íàáîð α è çàìåíèì â íåì ïåðâûé òàêîé íóëåâîé
ýëåìåíò íà 1, ïîëó÷èì íàáîð α≤α
1
, êîòîðûé îòëè÷àåòñÿ îò α òîëüêî
îäíèì ýëåìåíòîì (òàêèå íàáîðû íàçûâàþò ñîñåäíèìè). Ïîâòîðÿÿ
ýòó îïåðàöèþ k ðàç, ïîëó÷èì ïîñëåäîâàòåëüíîñòü íàáîðîâ
α≤α
1
≤≤α
k1
≤β
, â êîòîðîé ëþáûå äâà ñîñåäíèõ íàáîðà
îòëè÷àþòñÿ äðóã îò äðóãà òîëüêî îäíèì ýëåìåíòîì.  ýòîé öåïî÷êå
íàéäóòñÿ äâà òàêèå íàáîðà α
i
, α
i+1
, ÷òî f(α
i
) = 1, f(α
i+1
) = 0. Ïóñòü
ýòè íàáîðû îòëè÷àþòñÿ i-ì ýëåìåíòîì (çíà÷åíèåì ïåðåìåííîé x
i
),
îñòàëüíûå ýëåìåíòû îäèíàêîâû. Ïîäñòàâèì â f ýòè çíà÷åíèÿ. Òîãäà
ïîëó÷èì ôóíêöèþ f(α
i
1
,, x
i
, α
i
i+1
, , α
i
n
) = g(x
i
), êîòîðàÿ çàâèñèò
òîëüêî îò x
i
. Òîãäà g(0) = g(α
i
i
) = f(α
i
) = 1, g(1) = g(α
i+1
i
) = f(α
i+1
)=0.
Îòñþäà ñëåäóåò, ÷òî g(x
i
) = ¬x
i
.
Ñ ïîìîùüþ ïîäñòàíîâêè â íåëèíåéíóþ ôóíêöèþ êîíñòàíò è
èñïîëüçîâàíèÿ îòðèöàíèÿ ìîæíî ïîñòðîèòü êîíúþíêöèþ è äèçú-
þíêöèþ. Äåéñòâèòåëüíî, åñëè ôóíêöèÿ f íåëèíåéíàÿ, òî åå ïîëèíîì
Æåãàëêèíà ñîäåðæèò êîíúþíêöèþ ïåðåìåííûõ, íàïðèìåð, K=x
1
x
2
x
k
.
Ïîëîæèì x
3
= = x
k
= 1, à äëÿ âñåõ x
j
, íå ñîäåðæàùèõñÿ â K, x
j
= 0.
Òîãäà êîíúþíêöèÿ K = x
1
x
2
, îñòàëüíûå êîíúþíêöèè îáðàòÿòñÿ â 0,
à ïîëèíîì Æåãàëêèíà ïðèìåò âèä ϕ(x
1
,x
2
)=x
1
x
2
⊕α
1
x
1
⊕ α
2
x
2
⊕γ,
ãäå α
1
, α
2
, γ êîýôôèöèåíòû, ðàâíûå 0 èëè 1. Ïðè ïîäñòàíîâêå
ðàçëè÷íûõ êîíñòàíò âìåñòî α
1
, α
2
, γ áóäóò ïîëó÷åíû ðàçíûå ôóíê-
öèè. Ðàññìîòðèì ôóíêöèþ ψ(x
1
,x
2
), ïîëó÷àåìóþ èç ϕ(x
1
,x
2
) ñëåäó-
þùèì îáðàçîì:
ψ(x
1
,x
2
) = ϕ(x
1
⊕α
2
,x
2
⊕ α
1
) ⊕ α
1
α
2
⊕ γ =
= (x
1
⊕α
2
)(x
2
⊕ α
1
) ⊕ α
1
(x
1
⊕α
2
) ⊕ α
2
(x
2
⊕ α
1
) ⊕ γ ⊕ α
1
α
2
⊕ γ = x
1
x
2
.
Òàêèì îáðàçîì, êîíúþíêöèÿ ïîëó÷åíà.
Äëÿ ïîëó÷åíèÿ äèçúþíêöèè ïî çàêîíàì äå Ìîðãàíà ïîòðåáóåòñÿ
òîëüêî îòðèöàíèå.
Ïðèìåð. Ñèñòåìû ôóíêöèé {∨, ∧, ¬}, {⊕, ∧, 0, 1}, {→, ¬} ÿâëÿþòñÿ
ôóíêöèîíàëüíî ïîëíûìè. Äëÿ ïðèìåðà ïðîâåðèì ïîëíîòó ñèñòåìû
ôóíêöèé {¬, →}. Äëÿ èññëåäóåìîé ñèñòåìû ñîñòàâèì òàáëèöó Ïîñòà
(ñì. òàáë.9.5). Åñëè ôóíêöèÿ âõîäèò â ôóíêöèîíàëüíî çàìêíóòûé
êëàññ, òî â òàáëèöå Ïîñòà â ñîîòâåòñòâóþùåé ÿ÷åéêå ñòàâèòñÿ çíàê
«+», èíà÷å çíàê «».
Ôóíêöèÿ ¬x íå ñîõðàíÿåò 0 è 1, òàê êàê íà íóëåâîì íàáîðå îíà
ïðèíèìàåò çíà÷åíèå 1, à íà åäèíè÷íîì 0. Î÷åâèäíî, ÷òî äàííàÿ
ôóíêöèÿ íåìîíîòîííà. Ôóíêöèÿ ñàìîäâîéñòâåííà, òàê êàê íà
ïðîòèâîïîëîæíûõ íàáîðàõ îíà ïðèíèìàåò ïðîòèâîïîëîæíûå
çíà÷åíèÿ. Ôóíêöèÿ ëèíåéíà åå ïîëèíîì Æåãàëêèíà: ¬õ = õ⊕1.
Ôóíêöèÿ õ→ó íå ñîõðàíÿåò 0 è ñîõðàíÿåò 1. Ýòà ôóíêöèÿ íåìîíî-
òîííà, òàê êàê íàáîð (0,0) ïðåäøåñòâóåò íàáîðó (1,0), íî 0→0=1,
à 1→0 = 0. Íà ïðîòèâîïîëîæíûõ íàáîðàõ (0,0) è (1,1) ôóíêöèÿ
ïðèíèìàåò îäèíàêîâûå çíà÷åíèÿ 1, ñëåäîâàòåëüíî, îíà íåñàìî-
äâîéñòâåííà.
164 165Áóëåâà àëãåáðàÃëàâà 9
Äëÿ ïðîâåðêè ëèíåéíîñòè õ→ó ïîñòðîèì êàíîíè÷åñêèé ïîëè-
íîì Æåãàëêèíà:
õ→ó = ¬x¬ó ∨ ¬xó ∨ õó = (õ ⊕ 1)(ó ⊕ 1) ⊕ (õ ⊕ 1)ó ⊕ õó=
=õó⊕õ ⊕ 1. Ôóíêöèÿ íåëèíåéíà, òàê êàê ñîäåðæèò ýëåìåíò õó.
Òàáëèöà 9.5
Ñèñòåìà ôóíêöèé {¬, →} ïîëíà, òàê êàê â êàæäîì ñòîëáöå
òàáëèöû Ïîñòà èìååòñÿ õîòÿ áû îäèí çíàê «».
9.9. Ìèíèìèçàöèÿ áóëåâûõ ôóíêöèé
Îïðåäåëåíèå 9.22. Èìïëèêàíòîé áóëåâîé ôóíêöèè f(x
1
,...,x
n
)
íàçûâàåòñÿ òàêàÿ áóëåâà ôóíêöèÿ g(x
1
,...,x
n
), êîòîðàÿ ðàâíà
åäèíèöå íà íåêîòîðûõ èç òåõ íàáîðîâ, íà êîòîðûõ ðàâíà åäèíèöå
äàííàÿ ôóíêöèÿ, è ðàâíà íóëþ íà îñòàëüíûõ íàáîðàõ (Èç
îïðåäåëåíèÿ ñëåäóåò, ÷òî ôóíêöèÿ g èìïëèêàíòà f, åñëè
g→f≡1.) Ãîâîðÿò, ÷òî èìïëèêàíòà g ïîêðûâàåò ñâîèìè åäèíè-
öàìè íåêîòîðûå åäèíèöû äàííîé ôóíêöèè f.
Åñëè ôóíêöèÿ çàäàíà â âèäå ÄÍÔ, ò.å. â âèäå äèçúþíêöèè ýëå-
ìåíòàðíûõ êîíúþíêöèé, òî êàæäûé êîíúþíêò ÿâëÿåòñÿ èìïëèêàí-
òîé äàííîé ôóíêöèè. Äëèíà íåêîòîðûõ ýëåìåíòàðíûõ êîíúþíêöèé
ìîæåò áûòü óìåíüøåíà ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé.
Äëÿ ýòîãî ïðèìåíÿþòñÿ ñëåäóþùèå ñîîòíîøåíèÿ:
(9.24) çàêîí íåïîëíîãî ñêëåèâàíèÿ:
xy∨¬xy=y;
(x ∨ y)(¬x ∨ y)=y;
(9.25) çàêîí ïîëíîãî ñêëåèâàíèÿ:
xy∨¬xz=xy∨¬xz∨yz;
(x ∨ y)(¬x ∨ z)=(x ∨ y)(¬x ∨ z)(y ∨ z);
(9.26) çàêîíû ïîãëîùåíèÿ:
x ∨ xy = x;
x(x ∨ y) = x;
(9.27) x ∨ ¬xy = x ∨ y;
x (¬x ∨ y) = xy.
Îïðåäåëåíèå 9.23. Ýëåìåíòàðíàÿ êîíúþíêöèÿ, êîòîðàÿ ÿâëÿ-
åòñÿ èìïëèêàíòîé ôóíêöèè f, íî íèêàêàÿ åå ñîáñòâåííàÿ ÷àñòü
èìïëèêàíòîé ýòîé ôóíêöèè íå ÿâëÿåòñÿ, íàçûâàåòñÿ ïðîñòîé
èìïëèêàíòîé äàííîé ôóíêöèè.
Äëèíà ïðîñòîé èìïëèêàíòû óæå íå ìîæåò áûòü óìåíüøåíà
ïóòåì ñêëåèâàíèÿ åå ñ äðóãèìè èìïëèêàíòàìè äàííîé ôóíêöèè.
Îïðåäåëåíèå 9.24. Äèçúþíêöèÿ âñåõ ïðîñòûõ èìïëèêàíò áóëå-
âîé ôóíêöèè íàçûâàåòñÿ ñîêðàùåííîé äèçúþíêòèâíîé íîðìàëü-
íîé ôîðìîé áóëåâîé ôóíêöèè.
Ïðèìåð. Ñîêðàòèì ôîðìóëó: F(x, y, z) = xyz ∨ x¬yz ∨ xy¬z ∨
∨¬xy¬z. Ñêëåèì êîíñòèòóåíòû: xyz ∨ x¬yz = xz, xy¬z ∨ ¬xy¬z=
=y¬z, xyz∨ xy¬z = xy. Ïîëó÷èì ñîêðàùåííóþ ôîðìó: F(x, y, z) =
=xz ∨ y¬z ∨ xy.
Ìíîæåñòâî âñåõ ïðîñòûõ èìïëèêàíò ïîêðûâàåò âñå åäèíèöû
áóëåâîé ôóíêöèè. Îäíàêî ïðåäñòàâëåíèå áóëåâîé ôóíêöèè â âèäå
ñîêðàùåííîé ÄÍÔ åùå íå ÿâëÿåòñÿ ñàìûì ýêîíîìè÷íûì. Ñðåäè
ìíîæåñòâà ïðîñòûõ èìïëèêàíò ìîãóò îêàçàòüñÿ ëèøíèå, ò.å. òàêèå,
êîòîðûå ïîêðûâàþò åäèíèöû ôóíêöèè, óæå ïîêðûòûå äðóãèìè
èìïëèêàíòàìè. Óäàëÿÿ íåíóæíûå èìïëèêàíòû, ìîæíî ïîëó÷èòü
òóïèêîâóþ äèçúþíêòèâíóþ íîðìàëüíóþ ôîðìó. Òóïèêîâàÿ ÄÍÔ,
ñîäåðæàùàÿ íàèìåíüøåå êîëè÷åñòâî èìïëèêàíò è ïåðåìåííûõ,
íàçûâàåòñÿ ìèíèìàëüíîé ÄÍÔ.
9.9.1. Ìåòîä Êâàéíà ïîëó÷åíèÿ ñîêðàùåííîé
äèçúþíêòèâíîé íîðìàëüíîé ôîðìû
Òåîðåìà 9.14 (Êâàéíà). Åñëè â ñîâåðøåííîé äèçúþíêòèâíîé
íîðìàëüíîé ôîðìå áóëåâîé ôóíêöèè ïðîèçâåñòè âñå îïåðàöèè
íåïîëíîãî ñêëåèâàíèÿ (9.24), à çàòåì âñå îïåðàöèè ïîãëîùåíèÿ
(9.25, 9.26), òî â ðåçóëüòàòå áóäåò ïîëó÷åíà ñîêðàùåííàÿ ÄÍÔ
äàííîé ôóíêöèè.
Äëÿ ïðåîáðàçîâàíèÿ ïðîèçâîëüíîé ÄÍÔ ê âèäó ÑÄÍÔ íåîáõî-
äèìî ïðèìåíèòü ê ýëåìåíòàðíûì êîíúþíêöèÿì, ñîäåðæàùèì íå
âñå ïåðåìåííûå, îïåðàöèþ ðàçâåðòûâàíèÿ, íàïðèìåð: xy(z∨¬z)=
=xyz∨xy¬z, ãäå z íåäîñòàþùàÿ ïåðåìåííàÿ.
Ïðèìåð. Áóëåâà ôóíêöèÿ çàäàíà â âèäå: f(x, y, z)=¬xyz∨
∨x¬y¬z∨¬yz. Ïðèâåäåì ôîðìóëó ê ÑÄÍÔ: f(x,y,z)= =¬xyz∨
∨x¬y¬z∨¬yz(x∨¬x)=¬xyz∨x¬y¬z∨x¬yz∨¬x¬yz. Âûïèøåì
âñå êîíñòèòóåíòû åäèíèöû è ïðîèçâåäåì âñå îïåðàöèè íåïîëíîãî
ñêëåèâàíèÿ:
Ò
0
Ò
1
SML
¬ ++
→ +
* ¬xyz ¬yz
* x¬yz x¬y
* x¬y¬z ¬xz
* ¬x¬yz
166 167Áóëåâà àëãåáðàÃëàâà 9
Îòìå÷àåì âñå ñêëåèâàþùèåñÿ êîíúþíêöèè ñèìâîëîì «*». Îíè
ïîãëîùàþòñÿ èìïëèêàíòàìè, ïîëó÷åííûìè â ðåçóëüòàòå ñêëåèâà-
íèÿ. Íåîòìå÷åííûå êîíúþíêöèè íè÷åì íå ïîãëîùàþòñÿ è ÿâëÿþòñÿ
ïðîñòûìè èìïëèêàíòàìè. Ñîêðàùåííàÿ ÄÍÔ äàííîé ôóíêöèè:
f(x, y, z)=¬yz∨x¬y∨¬xz. Äëÿ íàõîæäåíèÿ ìèíèìàëüíîé ÄÍÔ
ñîñòàâèì èìïëèêàíòíóþ ìàòðèöó (òàáë.9.6), â êîòîðîé ïî ñòðîêàì
çàïèñûâàåì èìïëèêàíòû, ïî ñòîëáöàì êîíñòèòóåíòû åäèíèöû.
Òàáëèöà 9.6
 êëåòêàõ òàáëèöû êðåñòèêàìè îòìå÷àåì èìïëèêàíòû, ïîêðûâà-
þùèå åäèíèöû äàííîé ôóíêöèè. Âíèçó òàáëèöû ñèìâîëîì «*»
îòìå÷àåì òå ñòîëáöû, â êîòîðûõ ñòîèò òîëüêî îäèí êðåñòèê, ñîîòâåò-
ñòâóþùèå èì èìïëèêàíòû òàêæå îòìå÷àåì ñèìâîëîì «*» îíè
ÿâëÿþòñÿ îáÿçàòåëüíûìè. Îòìå÷àåì òàêæå ñèìâîëîì «+» òå ñòîëá-
öû, êîòîðûå ïîêðûâàþòñÿ îáÿçàòåëüíûìè èìïëèêàíòàìè. Åñëè âñå
ñòîëáöû îòìå÷åíû, òî ïîëó÷åííûé íàáîð îáÿçàòåëüíûõ èìïëèêàíò
ñîñòàâëÿåò ìèíèìàëüíóþ ÄÍÔ. Åñëè ÷àñòü ñòîëáöîâ îñòàåòñÿ íå-
ïîêðûòîé, èç îñòàâøèõñÿ èìïëèêàíò âûáèðàåòñÿ íàèìåíüøåå ÷èñëî
íàèáîëåå êîðîòêèõ èìïëèêàíò òàê, ÷òîáû âñå ñòîëáöû áûëè ïîêðû-
òû. Â íàøåì ïðèìåðå ìèíèìàëüíàÿ ÄÍÔ: f(x, y, z)=x¬y∨¬xz.
9.9.2. Ìèíèìèçàöèÿ áóëåâûõ ôóíêöèé ñ ïîìîùüþ
äèàãðàìì Âåé÷à
Áóëåâû ôóíêöèè ìîãóò áûòü ïðåäñòàâëåíû ãðàôè÷åñêè ñ âèäå
äèàãðàìì Âåé÷à èëè êàðò Êàðíî (îíè ðàçëè÷àþòñÿ òîëüêî îáîçíà÷å-
íèÿìè êëåòîê òàáëèöû). Ðàññìîòðèì äèàãðàììû Âåé÷à äëÿ ôóíê-
öèé îò òðåõ è ÷åòûðåõ ïåðåìåííûõ (ñì. ðèñ. 9.2).
Êàæäàÿ êëåòêà äèàãðàììû ñîîòâåòñòâóåò îäíîìó íàáîðó ïåðå-
ìåííûõ, íîìåð êëåòêè ýòî äâîè÷íûé êîä íàáîðà. Ïðè çàäàíèè
áóëåâîé ôóíêöèè â ñîîòâåòñòâóþùóþ íîìåðó íàáîðà êëåòêó çàïè-
ñûâàåòñÿ åäèíèöà, è, òàêèì îáðàçîì, êàæäàÿ êëåòêà äèàãðàììû ñ 1
ïðåäñòàâëÿåò ñîáîé îäíó êîíñòèòóåíòó åäèíèöû.
Ïðèìåð. Ïóñòü ôóíêöèÿ f(x, y, z, t) = 1 íà íàáîðàõ 0, 1, 2, 3, 6,
7, 8, 15. Äèàãðàììà Âåé÷à äëÿ çàäàííîé ôóíêöèè ïðåäñòàâëåíà íà
ðèñ.9.3. Åäèíèöû ôóíêöèè, ñòîÿùèå â ñîñåäíèõ êëåòêàõ, îòëè÷àþò-
ñÿ çíà÷åíèåì òîëüêî îäíîé ïåðåìåííîé, ñëåäîâàòåëüíî, îíè ñêëåèâà-
þòñÿ ïî ýòîé ïåðåìåííîé è îáðàçóþò èìïëèêàíòó.  ýòîì ñëó÷àå
ãîâîðÿò, ÷òî èìïëèêàíòà ïîêðûâàåò ñîîòâåòñòâóþùèå åäèíèöû áó-
ëåâîé ôóíêöèè. Íàïðèìåð, äâå åäèíèöû íà íàáîðàõ 7 è 15, ïîêðû-
âàþòñÿ èìïëèêàíòîé yzt, ÷åòûðå åäèíèöû íà íàáîðàõ 2,3,7,6
èìïëèêàíòîé ¬xz. Ïðè ýòîì ñîñåäíèìè ñ÷èòàþòñÿ òàêæå êëåòêè,
ñòîÿùèå âäîëü ëåâîãî è ïðàâîãî êðàÿ äèàãðàììû (îòëè÷àþòñÿ çíà÷å-
íèåì y) è âäîëü âåðõíåãî è íèæíåãî êðàÿ (îòëè÷àþòñÿ çíà÷åíèåìx).
Ðèñ. 9.2. Äèàãðàììû Âåé÷à
Ïðè ìèíèìèçàöèè
áóëåâîé ôóíêöèè íà
äèàãðàììå Âåé÷à ñíà-
÷àëà íàõîäÿò ïîêðû-
òèÿ, ñîäåðæàùèå ìàê-
ñèìàëüíîå ÷èñëî åäè-
íèö (8, 4, 2), à çàòåì
ïîêðûòèÿ, íàêðûâàþ-
ùèå îñòàâøèåñÿ åäè-
íèöû òàêèì îáðàçîì,
÷òîáû îíè òàêæå áûëè
ìàêñèìàëüíû ïî âåëè-
÷èíå è ïðè óäàëåíèè
ýòîãî ïîêðûòèÿ õîòÿ
áû îäíà åäèíèöà ôóíê-
öèè îñòàëàñü íåïîêðûòîé. Ïðè ýòîì íåêîòîðûå åäèíèöû ìîãóò áûòü
ïîêðûòû íåîäíîêðàòíî. Äëÿ ôóíêöèè, ïðåäñòàâëåííîé íà ðèñ.9.3,
ìèíèìàëüíàÿ ÄÍÔ: ¬x¬y ∨ ¬xz ∨ yzt ∨ ¬y¬z¬t.
Ìèíèìàëüíàÿ ÊÍÔ ñòðîèòñÿ äâîéñòâåííî ïî äèàãðàììå Âåé÷à,
çàïîëíåííîé íóëÿìè â ïóñòûõ êëåòêàõ. Äëÿ äàííîé ôóíêöèè ìèíè-
ìàëüíàÿ ÊÍÔ: (¬y∨z)(¬x∨¬z∨t)(¬x∨y∨¬t).
¬xyz x¬y¬x¬yz ¬x¬yz
¬yz ××
x¬y * ××
¬xz * ××
**++
Ðèñ. 9.3. Ìèíèìàëüíàÿ ÄÍÔ
169
Ãëàâà 10. ËÎÃÈÊÀ ÂÛÑÊÀÇÛÂÀÍÈÉ
10.1. Ìåòîäîëîãè÷åñêèå ïðèíöèïû
ôîðìàëüíîé ëîãèêè
Ëîãèêà íàóêà î ïðàâèëüíûõ ðàññóæäåíèÿõ, î ïðèåìàõ è ìåòî-
äàõ ïîçíàíèÿ ñ ïîìîùüþ ðàññóæäåíèé. Ñëîâî «ëîãèêà» ïðîèñõîäèò
îò äðåâíåãðå÷åñêîãî «ëîãîñ»: «ïîíÿòèå», «ðàçóì», ðàññóæäåíèå».
Ëîãèêà êàê íàóêà î ïðàâèëüíûõ ðàññóæäåíèÿõ áûëà çàëîæåíà â
äðåâíåé Ãðåöèè Àðèñòîòåëåì è íà ïðîòÿæåíèè ìíîãèõ âåêîâ
ðàçâèâàëàñü êàê ÷àñòü ôèëîñîôèè. Òîëüêî â êîíöå 19-ãî íà÷àëå
20-ãî âåêà ñ ïîÿâëåíèåì áóëåâîé àëãåáðû íà÷àëîñü áóðíîå ðàçâèòèå
ìàòåìàòè÷åñêîé (ôîðìàëüíîé) ëîãèêè.  íàñòîÿùåå âðåìÿ ðàçëè÷à-
þò òðàäèöèîííóþ ëîãèêó è ôîðìàëüíóþ, ìàòåìàòè÷åñêóþ ëîãèêó,
ñîîòíîøåíèå êîòîðûõ ïîêàçàíî íà ðèñ. 10.1.
Ðèñ.10. 1. Ñòðóêòóðà ëîãèêè
Ëîãèêà, èçó÷àÿ ïðàâèëüíûå ðàññóæäåíèÿ, îïåðèðóåò ïîíÿòèÿìè
èñòèííîñòè è ëîæíîñòè. Ïðàâèëüíîå ðàññóæäåíèå èëè âûñêàçûâà-
íèå ïîëàãàåòñÿ èñòèííûì, íåïðàâèëüíîå ëîæíûì. Ìåòîäîëîãè÷åñ-
êèå îñíîâû ôîðìàëüíîé ëîãèêè çàêëþ÷àþòñÿ â âûïîëíåíèè íåñ-
êîëüêèõ ïðèíöèïîâ.
Ïðèíöèï òîæäåñòâà. Èñòèííîñòü ôàêòîâ, ëåæàùèõ â îñíîâå âûñêà-
çûâàíèé è ðàññóæäåíèé, óñòàíàâëèâàåòñÿ íà îñíîâàíèè äåéñòâèòåëü-
íîñòè, èçâåñòíûõ çàêîíîâ, íàáëþäåíèé. Åñëè èñòèííîñòü êàêîãî-ëèáî
ôàêòà óñòàíîâëåíà, òî îíà íå ïîäâåðãàåòñÿ ñîìíåíèþ è íå èçìåíÿåòñÿ
â ïðîöåññå ðàññóæäåíèÿ. Ýòî îçíà÷àåò òàêæå, ÷òî îäèí è òîò æå òåðìèí
èñïîëüçóåòñÿ âñåãäà â îäíîì è òîì æå ñìûñëå.
Ïðèíöèï íåïðîòèâîðå÷èâîñòè îçíà÷àåò, ÷òî, óòâåðæäàÿ ÷òî-
ëèáî, íåëüçÿ îòðèöàòü òî æå ñàìîå. Îäèí è òîò æå ôàêò
(âûñêàçûâàíèå) íå ìîæåò áûòü îäíîâðåìåííî èñòèííûì è ëîæíûì.
Íàïðèìåð, âûñêàçûâàíèå Ñîêðàòà «ß çíàþ, ÷òî ÿ íè÷åãî íå çíàþ»
ïðîòèâîðå÷èâî, òàê êàê îäíîâðåìåííî óòâåðæäàåò è îïðîâåðãàåò
îäèí è òîò æå ôàêò: åñëè Ñîêðàò çíàåò, ÷òî îí íè÷åãî íå çíàåò, òî
îí íå çíàåò òàêæå è ýòîãî. Ñîãëàñíî ïðèíöèïó íåïðîòèâîðå÷èâîñòè,
èç ðàññìîòðåíèÿ èñêëþ÷àþòñÿ òàêèå âûñêàçûâàíèÿ, èñòèííîñòü èëè
ëîæíîñòü êîòîðûõ íå ìîæåò áûòü óñòàíîâëåíà, íàïðèìåð, âûñêàçû-
âàíèå î áðàäîáðåå, êîòîðûé äîëæåí (èëè íå äîëæåí) áðèòü ñàìîãî
ñåáÿ, âûñêàçûâàíèå êðèòÿíèíà î òîì, ÷òî âñå êðèòÿíå ëæåöû, è
äðóãèå ñåìàíòè÷åñêèå ïàðàäîêñû.
Ïðèíöèï èñêëþ÷åííîãî òðåòüåãî. Íåëüçÿ îäíîâðåìåííî îòâåð-
ãàòü âûñêàçûâàíèå è åãî îòðèöàíèå. Ëþáîå âûñêàçûâàíèå ìîæåò
áûòü ëèáî èñòèííûì, ëèáî ëîæíûì, òðåòüåãî íå äàíî.
Ïðèíöèï äîñòàòî÷íîãî îñíîâàíèÿ. Âñÿêîå âûñêàçûâàíèå
äîëæíî áûòü îáîñíîâàíî, ò.å. èñòèííîñòü óòâåðæäåíèÿ íåëüçÿ ïðè-
íèìàòü íà âåðó. Åñëè óòâåðæäåíèå âûâîäèòñÿ èç êàêèõ-ëèáî
ñóæäåíèé, äàííûõ, ôàêòîâ îñíîâàíèé, òî èõ äîëæíî áûòü
äîñòàòî÷íî äëÿ óñòàíîâëåíèÿ èñòèííîñòè óòâåðæäåíèÿ.
10.2. Îñíîâíûå ïîíÿòèÿ ëîãèêè âûñêàçûâàíèé
Ñóæäåíèå, èëè âûñêàçûâàíèå ýòî ìûñëü, â êîòîðîé óòâåðæ-
äàåòñÿ íàëè÷èå èëè îòñóòñòâèå êàêèõ-ëèáî ôàêòîâ èëè ñâÿçåé
ìåæäó ôàêòàìè. Âûñêàçûâàíèÿ âûðàæàþòñÿ ïîâåñòâîâàòåëüíûìè
ïðåäëîæåíèÿìè.
Îïðåäåëåíèå 10.1. Ïðîñòîå âûñêàçûâàíèå ýòî ïðîñòîå ïîâå-
ñòâîâàòåëüíîå ïðåäëîæåíèå, îòíîñèòåëüíî êîòîðîãî ìîæíî îäíî-
çíà÷íî ñêàçàòü, èñòèííî îíî èëè ëîæíî.
Âîïðîñèòåëüíûå è âîñêëèöàòåëüíûå ïðåäëîæåíèÿ âûñêàçûâàíè-
ÿìè íå ÿâëÿþòñÿ.
Ëîãè÷åñêèå çíà÷åíèÿ Èñòèííî (True) è Ëîæíî (False) áóäåì
îáîçíà÷àòü ñîîòâåòñòâåííî T è F.
Ïðèìåðû.
«Êèåâ ñòîëèöà Óêðàèíû» èñòèííîå âûñêàçûâàíèå, îíî èìååò
çíà÷åíèå True («èñòèííî»). «5>10» ëîæíîå âûñêàçûâàíèå, îíî
èìååò çíà÷åíèå False («ëîæíî»). «Âñå ëþäè ñìåðòíû» èñòèííîå
âûñêàçûâàíèå. «Íåêîòîðûå ëþäè þðèñòû» èñòèííîå âûñêà-
çûâàíèå.
Êàæäîå ïðîñòîå âûñêàçûâàíèå îáîçíà÷àþò ñèìâîëàìè ëàòèíñêî-
ãî àëôàâèòà (ñ èíäåêñàìè èëè áåç èíäåêñîâ), êîòîðûå íàçûâàþò
ïðîïîçèöèîíàëüíûìè ñèìâîëàìè: A, B, C, A
1
, A
2
.
Cëîæíûå âûñêàçûâàíèÿ ñîñòàâëÿþòñÿ èç ïðîñòûõ ñ ïîìîùüþ
ñîþçîâ «íå», «è», «èëè», «åñëè ..., òî...», «òîãäà è òîëüêî òîãäà».
Ýòèì ñîþçàì ñîîòâåòñòâóþò ëîãè÷åñêèå îïåðàöèè: óíàðíàÿ îïåðà-
öèÿ îòðèöàíèÿ ¬ («íå»), áèíàðíûå îïåðàöèè êîíúþíêöèè & («è»),
äèçúþíêöèè ∨ («èëè»), èìïëèêàöèè → («åñëè, òî», ýêâèâà-
ëåíòíîñòè ≡ («òîãäà è òîëüêî òîãäà»). Ñèìâîëû îïåðàöèé íàçûâàþò
ïðîïîçèöèîíàëüíûìè ñâÿçêàìè. Èñòèííîñòü èëè ëîæíîñòü ñëîæíîãî
âûñêàçûâàíèÿ çàâèñèò îò èñòèííîñòè èëè ëîæíîñòè âõîäÿùèõ â
Ëîãèêà âûñêàçûâàíèé
170 171
íåãî ïðîñòûõ âûñêàçûâàíèé, à òàêæå òåì ñïîñîáîì, êîòîðûìè îíè
êîìáèíèðóþòñÿ, ò.å. ñâÿçêîé, èñïîëüçóåìîé äëÿ ïîñòðîåíèÿ ñëîæíî-
ãî âûñêàçûâàíèÿ. Êàæäàÿ ëîãè÷åñêàÿ ñâÿçêà îïðåäåëÿåòñÿ ñâîåé
òàáëèöåé èñòèííîñòè (ñì. òàáë. 10.1, 10.2).
Ñ ïîìîùüþ ñâÿçêè îòðèöàíèÿ ¬ èç óòâåðäèòåëüíûõ ïîëó÷àþòñÿ
îòðèöàòåëüíûå âûñêàçûâàíèÿ. Íàïðèìåð, åñëè âûñêàçûâàíèå A
«âîðîáåé ïòèöà» èñòèííî, òî âûñêàçûâàíèå ¬A «âîðîáåé íå
ïòèöà» ëîæíî, à âûñêàçûâàíèå ¬¬A «Íåâåðíî, ÷òî âîðîáåé íå
ïòèöà» ýêâèâàëåíòíî âûñêàçûâàíèþ «âîðîáåé ïòèöà».
Êîíúþíêöèÿ A&B, ñîîòâåòñòâóþùàÿ ñîþçàì «è», «à», èñòèííà
â òîì è òîëüêî òîì ñëó÷àå, åñëè èñòèííû îáà âõîäÿùèõ â íåå âûñêà-
çûâàíèÿ. Íàïðèìåð, óòâåðæäåíèå «ñàìûé áîëüøîé ãîðîä Àíãëèè,
Ëîíäîí (A), ÿâëÿåòñÿ åå ñòîëèöåé (B)» ìîæíî çàïèñàòü êàê A&B.
Âûñêàçûâàíèå «íà óëèöå èäåò äîæäü (A) ñ ñèëüíûì âåòðîì (B)»
òàêæå âûðàæàåòñÿ ôîðìóëîé A&B. Êîíúþíêöèÿ êîììóòàòèâíà,
ïîòîìó âûñêàçûâàíèå «íà óëèöå ñèëüíûé âåòåð (B) è äîæäü (A)»,
âûðàçèìîå ôîðìóëîé B&A, ýêâèâàëåíòíî ïðåäûäóùåìó. Îäíàêî,
â åñòåñòâåííîì ÿçûêå ïîäîáíûå âûñêàçûâàíèÿ íå âñåãäà ýêâèâà-
ëåíòíû, íàïðèìåð, âûêàçûâàíèÿ «äåâóøêà âûøëà çàìóæ (A) è ðîäè-
ëà ðåáåíêà (B)» è «äåâóøêà ðîäèëà ðåáåíêà (B) è âûøëà çàìóæ
(A)», ýêâèâàëåíòíûå â ñèëó êîììóòàòèâíîñòè êîíúþíêöèè, îïèñû-
âàþò, ïî âñåé âèäèìîñòè, ñîâåðøåííî ðàçëè÷íûå ñèòóàöèè, â êîòî-
ðûõ íåÿâíî ïîäðàçóìåâàåòñÿ âðåìåííàÿ ïîñëåäîâàòåëüíîñòü ñîáû-
òèé. Äëÿ îïèñàíèÿ òàêèõ ñèòóàöèé ñðåäñòâ ëîãèêè âûñêàçûâàíèé
íåäîñòàòî÷íî.
Äëÿ êîíúþíêöèè âûïîëíåí çàêîí ïðîòèâîðå÷èÿ: A&¬A ≡ F
ôîðìàëüíîå âûðàæåíèå ïðèíöèïà íåïðîòèâîðå÷èâîñòè.
Äèçúþíêöèÿ A ∨ B, ñîîòâåòñòâóþùàÿ ñîþçó «èëè», èñòèííà â
ëþáîì ñëó÷àå, êîãäà èñòèííî õîòÿ áû îäíî âõîäÿùåå â íåå âûñêàçû-
âàíèå, è ëîæíà òîëüêî â òîì ñëó÷àå, åñëè îáà ïðîñòûõ âûñêàçûâàíèÿ
ëîæíû. Íàïðèìåð, âûñêàçûâàíèå «äâàæäû äâà ÷åòûðå (A) èëè
ïÿòü (B)» âûðàæàåòñÿ ôîðìóëîé A∨B è ÿâëÿåòñÿ èñòèííûì. Âû-
ñêàçûâàíèå «íàñåëåíèå Êàíàäû ãîâîðèò íà àíãëèéñêîì (A) èëè íà
ôðàíöóçñêîì ÿçûêå (B)» òàêæå âûðàæàåòñÿ ôîðìóëîé A∨B. Äëÿ
äèçúþíêöèè âûïîëíåí çàêîí èñêëþ÷åííîãî òðåòüåãî: A ∨ ¬A ≡ T.
Òàáëèöà 10.1 Òàáëèöà 10.2
A ¬AABA & BA ∨ BA → BA ≡ B
FT FF F F T T
TF FT F T T F
TF F T F F
TTTTTT
Èìïëèêàöèÿ A→B âûðàæàåò ëîãè÷åñêóþ (÷àñòî ïðè÷èííî-
ñëåäñòâåííóþ) ñâÿçü ìåæäó âûñêàçûâàíèÿìè A è B è ôîðìàëèçóåò
âûñêàçûâàíèå, â êîòîðîì èç ïîñûëêè (àíòåöåäåíòà) A ñëåäóåò
çàêëþ÷åíèå (êîíñåêâåíò) B. Ôîðìóëà A→B ÷èòàåòñÿ êàê «èç A
ñëåäóåò B» èëè «A âëå÷åò B». Èìïëèêàöèÿ èñòèííà â òîì ñëó÷àå,
åñëè èç èñòèííîé ïîñûëêè ñëåäóåò èñòèííîå çàêëþ÷åíèå: T→T=T,
è ëîæíà, åñëè èç èñòèííîé ïîñûëêè ñëåäóåò ëîæíîå çàêëþ÷åíèå:
T→F=F. Åñëè æå ïîñûëêà ëîæíà, òî èç íåå ìîæåò ñëåäîâàòü êàê
ëîæíîå, òàê è èñòèííîå çàêëþ÷åíèå, âûñêàçûâàíèå îñòàåòñÿ èñòèí-
íûì â îáîèõ ñëó÷àÿõ: F → T = T, F→ F = T, ò.å. èç ëæè ñëåäóåò âñå,
÷òî óãîäíî. Îáû÷íî èìïëèêàöèÿ A → B îïèñûâàåò íåêîòîðîå ïðàâè-
ëî, êîòîðîå âûðàæàåò äîñòàòî÷íîñòü èñòèííîñòè ïîñûëêè A äëÿ
òîãî, ÷òîáû âûïîëíÿëàñü èñòèííîñòü çàêëþ÷åíèÿ B, íàïðèìåð: «åñëè
âîäó íàãðåòü äî 100 ãðàäóñîâ (A), òî îíà çàêèïèò (B)»; «÷òîáû
ïîëó÷èòü äèïëîì (B), íóæíî çàêîí÷èòü èíñòèòóò (A)»; «åñëè êîøêà
ïåðåáåæèò äîðîãó (A), òî ñëó÷èòñÿ íåïðèÿòíîñòü (B)»; «êîãäà íà
íåáå òó÷è (A), ìîæåò ïîéòè äîæäü (B)».
Ýêâèâàëåíòíîñòü A ≡ B óòâåðæäàåò ðàâíîçíà÷íîñòü (ðàâíîñèëü-
íîñòü, òîæäåñòâåííîñòü) äâóõ âûñêàçûâàíèé A è B; îíà èñòèííà
òîãäà, êîãäà èñòèííîñòíûå çíà÷åíèÿ A è B ñîâïàäàþò. Íàïðèìåð,
âûñêàçûâàíèå «æèâîòíîå ÿâëÿåòñÿ ïòèöåé (A) òîãäà è òîëüêî òîã-
äà, êîãäà ó íåãî åñòü êðûëüÿ (B)» âûðàçèìî ôîðìóëîé A≡B.
A ≡ B =(À→Â)&(Â→À), ò.å. ýêâèâàëåíòíîñòü óòâåðæäàåò
íå òîëüêî äîñòàòî÷íîñòü óñëîâèÿ A äëÿ òîãî, ÷òîáû áûëî èñòèííî
B, íî è íåîáõîäèìîñòü ýòîãî óñëîâèÿ. Íàïðèìåð, óòâåðæäåíèå: «ïòè-
öû ëåòàþò íàä ìîðåì (A) çåìëÿ áëèçêà (B)», âûðàæàåò îäíîâðå-
ìåííî äâà óòâåðæäåíèÿ: äîñòàòî÷íîñòü óñëîâèÿ «åñëè ïòèöû
ëåòàþò íàä ìîðåì, òî áëèçêà çåìëÿ», è íåîáõîäèìîñòü: «åñëè çåìëÿ
áëèçêî, òî ïòèöû ëåòàþò íàä ìîðåì».
Ñ ïîìîùüþ ëîãè÷åñêèõ ñâÿçîê ñëîæíûå âûñêàçûâàíèÿ ìîæíî
çàïèñàòü â âèäå ôîðìóëû, êîòîðóþ íàçûâàþò ïðîïîçèöèîíàëüíîé
ôîðìîé.
Îïðåäåëåíèå 10.2.
•Êàæäàÿ ïðîïîçèöèîíàëüíàÿ áóêâà åñòü ôîðìóëà.
•Åñëè A è B ôîðìóëû, òî ôîðìóëàìè ÿâëÿþòñÿ: (¬A),
(A&B), (A ∨ B).
•Äðóãèõ ôîðìóë íåò.
Ïðè çàïèñè ôîðìóë ïðèíÿòû ñëåäóþùèå ñîãëàøåíèÿ: âíåøíèå
ñêîáêè ìîæíî îïóñêàòü; óñòàíîâëåí ïðèîðèòåò îïåðàöèé: ¬, &, ∨,
→, ≡. Ëîãè÷åñêèå ñâÿçêè äëÿ èìïëèêàöèè → è ýêâèâàëåíòíîñòè ≡
ââîäÿòñÿ äëÿ ñîêðàùåíèÿ çàïèñè ôîðìóë: À→Â=¬À∨Â=
=¬(À&¬Â), À≡Â=(À→Â)&(Â→À).
Ëîãèêà âûñêàçûâàíèéÃëàâà 10
172 173
Ïîñòðîèâ ôîðìóëó ëîãèêè âûñêàçûâàíèé, ìû îòâëåêàåìñÿ îò
åå ñîäåðæàòåëüíîãî ñìûñëà è îïåðèðóåì òîëüêî ñ ïîíÿòèÿìè èñòèí-
íîñòè è ëîæíîñòè.
Ïðèïèñûâàíèå ïðîïîçèöèîíàëüíûì áóêâàì èõ èñòèííîñòíûõ
çíà÷åíèé íàçûâàåòñÿ èíòåðïðåòàöèåé ôîðìóëû. Ìíîæåñòâî âñåõ
èíòåðïðåòàöèé ôîðìóëû îáðàçóåò åå òàáëèöó èñòèííîñòè. Åñëè
âûïîëíèòü îòîáðàæåíèÿ 0⇔F, 1⇔T, òî êàæäîé ïðîïîçèöèîíàëü-
íîé ñâÿçêå áóäåò ñîîòâåòñòâîâàòü áóëåâà îïåðàöèÿ, à êàæäîé
ôîðìóëå ëîãèêè âûñêàçûâàíèé áóëåâà ôîðìóëà, ñëåäîâàòåëüíî,
ëîãèêà âûñêàçûâàíèé ÿâëÿåòñÿ èíòåðïðåòàöèåé áóëåâîé àëãåáðû.
 ñâÿçè ñ ýòèì â íåé ñîõðàíÿþòñÿ âñå àêñèîìû è òåîðåìû áóëåâîé
àëãåáðû, â òîì ÷èñëå ïðåäñòàâèìîñòü ôîðìóë ëîãèêè âûñêàçûâà-
íèé â âèäå ÑÄÍÔ è ÑÊÍÔ.
Îïðåäåëåíèå 10.3. Òîæäåñòâåííî èñòèííàÿ ôîðìóëà íàçûâàåòñÿ
òàâòîëîãèåé. Òîæäåñòâåííî ëîæíàÿ ôîðìóëà íàçûâàåòñÿ ïðîòè-
âîðå÷èåì. Ôîðìóëà, êîòîðàÿ ïðèíèìàåò èñòèííîå çíà÷åíèå õîòÿ
áû íà îäíîé ñâîåé èíòåðïðåòàöèè, íàçûâàåòñÿ âûïîëíèìîé. Äâå
ôîðìóëû íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè èõ òàáëèöû èñòèí-
íîñòè ñîâïàäàþò.
Çàïèñü |= À îçíà÷àåò: «ôîðìóëà À òàâòîëîãèÿ». Î÷åâèäíî,
÷òî åñëè À òàâòîëîãèÿ, òî ¬À ïðîòèâîðå÷èå.
Òàâòîëîãèè ÿâëÿþòñÿ âûäåëåííûìè ôîðìóëàìè ëîãèêè
âûñêàçûâàíèé; èìåííî îíè ïðåäñòàâëÿþò íàèáîëüøèé èíòåðåñ, òàê
êàê ôîðìàëèçóþò ïðàâèëüíûå ñõåìû ðàññóæäåíèé. Ïðîñòûå òàâòî-
ëîãèè, òàêèå êàê «ñíåã áåëûé, ïîòîìó ÷òî îí áåëûé», «ìàñëî ìàñëÿ-
íîå», âûðàçèìû ôîðìóëîé: À→A, òîæäåñòâåííóþ èñòèííîñòü êî-
òîðîé íåòðóäíî ïðîâåðèòü: åñëè |À|=F, òî F→F =T, åñëè |À|= T,
òî T→T=T. Óòâåðæäåíèå: «Áîëüíîé ëèáî óìðåò, ëèáî âûæèâåò»
òîæå òàâòîëîãèÿ, òàê êàê îíî âûðàçèìî òîæäåñòâåííî èñòèííîé
ôîðìóëîé: A∨¬A. Çàêîíû äå Ìîðãàíà òàêæå ÿâëÿþòñÿ òàâòîëîãèÿ-
ìè; íåòðóäíî ïðèäàòü èì ñîäåðæàòåëüíûé ñìûñë:
|= ¬(À∨Â) ≡ (¬À&¬Â) «íåâåðíî, ÷òî ýòî ïðåñòóïëåíèå ñîâåð-
øèëè À èëè » ýêâèâàëåíòíî âûñêàçûâàíèþ: «íè À, íè  íå ñîâåðøàëè
ýòîãî ïðåñòóïëåíèÿ»;
|= ¬(À&Â) ≡ (¬À∨¬Â) «íåâåðíî, ÷òî À è  âìåñòå ó÷à-
ñòâîâàëè â îãðàáëåíèè» ýêâèâàëåíòíî «ëèáî À, ëèáî Â, ëèáî îáà îíè
â îãðàáëåíèè íå ó÷àñòâîâàëè».
Ïðîáëåìà ðàçðåøèìîñòè â àëãåáðå âûñêàçûâàíèé çàêëþ÷àåòñÿ
â òîì, ÷òîáû îòûñêàòü ýôôåêòèâíóþ ïðîöåäóðó (àëãîðèòì), ñ ïî-
ìîùüþ êîòîðîé äëÿ êàæäîé ôîðìóëû ëîãèêè âûñêàçûâàíèé ìîæíî
óñòàíîâèòü, ÿâëÿåòñÿ îíà òàâòîëîãèåé èëè íåò.
Ëîãèêà âûñêàçûâàíèéÃëàâà 10
Î÷åâèäíî, ÷òî òàêàÿ ïðîöåäóðà äëÿ ôîðìóë ëîãèêè âûñêàçûâà-
íèé ñóùåñòâóåò: ýòî ïîñòðîåíèå òàáëèö èñòèííîñòè.
Ïðèìåðû.
1.  êà÷åñòâå ïðèìåðà ðàññìîòðèì çàêîí óòâåðæäåíèÿ êîíñåêâåíòà:
|= A→(B→A). (Ñîäåðæàòåëüíî ýòà òàâòîëîãèÿ óòâåðæäàåò ïðèí-
öèï ìîíîòîííîñòè äîñòîâåðíûõ ðàññóæäåíèé: åñëè èñòèííîñòü íåêî-
òîðîãî âûñêàçûâàíèÿ A óæå óñòàíîâëåíà, òî äîáàâëåíèå íîâûõ ôàê-
òîâ íå èçìåíÿåò åãî èñòèííîñòè). Ïîñêîëüêó êàæäàÿ ñòðîêà òàáëèöû
èñòèííîñòè (òàáë. 10.3) ýòîé ôîðìóëû ñîäåðæèò çíà÷åíèÿ T, ôîð-
ìóëà ÿâëÿåòñÿ òàâòîëîãèåé.
2. Ìåòîä ðåäóêöèè (ñâåäåíèå ê ïðîòèâîðå÷èþ) ñëóæèò ñïîñîáîì
ñîêðàùåíèÿ ïåðåáîðîâ ïðè ñîñòàâëåíèè òàáëèöû èñòèííîñòè. Â
êà÷åñòâå ïðèìåðà äîêàæåì, ÷òî ôîðìóëà
(A → (B → C)) → ((A → B) → (A → C)) òàâòîëîãèÿ.
Ïðåäïîëîæèì, ÷òî ýòî íå òàê, ò.å. ñóùåñòâóåò òàêàÿ èíòåðïðåòàöèÿ,
íà êîòîðîé ôîðìóëà ïðèíèìàåò ëîæíîå çíà÷åíèå:
Ïîëó÷àåì ñèñòåìó óðàâíåíèé:
1)|A → (B → C)| = T,
2)|A → B| = T,
3)|A → C| = F.
Èç 3) ñëåäóåò: |A| = T, |C| = F. Ïîäñòàâèì ýòè çíà÷åíèÿ â 2): |T→B|=T,
îòêóäà |B| = T. Ïîäñòàâèì íàéäåííûå çíà÷åíèÿ |A| = T, |C| = F, |B| = T
â 1): |T → (T → F)| = |T→ F| = F. Ïîëó÷åííîå çíà÷åíèå ïðîòèâîðå÷èò
óñëîâèþ 1), ñëåäîâàòåëüíî, íå ñóùåñòâóåò òàêîé èíòåðïðåòàöèè,
íà êîòîðîé ôîðìóëà ïðèíèìàåò ëîæíîå çíà÷åíèå, ò.å. îíà ÿâëÿåòñÿ
òàâòîëîãèåé.
3. Ïðîâåðèì, ÿâëÿåòñÿ ëè ñëåäóþùàÿ ôîðìóëà òàâòîëîãèåé:
(A→(B → C)) → (A ∨ B → C).
Ïðåäïîëîæèì, ÷òî |(A → (B → C)) → (A ∨ B → C)| = F. Òîãäà
Òàáëèöà 10.3
AB B → AA → (B → A)
FF T T
FT F T
TF T T
TT T T
174 175Ëîãèêà âûñêàçûâàíèéÃëàâà 10
1)|A → (B → C)| = T,
2)|A ∨ B| = T,
3)|C| = F.
Èç 2) ñëåäóåò:
à) |A| = T, |B| = T;
á) |A| = T, |B| = F;
ñ) |A| = F, |B| = T.
Ïîäñòàâëÿÿ çíà÷åíèÿ |A|=T, |B| = T â 1), ïîëó÷àåì ïðîòèâîðå÷èå:
|T → (T → F)| = F. Îäíàêî, ýòî åùå íå äîêàçûâàåò, ÷òî ôîðìóëà
ÿâëÿåòñÿ òàâòîëîãèåé. Ðàññìîòðèì äðóãèå çíà÷åíèÿ:
á) |A| = T, |B| = F.
Ïîäñòàâëÿÿ ýòè çíà÷åíèÿ â 1), ïîëó÷èì: |T→(F→F)| = T. Òàêèì
îáðàçîì, íà èíòåðïðåòàöèè |A| = T, |B| = F, |C| = F ôîðìóëà ïðèíèìàåò
ëîæíîå çíà÷åíèå, ñëåäîâàòåëüíî, îíà íå ÿâëÿåòñÿ òàâòîëîãèåé.
10.3. Ëîãè÷åñêîå ñëåäîâàíèå
Îïðåäåëåíèå 10.4. Åñëè À è Â ôîðìóëû, òî ãîâîðÿò, ÷òî Â
ëîãè÷åñêè ñëåäóåò èç À, èëè À ëîãè÷åñêè âëå÷åò Â, åñëè íà âñåõ
èíòåðïðåòàöèÿõ, ãäå À ïðèíèìàåò èñòèííîå çíà÷åíèå,  òàêæå ïðè-
íèìàåò èñòèííîå çíà÷åíèå. Ýòî îáîçíà÷àåòñÿ êàê À|= èëè À⇒Â.
Ãîâîðÿò, ÷òî ëîãè÷åñêîå ñëåäîâàíèå ñîõðàíÿåò èñòèííîñòü.
Òåîðåìà 10.1. Ëîãè÷åñêîå ñëåäîâàíèå À|= âûïîëíåíî òîãäà è
òîëüêî òîãäà, êîãäà ôîðìóëà À→Â òàâòîëîãèÿ.
Äîêàçàòåëüñòâî. Ïóñòü ëîãè÷åñêîå ñëåäîâàíèå A|=B âûïîëíåíî.
Ýòî îçíà÷àåò, ÷òî íà âñåõ èíòåðïðåòàöèÿõ, íà êîòîðûõ ôîðìóëà
|A|=T, ôîðìóëà |B| = T, ñëåäîâàòåëüíî, |A→B| = T. Åñëè ôîðìóëà
|A| = F, òî |A → B| = T íåçàâèñèìî îò çíà÷åíèÿ B, ñëåäîâàòåëüíî,
ôîðìóëà A → B òàâòîëîãèÿ. Ïðåäïîëîæèì òåïåðü, ÷òî ôîðìóëà
A → B òàâòîëîãèÿ. Òîãäà íå ñóùåñòâóåò òàêîé èíòåðïðåòàöèè, íà
êîòîðîé |A → B| = F. Ñëåäîâàòåëüíî, åñëè ôîðìóëà |A| = T, òî è
|B|=T, ÷òî ñîîòâåòñòâóåò îïðåäåëåíèþ ëîãè÷åñêîãî ñëåäîâàíèÿ, ò.å.
À|=Â.
Îïðåäåëåíèå 10.5. Ôîðìóëà  ëîãè÷åñêè ñëåäóåò èç ôîðìóë
À
1
,..., A
n
, åñëè íà âñåõ òåõ èíòåðïðåòàöèÿõ, íà êîòîðûõ A
1
, ..., A
n
ïðèíèìàþò èñòèííûå çíà÷åíèÿ îäíîâðåìåííî, ôîðìóëà  òàêæå
ïðèíèìàåò èñòèííîå çíà÷åíèå. Ýòî îáîçíà÷àåòñÿ òàê:
A
1
,...A
n
|=B.
Òåîðåìà 10.2. À
1
,A
2
,...,A
n
|=B òîãäà è òîëüêî òîãäà, êîãäà
|À
1
&A
2
&...&A
n
→B.
Äîêàçàòü ñàìîñòîÿòåëüíî.
Îïðåäåëåíèå 10.6. Åñëè À|= è  |=À, òî ôîðìóëà À ëîãè÷åñêè
ýêâèâàëåíòíà ôîðìóëå Â. Ýòî îáîçíà÷àåòñÿ êàê À⇔Â, èëè
À≡Â.
Åñëè ôîðìóëà À ëîãè÷åñêè ýêâèâàëåíòíà Â, òî À≡ òàâ-
òîëîãèÿ.
Ïðèìåð. Ïðîâåðèì ëîãè÷åñêîå ñëåäîâàíèå: À→Â, À→¬Â
|=¬À è òàâòîëîãèþ: |=(À→Â)&(À→¬Â)→¬À. Îáîçíà÷èì
òàâòîëîãèþ ÷åðåç Å. Ïîñòðîèì òàáëèöó èñòèííîñòè (òàáë. 10.4).
Êàê âèäèì, íà òåõ íàáîðàõ, íà êîòîðûõ ïîñûëêè À→Â, À→¬Â
ïðèíèìàþò èñòèííîå çíà÷åíèå îäíîâðåìåííî, ôîðìóëà ¬À òàêæå ïðè-
íèìàåò èñòèííîå çíà÷åíèå. Ñëåäîâàòåëüíî, ëîãè÷åñêîå ñëåäîâàíèå
âûïîëíåíî. Ñ äðóãîé ñòîðîíû, ôîðìóëà (À→Â)&(À→¬Â)→¬À
ÿâëÿåòñÿ òàâòîëîãèåé, ÷òî òàêæå ÿâëÿåòñÿ äîêàçàòåëüñòâîì âûïîë-
íèìîñòè ëîãè÷åñêîãî ñëåäîâàíèÿ. Ñîäåðæàòåëüíî ëîãè÷åñêîå ñëåäîâà-
íèå À→Â, À→¬Â |=¬À (ïðèâåäåíèå ê àáñóðäó) ôîðìàëèçóåò
ñëåäóþùóþ ñõåìó ðàññóæäåíèé. Åñëè èç îäíîé è òîé æå ïîñûëêè À
âûâåäåíî äâà ïðîòèâîïîëîæíûõ çàêëþ÷åíèÿ Â è ¬Â, òî ïîñûëêà íåâåð-
íà (ýòî ïðèìåðíî òî, î ÷åì ãîâîðèë Êîçüìà Ïðóòêîâ: «Åñëè íà êëåòêå
ñ òèãðîì íàïèñàíî «ëåâ», íå âåðü ãëàçàì ñâîèì»).
10.4. Òåîðåìû î òàâòîëîãèÿõ
Ñëåäóþùèå òåîðåìû î òàâòîëîãèÿõ ïîçâîëÿþò ïîëó÷àòü íîâûå
òàâòîëîãèè èç äîêàçàííûõ ðàíåå.
Òåîðåìà 10.3 (ïðàâèëî modus ponens). Åñëè À òàâòîëîãèÿ è
À→Â òàâòîëîãèÿ, òî Â òàâòîëîãèÿ, ò.å. åñëè |=À è |=À→Â,
òî |=Â.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî íà íåêîòîðîé èíòåðïðåòà-
öèè |Â| =F. Òîãäà |A→B| = |A→F| = T íà òîé æå èíòåðïðåòàöèè
(ïî óñëîâèþ òåîðåìû). Ñëåäîâàòåëüíî, |À| = F, ÷òî íåâîçìîæíî, òàê
êàê À òàâòîëîãèÿ.
Ïðàâèëî modus ponens (ñîêðàùåííî MP) óñòàíàâëèâàåò ëîãè÷åñ-
êîå ñëåäîâàíèå A, A→B |=B è íàçûâàåòñÿ åùå ïðàâèëîì îòäåëåíèÿ.
Ïðàâèëî ÌÐ âûðàæàåò ýëåìåíòàðíûé àêò äåäóêöèè. Èìïëèêà-
öèþ A→B, êîòîðàÿ ïî îïðåäåëåíèþ èìååò ñìûñë «åñëè A, òî B»,
Òàáëèöà 10.4
ABA → BA → ¬B (A → B) & (A → ¬B) ¬ÀÅ
FF T T T TÒ
FT T T T TÒ
TF F T F FÒ
TT T F F FÒ
176 177Ëîãèêà âûñêàçûâàíèéÃëàâà 10
ìîæíî èíòåðïðåòèðîâàòü êàê ïðàâèëî, â êîòîðîì A ÿâëÿåòñÿ «ïðè-
÷èíîé», à B «ñëåäñòâèåì». Òîãäà ïðàâèëî ÌÐ ãîâîðèò î òîì, ÷òî
ñëåäñòâèå B íàñòóïàåò ïðè âûïîëíåíèè óñëîâèÿ A, ò.å. ïðè èñòèí-
íîñòè ïîñûëêè. Íàïðèìåð, ôîðìóëà A → B ìîæåò âûðàæàòü òàêîå
ïðàâèëî: «åñëè íà ñâåòîôîðå ãîðèò çåëåíûé ñâåò, òî ìîæíî ïåðåõî-
äèòü äîðîãó». Ìû æäåì çåëåíîãî ñâåòà íà ñâåòîôîðå, ÷òîáû ïåðåéòè
äîðîãó, ò.å. ìû íåÿâíî ïîëüçóåìñÿ ïðàâèëîì ÌÐ: êîãäà ïîñûëêà
ñòàíîâèòñÿ èñòèííîé (çåëåíûé ñâåò), òî èñòèííî è çàêëþ÷åíèå
(ìîæíî ïåðåõîäèòü äîðîãó). Òåì ñàìûì ìû âûïîëíÿåì ýëåìåíòàð-
íûé àêò äåäóêöèè: èç èñòèííîñòè ïîñûëêè ìû âûâîäèì èñòèííîå
çàêëþ÷åíèå. Ðàçóìååòñÿ, ýòîò âûâîä ñïðàâåäëèâ òîëüêî â òîì ñëó÷àå,
åñëè ïðàâèëî A→B èñòèííî. Íàïðèìåð, ìíîãèå ïîëàãàþò, ÷òî åñëè
êîøêà ïåðåáåæèò äîðîãó, òî ñëó÷èòñÿ íåïðèÿòíîñòü. Ïðèíèìàÿ ýòî
ïðàâèëî çà èñòèííîå, ÷åëîâåê, óâèäåâ ïåðåáåãàþùóþ åìó äîðîãó
êîøêó, âåñü äåíü æäåò íåïðèÿòíîñòè (è îáû÷íî åå íàõîäèò). Ìíîãèå
ïðàâèëà, îäíàêî, íå âûçûâàþò ñîìíåíèé â èõ èñòèííîñòè. Ýòî,
íàïðèìåð, ìàòåìàòè÷åñêèå òåîðåìû, ôèçè÷åñêèå, õèìè÷åñêèå è
äðóãèå óñòàíîâëåííûå çàêîíû.
Òåîðåìà 10.4 (ïðàâèëî ïîäñòàíîâêè). Åñëè À òàâòîëîãèÿ,
ñîäåðæàùàÿ ïðîïîçèöèîíàëüíûå ïåðåìåííûå à
1
,a
2
,...,a
n
, òî
ôîðìóëà Â, ïîëó÷åííàÿ èç À ïîäñòàíîâêîé ôîðìóë A
1
,A
2
,...,A
n
âìåñòî
êàæäîãî âõîæäåíèÿ à
1
,a
2
,...,a
n
ñîîòâåòñòâåííî, òàêæå
áóäåò òàâòîëîãèåé.
Äîêàçàòåëüñòâî. Ïóñòü çàäàíî èñòèííîñòíîå ðàñïðåäåëåíèå äëÿ
ïðîïîçèöèîíàëüíûõ áóêâ, âõîäÿùèõ â Â. Ôîðìóëû À
1
,,À
n
äëÿ
ýòîãî ðàñïðåäåëåíèÿ ïðèìóò íåêîòîðûå çíà÷åíèÿ δ
1
, δ
2
,, δ
n
, ãäå δ
i
åñòü T èëè F. Åñëè òàêîå æå ðàñïðåäåëåíèå ïðèäàòü ïðîïîçèöèîíàëü-
íûì áóêâàì à
1
,a
2
,...,a
n
, òî çíà÷åíèå ôîðìóëû À ñîâïàäåò ñî çíà÷åíè-
åì ôîðìóëû Â. Òàê êàê À òàâòîëîãèÿ, òî çíà÷åíèå  ïðè ýòîì
ðàñïðåäåëåíèè áóäåò T. Òàêèì îáðàçîì Â ïðè ëþáîì èñòèííîñòíîì
ðàñïðåäåëåíèè âõîäÿùèõ â íåå áóêâ áóäåò ïðèíèìàòü çíà÷åíèå T.
Ñëåäîâàòåëüíî, Â òàâòîëîãèÿ.
Ïðèìåð. Ôîðìóëà A→(B→A) òàâòîëîãèÿ. Ïîäñòàâèì A∨B
âìåñòî A, ïîëó÷èì íîâóþ òàâòîëîãèþ: |=A∨B→(B→A∨B).
Òàêèì îáðàçîì, êàæäóþ òàâòîëîãèþ ìîæíî ðàññìàòðèâàòü êàê ñõåìó,
èç êîòîðîé ñ ïîìîùüþ ïîäñòàíîâêè ìîæíî ïîëó÷èòü áåñêîíå÷íîå
ìíîæåñòâî òàâòîëîãèé.
Òåîðåìà 10.5 (ïðàâèëî ýêâèâàëåíòíîé çàìåíû). Åñëè B ïîëó÷àåò-
ñÿ èç A
ïîäñòàíîâêîé ôîðìóëû Â
1
âìåñòî îäíîãî èëè íåñêîëüêèõ
âõîæäåíèé ïîäôîðìóëû À
1
â À, òî ((A
1
≡B
1
)→(A≡B)) åñòü
òàâòîëîãèÿ, è, ñëåäîâàòåëüíî, åñëè À
1
è Â
1
ëîãè÷åñêè ýêâèâàëåíò-
íû, òî A è B òàêæå ëîãè÷åñêè ýêâèâàëåíòíû.
Èíûìè ñëîâàìè, åñëè åñòü òàâòîëîãèÿ À, è â íåé åñòü ïîäôîðìó-
ëà À
1
, è åñëè çàìåíèòü À
1
íà ýêâèâàëåíòíóþ åé ôîðìóëó Â
1
,
òî
ïîëó÷åííàÿ ôîðìóëà  áóäåò ýêâèâàëåíòíà À.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíîå èñòèííîñòíîå
ðàñïðåäåëåíèå ïåðåìåííûõ, âõîäÿùèõ â À, Â, À
1
, Â
1
. Åñëè ïðè ýòîì
ðàñïðåäåëåíèè À
1
è Â
1
èìåþò ðàçëè÷íûå çíà÷åíèÿ, òî |À
1
≡Â
1
|=F
è, ñëåäîâàòåëüíî, ((A
1
≡B
1
)→(A≡B)) ïðèìåò çíà÷åíèå Ò. Åñëè
æå À
1
è Â
1
ïðèíèìàþò îäèíàêîâûå çíà÷åíèÿ, òî îäèíàêîâûå èñòèí-
íîñòíûå çíà÷åíèÿ ïðèìóò À è Â, òàê êàê  îòëè÷àåòñÿ îò À òîëüêî
òåì, ÷òî íåêîòîðûå âõîæäåíèÿ ïîäôîðìóëû À
1
çàìåíåíû â íåé íà
Â
1
, êîòîðàÿ èìååò òî æå ñàìîå èñòèííîñòíîå çíà÷åíèå. Ñëåäîâàòåëü-
íî, â ýòîì ñëó÷àå, åñëè |A
1
≡B
1
|=Ò, òî è |A≡B| =Ò, è ((A
1
≡B
1
)→
→(A≡B)) åñòü òàâòîëîãèÿ.à
Ïðèìåð. Â òàâòîëîãèè À→(Â→À) çàìåíèì ïîäôîðìóëó
Â→À íà ýêâèâàëåíòíóþ åé ôîðìóëó ¬Â∨A, ïîëó÷èì íîâóþ òàâ-
òîëîãèþ À→¬Â∨A. Òàâòîëîãèåé òàêæå áóäåò ôîðìóëà:
A→¬(B&¬A), òàê êàê Â→À ýêâèâàëåíòíî ¬(B&¬A).
10.5. Ôîðìàëèçàöèÿ è ðåøåíèå ëîãè÷åñêèõ çàäà÷
ßçûê ëîãèêè âûñêàçûâàíèé èñïîëüçóåòñÿ äëÿ ôîðìàëèçàöèè
ïðåäëîæåíèé åñòåñòâåííîãî ÿçûêà è äîêàçàòåëüñòâà ëîãè÷åñêèõ
ñëåäîâàíèé. Äëÿ ýòîãî êàæäîå ïðîñòîå âûñêàçûâàíèå îáîçíà÷àåòñÿ
ïðîïîçèöèîíàëüíîé áóêâîé; ñëîæíîå âûêàçûâàíèå çàïèñûâàåòñÿ
êàê ôîðìóëà, â êîòîðîé ñâÿçêè åñòåñòâåííîãî ÿçûêà çàìåíÿþòñÿ
ïðîïîçèöèîíàëüíûìè ñâÿçêàìè (êàê ýòî óêàçàíî â 10.2).
Ïðèìåð 10.1. Ðàññìîòðèì ëîãè÷åñêîå ñëåäîâàíèå. Åñëè öåíû
ðàñòóò, óðîâåíü æèçíè ïàäàåò. Åñëè óðîâåíü æèçíè ïàäàåò, òî
ëþäè íåäîâîëüíû. Öåíû ðàñòóò. Ñëåäîâàòåëüíî, ëþäè íåäîâîëüíû.
Îáîçíà÷èì ïðîïîçèöèîíàëüíûìè áóêâàìè ïðîñòûå âûñêàçûâàíèÿ:
P «öåíû ðàñòóò»; S «óðîâåíü æèçíè ïàäàåò»; R «ëþäè
íåäîâîëüíû». Íåîáõîäèìî äîêàçàòü ëîãè÷åñêîå ñëåäîâàíèå: P→S,
S→R, P |= R.
Äîêàçàòåëüñòâî.
1 ñïîñîá. Ïðîâåðèòü, ÷òî ôîðìóëà (P→S)&(S→R)&P→R
òàâòîëîãèÿ. Äëÿ ýòîãî äîñòàòî÷íî ïîñòðîèòü òàáëèöó èñòèííîñòè.
2 ñïîñîá. Äîêàçàòåëüñòâî îò ïðîòèâíîãî (ìåòîä ðåäóêöèè).
Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò òàêàÿ èíòåðïðåòàöèÿ, íà êîòîðîé
âñå ïîñûëêè ïðèíèìàþò èñòèííîå çíà÷åíèå, à çàêëþ÷åíèå - ëîæíîå,
ò.å. |P→S| =T, |S→R| =T, |P| =T, |R| =F. Òîãäà èç |S→R| =
=|S→F|=Tñëåäóåò, ÷òî |S| =F; èç |P→S| = |P→F| = Tñëåäóåò,
÷òî |P| =F, ÷òî ïðîòèâîðå÷èò òðåòüåé ïîñûëêå |P| =T. Ýòî ïðîòèâî-
ðå÷èå äîêàçûâàåò ëîãè÷åñêîå ñëåäîâàíèå.
178 179
3 ñïîñîá. Ïîñòðîåíèå ëîãè÷åñêîãî âûâîäà.
Ëîãè÷åñêîå ñëåäîâàíèå ýòî íåêîòîðîå ïðàâèëüíîå ñ ëîãè÷åñêîé
òî÷êè çðåíèÿ ðàññóæäåíèå. Íåêîòîðûå ëîãè÷åñêèå ñëåäîâàíèÿ ôîð-
ìàëèçóþò ïðîñòåéøèå ñõåìû ðàññóæäåíèé è èñïîëüçóþòñÿ êàê ïðàâèëà
âûâîäà èñòèííûõ çàêëþ÷åíèé èç èñòèííûõ ïîñûëîê. Ïîñëåäîâàòåëüíîå
ïðèìåíåíèå ïðàâèë âûâîäà ê çàäàííîé ñèñòåìå ïîñûëîê ïîçâîëÿåò
ñòðîèòü ëîãè÷åñêèé âûâîä. Ëîãè÷åñêèé âûâîä, â êîòîðîì èç èñòèííûõ
ïîñûëîê ìîãóò áûòü ïîëó÷åíû òîëüêî èñòèííûå çàêëþ÷åíèÿ,
íàçûâàåòñÿ äîñòîâåðíûì (äåäóêòèâíûìè) âûâîäîì (ðàññóæäåíèåì).
Ïîñòðîèì ëîãè÷åñêèé âûâîä, èñïîëüçóÿ èçâåñòíûå ïðàâèëà
âûâîäà. Ëîãè÷åñêèé âûâîä çàïèñûâàåòñÿ îáû÷íî êàê íóìåðîâàííàÿ
ïîñëåäîâàòåëüíîñòü ôîðìóë, ñïðàâà îò êàæäîé ôîðìóëû
çàïèñûâàåòñÿ êîììåíòàðèé, óêàçûâàþùèé, íà êàêîì îñíîâàíèè
ôîðìóëà âêëþ÷åíà â ýòó ïîñëåäîâàòåëüíîñòü. Ïîñûëêè âûâîäà
îáû÷íî îáîçíà÷àþòñÿ áóêâîé à (ãèïîòåçà).
1. P→S Ã1
2. S→R Ã2
3. P Ã3
4. S ïðàâèëî MP(3,1)
5. R ïðàâèëî MP(4,2)
Ïîñëåäíÿÿ ôîðìóëà â ýòîì âûâîäå ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì
ïîñûëîê Ã1, Ã2, Ã3.
 ñèëó òîãî, ÷òî ïðàâèëî ÌÐ ñîõðàíÿåò èñòèííîñòü, êàæäàÿ
ôîðìóëà, ó÷àñòâóþùàÿ â âûâîäå, èñòèííà ïðè èñòèííîñòè ïîñûëîê
Ã1, Ã2, Ã3. Ïîýòîìó, åñëè ñîåäèíèòü ñèìâîëîì → ôîðìóëû, òàê
÷òîáû ïîñûëêà èìïëèêàöèè ïðåäøåñòâîâàëà çàêëþ÷åíèþ â ýòîì
âûâîäå, òî ïîëó÷åííàÿ ôîðìóëà òàêæå áóäåò èñòèííîé, è, ñëåäîâà-
òåëüíî, îíà ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäîâàíèåì èñõîäíûõ ïîñûëîê.
Ïîýòîìó èç äàííîãî âûâîäà ìû ìîæåì ïîëó÷èòü ëîãè÷åñêîå ñëåäî-
âàíèå: P→S, S→R |=P→R. Ýòî ëîãè÷åñêîå ñëåäîâàíèå ñîîòâåò-
ñòâóåò ïðàâèëó âûâîäà, êîòîðîå íàçûâàþò ïðàâèëîì ñèëëîãèçìà:
A→B, B→ C |= A→C.
Ïðèìåð 10.2. Èç-çà ïëîõîé ïîãîäû (À) ðåéñ ìîæåò áûòü îòëîæåí
(Â): A→B. Ðåéñ íå îòëîæåí (¬Â). Ñëåäîâàòåëüíî, ïîãîäà íå ïëîõàÿ
(¬À). Äîêàæåì A→B, ¬B |=¬A.
Ïðåäïîëîæèì, ÷òî |À→Â| = T, |¬Â| = T è |¬À| = F, òîãäà |À→Â|
= =|T → F| = F. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò ëîãè÷åñêîå
ñëåäîâàíèå.
Ýòî ëîãè÷åñêîå ñëåäîâàíèå ñîîòâåòñòâóåò ïðàâèëó âûâîäà modus
tollens (MT):
A→B, ¬B |=¬A.
Ïðèìåð 10.3. Äåëî ìîæåò áûòü ïåðåñìîòðåíî (B) â òîì ñëó÷àå,
åñëè ðåçóëüòàòû ðàññëåäîâàíèÿ âûçûâàþò ñîìíåíèÿ (A): A→B.
Ñëåäîâàòåëüíî, åñëè äåëî íå ïåðåñìàòðèâàåòñÿ (¬B), òî ðåçóëüòàòû
ðàññëåäîâàíèÿ íå âûçûâàþò ñîìíåíèÿ (¬A): ¬Â→ ¬À.
Ïðåäïîëîæèì, ÷òî |À→Â| = T, |¬Â→ ¬À| = F, òîãäà |¬Â| = T, |¬À|=F
è |À→Â| = |T → F| = F. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò ëîãè-
÷åñêîå ñëåäîâàíèå.
Ýòî ëîãè÷åñêîå ñëåäîâàíèå ñîîòâåòñòâóåò ïðàâèëó êîíòðàïîçèöèè:
A→B |= ¬Â→ ¬À.
Ïðèìåð 10.4. Ïîëó÷èòü âîçìîæíûå ëîãè÷åñêèå ñëåäîâàíèÿ èç
äàííîãî ìíîæåñòâà ïîñûëîê. Ìàëûå äåòè íåðàçóìíû. Òîò, êòî ìî-
æåò óêðîùàòü êðîêîäèëîâ, çàñëóæèâàåò óâàæåíèÿ. Íåðàçóìíûå ëþ-
äè íå çàñëóæèâàþò óâàæåíèÿ.
Ïóñòü À «÷åëîâåê ìàëûé ðåáåíîê», B «÷åëîâåê ðàçóìåí»,
C «÷åëîâåê çàñëóæèâàåò óâàæåíèÿ», D «÷åëîâåê ìîæåò óêðî-
ùàòü êðîêîäèëîâ». Ïîñòðîèì ëîãè÷åñêèé âûâîä, èñïîëüçóÿ
äîêàçàííûå ðàíåå ïðàâèëà âûâîäà.
1. À→¬Â Ã1
2. D→C Ã2
3. ¬Â→¬Ñ Ã3
4. À→¬Ñ ïðàâèëî ñèëëîãèçìà (1, 3).
(Ìàëûå äåòè íå çàñëóæèâàþò óâàæåíèÿ).
5. Ñ→Â ïðàâèëî êîíòðàïîçèöèè (3).
(Òîëüêî ðàçóìíûå ëþäè çàñëóæèâàþò óâàæåíèÿ).
6. D→B ïðàâèëî ñèëëîãèçìà (2, 5).
(Ðàçóìíî óêðîùàòü êðîêîäèëîâ).
7. ¬B→¬D ïðàâèëî êîíòðàïîçèöèè (6).
(Íåðàçóìíûå ëþäè íå óêðîùàþò êðîêîäèëîâ).
8. À→¬D ïðàâèëî ñèëëîãèçìà (1,7).
(Ìàëûå äåòè íå óêðîùàþò êðîêîäèëîâ).
Òàêèì îáðàçîì, èç äàííîãî íàáîðà ïîñûëîê ìû âûâåëè âñå âîçìîæ-
íûå çàêëþ÷åíèÿ. Òàêèå ëîãè÷åñêèå çàäà÷è íàçûâàþòñÿ ñîðèòàìè.
Ïîíÿòèå î äåäóêòèâíîì ìåòîäå ìû ïîëó÷àåì ïðåæäå âñåãî èç
äåòåêòèâíîé ëèòåðàòóðû, â ÷àñòíîñòè, îò Øåðëîêà Õîëìñà. Êàê
èçâåñòíî, Øåðëîê Õîëìñ ïîëüçîâàëñÿ ïðè ðàñêðûòèè ïðåñòóïëåíèé
èìåííî äåäóêòèâíûì ìåòîäîì. Âîò êàê îí îáúÿñíÿåò ñóùíîñòü
äåäóêòèâíîãî ìåòîäà: «Ìîé ïðèíöèï ðàññëåäîâàíèÿ ñîñòîèò â òîì,
÷òîáû èñêëþ÷èòü âñå ÿâíî íåâîçìîæíûå ïðåäïîëîæåíèÿ. Òîãäà òî,
÷òî îñòàåòñÿ, ÿâëÿåòñÿ èñòèíîé, êàêîé áû íåïðàâäîïîäîáíîé îíà
íè êàçàëàñü». Ýòî ðàññóæäåíèå ìîæíî âûðàçèòü òàêîé ñõåìîé: À∨Â,
¬À |= Â, ÷òî ýêâèâàëåíòíî ¬À→Â, ¬À |= Â, ò.å. ïðèìåíåíèþ
Ëîãèêà âûñêàçûâàíèéÃëàâà 10