ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 880
Скачиваний: 9
56
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
Îïðåäåëåíèå. Ôóíêöèÿ
x
∧
y
íàçûâàåòñÿ êîíúþíêöèåé
x
è
y
, îáîçíà-
÷àåòñÿ
x
∧
y
, èëè
x
&
y
, èëè
x
·
y
, èëè
xy
, èëè
min(
x, y
)
è ÷àñòî ÷èòàåòñÿ êàê
¾
x
è
y
¿.
Îïðåäåëåíèå. Ôóíêöèÿ
x
∨
y
íàçûâàåòñÿ äèçúþíêöèåé
x
è
y
, îáîçíà-
÷àåòñÿ
x
∨
y
èëè
max(
x, y
)
è ÷àñòî ÷èòàåòñÿ êàê ¾
x
èëè
y
¿.
Îïðåäåëåíèå. Ôóíêöèÿ
x
→
y
íàçûâàåòñÿ èìïëèêàöèåé
x
è
y
, îáîçíà-
÷àåòñÿ
x
→
y
èëè
x
⊃
y
, ÷àñòî ÷èòàåòñÿ êàê ¾
x
èìïëèöèðóåò
y
¿ èëè ¾èç
x
ñëåäóåò
y
¿.
Îïðåäåëåíèå. Ôóíêöèÿ
x
≡
y
íàçûâàåòñÿ ýêâèâàëåíòíîñòüþ (èëè ýê-
âèâàëåíöèåé)
x
è
y
, îáîçíà÷àåòñÿ
x
≡
y
, èëè
x y
, èëè
x
↔
y
è ÷àñòî ÷èòàåòñÿ
¾
x
ýêâèâàëåíòíî
y
¿.
Îïðåäåëåíèå. Ôóíêöèÿ
x
+
y
íàçûâàåòñÿ ñóììîé ïî ìîäóëþ 2 (èëè
áóëåâîé ñóììîé)
x
è
y
, îáîçíà÷àåòñÿ
x
+
y
, èëè
x
⊕
y
è ÷àñòî ÷èòàåòñÿ ¾
x
ïëþñ
y
¿.
Îïðåäåëåíèå. Ôóíêöèÿ
x
|
y
íàçûâàåòñÿ øòðèõîì (Øåôôåðà)
x
è
y
,
îáîçíà÷àåòñÿ
x
|
y
è ÷àñòî ÷èòàåòñÿ ¾
x
øòðèõ
y
¿, ¾íå
x
èëè íå
y
¿. Â òåõ-
íè÷åñêîé ëèòåðàòóðå ôóíêöèÿ
x
|
y
íàçûâàåòñÿ îáû÷íî ¾íå è¿ èëè àíòè-
êîíúþíêöèåé, òàê êàê îíà ðàâíà îòðèöàíèþ êîíúþíêöèè.
Îïðåäåëåíèå. Ôóíêöèÿ
x
↓
y
íàçûâàåòñÿ ñòðåëêîé (Ïèðñà)
x
è
y
, îáî-
çíà÷àåòñÿ
x
↓
y
è ÷àñòî ÷èòàåòñÿ ¾
x
ñòðåëêà
y
¿, ¾íè
x
, íè
y
¿ èëè ¾íå
x
è
íå
y
¿.  òåõíè÷åñêîé ëèòåðàòóðå ôóíêöèÿ
x
↓
y
íàçûâàåòñÿ îáû÷íî ¾íå
èëè¿ èëè àíòèäèçúþíêöèåé, òàê êàê îíà ðàâíà îòðèöàíèþ äèçúþíêöèè.
Ñèìâîëû îïåðàöèé, ó÷àñòâóþùèå â îáîçíà÷åíèÿõ ýëåìåíòàðíûõ ôóíê-
öèé, íàçûâàþòñÿ ëîãè÷åñêèìè ñâÿçêàìè (èëè ïðîñòî ñâÿçêàìè).
Èìåÿ çàïàñ ýëåìåíòàðíûõ ôóíêöèé. ìû ìîæåì ñòðîèòü èç íèõ áîëåå
ñëîæíûå ñ ïîìîùüþ ââåäåííûõ ëîãè÷åñêèõ ñâÿçîê. Íàïðèìåð,
((
x
→
y
)
|
(
y
→
z
))
∨
(¯
y
·
¯
z
) =
f
(
x, y, z
)
.
Î÷åâèäíî, ÷òî íå âñÿêàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ïåðåìåííûõ, çíàêîâ
ëîãè÷åñêèõ îïåðàöèé è ñêîáîê áóäåò ôîðìóëîé àëãåáðû ëîãèêè. Òàê, íà-
ïðèìåð, ïîñëåäîâàòåëüíîñòè
→ ∨
x
+
y x
|
y
≡
z
íå ìîãóò ðàññìàòðèâàòüñÿ
êàê ïðàâèëüíûå ôîðìóëû àëãåáðû ëîãèêè. Äàäèì èíäóêòèâíîå îïðåäåëå-
íèå ôîðìóëû.
Îïðåäåëåíèå. Ïóñòü
U
ìíîæåñòâî ïåðåìåííûõ. Òîãäà ìíîæåñòâî
ôîðìóë àëãåáðû ëîãèêè íàä
U
îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
1. Âñÿêàÿ ïåðåìåííàÿ ôîðìóëà.
2. Êîíñòàíòû 0 è 1 ôîðìóëû.
2.2. ÝËÅÌÅÍÒÀÐÍÛÅ ËÎÃÈ×ÅÑÊÈÅ ÎÏÅÐÀÖÈÈ(ÔÓÍÊÖÈÈ)
57
3. Åñëè
A
ôîðìóëà, òî
e
A
(èëè â äðóãîé çàïèñè
¯
A
) ôîðìóëà.
4. Åñëè
A
è
B
ôîðìóëû, òî
(
A
∧
B
)
,
(
A
∨
B
)
,
(
A
→
B
)
,
(
A
+
B
)
,
(
A
≡
B
)
,
(
A
|
B
)
,
(
A
↓
B
)
ôîðìóëû.
5. Ôîðìóëàìè ÿâëÿþòñÿ òå è òîëüêî òå âûðàæåíèÿ, êîòîðûå ìîãóò áûòü
ïîëó÷åíû èç êîíñòàíò, ïåðåìåííûõ è ëîãè÷åñêèõ ñâÿçîê çà êîíå÷íîå
÷èñëî øàãîâ 1 4.
 ïóíêòàõ 1 è 2 îïðåäåëåíû ýëåìåíòàðíûå ôîðìóëû, â ïóíêòàõ 3 è 4 çàäàíû
ïðàâèëà îáðàçîâàíèÿ èç ëþáûõ äàííûõ ôîðìóë íîâûõ. Îïðåäåëåíèÿ òàêî-
ãî òèïà íàçûâàþòñÿ èíäóêòèâíûìè îïðåäåëåíèÿìè. Âî âñÿêîì èíäóêòèâ-
íîì îïðåäåëåíèè èìåþòñÿ ïðÿìûå ïóíêòû (ï.ï. 14) è êîñâåííûé ïóíêò.
 ïðÿìûõ ïóíêòàõ çàäàþòñÿ îáúåêòû, êîòîðûå â äàëüíåéøåì èìåíóþòñÿ
îïðåäåëÿåìûì òåðìèíîì (â äàííîì ñëó÷àå ôîðìóëàìè àëãåáðû âûñêàçû-
âàíèé).  êîñâåííîì ïóíêòå ãîâîðèòñÿ, ÷òî òàêèå îáúåêòû èñ÷åðïûâàþòñÿ
çàäàííûìè â ïðÿìûõ ïóíêòàõ. Ñðåäè ïðÿìûõ ïóíêòîâ èìåþòñÿ áàçèñíûå
ïóíêòû (ï. 1 è ï. 2) è èíäóêòèâíûå ïóíêòû (â äàííîì ñëó÷àå ï. 3 è ï. 4).
 áàçèñíûõ ïóíêòàõ ïðÿìî óêàçûâàþòñÿ îáúåêòû, êîòîðûå â äàëüíåéøåì
èìåíóþòñÿ îïðåäåëÿåìûì òåðìèíîì. Â èíäóêòèâíûõ ïóíêòàõ äàþòñÿ ïðà-
âèëà ïîñòðîåíèÿ èç ëþáûõ îáúåêòîâ, îïðåäåëåííûõ â áàçèñíûõ ïóíêòàõ,
íîâûõ îáúåêòîâ, êîòîðûå òàêæå áóäóò èìåíîâàòüñÿ ýòèì òåðìèíîì.
Ïðèäàâàÿ âñåâîçìîæíûå çíà÷åíèÿ âñåì âõîäÿùèì â ôîðìóëó àëãåáðû
ëîãèêè ïåðåìåííûì, ìû ïîëó÷èì òàáëèöó çíà÷åíèé ôóíêöèè.  ýòîì ñìûñ-
ëå ìû áóäåì ãîâîðèòü, ÷òî çàäàííàÿ ôîðìóëà ðåàëèçóåò ôóíêöèþ àëãåáðû
ëîãèêè.
Äâå ôîðìóëû
A
è
B
(èëè
f
1
è
f
2
) áóäåì íàçûâàòü ðàâíîñèëüíûìè (ðàâ-
íûìè) è ïèñàòü
A
=
B
(èëè
f
1
=
f
2
), åñëè îíè ðåàëèçóþò îäíó è òó æå
ôóíêöèþ àëãåáðû ëîãèêè.
Î÷åâèäíî, ÷òî åñëè
A
0
ïîäôîðìóëà ôîðìóëû
A
, òî ïðè çàìåíå ëþáîãî
åå âõîæäåíèÿ íà ðàâíóþ ôîðìóëó
B
ôîðìóëà
A
ïåðåéäåò â ôîðìóëó
B
,
êîòîðàÿ áóäåò ðàâíà
A
.
Îáû÷íî ïðèíèìàþòñÿ ñëåäóþùèå ñîãëàøåíèÿ äëÿ ñîêðàùåíèÿ çàïèñè
ôîðìóë:
•
âíåøíèå ñêîáêè ó ôîðìóë îïóñêàþòñÿ;
•
ôîðìóëà
e
çàïèñûâàåòñÿ êàê
¯
A
;
•
ñ÷èòàåòñÿ, ÷òî îïåðàöèÿ îòðèöàíèÿ ñòàðøå ëþáîé äðóãîé îïåðàöèè,
òî åñòü åñëè çà ñâÿçêîé
e
ñëåäóåò ñèìâîë ïåðåìåííîé (áóêâà), òî îò-
ðèöàíèå îòíîñèòñÿ òîëüêî ê ýòîé ïåðåìåííîé, åñëè æå ñðàçó ïîñëå
58
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
îòðèöàíèÿ
e
îòêðûâàåòñÿ ñêîáêà, òî îòðèöàíèå îòíîñèòñÿ êî âñåìó
çàêëþ÷åííîìó â ñêîáêè âûðàæåíèþ;
•
ôîðìóëà
A
∧
B
çàïèñûâàåòñÿ êàê
A
·
B
, èëè
A
&
B
, èëè
AB
;
•
ñâÿçêà
∧
ñ÷èòàåòñÿ ñòàðøå (ñèëüíåå) ëþáîé äðóãîé äâóõìåñòíîé ñâÿç-
êè.
Ýòè ñîãëàøåíèÿ ïîçâîëÿþò, íàïðèìåð, çàïèñàòü ôîðìóëó
((((
e
x
) +
y
)
∧
z
)
→
((
x
∧
(
e
y
))
∨
z
))
â âèäå
(¯
x
+
y
)
→
(
x
¯
y
∨
z
)
.
2.3 Àëãåáðàè÷åñêèå ñâîéñòâà ýëåìåíòàðíûõ îïå-
ðàöèé
Âàæíåéøèìè àëãåáðàè÷åñêèìè ñâîéñòâàìè ëîãè÷åñêèõ îïåðàöèé ÿâëÿþò-
ñÿ, êàê îáû÷íî, òàêèå ñâîéñòâà, êàê êîììóòàòèâíîñòü, àññîöèàòèâíîñòü è
äèñòðèáóòèâíîñòü îäíèõ îïåðàöèé îòíîñèòåëüíî äðóãèõ.
1. Êîììóòàòèâíîñòü (èëè ïåðåñòàíîâî÷íîñòü) îïåðàöèè * îçíà÷àåò,
÷òî
x
∗
y
=
y
∗
x
. Ëîãè÷åñêàÿ îïåðàöèÿ * êîììóòàòèâíà, åñëè ñâÿçêà *
ïðèíàäëåæèò ñëåäóþùåìó ìíîæåñòâó ñâÿçîê (ñóùåñòâåííî òîëüêî,
÷òîáû ñèìâîë * â ðàâåíñòâå âñþäó èìåë îäèí è òîò æå ñìûñë):
∗ ∈ {∨
,
∧
,
+
,
≡
,
|
,
↓}
.
2. Àññîöèàòèâíîñòü îïåðàöèè * îçíà÷àåò, ÷òî
x
∗
(
y
∗
z
) = (
x
∗
y
)
∗
z
.
Ñâîéñòâî àññîöèàòèâíîñòè ïîçâîëÿåò çàïèñûâàòü ôîðìóëû, ñîäåðæà-
ùèå îäèíàêîâûå àññîöèàòèâíûå ñâÿçêè, áåç ñêîáîê, íàïðèìåð,
x
∨
y
∨
z
,
x
∧
y
∧
z
.
Ëîãè÷åñêàÿ îïåðàöèÿ * àññîöèàòèâíà, åñëè ñâÿçêà * ïðèíàäëåæèò ñëå-
äóþùåìó ìíîæåñòâó ñâÿçîê (ñóùåñòâåííî òîëüêî, ÷òîáû ñèìâîë â ðà-
âåíñòâå âñþäó èìåë îäèí è òîò æå ñìûñë):
∗ ∈ {∧
,
∨
,
+
,
≡}
2.3. ÀËÃÅÁÐÀÈ×ÅÑÊÈÅ ÑÂÎÉÑÒÂÀ ÝËÅÌÅÍÒÀÐÍÛÕ ÎÏÅÐÀÖÈÉ59
3. Äèñòðèáóòèâíîñòü (ðàñïðåäåëèòåëüíûé çàêîí) îïåðàöèè * îòíîñè-
òåëüíî îïåðàöèè
•
îçíà÷àåò, ÷òî
x
∗
(
y
•
z
) = (
x
∗
y
)
•
(
x
∗
z
)
.
Äèñòðèáóòèâíîñòü êîíúþíêöèè:
x
∧
(
y
∨
z
) = (
x
∧
y
)
∨
(
x
∧
z
)
äèñòðèáóòèâíîñòü êîíúþíêöèè îòíî-
ñèòåëüíî äèçúþíêöèè;
x
∧
(
y
+
z
) = (
x
∧
y
) + (
x
∧
z
)
äèñòðèáóòèâíîñòü êîíúþíêöèè îòíî-
ñèòåëüíî ëîãè÷åñêîé ñóììû.
Äèñòðèáóòèâíîñòü äèçúþíêöèè:
x
∨
(
y
∧
z
) = (
x
∨
y
)
∧
(
x
∨
z
)
äèñòðèáóòèâíîñòü äèçúþíêöèè îòíî-
ñèòåëüíî êîíúþíêöèè;
x
∨
(
y
→
z
) = (
x
∨
y
)
→
(
x
∨
z
)
äèñòðèáóòèâíîñòü äèçúþíêöèè îòíî-
ñèòåëüíî èìïëèêàöèè;
x
∨
(
y
≡
z
) = (
x
∨
y
)
≡
(
x
∨
z
)
äèñòðèáóòèâíîñòü äèçúþíêöèè
îòíîñèòåëüíî ýêâèâàëåíòíîñòè.
Äèñòðèáóòèâíîñòü èìïëèêàöèè:
x
→
(
y
∧
z
) = (
x
→
y
)
∧
(
x
→
z
)
äèñòðèáóòèâíîñòü èìïëèêàöèè
îòíîñèòåëüíî êîíúþíêöèè;
x
→
(
y
∨
z
) = (
x
→
y
)
∨
(
x
→
z
)
äèñòðèáóòèâíîñòü èìïëèêàöèè
îòíîñèòåëüíî äèçúþíêöèè;
x
→
(
y
→
z
) = (
x
→
y
)
→
(
x
→
z
)
äèñòðèáóòèâíîñòü èìïëèêàöèè
îòíîñèòåëüíî èìïëèêàöèè.
4. Èìååò ìåñòî ñëåäóþùåå ñîîòíîøåíèå äëÿ äâîéíîãî îòðèöàíèÿ:
¯
¯
x
=
x
.
5. Èìåþò ìåñòî ñëåäóþùèå ñîîòíîøåíèÿ ìåæäó îòðèöàíèåì, êîíúþíê-
öèåé è äèçúþíêöèåé.
Ïðàâèëà äà Ìîðãàíà:
x
∧
y
= ¯
x
∨
¯
y
x
∨
y
= ¯
x
∧
¯
y
Óêàçàííûå ñîîòíîøåíèÿ îòðàæàþò îòíîøåíèå äâîéñòâåííîñòè ìåæäó
äèçúþíêöèåé è êîíúþíêöèåé.
6. Èìåþò ìåñòî ñëåäóþùèå ñîîòíîøåíèÿ, ñâÿçàííûå ñ ¾íàâåøèâàíèåì
îòðèöàíèÿ¿ íà ýëåìåíòàðíûå ëîãè÷åñêèå ôóíêöèè:
x
|
y
=
x
∧
y
;
x
↓
y
=
x
∨
y
;
x
+
y
=
x
≡
y
;
x
≡
y
=
x
+
y
x
→
y
= ¯
x
∨
y
=
x
¯
y
.
60
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
7.
0 =
x
∧
¯
x
=
x
∧
0 =
x
+
x
1 =
x
∨
¯
x
=
x
∨
1 =
x
≡
x
.
8. Ïðàâèëà ïîãëîùåíèÿ:
x
∨
(
x
∧
y
) =
x
x
∧
(
x
∨
y
) =
x
9. Âûïîëíÿþòñÿ ñëåäóþùèå ñâîéñòâà êîíúþíêöèè è äèçúþíêöèè:
x
∧
x
=
x,
x
∨
x
=
x,
x
∧
¯
x
= 0
,
x
∨
¯
x
= 1
,
x
∧
0 = 0
,
x
∨
0 =
x,
x
∧
1 =
x,
x
∨
1 = 1
.
Âñå óêàçàííûå òîæäåñòâà ìîãóò áûòü ïðîâåðåíû ïóòåì ñîïîñòàâëåíèÿ
ôóíêöèé, ðåàëèçóåìûõ ïðàâîé è ëåâîé ÷àñòÿìè ôîðìóë.
Ââåäåííûå íàìè ýëåìåíòàðíûå ôóíêöèè íå ÿâëÿþòñÿ íåçàâèñèìûìè,
òàê, íàïðèìåð:
x
≡
y
=(
x
→
y
)&(
y
→
x
) =
x
∧
y
∨
¯
x
∧
¯
y
;
x
→
y
= ¯
x
∨
y.
Èìååòñÿ ãîðàçäî áîëåå ðàäèêàëüíàÿ âîçìîæíîñòü ñâåäåíèÿ: âñå ýëåìåí-
òàðíûå ôóíêöèè ìîãóò áûòü âûðàæåíû ÷åðåç îäíó-åäèíñòâåííóþ: øòðèõ
Øåôôåðà èëè ñòðåëêó Ïèðñà.
Çàäà÷à. Âûðàçèòü âñå ýëåìåíòàðíûå ôóíêöèè ÷åðåç
|
è
↓
.
2.4 Ðàçëîæåíèå ôóíêöèé àëãåáðû ëîãèêè ïî
ïåðåìåííûì
Ãîâîðÿ î ÿçûêå ôîðìóë, ìû ñîçíàòåëüíî íå êàñàëèñü âåñüìà âàæíîãî âî-
ïðîñà: âñÿêàÿ ëè ôóíêöèÿ àëãåáðû ëîãèêè ìîæåò áûòü âûðàæåíà â âèäå
ôîðìóëû, åñëè äîïóñòèòü íåêîòîðûé çàïàñ ýëåìåíòàðíûõ ôóíêöèé? Áëè-
æàéøèå ðàññìîòðåíèÿ íàïðàâëåíû íà ðåøåíèå ýòîãî âîïðîñà.
×òîáû èìåòü âîçìîæíîñòü åäèíîîáðàçíî çàïèñûâàòü ïåðåìåííûå ñ îò-
ðèöàíèåì è áåç îòðèöàíèÿ ââåäåì ñëåäóþùåå îáîçíà÷åíèå:
x
σ
=
(
x,
åñëè
σ
= 1
¯
x,
åñëè
σ
= 0
.