Математическая логика и теория алгоритмов. Самохин А.В. - 212 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

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

Рубрика: 

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);
212                                                                                           úÁÄÁÞÉ

1-Ñ ÓÈÅÍÁ:
                                                          ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
                         ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ             z             }|           {
 (x1 ∨ x3)(x2 ∨ x3)             ≡           x1 x2 ∨ x3 x2 ∨       | {z } ≡
                                                                  x1 x 3 ∨ x 3
                              ÚÁËÏÎ
                                                               ÚÁËÏÎ ÐÏÇÌÏÝÅÎÉÑ
                                                                             ÚÁËÏÎ
                                                          ≡   x1 x2 ∨ x3      ≡      x1   ∨ x2 ∨ x3 .
                                                                          ÄÅ íÏÒÇÁÎÁ

2-Ñ ÓÈÅÍÁ:
                            ÚÁËÏÎ                    ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
        x1 ∨ x 2 ∨ x 3      ≡         x1 · x2 ∨ x3          ≡         (x1 ∨ x3)(x2 ∨ x3).
                         ÄÅ íÏÒÇÁÎÁ                       ÚÁËÏÎ

3-Ñ ÓÈÅÍÁ:
                              ÄÉÓÔÒÉÂÕÔÉ×ÎÙÊ
      (x1 ∨ x2 )(x2 ∨ x3)             ≡         x1 x2 ∨ x2x2 ∨ x1 x3 ∨ x3 ≡ x1x2 ∨ x3 ;
                                    ÚÁËÏÎ
                                                  ÚÁËÏÎ
                              x1 ∨ x 2 ∨ x 3         ≡      x1 x2 ∨ x3.
                                               ÄÅ íÏÒÇÁÎÁ

   úÁÍÅÞÁÎÉÅ. óÌÅÄÕÅÔ ÉÍÅÔØ × ×ÉÄÕ, ÞÔÏ ÓÒÅÄÉ ÐÒÉÍÅÒÏ× ÎÁ ÄÏËÁÚÁÔÅÌØ-
ÓÔ×Ï ÒÁ×ÎÏÓÉÌØÎÏÓÔÉ ÆÏÒÍÕÌ ÅÓÔØ ÐÒÉÍÅÒÙ Ó ÏÔÒÉÃÁÔÅÌØÎÙÍ ÏÔ×ÅÔÏÍ. ÷
ÜÔÏÍ ÓÌÕÞÁÅ ÎÉ ÏÄÎÁ ÉÚ ÓÈÅÍ ÎÅ ÐÒÉ×ÏÄÉÔ Ë ÐÏÌÕÞÅÎÉÀ ÏÔ×ÅÔÁ. ïÄÎÁËÏ,
ÎÅÕÄÁÞÁ ÐÒÉ ÉÓÐÏÌØÚÏ×ÁÎÉÉ ÓÈÅÍ 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);

Страницы