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

UptoLike

ВУЗ: 

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

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

Рубрика: 

60 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
ðÒÉÍÅÒ. òÁÓÓÍÏÔÒÉÍ ÆÏÒÍÕÌÕ (p∧(q ∧¬r)). ïÎÁ ÉÓÔÉÎÎÁ × ÅÄÉÎÓÔ×ÅÎÎÏÍ
ÓÌÕÞÁÅ ¡ ËÏÇÄÁ p É q ÉÓÔÉÎÎÙ, Á r ÌÏÖÎÏ (ÓÍ. ÔÁÂÌÉÃÕ 3).
p q r ¬r (q ∧ ¬r) (p ∧ (q ∧ ¬r))
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 1 1 0
0 1 1 0 0 0
1 0 0 1 0 0
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 0 0 0
ðÒÉÌÏÖÅÎÉÅ 3. ôÁÂÌÉÃÁ ÉÓÔÉÎÎÏÓÔÉ ÄÌÑ (p ∧ (q ∧ ¬r)).
îÅËÏÔÏÒÙÅ ÆÏÒÍÕÌÙ ×ÙÒÁÖÁÀÔ ÌÏÇÉÞÅÓËÉÅ ÚÁËÏÎÙ ¡ ÓÏÓÔÁ×ÎÙÅ ×ÙÓËÁ-
ÚÙ×ÁÎÉÑ, ÉÓÔÉÎÎÙÅ ÎÅÚÁ×ÉÓÉÍÏ ÏÔ ÓÍÙÓÌÁ ÉÈ ÞÁÓÔÅÊ. ôÁËÉÅ ÆÏÒÍÕÌÙ (ÉÓ-
ÔÉÎÎÙÅ ÐÒÉ ×ÓÅÈ ÚÎÁÞÅÎÉÑÈ ×ÈÏÄÑÝÉÈ × ÎÉÈ ÐÅÒÅÍÅÎÎÙÈ) ÎÁÚÙ×ÁÀÔ ÔÁ×ÔÏ-
ÌÏÇÉÑÍÉ.
ðÒÉÍÅÒ. æÏÒÍÕÌÁ ((p ∧ q) → p) Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ (ÜÔÏ ÍÏÖÎÏ ÐÒÏ×Å-
ÒÉÔØ, ÎÁÐÒÉÍÅÒ, ÓÏÓÔÁ×É× ÔÁÂÌÉÃÕ). ïÎÁ ×ÙÒÁÖÁÅÔ ÔÁËÏÊ ÌÏÇÉÞÅÓËÉÊ ÚÁËÏÎ:
ÉÚ ËÏÎßÀÎËÃÉÉ ÕÔ×ÅÒÖÄÅÎÉÊ ÓÌÅÄÕÅÔ ÐÅÒ×ÏÅ ÉÚ ÎÉÈ.
úÁÄÁÞÁ 102. ëÁË ×ÙÇÌÑÄÉÔ ÓÉÍÍÅÔÒÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÌÑ ÄÉÚßÀÎË-
ÃÉÉ É ËÁËÁÑ ÆÏÒÍÕÌÁ ÅÇÏ ×ÙÒÁÖÁÅÔ?
ä×Å ÆÏÒÍÕÌÙ ÎÁÚÙ×ÁÀÔ ÜË×É×ÁÌÅÎÔÎÙÍÉ, ÅÓÌÉ ÏÎÉ ÉÓÔÉÎÎÙ ÐÒÉ ÏÄÎÉÈ
É ÔÅÈ ÖÅ ÚÎÁÞÅÎÉÑÈ ÐÅÒÅÍÅÎÎÙÈ (ÄÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÅÓÌÉ ÏÎÉ ÚÁÄÁÀÔ ÏÄÎÕ
É ÔÕ ÖÅ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ). îÁÐÒÉÍÅÒ, ÆÏÒÍÕÌÁ (p ∧ (p → q)) ÉÓÔÉÎÎÁ ÌÉÛØ
ÐÒÉ p = q = é, É ÐÏÔÏÍÕ ÜË×É×ÁÌÅÎÔÎÁ ÆÏÒÍÕÌÅ (p ∧ q).
òÁÓÓÍÏÔÒÉÍ ÆÏÒÍÕÌÕ ((p ∧ q) ∨ q). ïÎÁ ÉÓÔÉÎÎÁ, ÅÓÌÉ ÐÅÒÅÍÅÎÎÁÑ q ÉÓ-
ÔÉÎÎÁ, É ÌÏÖÎÁ, ÅÓÌÉ ÐÅÒÅÍÅÎÎÁÑ q ÌÏÖÎÁ. èÏÔÅÌÏÓØ ÂÙ ÓËÁÚÁÔØ, ÞÔÏ ÏÎÁ
ÜË×É×ÁÌÅÎÔÎÁ ÆÏÒÍÕÌÅ q, ÎÏ ÔÕÔ ÅÓÔØ ÆÏÒÍÁÌØÎÁÑ ÔÒÕÄÎÏÓÔØ: ÏÎÁ ÓÏÄÅÒ-
ÖÉÔ Ä×Å ÐÅÒÅÍÅÎÎÙÅ É ÐÏÔÏÍÕ ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÔ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ× (ÔÉÐÁ
B × B → B), × ÔÏ ×ÒÅÍÑ ËÁË ÆÏÒÍÕÌÁ q ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎ-
ÔÁ. íÙ ÎÅ ÂÕÄÅÍ ÏÂÒÁÝÁÔØ ÎÁ ÜÔÏ ×ÎÉÍÁÎÉÑ É ÂÕÄÅÍ ÓÞÉÔÁÔØ ÜÔÉ ÆÏÒÍÕÌÙ
ÜË×É×ÁÌÅÎÔÎÙÍÉ. ÷ÏÏÂÝÅ, ÅÓÌÉ ÅÓÔØ ÓÐÉÓÏË ÐÅÒÅÍÅÎÎÙÈ p
1
, . . . , p
n
, ÓÏÄÅÒ-
ÖÁÝÉÊ ×ÓÅ ÐÅÒÅÍÅÎÎÙÅ ÎÅËÏÔÏÒÏÊ ÆÏÒÍÕÌÙ ϕ (É, ×ÏÚÍÏÖÎÏ, Åݾ ËÁËÉÅ-ÔÏ
ÐÅÒÅÍÅÎÎÙÅ), ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÔ n ÁÒÇÕ-
ÍÅÎÔÏ×, ×ÏÚÍÏÖÎÏ, ÎÁ ÄÅÌÅ ÚÁ×ÉÓÑÝÕÀ ÎÅ ÏÔ ×ÓÅÈ ÁÒÇÕÍÅÎÔÏ× (ÐÏÓÔÏÑÎÎÕÀ
ÐÏ ÎÅËÏÔÏÒÙÍ ÁÒÇÕÍÅÎÔÁÍ)
60                                       çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

   ðÒÉÍÅÒ. òÁÓÓÍÏÔÒÉÍ ÆÏÒÍÕÌÕ (p ∧ (q ∧ ¬r)). ïÎÁ ÉÓÔÉÎÎÁ × ÅÄÉÎÓÔ×ÅÎÎÏÍ
ÓÌÕÞÁÅ ¡ ËÏÇÄÁ p É q ÉÓÔÉÎÎÙ, Á r ÌÏÖÎÏ (ÓÍ. ÔÁÂÌÉÃÕ 3).
                   p   q   r ¬r (q ∧ ¬r) (p ∧ (q ∧ ¬r))
                   0   0   0 1      0           0
                   0   0   1 0      0           0
                   0   1   0 1      1           0
                   0   1   1 0      0           0
                   1   0   0 1      0           0
                   1   0   1 0      0           0
                   1   1   0 1      1           1
                   1   1   1 0      0           0

        ðÒÉÌÏÖÅÎÉÅ 3. ôÁÂÌÉÃÁ ÉÓÔÉÎÎÏÓÔÉ ÄÌÑ (p ∧ (q ∧ ¬r)).

   îÅËÏÔÏÒÙÅ ÆÏÒÍÕÌÙ ×ÙÒÁÖÁÀÔ ÌÏÇÉÞÅÓËÉÅ ÚÁËÏÎÙ ¡ ÓÏÓÔÁ×ÎÙÅ ×ÙÓËÁ-
ÚÙ×ÁÎÉÑ, ÉÓÔÉÎÎÙÅ ÎÅÚÁ×ÉÓÉÍÏ ÏÔ ÓÍÙÓÌÁ ÉÈ ÞÁÓÔÅÊ. ôÁËÉÅ ÆÏÒÍÕÌÙ (ÉÓ-
ÔÉÎÎÙÅ ÐÒÉ ×ÓÅÈ ÚÎÁÞÅÎÉÑÈ ×ÈÏÄÑÝÉÈ × ÎÉÈ ÐÅÒÅÍÅÎÎÙÈ) ÎÁÚÙ×ÁÀÔ ÔÁ×ÔÏ-
ÌÏÇÉÑÍÉ.
   ðÒÉÍÅÒ. æÏÒÍÕÌÁ ((p ∧ q) → p) Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ (ÜÔÏ ÍÏÖÎÏ ÐÒÏ×Å-
ÒÉÔØ, ÎÁÐÒÉÍÅÒ, ÓÏÓÔÁ×É× ÔÁÂÌÉÃÕ). ïÎÁ ×ÙÒÁÖÁÅÔ ÔÁËÏÊ ÌÏÇÉÞÅÓËÉÊ ÚÁËÏÎ:
ÉÚ ËÏÎßÀÎËÃÉÉ ÕÔ×ÅÒÖÄÅÎÉÊ ÓÌÅÄÕÅÔ ÐÅÒ×ÏÅ ÉÚ ÎÉÈ.
  úÁÄÁÞÁ 102. ëÁË ×ÙÇÌÑÄÉÔ ÓÉÍÍÅÔÒÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÌÑ ÄÉÚßÀÎË-
ÃÉÉ É ËÁËÁÑ ÆÏÒÍÕÌÁ ÅÇÏ ×ÙÒÁÖÁÅÔ?
   ä×Å ÆÏÒÍÕÌÙ ÎÁÚÙ×ÁÀÔ ÜË×É×ÁÌÅÎÔÎÙÍÉ, ÅÓÌÉ ÏÎÉ ÉÓÔÉÎÎÙ ÐÒÉ ÏÄÎÉÈ
É ÔÅÈ ÖÅ ÚÎÁÞÅÎÉÑÈ ÐÅÒÅÍÅÎÎÙÈ (ÄÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÅÓÌÉ ÏÎÉ ÚÁÄÁÀÔ ÏÄÎÕ
É ÔÕ ÖÅ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ). îÁÐÒÉÍÅÒ, ÆÏÒÍÕÌÁ (p ∧ (p → q)) ÉÓÔÉÎÎÁ ÌÉÛØ
ÐÒÉ p = q = é, É ÐÏÔÏÍÕ ÜË×É×ÁÌÅÎÔÎÁ ÆÏÒÍÕÌÅ (p ∧ q).
   òÁÓÓÍÏÔÒÉÍ ÆÏÒÍÕÌÕ ((p ∧ q) ∨ q). ïÎÁ ÉÓÔÉÎÎÁ, ÅÓÌÉ ÐÅÒÅÍÅÎÎÁÑ q ÉÓ-
ÔÉÎÎÁ, É ÌÏÖÎÁ, ÅÓÌÉ ÐÅÒÅÍÅÎÎÁÑ q ÌÏÖÎÁ. èÏÔÅÌÏÓØ ÂÙ ÓËÁÚÁÔØ, ÞÔÏ ÏÎÁ
ÜË×É×ÁÌÅÎÔÎÁ ÆÏÒÍÕÌÅ q, ÎÏ ÔÕÔ ÅÓÔØ ÆÏÒÍÁÌØÎÁÑ ÔÒÕÄÎÏÓÔØ: ÏÎÁ ÓÏÄÅÒ-
ÖÉÔ Ä×Å ÐÅÒÅÍÅÎÎÙÅ É ÐÏÔÏÍÕ ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÔ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ× (ÔÉÐÁ
B × B → B), × ÔÏ ×ÒÅÍÑ ËÁË ÆÏÒÍÕÌÁ q ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎ-
ÔÁ. íÙ ÎÅ ÂÕÄÅÍ ÏÂÒÁÝÁÔØ ÎÁ ÜÔÏ ×ÎÉÍÁÎÉÑ É ÂÕÄÅÍ ÓÞÉÔÁÔØ ÜÔÉ ÆÏÒÍÕÌÙ
ÜË×É×ÁÌÅÎÔÎÙÍÉ. ÷ÏÏÂÝÅ, ÅÓÌÉ ÅÓÔØ ÓÐÉÓÏË ÐÅÒÅÍÅÎÎÙÈ p1, . . . , pn, ÓÏÄÅÒ-
ÖÁÝÉÊ ×ÓÅ ÐÅÒÅÍÅÎÎÙÅ ÎÅËÏÔÏÒÏÊ ÆÏÒÍÕÌÙ ϕ (É, ×ÏÚÍÏÖÎÏ, Åݾ ËÁËÉÅ-ÔÏ
ÐÅÒÅÍÅÎÎÙÅ), ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ ÚÁÄÁ¾Ô ÆÕÎËÃÉÀ ÏÔ n ÁÒÇÕ-
ÍÅÎÔÏ×, ×ÏÚÍÏÖÎÏ, ÎÁ ÄÅÌÅ ÚÁ×ÉÓÑÝÕÀ ÎÅ ÏÔ ×ÓÅÈ ÁÒÇÕÍÅÎÔÏ× (ÐÏÓÔÏÑÎÎÕÀ
ÐÏ ÎÅËÏÔÏÒÙÍ ÁÒÇÕÍÅÎÔÁÍ)

Страницы