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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§1. éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ 89
úÁÄÁÞÁ 119. äÏÂÁ×ÉÍ Ë ÉÓÞÉÓÌÅÎÉÀ ×ÙÓËÁÚÙ×ÁÎÉÊ, ÐÏÍÉÍÏ ÐÒÁ×ÉÌÁ
modus ponens, Åݾ ÏÄÎÏ ÐÒÁ×ÉÌÏ, ÎÁÚÙ×ÁÅÍÏÅ ÐÒÁ×ÉÌÏÍ ÐÏÄÓÔÁÎÏ×ËÉ. ïÎÏ
ÒÁÚÒÅÛÁÅÔ ÚÁÍÅÎÉÔØ × ×Ù×ÅÄÅÎÎÏÊ ÆÏÒÍÕÌÅ ×ÓÅ ÐÅÒÅÍÅÎÎÙÅ ÎÁ ÐÒÏÉÚ×ÏÌØ-
ÎÙÅ ÆÏÒÍÕÌÙ (ÅÓÔÅÓÔ×ÅÎÎÏ, ×ÈÏÖÄÅÎÉÑ ÏÄÎÏÊ ÐÅÒÅÍÅÎÎÏÊ ÄÏÌÖÎÙ ÚÁÍÅ-
ÎÑÔØÓÑ ÎÁ ÏÄÎÕ É ÔÕ ÖÅ ÆÏÒÍÕÌÕ). ðÏËÁÖÉÔÅ, ÞÔÏ ÐÏÓÌÅ ÄÏÂÁ×ÌÅÎÉÑ
ÔÁËÏÇÏ ÐÒÁ×ÉÌÁ ËÌÁÓÓ ×Ù×ÏÄÉÍÙÈ ÆÏÒÍÕÌ ÎÅ ÉÚÍÅÎÉÔÓÑ, ÎÏ ÔÅÏÒÅÍÁ Ï
ÄÅÄÕËÃÉÉ ÐÅÒÅÓÔÁÎÅÔ ÂÙÔØ ×ÅÒÎÏÊ.
úÁÍÅÔÉÍ, ÞÔÏ ÍÙ ÐÏËÁ ÞÔÏ ÉÓÐÏÌØÚÏ×ÁÌÉ ÔÏÌØËÏ Ä×Å ÐÅÒ×ÙÅ ÁËÓÉÏÍÙ ÉÓ-
ÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ. ÷ÉÄÎÏ, ËÓÔÁÔÉ, ÞÔÏ ÏÎÉ ÓÐÅÃÉÁÌØÎÏ ÐÏÄÏÂÒÁÎÙ ÔÁË,
ÞÔÏÂÙ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ Ï ÄÅÄÕËÃÉÉ ÐÒÏÛÌÏ.
äÒÕÇÉÅ ÁËÓÉÏÍÙ ÏÐÉÓÙ×ÁÀÔ Ó×ÏÊÓÔ×Á ÌÏÇÉÞÅÓËÉÈ Ó×ÑÚÏË. áËÓÉÏÍÙ 3 É
4 ÇÏ×ÏÒÑÔ, ËÁËÉÅ ÓÌÅÄÓÔ×ÉÑ ÍÏÖÎÏ ×Ù×ÅÓÔÉ ÉÚ ËÏÎßÀÎËÃÉÉ (A ∧ B ` A É
A ∧ B ` B). îÁÐÒÏÔÉ×, ÁËÓÉÏÍÁ 5 ÇÏ×ÏÒÉÔ, ËÁË ÍÏÖÎÏ ×Ù×ÅÓÔÉ ËÏÎßÀÎËÃÉÀ.
éÚ Îž ÌÅÇËÏ ÓÌÅÄÕÅÔ ÔÁËÏÅ ÐÒÁ×ÉÌÏ: ÅÓÌÉ • ` A É • ` B, ÔÏ • ` (A ∧ B)
(ÐÒÉÍÅÎÑÅÍ ÜÔÕ ÁËÓÉÏÍÕ É Ä×ÁÖÄÙ ÐÒÁ×ÉÌÏ MP). þÁÓÔÏ ÐÏÄÏÂÎÙÅ ÐÒÁ×ÉÌÁ
ÚÁÐÉÓÙ×ÁÀÔ ÔÁË:
• ` A • ` B
• ` A ∧ B
(ÎÁÄ ÞÅÒÔÏÊ ÐÉÛÕÔ ¥ÐÏÓÙÌËÉ¥ ÐÒÁ×ÉÌÁ, Á ÓÎÉÚÕ ¡ ÅÇÏ ¥ÚÁËÌÀÞÅÎÉÅ¥, ×ÙÔÅ-
ËÁÀÝÅÅ ÉÚ ÐÏÓÙÌÏË).
úÁÄÁÞÁ 120. äÏËÁÖÉÔÅ, ÞÔÏ ÆÏÒÍÕÌÁ (A → (B → C)) → ((A ∧ B) →
→ C), ÔÁË ÖÅ ËÁË É ÏÂÒÁÔÎÁÑ Ë ÎÅÊ ÆÏÒÍÕÌÁ (× ËÏÔÏÒÏÊ ÐÏÓÙÌËÁ É ÚÁ-
ËÌÀÞÅÎÉÅ ÐÅÒÅÓÔÁ×ÌÅÎÙ), Ñ×ÌÑÀÔÓÑ ÔÅÏÒÅÍÁÍÉ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ.
äÏËÁÖÉÔÅ ÁÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÐÒÏ ÆÏÒÍÕÌÙ (A ∧ B) → (B ∧ A) É
((A ∧ B) ∧ C) → (A ∧ (B ∧ C)).
áËÓÉÏÍÙ 6 7 ÐÏÚ×ÏÌÑÀÔ ÕÔ×ÅÒÖÄÁÔØ, ÞÔÏ A ` A ∨ B É B ` A ∨ B.
áËÓÉÏÍÁ 8 ÏÂÅÓÐÅÞÉ×ÁÅÔ ÔÁËÏÅ ÐÒÁ×ÉÌÏ:
•, A ` C •, B ` C
•, A ∨ B ` C
ïÎÏ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÔÁËÏÊ ÓÈÅÍÅ ÒÁÓÓÕÖÄÅÎÉÑ: ¥ðÕÓÔØ ×ÙÐÏÌÎÅÎÏ A∨B. òÁÚ-
ÂÅÒ¾Í Ä×Á ÓÌÕÞÁÑ. åÓÌÉ ×ÙÐÏÌÎÅÎÏ A, ÔÏ h . . . i É ÐÏÔÏÍÕ C. åÓÌÉ ×ÙÐÏÌÎÅÎÏ
B, ÔÏ h . . . i É ÐÏÔÏÍÕ C. ÷ ÏÂÏÉÈ ÓÌÕÞÁÑÈ ×ÅÒÎÏ C. úÎÁÞÉÔ, A∨ B ×ÌÅÞ¾Ô C.¥
ïÂÏÓÎÏ×ÁÎÉÅ: Ä×ÁÖÄÙ ×ÏÓÐÏÌØÚÕÅÍÓÑ ÌÅÍÍÏÊ Ï ÄÅÄÕËÃÉÉ, ÐÏÌÕÞÉ× • ` (A →
→ C) É • ` (B → C), Á ÚÁÔÅÍ Ä×ÁÖÄÙ ÐÒÉÍÅÎÉÍ ÐÒÁ×ÉÌÏ MP Ë ÜÔÉÍ ÆÏÒÍÕ-
ÌÁÍ É ÁËÓÉÏÍÅ (A → C) → ((B → C) → ((A ∨ B) → C)). ðÏÌÕÞÉ× ÆÏÒÍÕÌÕ
(A ∨ B) → C, ÏÐÑÔØ ÐÒÉÍÅÎÉÍ ÐÒÁ×ÉÌÏ MP Ë ÎÅÊ É ÆÏÒÍÕÌÅ (A ∨ B).
§1. éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ                                               89

   úÁÄÁÞÁ 119. äÏÂÁ×ÉÍ Ë ÉÓÞÉÓÌÅÎÉÀ ×ÙÓËÁÚÙ×ÁÎÉÊ, ÐÏÍÉÍÏ ÐÒÁ×ÉÌÁ
modus ponens, Åݾ ÏÄÎÏ ÐÒÁ×ÉÌÏ, ÎÁÚÙ×ÁÅÍÏÅ ÐÒÁ×ÉÌÏÍ ÐÏÄÓÔÁÎÏ×ËÉ. ïÎÏ
ÒÁÚÒÅÛÁÅÔ ÚÁÍÅÎÉÔØ × ×Ù×ÅÄÅÎÎÏÊ ÆÏÒÍÕÌÅ ×ÓÅ ÐÅÒÅÍÅÎÎÙÅ ÎÁ ÐÒÏÉÚ×ÏÌØ-
ÎÙÅ ÆÏÒÍÕÌÙ (ÅÓÔÅÓÔ×ÅÎÎÏ, ×ÈÏÖÄÅÎÉÑ ÏÄÎÏÊ ÐÅÒÅÍÅÎÎÏÊ ÄÏÌÖÎÙ ÚÁÍÅ-
ÎÑÔØÓÑ ÎÁ ÏÄÎÕ É ÔÕ ÖÅ ÆÏÒÍÕÌÕ). ðÏËÁÖÉÔÅ, ÞÔÏ ÐÏÓÌÅ ÄÏÂÁ×ÌÅÎÉÑ
ÔÁËÏÇÏ ÐÒÁ×ÉÌÁ ËÌÁÓÓ ×Ù×ÏÄÉÍÙÈ ÆÏÒÍÕÌ ÎÅ ÉÚÍÅÎÉÔÓÑ, ÎÏ ÔÅÏÒÅÍÁ Ï
ÄÅÄÕËÃÉÉ ÐÅÒÅÓÔÁÎÅÔ ÂÙÔØ ×ÅÒÎÏÊ.

   úÁÍÅÔÉÍ, ÞÔÏ ÍÙ ÐÏËÁ ÞÔÏ ÉÓÐÏÌØÚÏ×ÁÌÉ ÔÏÌØËÏ Ä×Å ÐÅÒ×ÙÅ ÁËÓÉÏÍÙ ÉÓ-
ÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ. ÷ÉÄÎÏ, ËÓÔÁÔÉ, ÞÔÏ ÏÎÉ ÓÐÅÃÉÁÌØÎÏ ÐÏÄÏÂÒÁÎÙ ÔÁË,
ÞÔÏÂÙ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ Ï ÄÅÄÕËÃÉÉ ÐÒÏÛÌÏ.
   äÒÕÇÉÅ ÁËÓÉÏÍÙ ÏÐÉÓÙ×ÁÀÔ Ó×ÏÊÓÔ×Á ÌÏÇÉÞÅÓËÉÈ Ó×ÑÚÏË. áËÓÉÏÍÙ 3 É
4 ÇÏ×ÏÒÑÔ, ËÁËÉÅ ÓÌÅÄÓÔ×ÉÑ ÍÏÖÎÏ ×Ù×ÅÓÔÉ ÉÚ ËÏÎßÀÎËÃÉÉ (A ∧ B ` A É
A ∧ B ` B). îÁÐÒÏÔÉ×, ÁËÓÉÏÍÁ 5 ÇÏ×ÏÒÉÔ, ËÁË ÍÏÖÎÏ ×Ù×ÅÓÔÉ ËÏÎßÀÎËÃÉÀ.
éÚ Îž ÌÅÇËÏ ÓÌÅÄÕÅÔ ÔÁËÏÅ ÐÒÁ×ÉÌÏ: ÅÓÌÉ • ` A É • ` B, ÔÏ • ` (A ∧ B)
(ÐÒÉÍÅÎÑÅÍ ÜÔÕ ÁËÓÉÏÍÕ É Ä×ÁÖÄÙ ÐÒÁ×ÉÌÏ MP). þÁÓÔÏ ÐÏÄÏÂÎÙÅ ÐÒÁ×ÉÌÁ
ÚÁÐÉÓÙ×ÁÀÔ ÔÁË:
                            •`A       •`B
                               • `A∧B
(ÎÁÄ ÞÅÒÔÏÊ ÐÉÛÕÔ ¥ÐÏÓÙÌËÉ¥ ÐÒÁ×ÉÌÁ, Á ÓÎÉÚÕ ¡ ÅÇÏ ¥ÚÁËÌÀÞÅÎÉÅ¥, ×ÙÔÅ-
ËÁÀÝÅÅ ÉÚ ÐÏÓÙÌÏË).

   úÁÄÁÞÁ 120. äÏËÁÖÉÔÅ, ÞÔÏ ÆÏÒÍÕÌÁ (A → (B → C)) → ((A ∧ B) →
→ C), ÔÁË ÖÅ ËÁË É ÏÂÒÁÔÎÁÑ Ë ÎÅÊ ÆÏÒÍÕÌÁ (× ËÏÔÏÒÏÊ ÐÏÓÙÌËÁ É ÚÁ-
ËÌÀÞÅÎÉÅ ÐÅÒÅÓÔÁ×ÌÅÎÙ), Ñ×ÌÑÀÔÓÑ ÔÅÏÒÅÍÁÍÉ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ.
äÏËÁÖÉÔÅ ÁÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÐÒÏ ÆÏÒÍÕÌÙ (A ∧ B) → (B ∧ A) É
((A ∧ B) ∧ C) → (A ∧ (B ∧ C)).

  áËÓÉÏÍÙ 6 7 ÐÏÚ×ÏÌÑÀÔ ÕÔ×ÅÒÖÄÁÔØ, ÞÔÏ A ` A ∨ B É B ` A ∨ B.
áËÓÉÏÍÁ 8 ÏÂÅÓÐÅÞÉ×ÁÅÔ ÔÁËÏÅ ÐÒÁ×ÉÌÏ:
                           •, A ` C    •, B ` C
                               •, A ∨ B ` C
ïÎÏ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÔÁËÏÊ ÓÈÅÍÅ ÒÁÓÓÕÖÄÅÎÉÑ: ¥ðÕÓÔØ ×ÙÐÏÌÎÅÎÏ A∨B. òÁÚ-
ÂÅÒ¾Í Ä×Á ÓÌÕÞÁÑ. åÓÌÉ ×ÙÐÏÌÎÅÎÏ A, ÔÏ h . . . i É ÐÏÔÏÍÕ C. åÓÌÉ ×ÙÐÏÌÎÅÎÏ
B, ÔÏ h . . . i É ÐÏÔÏÍÕ C. ÷ ÏÂÏÉÈ ÓÌÕÞÁÑÈ ×ÅÒÎÏ C. úÎÁÞÉÔ, A ∨ B ×ÌÅÞ¾Ô C.¥
ïÂÏÓÎÏ×ÁÎÉÅ: Ä×ÁÖÄÙ ×ÏÓÐÏÌØÚÕÅÍÓÑ ÌÅÍÍÏÊ Ï ÄÅÄÕËÃÉÉ, ÐÏÌÕÞÉ× • ` (A →
→ C) É • ` (B → C), Á ÚÁÔÅÍ Ä×ÁÖÄÙ ÐÒÉÍÅÎÉÍ ÐÒÁ×ÉÌÏ MP Ë ÜÔÉÍ ÆÏÒÍÕ-
ÌÁÍ É ÁËÓÉÏÍÅ (A → C) → ((B → C) → ((A ∨ B) → C)). ðÏÌÕÞÉ× ÆÏÒÍÕÌÕ
(A ∨ B) → C, ÏÐÑÔØ ÐÒÉÍÅÎÉÍ ÐÒÁ×ÉÌÏ MP Ë ÎÅÊ É ÆÏÒÍÕÌÅ (A ∨ B).

Страницы