ΠΡΠΏΠΎΠΌΠ½ΠΈΠΌ Π΅ΡΠ΅ ΡΠ°Π· ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡ Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ:
Π₯Ρ
… Π₯ΠΏ |= Y, Π΅ΡΠ»ΠΈ ΠΈ ΡΠΎΠ»ΡΠΊΠΎ Π΅ΡΠ»ΠΈ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠ°ΠΊΠΎΠΉ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ², Π²Ρ
ΠΎΠ΄ΡΡΠΈΡ
Π² ΡΠΎΡΡΠ°Π² Π₯Ρ
… Π₯ΠΏ ΠΈ Π£ (ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ Π²Π΅ΡΠ΅ΠΉ), ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΉ (ΠΊΠΎΡΠΎΡΠΎΠΌ) ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΈΠ· ΡΠΎΡΠΌΡΠ» Π₯Ρ
… Π₯ΠΏ ΠΏΡΠΈΠ½ΡΠ»Π° Π±Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ «ΠΈΡΡΠΈΠ½Π°"Ρ Π° ΡΠΎΡΠΌΡΠ»Π° Π£ — Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ «Π»ΠΎΠΆΡ».
ΠΠΎΠΏΡΡΡΠΈΠΌ ΡΠ΅ΠΏΠ΅ΡΡ, ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠΎΡΠΌΡΠ» Π₯Ρ
… Π₯ΠΏ ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ²ΠΎ, Ρ. Π΅. ΡΠΎΡΠΌΡΠ»Ρ Π₯Ρ
… Π₯ΠΏ Π½Π΅ΡΠΎΠ²ΠΌΠ΅ΡΡΠΈΠΌΡ ΠΏΠΎ ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ: (Π₯Ρ
&… &Π₯") = _1_. Π’ΠΎΠ³Π΄Π° ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ Π½ΠΈΡ
Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΡΡΠΎΠ³ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΡΠΎΠ²Π΅ΡΡΠ΅Π½Π½ΠΎ ΡΠ΄ΠΈΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ Π·Π°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅.
ΠΡΠ° Π·Π°ΠΊΠΎΠ½ΠΎΠΌΠ΅ΡΠ½ΠΎΡΡΡ ΠΈΠ·Π²Π΅ΡΡΠ½Π° Π² ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΊΠ°ΠΊ ΠΏΡΠΈΠ½ΡΠΈΠΏ «ΠΈΠ· ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΡ ΡΠ»Π΅Π΄ΡΠ΅Ρ Π²ΡΠ΅ ΡΡΠΎ ΡΠ³ΠΎΠ΄Π½ΠΎ»: 1 |= Π£.
Π£ ΡΡΠΎΠ³ΠΎ «ΠΏΠ°ΡΠ°Π΄ΠΎΠΊΡΠ°» Π΅ΡΡΡ Π΄Π²ΠΎΠΉΡΡΠ²Π΅Π½Π½Π°Ρ ΡΠΎΡΠΌΠ°. ΠΡΠ»ΠΈ Y — ΡΠΎΠΆΠ΄Π΅ΡΡΠ²Π΅Π½Π½ΠΎΠΈΡΡΠΈΠ½Π½Π°Ρ ΡΠΎΡΠΌΡΠ»Π° (Π£ = Π’), ΡΠΎ.
ΠΡΠ° Π·Π°ΠΊΠΎΠ½ΠΎΠΌΠ΅ΡΠ½ΠΎΡΡΡ ΠΈΠ·Π²Π΅ΡΡΠ½Π° Π² ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΊΠ°ΠΊ ΠΏΡΠΈΠ½ΡΠΈΠΏ «Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠΉ Π·Π°ΠΊΠΎΠ½ ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΈΠ· ΡΠ΅Π³ΠΎ ΡΠ³ΠΎΠ΄Π½ΠΎ»: X =Π’.
Π ΡΠ΅ΠΌ ΠΆΠ΅ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ «ΠΏΠ°ΡΠ°Π΄ΠΎΠΊΡΠ°Π»ΡΠ½ΠΎΡΡΡ» ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠΉ _L ^ Y ΠΈ X |= Π’ (X ΠΈ Π£ — ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ»ΡΠ½ΡΠ΅ ΡΠΎΡΠΌΡΠ»Ρ)? Π Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ ΠΎΠ½Π° Π² Π½Π΅ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ ΠΌΠ΅ΠΆΠ΄Ρ ΠΈΡ
ΡΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅ΠΌ ΠΈ ΠΎΠ±ΡΠ΄Π΅Π½Π½ΠΎΠΉ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠ°ΡΠΈΠ΅ΠΉ Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ (ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°ΡΡΠ΅ΠΉ ΡΠ΅Π°Π»ΡΠ½ΠΎΠ΅ ΠΎΠ±ΡΡΠ»ΠΎΠ²Π»ΠΈΠ²Π°Π½ΠΈΠ΅, ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ²Π½ΡΡ ΡΠ²ΡΠ·Ρ «ΠΏΠΎΡΡΠ»ΠΎΠΊ» ΠΈ «Π·Π°ΠΊΠ»ΡΡΠ΅Π½ΠΈΡ»). ΠΡΠΎ ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΡΠΌΠ°Π»ΡΠ½ΡΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ ΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ Π² ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΈ ΡΠ΅ΠΌ ΠΈΠ½ΡΡΠΈΡΠΈΠ²Π½ΡΠΌ ΡΠΌΡΡΠ»ΠΎΠΌ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΡ ΠΏΡΡΠ°Π΅ΠΌΡΡ Π²Π»ΠΎΠΆΠΈΡΡ Π² ΡΡΠΎ ΠΏΠΎΠ½ΡΡΠΈΠ΅ ΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ.
ΠΡΠ»ΠΈ ΡΡΠ°ΠΊΡΠΎΠ²Π°ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ²Π½ΠΎΡΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ ΠΊΠ°ΠΊ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΡΠ½ΠΈΠΆΠ΅Π½ΠΈΡ Π½Π΅ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡΠΈ Π½Π°ΡΠ΅Π³ΠΎ Π·Π½Π°Π½ΠΈΡ ΠΏΡΠΈ Π΅Π³ΠΎ ΠΏΡΠΈΠ½ΡΡΠΈΠΈ (Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅ «ΠΡΠΎ ΠΆΠΈΠ²ΠΎΡΠ½ΠΎΠ΅ — ΡΠΎΠ±Π°ΠΊΠ°» Π±ΠΎΠ»Π΅Π΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ²Π½ΠΎ, ΡΠ΅ΠΌ «ΠΡΠΎ ΠΆΠΈΠ²ΠΎΡΠ½ΠΎΠ΅ — ΠΌΠ»Π΅ΠΊΠΎΠΏΠΈΡΠ°ΡΡΠ΅Π΅», ΡΡΠΎ Π²ΡΡΠ°ΠΆΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΡΠΎΠ±Π°ΠΊ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ ΠΌΠ΅Π½ΡΡΠ΅, ΡΠ΅ΠΌ Π²ΡΠ΅Ρ
ΠΌΠ»Π΅ΠΊΠΎΠΏΠΈΡΠ°ΡΡΠΈΡ
, ΠΏΠΎΡΡΠΎΠΌΡ Π²ΡΠ±ΠΎΡ ΠΌΠ΅ΠΆΠ΄Ρ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠΌΠΈ Π°Π»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²Π°ΠΌΠΈ ΡΠΌΠ΅Π½ΡΡΠ°Π΅ΡΡΡ), ΠΊΠ°ΠΊ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΡΡΠΆΠ΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠ΅ΠΉ, ΠΎΠ±ΡΡΠ»ΠΎΠ²Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΠΏΡΠΈΠ½ΡΡΠΈΠ΅ΠΌ Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΈΡΡΠΈΠ½Π½ΠΎΠ³ΠΎ, ΡΠΎ ΠΌΡ Π±ΡΠ΄Π΅ΠΌ Π²ΡΠ½ΡΠΆΠ΄Π΅Π½Ρ ΡΡΠ°ΠΊΡΠΎΠ²Π°ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ, Π·Π°ΠΊΠ»ΡΡΠ΅Π½Π½ΡΡ Π² ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ²ΠΎΠΌ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΈ, ΠΊΠ°ΠΊ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ (ΠΈΠ· Π½Π΅Π΅ Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈ ΡΠ»Π΅Π΄ΡΠ΅Ρ, Ρ. Π΅. Π² Π½Π΅ΠΉ Π·Π°ΠΊΠ»ΡΡΠ΅Π½Π°, Π»ΡΠ±Π°Ρ Π΄ΡΡΠ³Π°Ρ), Π² Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈ ΠΈΡΡΠΈΠ½Π½ΠΎΠΌ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΈ — ΠΊΠ°ΠΊ Π½ΡΠ»Π΅Π²ΡΡ (ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΎΠ½Π° ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°ΡΡΡΡ Π»ΡΠ±ΠΎΠΉ Π΄ΡΡΠ³ΠΎΠΉ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ). ΠΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ΅, ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π·Π°ΠΊΠ»ΡΡΠ°Π΅Ρ Π² ΡΠ΅Π±Π΅ Π²ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ ΠΎ ΠΌΠΈΡΠ΅, Π° Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠ΅ Π·Π°ΠΊΠΎΠ½Ρ Π½Π΅ ΡΠ²Π»ΡΡΡΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠ²Π½ΡΠΌΠΈ Π²ΠΎΠΎΠ±ΡΠ΅.
Π’Π°ΠΊΠΎΠ²Ρ ΠΎΠ±ΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° ΠΠΠ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΠΊΠ°ΠΊ Π΅Π΅ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΊΠΈ. ΠΠΎ ΠΎΠΏΡΡΡ-ΡΠ°ΠΊΠΈ Π½Π°Π΄ΠΎ Π²ΡΠ΅ Π²ΡΠ΅ΠΌΡ ΠΏΠΎΠΌΠ½ΠΈΡΡ, ΡΡΠΎ «Π½Π°ΡΠΈ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΊΠΈ Π΅ΡΡΡ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ΅Π½ΠΈΠ΅ Π½Π°ΡΠΈΡ
Π΄ΠΎΡΡΠΎΠΈΠ½ΡΡΠ²», Π² Π΄Π°Π½Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ — ΠΏΡΠ΅ΠΆΠ΄Π΅ Π²ΡΠ΅Π³ΠΎ ΡΠ²ΠΎΠΉΡΡΠ²Π° ΡΠΊΡΡΠ΅Π½ΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΡΡΠΈ.
ΠΡΠΏΠΎΠ»Π½ΠΈΡΠ΅ ΡΠΏΡΠ°ΠΆΠ½Π΅Π½ΠΈΠ΅ 25 ΠΈΠ· ΠΡΠ°ΠΊΡΠΈΠΊΡΠΌΠ°.