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

UptoLike

ВУЗ: 

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

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

Рубрика: 

86 çÌÁ×Á IV. éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ
÷ÏÔ ÐÒÉÍÅÒ ×Ù×ÏÄÁ (× Î¾Í ÐÅÒ×ÁÑ ÆÏÒÍÕÌÁ Ñ×ÌÑÅÔÓÑ ÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ
ÓÈÅÍÙ (1), ×ÔÏÒÁÑ ¡ ÓÈÅÍÙ (2), Á ÐÏÓÌÅÄÎÑÑ ÐÏÌÕÞÁÅÔÓÑ ÉÚ Ä×ÕÈ ÐÒÅÄÙÄÕÝÉÈ
ÐÏ ÐÒÁ×ÉÌÕ modus ponens):
(p → (q → p)),
(p → (q → p)) → ((p → q) → (p → p)),
((p → q) → (p → p)).
ðÒÏÐÏÚÉÃÉÏÎÁÌØÎÁÑ ÆÏÒÍÕÌÁ A ÎÁÚÙ×ÁÅÔÓÑ ×Ù×ÏÄÉÍÏÊ × ÉÓÞÉÓÌÅÎÉÉ ×Ù-
ÓËÁÚÙ×ÁÎÉÊ, ÉÌÉ ÔÅÏÒÅÍÏÊ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ×Ù-
×ÏÄ, × ËÏÔÏÒÏÍ ÐÏÓÌÅÄÎÑÑ ÆÏÒÍÕÌÁ ÒÁ×ÎÁ A. ôÁËÏÊ ×Ù×ÏÄ ÎÁÚÙ×ÁÀÔ ×Ù×ÏÄÏÍ
ÆÏÒÍÕÌÙ A. (÷ ÐÒÉÎÃÉÐÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ É ÎÅ ÔÒÅÂÏ×ÁÔØ, ÞÔÏÂÙ ÆÏÒÍÕÌÁ A
ÂÙÌÁ ÐÏÓÌÅÄÎÅÊ ¡ ×ÓÅ ÄÁÌØÎÅÊÛÉÅ ÆÏÒÍÕÌÙ ÍÏÖÎÏ ÐÒÏÓÔÏ ×ÙÞÅÒËÎÕÔØ.)
ëÁË ÍÙ ÕÖÅ ÇÏ×ÏÒÉÌÉ, × ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ ×Ù×ÏÄÑÔÓÑ ×ÓÅ ÔÁ×-
ÔÏÌÏÇÉÉ É ÔÏÌØËÏ ÏÎÉ. ïÂÙÞÎÏ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÒÁÚÂÉ×ÁÀÔ ÎÁ Ä×Å ÞÁÓÔÉ:
ÐÒÏÓÔÕÀ É ÓÌÏÖÎÕÀ. îÁÞÎ¾Í Ó ÐÒÏÓÔÏÊ:
ôÅÏÒÅÍÁ 32 (Ï ËÏÒÒÅËÔÎÏÓÔÉ é÷). ÷ÓÑËÁÑ ÔÅÏÒÅÍÁ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁ-
ÚÙ×ÁÎÉÊ ÅÓÔØ ÔÁ×ÔÏÌÏÇÉÑ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. îÅÓÌÏÖÎÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏ ×ÓÅ ÁËÓÉÏÍÙ ¡ ÔÁ×ÔÏÌÏÇÉÉ.
äÌÑ ÐÒÉÍÅÒÁ ÐÒÏÄÅÌÁÅÍ ÜÔÏ ÄÌÑ ÓÁÍÏÊ ÄÌÉÎÎÏÊ ÁËÓÉÏÍÙ (ÔÏÞÎÅÅ, ÓÈÅÍÙ
ÁËÓÉÏÍ) ¡ ÄÌÑ ×ÔÏÒÏÊ. ÷ ËÁËÏÍ ÓÌÕÞÁÅ ÆÏÒÍÕÌÁ
(A → (B → C)) → ((A → B) → (A → C))
(ÇÄÅ A, B, C ¡ ÎÅËÏÔÏÒÙÅ ÆÏÒÍÕÌÙ) ÍÏÇÌÁ ÂÙ ÂÙÔØ ÌÏÖÎÏÊ? äÌÑ ÜÔÏÇÏ
ÐÏÓÙÌËÁ A → (B → C) ÄÏÌÖÎÁ ÂÙÔØ ÉÓÔÉÎÎÏÊ, Á ÚÁËÌÀÞÅÎÉÅ (A → B) →
(A → C) ¡ ÌÏÖÎÙÍ. þÔÏÂÙ ÚÁËÌÀÞÅÎÉÅ ÂÙÌÏ ÌÏÖÎÙÍ, ÆÏÒÍÕÌÁ A → B
ÄÏÌÖÎÁ ÂÙÔØ ÉÓÔÉÎÎÏÊ, Á ÆÏÒÍÕÌÁ A → C ¡ ÌÏÖÎÏÊ. ðÏÓÌÅÄÎÅÅ ÏÚÎÁÞÁÅÔ,
ÞÔÏ A ÉÓÔÉÎÎÁ, Á C ÌÏÖÎÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÍÙ ÚÎÁÅÍ, ÞÔÏ A, (A → B) É
(A → (B → C)) ÉÓÔÉÎÎÙ. ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ B É (B → C) ÉÓÔÉÎÎÙ,
É ÐÏÔÏÍÕ C ÉÓÔÉÎÎÁ ¡ ÐÒÏÔÉ×ÏÒÅÞÉÅ. úÎÁÞÉÔ, ÎÁÛÁ ÆÏÒÍÕÌÁ ÎÅ ÂÙ×ÁÅÔ
ÌÏÖÎÏÊ.
ëÏÒÒÅËÔÎÏÓÔØ ÐÒÁ×ÉÌÁ MP ÔÁËÖÅ ÏÞÅ×ÉÄÎÁ: ÅÓÌÉ ÆÏÒÍÕÌÙ (A → B) É A
×ÓÅÇÄÁ ÉÓÔÉÎÎÙ, ÔÏ ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ ÉÍÐÌÉËÁÃÉÉ ÆÏÒÍÕÌÁ B ÔÁËÖÅ ×ÓÅÇÄÁ
ÉÓÔÉÎÎÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ×ÓÅ ÆÏÒÍÕÌÙ, ×ÈÏÄÑÝÉÅ × ×Ù×ÏÄÙ (×ÓÅ ÔÅÏÒÅÍÙ)
Ñ×ÌÑÀÔÓÑ ÔÁ×ÔÏÌÏÇÉÑÍÉ.
çÏÒÁÚÄÏ ÓÌÏÖÎÅÅ ÄÏËÁÚÁÔØ ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ.
ôÅÏÒÅÍÁ 33 (Ï ÐÏÌÎÏÔÅ é÷). ÷ÓÑËÁÑ ÔÁ×ÔÏÌÏÇÉÑ ÅÓÔØ ÔÅÏÒÅÍÁ ÉÓÞÉ-
ÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ.
86                                  çÌÁ×Á IV. éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ

   ÷ÏÔ ÐÒÉÍÅÒ ×Ù×ÏÄÁ (× Î¾Í ÐÅÒ×ÁÑ ÆÏÒÍÕÌÁ Ñ×ÌÑÅÔÓÑ ÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ
ÓÈÅÍÙ (1), ×ÔÏÒÁÑ ¡ ÓÈÅÍÙ (2), Á ÐÏÓÌÅÄÎÑÑ ÐÏÌÕÞÁÅÔÓÑ ÉÚ Ä×ÕÈ ÐÒÅÄÙÄÕÝÉÈ
ÐÏ ÐÒÁ×ÉÌÕ modus ponens):
                   (p → (q → p)),
                   (p → (q → p)) → ((p → q) → (p → p)),
                   ((p → q) → (p → p)).
   ðÒÏÐÏÚÉÃÉÏÎÁÌØÎÁÑ ÆÏÒÍÕÌÁ A ÎÁÚÙ×ÁÅÔÓÑ ×Ù×ÏÄÉÍÏÊ × ÉÓÞÉÓÌÅÎÉÉ ×Ù-
ÓËÁÚÙ×ÁÎÉÊ, ÉÌÉ ÔÅÏÒÅÍÏÊ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ×Ù-
×ÏÄ, × ËÏÔÏÒÏÍ ÐÏÓÌÅÄÎÑÑ ÆÏÒÍÕÌÁ ÒÁ×ÎÁ A. ôÁËÏÊ ×Ù×ÏÄ ÎÁÚÙ×ÁÀÔ ×Ù×ÏÄÏÍ
ÆÏÒÍÕÌÙ A. (÷ ÐÒÉÎÃÉÐÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ É ÎÅ ÔÒÅÂÏ×ÁÔØ, ÞÔÏÂÙ ÆÏÒÍÕÌÁ A
ÂÙÌÁ ÐÏÓÌÅÄÎÅÊ ¡ ×ÓÅ ÄÁÌØÎÅÊÛÉÅ ÆÏÒÍÕÌÙ ÍÏÖÎÏ ÐÒÏÓÔÏ ×ÙÞÅÒËÎÕÔØ.)
   ëÁË ÍÙ ÕÖÅ ÇÏ×ÏÒÉÌÉ, × ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ ×Ù×ÏÄÑÔÓÑ ×ÓÅ ÔÁ×-
ÔÏÌÏÇÉÉ É ÔÏÌØËÏ ÏÎÉ. ïÂÙÞÎÏ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÒÁÚÂÉ×ÁÀÔ ÎÁ Ä×Å ÞÁÓÔÉ:
ÐÒÏÓÔÕÀ É ÓÌÏÖÎÕÀ. îÁÞÎ¾Í Ó ÐÒÏÓÔÏÊ:
  ôÅÏÒÅÍÁ 32 (Ï ËÏÒÒÅËÔÎÏÓÔÉ é÷). ÷ÓÑËÁÑ ÔÅÏÒÅÍÁ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁ-
ÚÙ×ÁÎÉÊ ÅÓÔØ ÔÁ×ÔÏÌÏÇÉÑ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. îÅÓÌÏÖÎÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏ ×ÓÅ ÁËÓÉÏÍÙ ¡ ÔÁ×ÔÏÌÏÇÉÉ.
äÌÑ ÐÒÉÍÅÒÁ ÐÒÏÄÅÌÁÅÍ ÜÔÏ ÄÌÑ ÓÁÍÏÊ ÄÌÉÎÎÏÊ ÁËÓÉÏÍÙ (ÔÏÞÎÅÅ, ÓÈÅÍÙ
ÁËÓÉÏÍ) ¡ ÄÌÑ ×ÔÏÒÏÊ. ÷ ËÁËÏÍ ÓÌÕÞÁÅ ÆÏÒÍÕÌÁ
                  (A → (B → C)) → ((A → B) → (A → C))
(ÇÄÅ A, B, C ¡ ÎÅËÏÔÏÒÙÅ ÆÏÒÍÕÌÙ) ÍÏÇÌÁ ÂÙ ÂÙÔØ ÌÏÖÎÏÊ? äÌÑ ÜÔÏÇÏ
ÐÏÓÙÌËÁ A → (B → C) ÄÏÌÖÎÁ ÂÙÔØ ÉÓÔÉÎÎÏÊ, Á ÚÁËÌÀÞÅÎÉÅ (A → B) →
(A → C) ¡ ÌÏÖÎÙÍ. þÔÏÂÙ ÚÁËÌÀÞÅÎÉÅ ÂÙÌÏ ÌÏÖÎÙÍ, ÆÏÒÍÕÌÁ A → B
ÄÏÌÖÎÁ ÂÙÔØ ÉÓÔÉÎÎÏÊ, Á ÆÏÒÍÕÌÁ A → C ¡ ÌÏÖÎÏÊ. ðÏÓÌÅÄÎÅÅ ÏÚÎÁÞÁÅÔ,
ÞÔÏ A ÉÓÔÉÎÎÁ, Á C ÌÏÖÎÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÍÙ ÚÎÁÅÍ, ÞÔÏ A, (A → B) É
(A → (B → C)) ÉÓÔÉÎÎÙ. ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ B É (B → C) ÉÓÔÉÎÎÙ,
É ÐÏÔÏÍÕ C ÉÓÔÉÎÎÁ ¡ ÐÒÏÔÉ×ÏÒÅÞÉÅ. úÎÁÞÉÔ, ÎÁÛÁ ÆÏÒÍÕÌÁ ÎÅ ÂÙ×ÁÅÔ
ÌÏÖÎÏÊ.
   ëÏÒÒÅËÔÎÏÓÔØ ÐÒÁ×ÉÌÁ MP ÔÁËÖÅ ÏÞÅ×ÉÄÎÁ: ÅÓÌÉ ÆÏÒÍÕÌÙ (A → B) É A
×ÓÅÇÄÁ ÉÓÔÉÎÎÙ, ÔÏ ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ ÉÍÐÌÉËÁÃÉÉ ÆÏÒÍÕÌÁ B ÔÁËÖÅ ×ÓÅÇÄÁ
ÉÓÔÉÎÎÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ×ÓÅ ÆÏÒÍÕÌÙ, ×ÈÏÄÑÝÉÅ × ×Ù×ÏÄÙ (×ÓÅ ÔÅÏÒÅÍÙ)
Ñ×ÌÑÀÔÓÑ ÔÁ×ÔÏÌÏÇÉÑÍÉ.
     çÏÒÁÚÄÏ ÓÌÏÖÎÅÅ ÄÏËÁÚÁÔØ ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ.
   ôÅÏÒÅÍÁ 33 (Ï ÐÏÌÎÏÔÅ é÷). ÷ÓÑËÁÑ ÔÁ×ÔÏÌÏÇÉÑ ÅÓÔØ ÔÅÏÒÅÍÁ ÉÓÞÉ-
ÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ.

Страницы