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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§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. ðÅÒÅÊÔÉ Ë ÆÏÒÍÕÌÅ Ó ÔÅÓÎÙÍÉ ÏÔÒÉÃÁÎÉÑÍÉ, ÔÏ ÅÓÔØ Ë ÆÏÒÍÕÌÅ, ×
ËÏÔÏÒÏÊ ÏÔÒÉÃÁÎÉÑ ÎÁÈÏÄÑÔÓÑ ÎÅ ×ÙÛÅ, ÞÅÍ ÎÁÄ ÐÅÒÅÍÅÎÎÙÍÉ.
§3. îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ: äîæ, ëîæ, óäîæ, óëîæ                                   215

  §3. îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ: äîæ, ëîæ, óäîæ, óëîæ
   îÏÒÍÁÌØÎÙÅ ÆÏÒÍÙ ÆÏÒÍÕÌ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÂÙ×ÁÀÔ Ä×ÕÈ ÔÉÐÏ×:
ÄÉÚßÀÎËÔÉ×ÎÙÅ É ËÏÎßÀÎËÔÉ×ÎÙÅ, × ËÁÖÄÏÍ ÉÚ ÜÔÉÈ ÔÉÐÏ× ×ÙÄÅÌÅÎ ËÌÁÓÓ
ÓÏ×ÅÒÛÅÎÎÙÈ ÆÏÒÍ.
   áÌÇÏÒÉÔÍ ÐÏÓÔÒÏÅÎÉÑ ÄÉÚßÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÙ (äîæ):
   1. ðÅÒÅÊÔÉ Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ.
   2. ðÅÒÅÊÔÉ Ë ÆÏÒÍÕÌÅ Ó ÔÅÓÎÙÍÉ ÏÔÒÉÃÁÎÉÑÍÉ, ÔÏ ÅÓÔØ Ë ÆÏÒÍÕÌÅ, ×
ËÏÔÏÒÏÊ ÏÔÒÉÃÁÎÉÑ ÎÁÈÏÄÑÔÓÑ ÎÅ ×ÙÛÅ, ÞÅÍ ÎÁÄ ÐÅÒÅÍÅÎÎÙÍÉ.
   3. òÁÓËÒÙÔØ ÓËÏÂËÉ.
   4. ðÏ×ÔÏÒÑÀÝÉÅÓÑ ÓÌÁÇÁÅÍÙÅ ×ÚÑÔØ ÐÏ ÏÄÎÏÍÕ ÒÁÚÕ.
   5. ðÒÉÍÅÎÉÔØ ÚÁËÏÎÙ ÐÏÇÌÏÝÅÎÉÑ É ÐÏÌÕÐÏÇÌÏÝÅÎÉÑ.
   ðÒÉÍÅÒ 6. îÁÊÔÉ äîæ ÆÏÒÍÕÌÙ
                           (x1 → x2x3 ) → (x1 ∼ x3).
  òÅÛÅÎÉÅ.
 (x1 → x2x3 ) → (x1 ∼ x3) ≡ (x1 → x2 x3 ) ∨ (x1x3 ∨ x1 x3 ) ≡
        ≡ x1 · (x2 ∨ x3) ∨ x1x3 ∨ x1 x3 ≡ x1x2 ∨ x1x3 ∨ x1x3 ∨ x1 x3 ≡
                                                        ≡ x1x2 ∨ x1x3 ∨ x1 x3.
  ëÏÎßÀÎËÔÉ×ÎÁÑ ÎÏÒÍÁÌØÎÁÑ ÆÏÒÍÁ (ëîæ) ¡ Ä×ÏÊÓÔ×ÅÎÎÏÅ ÄÌÑ äîæ ÐÏ-
ÎÑÔÉÅ, ÐÏÜÔÏÍÕ Å¾ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÐÏ ÓÈÅÍÅ:
                     f ≡ (f ∗)∗ ≡ (äîæ(f ∗))∗ ≡ ëîæ(f ).
  ðÒÉÍÅÒ 7. îÁÊÔÉ ëîæ ÆÏÒÍÕÌÙ
                             (x1 → x2x3 )(x1 ∼ x3).
  òÅÛÅÎÉÅ.
 (x1 → x2x3 )(x1 ∼ x3) ≡ (((x1 → x2 x3 )(x1 ∼ x3 ))∗)∗ ≡
                      ≡ (((x1 ∨ x2x3 )(x1x3 ∨ x1 x3 ))∗)∗ ≡
                  ≡ (x1 · (x2 ∨ x3 ) ∨ (x1 ∨ x3 ) · (x1 ∨ x3))∗ ≡
          ≡ (x1x2 ∨ x1 x3 ∨ x1x3 ∨ x1 x3)∗ ≡ (x1x2 ∨ x1 x3 ∨ x1 x3)∗ ≡
                                                ≡ (x1 ∨ x2)(x1 ∨ x3 )(x1 ∨ x3).
  óÏ×ÅÒÛÅÎÎÕÀ ÄÉÚßÀÎËÔÉ×ÎÕÀ ÎÏÒÍÁÌØÎÕÀ ÆÏÒÍÕ (óäîæ) ÍÏÖÎÏ ÐÏ-
ÓÔÒÏÉÔØ, ÉÓÐÏÌØÚÕÑ ÓÌÅÄÕÀÝÉÊ ÁÌÇÏÒÉÔÍ:
  1. ðÅÒÅÊÔÉ Ë ÂÕÌÅ×ÙÍ ÏÐÅÒÁÃÉÑÍ.
  2. ðÅÒÅÊÔÉ Ë ÆÏÒÍÕÌÅ Ó ÔÅÓÎÙÍÉ ÏÔÒÉÃÁÎÉÑÍÉ, ÔÏ ÅÓÔØ Ë ÆÏÒÍÕÌÅ, ×
ËÏÔÏÒÏÊ ÏÔÒÉÃÁÎÉÑ ÎÁÈÏÄÑÔÓÑ ÎÅ ×ÙÛÅ, ÞÅÍ ÎÁÄ ÐÅÒÅÍÅÎÎÙÍÉ.

Страницы