Самохин А.В. Математическая логика и теория алгоритмов
Подождите немного. Документ загружается.
§1. áÌÇÅÂÒÁ ×ÙÓËÁÚÙ×ÁÎÉÊ 211
ðÒÉÍÅÒ 2. ó ÐÏÍÏÝØÀ ÒÁ×ÎÏÓÉÌØÎÙÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ ÕÐÒÏÓÔÉÔØ ÆÏÒÍÕ-
ÌÕ
x
1
x
2
→ (x
1
∨ x
2
)x
3
.
òÅÛÅÎÉÅ.
x
1
x
2
→ (x
1
∨ x
2
)x
3
ÐÅÒÅÈÏÄ Ë
≡
ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ
x
1
x
2
∨ (x
1
∨ x
2
)x
3
≡
ÚÁËÏÎ ÄÅ íÏÒÇÁÎÁ
≡
ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ ÚÁËÏÎ
x
1
∨ x
2
∨ x
1
x
3
∨ x
2
x
3
ÚÁËÏÎ
≡
Ä×ÏÊÎÏÇÏ ÏÔÒÉÃÁÎÉÑ
≡ x
1
∨ x
1
x
3
|
{z }
ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
∨ x
2
∨ x
2
x
3
|
{z }
ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
≡
≡ x
1
∨ x
2
∨ x
3
≡
Á)
x
1
∨ (x
2
∨ x
3
) ≡ x
1
→ (x
2
∨ x
3
),
Â) x
3
∨ (x
1
∨ x
2
) ≡ x
3
→ (x
1
∨ x
2
),
×) x
2
∨ x
1
∨ x
3
≡ x
2
∨ x
1
x
3
,
Ç) x
1
∨ x
3
∨ x
2
≡ x
1
x
3
∨ x
2
≡ x
1
x
3
→ x
2
,
Ä) x
1
∨ x
2
∨ x
3
≡ x
1
· x
2
· x
3
.
úÁÍÅÞÁÎÉÅ. ìÀÂÕÀ ÚÁÐÉÓØ Á) ¡ Ä) ÍÏÖÎÏ ÓÞÉÔÁÔØ ÏÔ×ÅÔÏÍ.
óÌÅÄÕÀÝÉÊ ÔÉÐ ÐÒÉÍÅÒÏ× ¡ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÒÁ×ÎÏÓÉÌØÎÏÓÔÉ Ä×ÕÈ ÚÁÄÁÎ-
ÎÙÈ ÆÏÒÍÕÌ Ó ÐÏÍÏÝØÀ ÒÁ×ÎÏÓÉÌØÎÙÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ. óÕÝÅÓÔ×ÕÀÔ ÔÒÉ
ÏÓÎÏ×ÎÙÅ ÓÈÅÍÙ ÒÅÛÅÎÉÑ ÔÁËÉÈ ÐÒÉÍÅÒÏ×. ëÁÖÄÁÑ ÉÚ ÎÉÈ ÐÒÅÄÐÏÌÁÇÁÅÔ ×Ù-
ÐÏÌÎÅÎÉÅ ÐÅÒÅÈÏÄÁ Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ × ÉÓÈÏÄÎÙÈ ÆÏÒÍÕÌÁÈ.
äÁÌÅÅ, ÐÏ ÐÅÒ×ÏÊ ÓÈÅÍÅ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÎÁÞÉÎÁÑ Ó ÌÅ×ÏÊ ÆÏÒÍÕÌÙ, ÐÒÏ×Å-
ÓÔÉ ÃÅÐÏÞËÕ ÒÁ×ÎÏÓÉÌØÎÙÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ, ÚÁ×ÅÒÛÉ× Å¾ ÎÁ ÐÒÁ×ÏÊ ÆÏÒÍÕÌÅ.
÷ÔÏÒÁÑ ÓÈÅÍÁ ¡ ÚÅÒËÁÌØÎÏÅ ÏÔÒÁÖÅÎÉÅ ÐÅÒ×ÏÊ.
ôÒÅÔØÑ ÓÈÅÍÁ ÐÒÅÄÐÏÌÁÇÁÅÔ ÐÒÏ×ÅÄÅÎÉÅ ÐÁÒÁÌÌÅÌØÎÙÈ ÃÅÐÏÞÅË ÒÁ×ÎÏ-
ÓÉÌØÎÙÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ ÌÅ×ÏÊ É ÐÒÁ×ÏÊ ÆÏÒÍÕÌ ÄÏ ÔÅÈ ÐÏÒ, ÐÏËÁ × ÜÔÉÈ
ÃÅÐÏÞËÁÈ ÎÅ ÏÂÎÁÒÕÖÉÔÓÑ ÓÏ×ÐÁÄÅÎÉÅ ËÁËÉÈ-ÔÏ Ú×ÅÎØÅ× (ÏÄÎÏÇÏ Ú×ÅÎÁ ÌÅ×ÏÊ
ÃÅÐÏÞËÉ Ó ÏÄÎÉÍ Ú×ÅÎÏÍ ÐÒÁ×ÏÊ).
ðÒÉÍÅÒ 3. äÏËÁÚÁÔØ, ÞÔÏ
(x
1
→ x
3
)(x
2
→ x
3
) ≡ (x
1
∨ x
2
) → x
3
.
òÅÛÅÎÉÅ. ðÅÒÅÊÄ¾Í Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ
(x
1
∨ x
3
)(x
2
∨ x
3
) ≡ x
1
∨ x
2
∨ x
3
.
212 úÁÄÁÞÉ
1-Ñ ÓÈÅÍÁ:
(x
1
∨ x
3
)(x
2
∨ x
3
)
ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
≡
ÚÁËÏÎ
x
1
x
2
∨
ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
z
}| {
x
3
x
2
∨ x
1
x
3
∨ x
3
|
{z }
ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
≡
≡ x
1
x
2
∨ x
3
ÚÁËÏÎ
≡
ÄÅ íÏÒÇÁÎÁ
x
1
∨ x
2
∨ x
3
.
2-Ñ ÓÈÅÍÁ:
x
1
∨ x
2
∨ x
3
ÚÁËÏÎ
≡
ÄÅ íÏÒÇÁÎÁ
x
1
· x
2
∨ x
3
ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
≡
ÚÁËÏÎ
(
x
1
∨ x
3
)(x
2
∨ x
3
).
3-Ñ ÓÈÅÍÁ:
(x
1
∨ x
2
)(x
2
∨ x
3
)
ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
≡
ÚÁËÏÎ
x
1
x
2
∨ x
2
x
2
∨ x
1
x
3
∨ x
3
≡ x
1
x
2
∨ x
3
;
x
1
∨ x
2
∨ x
3
ÚÁËÏÎ
≡
ÄÅ íÏÒÇÁÎÁ
x
1
x
2
∨ x
3
.
úÁÍÅÞÁÎÉÅ. óÌÅÄÕÅÔ ÉÍÅÔØ × ×ÉÄÕ, ÞÔÏ ÓÒÅÄÉ ÐÒÉÍÅÒÏ× ÎÁ ÄÏËÁÚÁÔÅÌØ-
ÓÔ×Ï ÒÁ×ÎÏÓÉÌØÎÏÓÔÉ ÆÏÒÍÕÌ ÅÓÔØ ÐÒÉÍÅÒÙ Ó ÏÔÒÉÃÁÔÅÌØÎÙÍ ÏÔ×ÅÔÏÍ. ÷
ÜÔÏÍ ÓÌÕÞÁÅ ÎÉ ÏÄÎÁ ÉÚ ÓÈÅÍ ÎÅ ÐÒÉ×ÏÄÉÔ Ë ÐÏÌÕÞÅÎÉÀ ÏÔ×ÅÔÁ. ïÄÎÁËÏ,
ÎÅÕÄÁÞÁ ÐÒÉ ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÓÈÅÍ 1 ¡ 3 ÍÏÖÅÔ ÇÏ×ÏÒÉÔØ É Ï ÎÅÄÏÓÔÁÔÏÞÎÏ
×ÙÓÏËÏÊ ÔÅÈÎÉËÅ ÒÁ×ÎÏÓÉÌØÎÙÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ. ÷ ÓÌÕÞÁÅ ÎÅÕÄÁÞÎÙÈ ÐÏÐÙ-
ÔÏË ÐÒÉÍÅÎÅÎÉÑ ÓÈÅÍ 1 ¡ 3 ÓÌÅÄÕÅÔ ÄÌÑ ÏÂÅÉÈ ÆÏÒÍÕÌ ÐÏÓÔÒÏÉÔØ ÔÁÂÌÉÃÙ
ÉÓÔÉÎÎÏÓÔÉ. óÏ×ÐÁÄÅÎÉÅ ÓÔÏÌÂÃÏ× ÚÎÁÞÅÎÉÊ ÆÏÒÍÕÌ ÂÕÄÅÔ ÏÚÎÁÞÁÔØ ÉÈ ÒÁ×-
ÎÏÓÉÌØÎÏÓÔØ, Á ÎÅÓÏ×ÐÁÄÅÎÉÅ ¡ ÎÅÒÁ×ÎÏÓÉÌØÎÏÓÔØ.
ðÒÉÍÅÎÑÑ ÒÁ×ÎÏÓÉÌØÎÙÅ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ, ÄÏËÁÚÁÔØ ÓÌÅÄÕÀÝÉÅ ÓÏÏÔÎÏÛÅ-
ÎÉÑ:
71. x ∨ y ≡ x · y; 72. xy ≡ x ∨ y; 73. x → y ≡ x · y; 74. x → y ≡ y → x;
75. xy ∨ xy ≡ x; 76. x ∨ xy ≡ x; 77. x(x ∨ y) ≡ x; 78. x ∨ xy ≡ x ∨ y;
79. x(x ∨ y) ≡ xy; 80. (x → y) → y ≡ x ∨ y; 81. (x ∨ y)(x ∨ y) ≡ x;
82. x ∨ y ≡ y → x; 83. x ∼ y ≡ x ∼ y; 84. xy ∨ xy ∨ xy ≡ x → y;
85. x → (y → z) ≡ (x ∨ z)(y ∨ z); 86. x → (y → z) ≡ y → (x → z);
87. x ∨ xy ∨ xz ∨ xy ∨ xz ≡ x → y ∨ z.
ðÒÉÍÅÎÑÑ ÒÁ×ÎÏÓÉÌØÎÙÅ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ, ÄÏËÁÚÁÔØ ÔÏÖÄÅÓÔ×ÅÎÎÕÀ ÉÓ-
ÔÉÎÎÏÓÔØ ÆÏÒÍÕÌ:
88. x → x ∨ y; 89. xy → x; 90. x → (x → y); 91. (x → y) → (x ∨ y);
92. (x ∨
xy) ∼ (x ∨ y); 93. (x → y) → (y → x); 94. (x → y) → (y → x);
95. (x → y) ∨ (y → x); 96. (x → y) ∨ (x → y); 97. x → (y → xy);
98. (x → y)x → y; 99. (x → y)
y → x; 100. (x ∨ y)x → y;
101. (x∨∨ y)x → y (¤∨ ∨¥ ¡ ÁÌØÔÅÒÎÁÔÉ×ÎÁÑ ÄÉÚßÀÎËÃÉÑ: (x∨∨ y) ≡ x ∼ y);
§2. ä×ÏÊÓÔ×ÅÎÎÏÓÔØ × ÁÌÇÅÂÒÅ ×ÙÓËÁÚÙ×ÁÎÉÊ 213
102. (x → y)(y → z) → (x → z); 103. (x → (y → z)) → (xy → z);
104. (x → z)(y → z) → (x∨y → z); 105. (x → z) → ((y → z) → (x∨y → z)).
ðÒÉÍÅÎÑÑ ÒÁ×ÎÏÓÉÌØÎÙÅ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ, ¤ÕÐÒÏÓÔÉÔØ¥:
106. xy ∨ (x → y)x; 107.
x ∨ y → x ∨ y
y; 108. (x → y)(y → x);
109. (x∨y)(x ∼ y); 110. (x → y)(y → z) → (z → x); 111. xz ∨xz∨yz ∨xyz;
112. xy(x → y); 113. xy(x ∼ y); 114. (x → y)(x ∼ y); 115. (x → y)∨(x ∨ y).
óÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ ÐÒÅÏÂÒÁÚÏ×ÁÔØ ÔÁË, ÞÔÏÂÙ ÏÎÉ ÓÏÄÅÒÖÁÌÉ ÔÏÌØËÏ
¤∧¥ É ¤¬¥:
116. x ∨ y; 117. x → y; 118. x ∼ y; 119. x ∨ y ∨ z; 120. x → (y → z);
121. x∨ (x ∼ y); 122. x → y ∨ (x → y); 123. x ∨∨ y; 124. xy → (y → x);
125. x ∨ y → (x → z).
óÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ ÐÒÅÏÂÒÁÚÏ×ÁÔØ ÔÁË, ÞÔÏÂÙ ÏÎÉ ÓÏÄÅÒÖÁÌÉ ÔÏÌØËÏ
¤∨¥ É ¤¬¥:
126. xy; 127. xyz; 128. x ∼ y; 129. x ∨ ∨ y; 130. x(y ∼ z);
131. x ∼ y ∼ z; 132. (x ∼ y)(y ∼ z); 133. xy ∼ xz.
ðÒÅÏÂÒÁÚÏ×ÁÔØ ÓÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ ÔÁË, ÞÔÏÂÙ ÚÎÁË ÏÔÒÉÃÁÎÉÑ ÂÙÌ ÏÔ-
ÎÅӾΠÔÏÌØËÏ Ë ÐÅÒÅÍÅÎÎÙÍ ×ÙÓËÁÚÙ×ÁÎÉÑÍ:
134. x ∨ y; 135. xy ∨ z; 136. xy ∨ z → xyz; 137. x → (y → z);
138. x → y → (x → z); 139. (x ∼ y)(y ∼ z).
ðÒÅÏÂÒÁÚÏ×ÁÔØ ÆÏÒÍÕÌÙ ÔÁË, ÞÔÏÂÙ ÏÎÉ ÓÏÄÅÒÖÁÌÉ ÔÏÌØËÏ ÏÐÅÒÁÃÉÉ ¤∨¥,
¤∧¥ É ¤¬¥:
140. x ∼ y; 141. (x → y) ∼ (y → z); 142. (x ∼ y) → (y → z);
143. (x ∼ y) → (y ∼ z); 144. (x ∼ y)(y ∼ z) → (x ∼ z);
145. (x ∼ y) ∨ (y ∼ z) → (x ∼ y ∼ z); 146. x ∼ y ∼ z ∼ v;
147. (x → y) ∼ (z → (x ∼ z)).
§2. ä×ÏÊÓÔ×ÅÎÎÏÓÔØ × ÁÌÇÅÂÒÅ ×ÙÓËÁÚÙ×ÁÎÉÊ
ðÏÓÔÒÏÅÎÉÅ Ä×ÏÊÓÔ×ÅÎÎÙÈ ÆÏÒÍÕÌ ÏÓÎÏ×ÁÎÏ ÎÁ ÏÂÝÅÍ É ÂÕÌÅ×ÏÍ ÐÒÉÎÃÉ-
ÐÁÈ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ.
ïÂÝÉÊ ÐÒÉÎÃÉÐ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ ÓÏÓÔÏÉÔ × ÓÌÅÄÕÀÝÅÍ: ÅÓÌÉ ÉÓÈÏÄÎÁÑ
ÆÏÒÍÕÌÁ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ÐÏÄÓÔÁÎÏ×ËÕ ÆÏÒÍÕÌ × ÆÏÒÍÕÌÕ, ÔÏ Ä×ÏÊÓÔ×ÅÎ-
ÎÁÑ ÆÏÒÍÕÌÁ ¡ ÁÎÁÌÏÇÉÞÎÁÑ ÐÏÄÓÔÁÎÏ×ËÁ Ä×ÏÊÓÔ×ÅÎÎÙÈ ÆÏÒÍÕÌ × Ä×ÏÊ-
ÓÔ×ÅÎÎÕÀ ÆÏÒÍÕÌÕ.
ðÒÉÍÅÒ 4. ðÕÓÔØ
F (x
1
, x
2
, x
3
) = (x
1
→ x
2
x
3
) ∨ (x
1
∼ x
3
).
îÁÊÔÉ Ä×ÏÊÓÔ×ÅÎÎÕÀ ÆÏÒÍÕÌÕ F
∗
.
214 úÁÄÁÞÉ
òÅÛÅÎÉÅ. ïÂÏÚÎÁÞÉÍ y
1
= x
1
→ x
2
x
3
, y
2
= x
1
∼ x
3
, ÔÏÇÄÁ F = y
1
∨ y
2
.
îÁÊÄ¾Í Ä×ÏÊÓÔ×ÅÎÎÙÅ ÆÏÒÍÕÌÙ ÄÌÑ ÐÏÄÓÔÁ×ÌÑÅÍÙÈ ÆÏÒÍÕÌ (y
1
, y
2
) É ÄÌÑ
ÆÏÒÍÕÌÙ, × ËÏÔÏÒÕÀ ÏÓÕÝÅÓÔ×ÌÑÅÔÓÑ ÐÏÄÓÔÁÎÏ×ËÁ (F):
(y
1
∨ y
2
)
∗
≡ y
1
∨ y
2
≡ y
1
· y
2
≡ y
1
· y
2
;
(x
1
→ x
2
x
3
)
∗
≡ x
1
→ x
2
x
3
≡ x
1
∨ x
2
x
3
≡
≡ x
1
∨ x
2
x
3
≡ x
1
· x
2
· x
3
≡ x
1
(x
2
∨ x
3
) ≡ x
1
(x
2
→ x
3
);
(x
1
∼ x
3
)
∗
≡ x
1
∼ x
3
≡ x
1
· x
3
∨ x
1
· x
3
≡ x
1
x
3
∨ x
1
x
3
≡
≡ x
1
x
3
· x
1
· x
3
≡ (x
1
∨ x
3
)(x
1
∨ x
3
) ≡ x
1
x
3
∨ x
1
x
3
≡ x
1
∼ x
3
.
ðÒÉÍÅÎÉÍ ÔÅÐÅÒØ ÏÂÝÉÊ ÐÒÉÎÃÉÐ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ:
F
∗
≡ y
1
· y
2
≡ x
1
(x
2
→ x
3
)(x
1
∼ x
3
).
âÕÌÅ× ÐÒÉÎÃÉÐ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ ÓÏÓÔÏÉÔ × ÓÌÅÄÕÀÝÅÍ: ÆÏÒÍÕÌÁ, Ä×ÏÊ-
ÓÔ×ÅÎÎÁÑ Ë ÂÕÌÅ×ÏÊ ÆÏÒÍÕÌÅ ÐÏÌÕÞÁÅÔÓÑ ÚÁÍÅÎÏÊ ∨ ÎÁ ∧, ∧ ÎÁ ∨, 0 ÎÁ 1, 1
ÎÁ 0 É ÓÏÈÒÁÎÅÎÉÅÍ ÓÔÒÕËÔÕÒÙ ÆÏÒÍÕÌÙ.
ðÒÉÍÅÒ 5. îÁÊÔÉ ÆÏÒÍÕÌÕ, Ä×ÏÊÓÔ×ÅÎÎÕÀ Ë ÆÏÒÍÕÌÅ
(x
1
→ x
2
x
3
) ∨ (x
1
∼ x
3
),
ÐÏÌØÚÕÑÓØ ÂÕÌÅ×ÙÍ ÐÒÉÎÃÉÐÏÍ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ.
òÅÛÅÎÉÅ.
((x
1
→ x
2
x
3
) ∨ (x
1
∼ x
3
))
∗
≡ ((x
1
∨ x
2
x
3
) ∨ (x
1
x
3
∨ x
1
x
3
))
∗
ÂÕÌÅ× ÐÒÉÎÃÉÐ
≡
Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ
≡
x
1
· (x
2
∨ x
3
) · ((x
1
∨ x
3
)(x
1
∨ x
3
))
ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
≡
ÚÁËÏÎ
≡ x
1
(x
2
→ x
3
)(x
1
x
3
∨ x
3
x
1
) ≡ x
1
(x
2
→ x
3
)(x
1
∼ x
3
).
îÁÊÔÉ Ä×ÏÊÓÔ×ÅÎÎÙÅ ÆÏÒÍÕÌÙ:
148. x(y∨z); 149. xy∨xz; 150. (x ∨ y)(x∨yz); 151. (xy∨yz∨zv)(x ∨ y ∨ z);
152. x
y ∨ z(x ∨ y)
; 153. xyz∨xyz∨xyz∨xyz; 154.
(x ∨ y)(x ∨ z) ∨ xy
∨
∨
(x ∨ y)z ∨ x
; 155. xy
yz ∨ xyz(xz ∨ yz) ∨ xy
(x ∨ y ∨ z).
ðÒÉÍÅÎÉÔØ ÚÁËÏÎ Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ Ë ÓÌÅÄÕÀÝÉÍ ÒÁ×ÎÏÓÉÌØÎÏÓÔÑÍ:
156. xx ≡ x; 157. x ∨ 0 ≡ x; 158. xy ≡ yx; 159. x ∨ (y ∨ z) ≡ (x ∨ y) ∨ z;
160. xy ≡ x ∨ y; 161. x(x ∨ y) ≡ x; 162. x ∨ xy ≡ x ∨ y;
163. x ∨ xy ∨ yz ∨ xz ≡ x ∨ z.
§3. îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ: äîæ, ëîæ, óäîæ, óëîæ 215
§3. îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ: äîæ, ëîæ, óäîæ, óëîæ
îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ ÆÏÒÍÕÌ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÂÙ×ÁÀÔ Ä×ÕÈ ÔÉÐÏ×:
ÄÉÚßÀÎËÔÉ×ÎÙÅ É ËÏÎßÀÎËÔÉ×ÎÙÅ, × ËÁÖÄÏÍ ÉÚ ÜÔÉÈ ÔÉÐÏ× ×ÙÄÅÌÅÎ ËÌÁÓÓ
ÓÏ×ÅÒÛÅÎÎÙÈ ÆÏÒÍ.
áÌÇÏÒÉÔÍ ÐÏÓÔÒÏÅÎÉÑ ÄÉÚßÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÙ (äîæ):
1. ðÅÒÅÊÔÉ Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ.
2. ðÅÒÅÊÔÉ Ë ÆÏÒÍÕÌÅ Ó ÔÅÓÎÙÍÉ ÏÔÒÉÃÁÎÉÑÍÉ, ÔÏ ÅÓÔØ Ë ÆÏÒÍÕÌÅ, ×
ËÏÔÏÒÏÊ ÏÔÒÉÃÁÎÉÑ ÎÁÈÏÄÑÔÓÑ ÎÅ ×ÙÛÅ, ÞÅÍ ÎÁÄ ÐÅÒÅÍÅÎÎÙÍÉ.
3. òÁÓËÒÙÔØ ÓËÏÂËÉ.
4. ðÏ×ÔÏÒÑÀÝÉÅÓÑ ÓÌÁÇÁÅÍÙÅ ×ÚÑÔØ ÐÏ ÏÄÎÏÍÕ ÒÁÚÕ.
5. ðÒÉÍÅÎÉÔØ ÚÁËÏÎÙ ÐÏÇÌÏÝÅÎÉÑ É ÐÏÌÕÐÏÇÌÏÝÅÎÉÑ.
ðÒÉÍÅÒ 6. îÁÊÔÉ äîæ ÆÏÒÍÕÌÙ
(x
1
→ x
2
x
3
) → (x
1
∼ x
3
).
òÅÛÅÎÉÅ.
(x
1
→ x
2
x
3
) → (x
1
∼ x
3
) ≡ (x
1
→ x
2
x
3
) ∨ (x
1
x
3
∨ x
1
x
3
) ≡
≡ x
1
· (x
2
∨ x
3
) ∨ x
1
x
3
∨ x
1
x
3
≡ x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
∨ x
1
x
3
≡
≡ x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
.
ëÏÎßÀÎËÔÉ×ÎÁÑ ÎÏÒÍÁÌØÎÁÑ ÆÏÒÍÁ (ëîæ) ¡ Ä×ÏÊÓÔ×ÅÎÎÏÅ ÄÌÑ äîæ ÐÏ-
ÎÑÔÉÅ, ÐÏÜÔÏÍÕ Å¾ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÐÏ ÓÈÅÍÅ:
f ≡ (f
∗
)
∗
≡ (äîæ(f
∗
))
∗
≡ ëîæ(f).
ðÒÉÍÅÒ 7. îÁÊÔÉ ëîæ ÆÏÒÍÕÌÙ
(x
1
→ x
2
x
3
)(x
1
∼ x
3
).
òÅÛÅÎÉÅ.
(x
1
→ x
2
x
3
)(x
1
∼ x
3
) ≡ (((x
1
→ x
2
x
3
)(x
1
∼ x
3
))
∗
)
∗
≡
≡ (((x
1
∨ x
2
x
3
)(x
1
x
3
∨ x
1
x
3
))
∗
)
∗
≡
≡ (x
1
· (x
2
∨ x
3
) ∨ (x
1
∨ x
3
) · (x
1
∨ x
3
))
∗
≡
≡ (x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
∨ x
1
x
3
)
∗
≡ (x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
)
∗
≡
≡ (x
1
∨ x
2
)(x
1
∨ x
3
)(x
1
∨ x
3
).
óÏ×ÅÒÛÅÎÎÕÀ ÄÉÚßÀÎËÔÉ×ÎÕÀ ÎÏÒÍÁÌØÎÕÀ ÆÏÒÍÕ (óäîæ) ÍÏÖÎÏ ÐÏ-
ÓÔÒÏÉÔØ, ÉÓÐÏÌØÚÕÑ ÓÌÅÄÕÀÝÉÊ ÁÌÇÏÒÉÔÍ:
1. ðÅÒÅÊÔÉ Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ.
2. ðÅÒÅÊÔÉ Ë ÆÏÒÍÕÌÅ Ó ÔÅÓÎÙÍÉ ÏÔÒÉÃÁÎÉÑÍÉ, ÔÏ ÅÓÔØ Ë ÆÏÒÍÕÌÅ, ×
ËÏÔÏÒÏÊ ÏÔÒÉÃÁÎÉÑ ÎÁÈÏÄÑÔÓÑ ÎÅ ×ÙÛÅ, ÞÅÍ ÎÁÄ ÐÅÒÅÍÅÎÎÙÍÉ.
216 úÁÄÁÞÉ
3. òÁÓËÒÙÔØ ÓËÏÂËÉ.
4. ðÏ×ÔÏÒÑÀÝÉÅÓÑ ÓÌÁÇÁÅÍÙÅ ×ÚÑÔØ ÐÏ ÏÄÎÏÍÕ ÒÁÚÕ.
5. ïÐÕÓÔÉÔØ ÔÏÖÄÅÓÔ×ÅÎÎÏ ÌÏÖÎÙÅ ÓÌÁÇÁÅÍÙÅ, ÔÏ ÅÓÔØ ÓÌÁÇÁÅÍÙÅ ×ÉÄÁ:
. . . · x
i
· x
i
· . . .
6. ðÏÐÏÌÎÉÔØ ÏÓÔÁ×ÛÉÅÓÑ ÓÌÁÇÁÅÍÙÅ ÎÅÄÏÓÔÁÀÝÉÍÉ ÐÅÒÅÍÅÎÎÙÍÉ.
(ðÒÉÍÅÒ ÎÁ ÐÏÐÏÌÎÅÎÉÅ (ÐÅÒÅÍÅÎÎÙÅ x
1
, x
2
, x
3
):
. . . ∨ x
1
x
3
∨ . . . ≡ . . . x
1
(x
2
∨ x
2
)x
3
. . . ≡ . . . ∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ . . . )
7. ðÏ×ÔÏÒÑÀÝÉÅÓÑ ÓÌÁÇÁÅÍÙÅ ×ÚÑÔØ ÐÏ ÏÄÎÏÍÕ ÒÁÚÕ.
ðÒÉÍÅÒ 8. îÁÊÔÉ óäîæ ÆÏÒÍÕÌÙ
(x
1
→ x
2
x
3
) → (x
1
∼ x
3
).
òÅÛÅÎÉÅ.
(x
1
→ x
2
x
3
)(x
1
∼ x
3
)
1
≡ x
1
→ x
2
x
3
∨ (x
1
x
3
∨ x
1
x
3
)
2
≡
≡ x
1
· (x
2
∨ x
3
) ∨ x
1
x
3
∨ x
1
x
3
3
≡
≡ x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
∨ x
1
x
3
4
≡ x
1
x
2
∨ x
1
x
3
∨ x
1
x
3
6
≡
≡ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
7
≡
≡ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
.
óÏ×ÅÒÛÅÎÎÕÀ ËÏÎßÀÎËÔÉ×ÎÕÀ ÎÏÒÍÁÌØÎÕÀ ÆÏÒÍÕ (óëîæ) ÍÏÖÎÏ ÐÏ-
ÓÔÒÏÉÔØ ÐÏ ÓÌÅÄÕÀÝÅÊ ÓÈÅÍÅ:
f ≡ (f
∗
)
∗
≡ (óäîæ(f
∗
))
∗
ÐÒÉÎÃÉÐ
≡
Ä×ÏÊÓÔ×ÅÎÎÏÓÔÉ
óëîæ(f).
ðÒÉÍÅÒ 9. îÁÊÔÉ óëîæ ÆÏÒÍÕÌÙ
(x
1
→ x
2
x
3
) → (x
1
∼ x
3
).
òÅÛÅÎÉÅ.
(x
1
→ x
2
x
3
) → (x
1
∼ x
3
) ≡
(x
1
→ x
2
x
3
) ∨ (x
1
x
3
∨ x
1
x
3
)
∗
∗
≡
≡ (x
1
(x
2
∨ x
3
) ∨ x
1
x
3
∨ x
1
x
3
)
∗
)
∗
≡ ((x
1
∨ x
2
x
3
) · (x
1
∨ x
3
) · (x
1
∨ x
3
))
∗
≡
≡ ((x
1
∨ x
1
x
2
x
3
∨ x
1
x
3
∨ x
2
x
3
)(x
1
∨ x
3
))
∗
≡ (x
1
x
2
x
3
∨ x
1
x
3
)
∗
≡
≡ (x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
)
∗
≡ (x
1
∨ x
2
∨ x
3
)(x
1
∨ x
2
∨ x
3
)(x
1
∨ x
2
∨ x
3
).
éÚ×ÅÓÔÎÏ, ÞÔÏ óäîæ É óëîæ ÏÐÒÅÄÅÌÅÎÙ ÆÏÒÍÕÌÏÊ ÏÄÎÏÚÎÁÞÎÏ É, ÚÎÁ-
ÞÉÔ, ÉÈ ÍÏÖÎÏ ÓÔÒÏÉÔØ ÐÏ ÔÁÂÌÉÃÅ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ.
óÈÅÍÁ ÐÏÓÔÒÏÅÎÉÑ óäîæ É óëîæ ÐÏ ÔÁÂÌÉÃÅ ÉÓÔÉÎÎÏÓÔÉ ÐÒÉ×ÅÄÅÎÁ ÎÉ-
ÖÅ ÄÌÑ ÆÏÒÍÕÌÙ (x
1
→ x
2
x
3
)(x
1
∼ x
3
).
§3. îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ: äîæ, ëîæ, óäîæ, óëîæ 217
x
1
x
2
x
3
(x
1
→ x
2
x
3
)(x
1
∼ x
3
)
0 0 0 1 → x
1
x
2
x
3
0 0 1 0 → x
1
∨ x
2
∨ x
3
0 1 0 1 → x
1
x
2
x
3
0 1 1 0 → x
1
∨ x
2
∨ x
3
1 0 0 1 → x
1
x
2
x
3
1 0 1 1 → x
1
x
2
x
3
1 1 0 0 → x
1
∨ x
2
∨ x
3
1 1 1 1 → x
1
x
2
x
3
óäîæ: x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
;
óëîæ: (x
1
∨ x
2
∨ x
3
)(x
1
∨ x
2
∨ x
3
)(x
1
∨ x
2
∨ x
3
).
ðÒÉ×ÅÓÔÉ Ë ÄÉÚßÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÅ (äîæ):
164. x → (y → z); 165. xy ∨ (x → y); 166. (x ∨ y ∨ z)(x → y);
167. (x ∨ y)(y ∨ z) → (x ∨ z); 168. x ∼ y; 169. x ∨ ∨ y; 170. x ∼ y ∼ z;
171. (x → y) ∼ (x → (y → z)); 172. (x ∼ y)(y ∼ z) → (x ∼ z);
173. (x ∼ y)(y ∼ z)(z ∼ x).
ðÒÉ×ÅÓÔÉ Ë ËÏÎßÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÅ (ëîæ):
174. x ∨ yz; 175. xy ∨ yz ∨ z; 176. x ∨ yz ∨ x y z; 177. x → yz;
178. x → yzv; 179. x ∼ yz; 180. xy ∼ x y; 181. x ∼ y ∼ z;
182. x ∨ y ∼ x ∼ z; 183. x ∨∨ (y ∨∨ z).
ðÒÉ×ÅÄÅÎÉÅÍ Ë ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÅ ×ÙÑÓÎÉÔØ, ËÁËÉÅ ÉÚ ÆÏÒÍÕÌ Ñ×ÌÑÀÔÓÑ
ÔÏÖÄÅÓÔ×ÅÎÎÏ ÉÓÔÉÎÎÙÍÉ, ÔÏÖÄÅÓÔ×ÅÎÎÏ ÌÏÖÎÙÍÉ, ×ÙÐÏÌÎÉÍÙÍÉ:
184. xy → x ∨ y; 185. x ∨ y → xy; 186. xy → xy;
187. (x → y)x → x ∨ y ∨ z; 188. x ∨ y → x ∨ z; 189. (x → y) → (y → x);
190. (x → z) → ((y → z) → ((x ∨ y) → z)); 191. xyz ∨ xyz ∨ xyz ∨ x y z;
192. xy ∨ x y ∼ (x ∨ y)(x ∨ y).
äÌÑ ËÁÖÄÏÊ ÉÚ ÓÌÅÄÕÀÝÉÈ ÆÏÒÍÕÌ ÎÁÊÔÉ ÄÉÚßÀÎËÔÉ×ÎÏÅ É ËÏÎßÀÎËÔÉ×-
ÎÏÅ ÒÁÚÌÏÖÅÎÉÅ:
193. x ∨ y; 194. xy; 195. x → y; 196. x ∼ y; 197. x ∨∨ y;
198. x → (y → x); 199. xy(x → y); 200. x ∨ y → z; 201. xy → z.
ðÒÉ×ÅÓÔÉ Ë ÓÏ×ÅÒÛÅÎÎÏÊ äîæ (óäîæ) ÓÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ:
202. x ∨ y; 203. (x → y) → x; 204. x → (y → x); 205. x → (y → z);
206. (x → y)(y → z) → (x → z); 207. (x → y)(y → z)(z → x);
208. (x ∨ y)(y ∨ z)(z ∼ x); 209. (x → y)(y → z)(z → v).
ðÒÉ×ÅÓÔÉ Ë ÓÏ×ÅÒÛÅÎÎÏÊ ëîæ (óëîæ) ÓÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ:
210. (x → y) → x ∨ y; 211. xx · y; 212. xy(x → y); 213. x → yz;
218 úÁÄÁÞÉ
214. xyz; 215. (x ∨ y)(y → z)(z ∼ x); 216. x ∨ y → (x → z);
217. ((x → y) ∼ (y → x))z; 218. x ∨ y ∨ z → (x ∨ y)z; 219. xy → zv.
ðÒÉ×ÅÄÅÎÉÅÍ Ë ÓÏ×ÅÒÛÅÎÎÙÍ ÎÏÒÍÁÌØÎÙÍ ÆÏÒÍÁÍ ÄÏËÁÚÁÔØ ÎÅÒÁ×ÎÏ-
ÓÉÌØÎÏÓÔØ ÓÌÅÄÕÀÝÉÈ ÆÏÒÍÕÌ:
220. x ∨ y É x → y; 221. x → y É x ∼ y; 222. x ∨ y É x ⊕ y;
223. x → (y → z) É (x → y) → z; 224. xy ∨ z É x(y ∨ z); 225. (x → y) ∨ z
É x ∨ y → z; 226. (x → y)z É x → yz; 227. (x → y) ∼ z É (x ∼ y) → z;
228. (x ∨ y) ∼ z É (x ∼ y) ∨ z; 229. xy ∼ z É (x ∼ y)z.
óÌÅÄÕÀÝÉÅ ÆÏÒÍÕÌÙ ÒÁÚÌÏÖÉÔØ ÐÏ ÐÅÒÅÍÅÎÎÙÍ x, y, z:
230. xy; 231. x ∨ y; 232. x; 233. (x ∨ y)(
x ∨ y); 234. xy ∨ xy ∨ x y.
ïÐÒÅÄÅÌÅÎÉÅ. æÏÒÍÕÌÁ F ÎÁÚÙ×ÁÅÔÓÑ ÌÏÇÉÞÅÓËÉÍ ÓÌÅÄÓÔ×ÉÅÍ ÆÏÒÍÕÌ
(ÐÏÓÙÌÏË) f
1
, . . . , f
n
, ÅÓÌÉ f
1
· f
2
· . . . · f
n
→ F ≡ 1.
÷ÙÑÓÎÉÔØ, Ñ×ÌÑÅÔÓÑ ÌÉ ÐÅÒ×ÁÑ ÆÏÒÍÕÌÁ ÌÏÇÉÞÅÓËÉÍ ÓÌÅÄÓÔ×ÉÅÍ ÏÓÔÁÌØ-
ÎÙÈ:
235. y; x → y, x; 236. x; x → y, y; 237. x; x → y, y; 238. y; x → y,
x; 239. y; x ∨ y, x; 240. y; x ∨∨ y, x; 241. x → z; x → y, y → z;
242. x ∨ y → z; x → z, y → z; 243. z → x; x → y, y → z; 244. x ∨ y;
x → y, y → x, x ∨ y; 245. x; x ∼ y, y ∨ z, z; 246. z; x → y, y ∨ z, x;
247. y ∨ z; x ∨ z, y → x · z, x; 248. z → y; x → y, x, z; 249. z → x;
x → y, xy, z → y; 250. x ∨ t; x → y, y → z, x ∨ z → yt; 251. xt; x → z,
y ∨ z, z → y ∨ t, z ∨ t.
îÁÊÔÉ ×ÓÅ (Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÒÁ×ÎÏÓÉÌØÎÏÓÔÉ) ÌÏÇÉÞÅÓËÉÅ ÓÌÅÄÓÔ×ÉÑ ÉÚ ÐÏ-
ÓÙÌÏË:
252. x, x → y; 253. x, x ∼ y; 254. x, y, x ∨ y; 255. x → (y → z),
y → z; 256. x → (y → z), y → z; 257. x → y, y → z; 258. x ∨ y,
y ∨ z, z ∨ x; 259. x, x ∨ y, x ∨ y ∨ z; 260. x → (y → (z → t)),
x → (y → z); 261. x → (y → z), y → (z → t).
îÁÊÔÉ ×ÓÅ (Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÒÁ×ÎÏÓÉÌØÎÏÓÔÉ) ÐÏÓÙÌËÉ, ÌÏÇÉÞÅÓËÉÍ ÓÌÅÄ-
ÓÔ×ÉÅÍ ËÏÔÏÒÙÈ Ñ×ÌÑÀÔÓÑ ÆÏÒÍÕÌÙ:
262. x · y; 263. x ∼ y; 264. x ∨ y; 265. x → y; 266. x ∨ y → x · y;
267. x · y · z; 268. (x ∨ y) · z; 269. (x → y) · z; 270. x → y · z;
271. x → (y → z).
ïÐÒÅÄÅÌÅÎÉÅ. ÷Ù×ÏÄ f
1
, . . . , f
n
⇒ F ÎÁÚÙ×ÁÅÔÓÑ ÐÒÁ×ÉÌØÎÙÍ, ÅÓÌÉ ÆÏÒ-
ÍÕÌÁ F Ñ×ÌÑÅÔÓÑ ÌÏÇÉÞÅÓËÉÍ ÓÌÅÄÓÔ×ÉÅÍ ÆÏÒÍÕÌ f
1
, . . . , f
n
.
äÏËÁÖÉÔÅ ÐÒÁ×ÉÌØÎÏÓÔØ ×Ù×ÏÄÏ×:
272. a → b, a ⇒ b; 273. a → b, b ⇒ a; 274. a∨b, a ⇒ b; 275. a∨ ∨b, a ⇒ b;
276. a ∨∨ b, a ⇒ b; 277. a → b, b → c ⇒ a → c; 278. a ∨ b, a → b ⇒ b;
§4. òÅÌÅÊÎÏ-ËÏÎÔÁËÔÎÙÅ ÓÈÅÍÙ É ÓÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×219
279. a → b, b → c, c ⇒ a; 280. a → b, b → c, a ⇒ b; 281. a∨ ∨b, a → b ⇒ b;
282. a ∨∨ b, b ∨∨ c ⇒ a → c; 283. a → b, b → c, c → a ⇒ a → bc.
÷ÙÑÓÎÉÔØ, ÐÒÁ×ÉÌØÎÙ ÌÉ ÓÌÅÄÕÀÝÉÅ ×Ù×ÏÄÙ:
284. a → b, b ⇒ a; 285. a → b, a ⇒ b; 286. a → b, a → b ⇒ a ∼ b;
287. a → b, b → a ⇒ a ∼ b; 288. a → b, a ∨ b ⇒ a; 289. a → b,
b → a, a ∨ b ⇒ a · b; 290. a → (b → c), (a → b) → c ⇒ b → c;
291. a → (b → c), (a → b) → c ⇒ a → c; 292. a → bc, b → ac,
c → ab, a∨b∨c ⇒ a·b·c; 293. a∨b → c, a∨c → b, b∨c → a, a∨b∨c ⇒ a·b·c.
§4. òÅÌÅÊÎÏ-ËÏÎÔÁËÔÎÙÅ ÓÈÅÍÙ É ÓÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØ-
ÎÙÈ ÜÌÅÍÅÎÔÏ×
4.1. úÁÄÁÞÉ ÓÉÎÔÅÚÁ
ðÒÉÍÅÒ 10. ðÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÍÁÛÉÎÙ ÜËÚÁÍÅÎÁÔÏÒÁ, × ËÏÔÏÒÏÊ ÓÔÕÄÅÎÔÕ
ÐÒÅÄÌÁÇÁÅÔÓÑ ×ÏÐÒÏÓ É ÞÅÔÙÒÅ ×ÁÒÉÁÎÔÁ ÏÔ×ÅÔÁ ÎÁ ÎÅÇÏ, ÔÏÌØËÏ ÏÄÉÎ ÉÚ ËÏ-
ÔÏÒÙÈ ÐÒÁ×ÉÌØÎÙÊ. ÷ ÓÌÕÞÁÅ, ËÏÇÄÁ ÏÔ×ÅÔ ÐÒÁ×ÉÌØÎÙÊ, ÄÏÌÖÎÏ ÚÁÖÉÇÁÔØÓÑ
ÔÁÂÌÏ ¤ÏÔ×ÅÔ ×ÅÒÅÎ¥.
òÅÛÅÎÉÅ. úÁËÏÄÉÒÕÅÍ ÎÏÍÅÒÁ ÏÔ×ÅÔÏ× Ä×ÕÈÒÁÚÒÑÄÎÙÍÉ Ä×ÏÉÞÎÙÍÉ
ÞÉÓÌÁÍÉ 00, 01, 10, 11. óÔÕÄÅÎÔ
É ÍÁÛÉÎÁ ÄÏÌÖÎÙ ÇÅÎÅÒÉÒÏ×ÁÔØ
Ä×ÕÈÒÁÚÒÑÄÎÙÅ ÕÐÒÁ×ÌÑÀÝÉÅ ÓÉÇ-
ÎÁÌÙ. æÕÎËÃÉÑ ÐÒÏ×ÏÄÉÍÏÓÔÉ ÓÈÅ-
ÍÙ ÚÁÄÁ¾ÔÓÑ ÔÁÂÌÉÃÅÊ
C
1
C
2
M
1
M
2
f
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1
220 úÁÄÁÞÉ
÷ÙÐÉÛÅÍ É ÕÐÒÏÓÔÉÍ óäîæ ÆÕÎËÃÉÉ f:
f ≡ C
1
C
2
M
1
M
2
∨ C
1
C
2
M
1
M
2
∨ C
1
C
2
M
1
M
2
∨ C
1
C
2
M
1
M
2
≡
≡ C
1
C
2
M
2
∨ C
2
M
2
M
1
∨ C
1
C
2
M
2
∨ C
2
M
2
M
1
≡
≡
C
2
M
2
∨ C
2
M
2
C
1
M
1
∨ C
1
M
1
.
óÈÅÍÁ ÉÍÅÅÔ ×ÉÄ:
Á)
ÉÌÉ
Â)
óÈÅÍÁ Á) ÐÒÅÄÐÏÞÔÉÔÅÌØÎÅÊ ÓÈÅÍÙ Â).
4.2. áÎÁÌÉÚ ÓÈÅÍ
ðÒÉÍÅÒ 11. îÁÊÔÉ ÆÕÎËÃÉÀ ÐÒÏ×ÏÄÉÍÏÓÔÉ ÓÈÅÍÙ
òÅÛÅÎÉÅ. ðÒÉ ÒÅÛÅÎÉÉ ÚÁÄÁÞ ÔÁËÏÇÏ ÔÉÐÁ ÓÌÅÄÕÅÔ ÐÏÍÎÉÔØ, ÞÔÏ ÐÏÓÌÅ-
ÄÏ×ÁÔÅÌØÎÏÅ ÓÏÅÄÉÎÅÎÉÅ ÒÅÌÅ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ËÏÎßÀÎËÃÉÉ, Á ÐÁÒÁÌÌÅÌØÎÏÅ ¡
ÄÉÚßÀÎËÃÉÉ. ðÏÌÅÚÎÙÍ Ñ×ÌÑÅÔÓÑ ÕÍÅÎÉÅ ÐÒÅÏÂÒÁÚÏ×ÁÔØ ÔÏÐÏÌÏÇÉÀ ÓÈÅÍÙ
ÔÁË, ÞÔÏÂÙ Ñ×ÎÏ ÂÙÌÉ ×ÉÄÎÙ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ É ÐÁÒÁÌÌÅÌØÎÙÅ ÕÞÁÓÔËÉ
ÓÈÅÍÙ. ðÒÅÏÂÒÁÚÕÅÍ ÔÏÐÏÌÏÇÉÀ ÓÈÅÍÙ (ÄÏÂÁ×ÌÅÎÎÙÅ ÕÞÁÓÔËÉ ÏÂÏÚÎÁÞÅÎÙ
ÐÕÎËÔÉÒÏÍ, ÕÄÁÌÑÅÍÙÅ ÕÞÁÓÔËÉ ÐÏÍÅÞÅÎÙ ¤×¥):