ΠšΠ°Ρ€Ρ‚Ρ‹ ΠΊΠ°Ρ€Π½ΠΎ: Π‘Ρ…Π΅ΠΌΠΎΡ‚Π΅Ρ…Π½ΠΈΠΊΠ°. ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ логичСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ / Π₯Π°Π±Ρ€

ΠšΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ для 4-Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… β€” БтудопСдия

ПодСлись  

Как ΠΈ Π² ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹Ρ… Ρ‚Π°Π±Π»ΠΈΡ†Π°Ρ… соотвСтствия ΠΊΠ»Π΅Ρ‚ΠΊΠΈ Π½Π°Π±ΠΎΡ€ΠΎΠ², Π½Π° ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… функция ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 1, Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ Π΅Π΄ΠΈΠ½ΠΈΡ†Π°ΠΌΠΈ (Π½ΡƒΠ»ΠΈ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π½Π΅ Π²ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ, ΠΈΠΌ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ пустыС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ).

НапримСр, Π½Π° рис. ΠΏΠΎΠΊΠ°Π·Π°Π½Π° ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π΄Π°Π½ΠΎ Π½Π° 4-Ρ…-ΠΌΠ΅Ρ€Π½ΠΎΠΌ ΠΊΡƒΠ±Π΅ (см. рис.).

Для упрощСния строки ΠΈ столбцы, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ значСниям β€œ1” для Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ, Π²Ρ‹Π΄Π΅Π»ΡΡŽΡ‚ΡΡ Ρ„ΠΈΠ³ΡƒΡ€Π½ΠΎΠΉ скобкой с ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ этой ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ.

Рис. Π°) ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…;

Π±) ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π΅Π΅ минимального покрытия.

ΠœΠ΅ΠΆΠ΄Ρƒ отобраТСниями Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π½Π° n-ΠΌΠ΅Ρ€Π½ΠΎΠΌ ΠΊΡƒΠ±Π΅ ΠΈ Π½Π° ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ ΠΈΠΌΠ΅Π΅Ρ‚ мСсто Π²Π·Π°ΠΈΠΌΠ½ΠΎ-ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ΅ соотвСтствиС. На ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ S-ΠΊΡƒΠ±Ρƒ соотвСтствуСт ΡΠΎΠ²ΠΎΠΊΡƒΠΏΠ½ΠΎΡΡ‚ΡŒ 2-Ρ… сосСдних ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, Ρ€Π°Π·ΠΌΠ΅Ρ‰Π΅Π½Π½Ρ‹Ρ… Π² строкС, столбцС, ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π΅ ΠΈΠ»ΠΈ ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ΅. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ всС полоТСния, ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ€Π°Π½Π΅Π΅, справСдливы ΠΈ для ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ. Π’Π°ΠΊ Π½Π° рис. Π±) ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ Π΅Π΄ΠΈΠ½ΠΈΡ† ΠΊΠ°Ρ€Ρ‚Ρ‹, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ минимальной Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅

Ρƒ= , рассматриваСмой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Π‘Ρ‡ΠΈΡ‚Ρ‹Π²Π°Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ² с ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ осущСствляСтся ΠΏΠΎ простому ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ. ΠšΠ»Π΅Ρ‚ΠΊΠΈ, ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‰ΠΈΠ΅ S-ΠΊΡƒΠ±, Π΄Π°ΡŽΡ‚ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌ (n-S)-Π³ΠΎ Ρ€Π°Π½Π³Π°, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ входят Ρ‚Π΅ (n-S)-ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΡ…Ρ€Π°Π½ΡΡŽΡ‚ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Π΅ значСния Π½Π° этом S-ΠΊΡƒΠ±Π΅, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ значСниям β€œ1” ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ сами ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, Π° значСниям β€œ0” ΠΈΡ… ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅.

ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π΅ ΡΠΎΡ…Ρ€Π°Π½ΡΡŽΡ‚ свои значСния Π½Π° S-ΠΊΡƒΠ±Π΅, Π² ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠ΅ ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‚. Π Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ способы считывания приводят ΠΊ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌ прСдставлСниям Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π² ДНЀ.

Ρƒ= Ρƒ=

Ρƒ=

ИспользованиС ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π±ΠΎΠ»Π΅Π΅ простых построСний ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ΠΌ Π½Π° n-ΠΌΠ΅Ρ€Π½ΠΎΠΌ ΠΊΡƒΠ±Π΅, особСнно Π² случаС 4-Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Для отобраТСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ 5-Ρ‚ΠΈ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Π΄Π²Π΅ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ Π½Π° 4-Ρ€Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, Π° для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ 6-Ρ‚ΠΈ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… β€” Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°Ρ€Ρ‚Ρ‹.

ΠŸΡ€ΠΈ дальнСйшСм ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ числа ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ становятся практичСски Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Ρ‹.

ΠœΠ΅Ρ‚ΠΎΠ΄ Мак-Класски (алгСбраичСский ΠΌΠ΅Ρ‚ΠΎΠ΄)

АлгСбраичСский ΠΌΠ΅Ρ‚ΠΎΠ΄ извСстСн ΠΊΠ°ΠΊ ΠΌΠ΅Ρ‚ΠΎΠ΄ Мак-Класски, ΠΌΠΎΠ΄ΠΈΡ„ΠΈΡ†ΠΈΡ€ΠΎΠ²Π°Π²ΡˆΠ΅Π³ΠΎ Π² 1956 Π³ΠΎΠ΄Ρƒ ΠΌΠ΅Ρ‚ΠΎΠ΄ Квайна. БазируСтся Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ΅.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Если Π² БДНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ произвСсти всСвозмоТныС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π½Π΅ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ склСивания, Π° Π·Π°Ρ‚Π΅ΠΌ всСвозмоТныС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ элСмСнтарного поглощСния, Ρ‚ΠΎ получСнная Ρ„ΠΎΡ€ΠΌΠ° Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π±ΡƒΠ΄Π΅Ρ‚ сокращСнной.

Π­Π»Π΅ΠΌΠ΅Π½Ρ‚Π°Ρ€Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ Ρ€Π°Π½Π³Π° n Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠΌ Ρ€Π°Π½Π³Π° n.

ЭлСмСнтарная ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ называСтся ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ΠΎΠΉ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ , Ссли , Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π±ΡƒΠ»Π΅Π²Π° функция Π½Π° Π΄Π°Π½Π½ΠΎΠΌ Π½Π°Π±ΠΎΡ€Π΅ являСтся константной ΠΈ Ρ€Π°Π²Π½Π° 1.

ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρƒ Мак-Класски осущСствляСтся согласно ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ дСйствий:

1. Π—Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡ‹ Π² Π²ΠΈΠ΄Π΅ ΠΈΡ… Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹Ρ… ΠΊΠΎΠ΄ΠΎΠ² ΠΈ Ρ€Π°Π·Π±ΠΈΡ‚ΡŒ ΠΈΡ… Π½Π° Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΠ΅ΡΡ Π³Ρ€ΡƒΠΏΠΏΡ‹ ΠΏΠΎ числу Π΅Π΄ΠΈΠ½ΠΈΡ† Π² этих Π³Ρ€ΡƒΠΏΠΏΠ°Ρ…. Π’ i-ю Π³Ρ€ΡƒΠΏΠΏΡƒ Π²ΠΎΠΉΠ΄ΡƒΡ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚Π΅ ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π² своСй Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠΉ записи содСрТат Ρ€ΠΎΠ²Π½ΠΎ i Π΅Π΄ΠΈΠ½ΠΈΡ†. Π“Ρ€ΡƒΠΏΠΏΡ‹ Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ роста i.

2. ΠŸΠΎΠΏΠ°Ρ€Π½ΠΎΠ΅ сравнСниС ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ².

2.1. ΠŸΡ€ΠΎΠΈΠ·Π²Π΅ΡΡ‚ΠΈ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎΠ΅ сравнСниС Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹Ρ… Π½ΠΎΠΌΠ΅Ρ€ΠΎΠ² всСх Ρ‡Π»Π΅Π½ΠΎΠ² Π³Ρ€ΡƒΠΏΠΏΡ‹ с индСксом i с Ρ‡Π»Π΅Π½Π°ΠΌΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π³Ρ€ΡƒΠΏΠΏΡ‹ с индСксом (i+1).

2.2. Если Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄Π²Π° ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠ° ΠΈΠΌΠ΅ΡŽΡ‚ Π²ΠΈΠ΄ axi ΠΈ , Ρ‚ΠΎ Π²Ρ‹ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ Π°, которая являСтся ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠΌ Ρ€Π°Π½Π³Π° (n-1), Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Ссли сравниваСмы Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹ Ρ€Π°Π·Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΎΠ΄Π½ΠΎΠΌ разрядС, Ρ‚ΠΎ Π² столбСц остатков записываСтся Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹ΠΉ ΠΊΠΎΠ΄ с ΠΏΡ€ΠΎΡ‡Π΅Ρ€ΠΊΠΎΠΌ β€œ-” Π½Π° мСстС этого разряда (этот ΠΊΠΎΠ΄ соотвСтствуСт ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡƒ (n-1)-Π³ΠΎ Ρ€Π°Π½Π³Π°.

2.3. ВсС Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹ Π½ΠΎΠΌΠ΅Ρ€ΠΎΠ², ΡƒΡ‡Π°ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… Π² ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ сравнСния ΠΏΡ€ΠΈ условии ΠΈΡ… склСивания, ΠΎΡ‚ΠΌΠ΅Ρ‡Π°ΡŽΡ‚ΡΡ Π·Π½Π°ΠΊΠΎΠΌ β€œ*”.

2.4. ΠŸΡƒΠ½ΠΊΡ‚Ρ‹ 2.1-2.3. ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡŽΡ‚ΡΡ для всСх Π³Ρ€ΡƒΠΏΠΏ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ Π² порядкС возрастания i. Π”Π²ΠΎΠΈΡ‡Π½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹, Π½Π΅ ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Π΅ Π·Π½Π°ΠΊΠΎΠΌ β€œ*”, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ простым ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°ΠΌ.

2.5. ПослС построСния всСх ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ² (n-1) Ρ€Π°Π½Π³Π° ΠΏΠΎ ΠΏΡƒΠ½ΠΊΡ‚Π°ΠΌ 2.1-2.3, ΠΎΠ½ΠΈ Ρ‚Π°ΠΊΠΆΠ΅ ΡΡ€Π°Π²Π½ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΌΠ΅ΠΆΠ΄Ρƒ собой ΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π°ΡŽΡ‚ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡ‹ Ρ€Π°Π½Π³Π° (n-2) ΠΈ Ρ‚.Π΄. Π Π°Π±ΠΎΡ‚Π° ΠΏΠΎ ΠΏΠ΅Ρ€Π²ΠΎΠΌΡƒ этапу продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° срСди Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹Ρ… ΠΊΠΎΠ΄ΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΡ‚ΡŒ сравнимыС, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Ρ‚Π°ΠΊΠΈΠ΅ ΡƒΠΊΠΎΡ€ΠΎΡ‡Π΅Π½Π½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ содСрТат ΠΏΡ€ΠΎΡ‡Π΅Ρ€ΠΊΠΈ Π² ΠΎΠ΄Π½ΠΈΡ… ΠΈ Ρ‚Π΅Ρ… ΠΆΠ΅ разрядах ΠΈ Ρ€Π°Π·Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΎΠ΄Π½ΠΎΠ³ΠΎ разряда.

ВсС Π½Π΅ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½Π½Ρ‹Π΅ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡ‹ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½Ρ‹ΠΌΠΈ ΠΈΠ»ΠΈ простыми ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°ΠΌΠΈ.

3. ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹. Бтроится Ρ‚Π°Π±Π»ΠΈΡ†Π°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ число строк Ρ€Π°Π²Π½ΠΎ числу ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½Ρ‹Ρ… ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠ΅ΠΌΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Π° число столбцов Ρ€Π°Π²Π½ΠΎ числу ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ² исходной БДНЀ. Если Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌ исходной БДНЀ Π²Ρ…ΠΎΠ΄ΠΈΡ‚ пСрвичная ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°, Ρ‚ΠΎ Π½Π° пСрСсСчСнии строки ΠΈ столбца ставится ΠΌΠ΅Ρ‚ΠΊΠ°. Π”Π°Π½Π½Ρ‹Π΅ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Ρ‹, отбросив ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅, ΠΈΡΡ‚ΠΈΠ½Π½ΠΎΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π½Π΅ измСнится.

4. НахоТдСниС сущСствСнных ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚. Если Π² ΠΊΠ°ΠΊΠΎΠΌ-Π»ΠΈΠ±ΠΎ ΠΈΠ· столбцов ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ имССтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½Π° ΠΌΠ΅Ρ‚ΠΊΠ°, Ρ‚ΠΎ пСрвичная ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°, стоящая Π² ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ строкС, называСтся сущСствСнной. БущСствСнная ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ДНЀ, Π° ΠΈΠ· Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈΡΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‚ΡΡ строки, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ сущСствСнным ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°ΠΌ, Π° Ρ‚Π°ΠΊΠΆΠ΅ столбцы ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ², ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅ΠΌΡ‹Π΅ этими сущСствСнными ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°ΠΌΠΈ. Если Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π½Π΅Ρ‚ столбцов, содСрТащих Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½Ρƒ ΠΌΠ΅Ρ‚ΠΊΡƒ, Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ Π½Π° ΠΏ. 7.

5. Π’Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π½ΠΈΠ΅ Π»ΠΈΡˆΠ½ΠΈΡ… столбцов. Если Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ послС Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚ΠΎΠ³ΠΎ этапа Π΅ΡΡ‚ΡŒ Π΄Π²Π° столбца, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… стоят ΠΌΠ΅Ρ‚ΠΊΠΈ Π² ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… строках, Ρ‚ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π½ΠΈΡ… Π²Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°ΡŽΡ‚, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ ΠΎΡΡ‚Π°Π²ΡˆΠ΅Π³ΠΎΡΡ столбца Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΡΡƒΡ‰Π΅ΡΡ‚Π²Π»ΡΡ‚ΡŒ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠ°.

6. Π’Ρ‹Ρ‡Π΅Ρ€ΠΊΠΈΠ²Π°Π½ΠΈΠ΅ Π»ΠΈΡˆΠ½ΠΈΡ… ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½Ρ‹Ρ… ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚. Если Π½Π° пятом этапС ΠΏΠΎΡΠ²Π»ΡΡŽΡ‚ΡΡ строки, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠΊ, Ρ‚ΠΎ пСрвичная ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ ΠΈΠ· дальнСйшСго рассмотрСния.

7. Π’Ρ‹Π±ΠΎΡ€ минимального покрытия. Π’Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ наимСньшСС число строк Ρ‚Π°ΠΊΠΈΡ…, Ρ‡Ρ‚ΠΎΠ±Ρ‹ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ столбца ΠΈΠ· Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΌΠ΅Ρ‚ΠΊΠΈ Π² этом столбцС нашлась Π±Ρ‹ ΠΏΠΎ ΠΊΡ€Π°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅Ρ€Π΅ ΠΎΠ΄Π½Π° строка ΠΈΠ· мноТСства Π²Ρ‹Π±Ρ€Π°Π½Π½Ρ‹Ρ… строк, которая содСрТит эту ΠΌΠ΅Ρ‚ΠΊΡƒ.

Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ всСх простых ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ΠΎΠ² покрытия, Π² Ρ‚ΠΎΠΌ числС ΠΈ сущСствСнных, ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅Ρ‚ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. Из Π½Π°ΠΉΠ΄Π΅Π½Π½Ρ‹Ρ… Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΏΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡŒΡˆΠ΅ΠΌΡƒ числу Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ ΠΈ элСмСнтов ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

ΠŸΡ€ΠΈΠΌΠ΅Ρ€.

.

1) ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½ΠΈΠ΅ Π³Ρ€ΡƒΠΏΠΏ ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Ρ… ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ. 0011 0100 0101 0111 1001 1011 1100 1101

1 Π³Ρ€. 0100 2 Π³Ρ€. 0011 3 Π³Ρ€. 0111

0101 1011

1001 1101

2) ΠŸΠΎΠΏΠ°Ρ€Π½ΠΎΠ΅ сравнСниС ΠΌΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΠΎΠ².

ΠœΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡ‹ 3-Π³ΠΎ Ρ€Π°Π½Π³Π°: 010-*, -100, 0-11, -011, -101, 10-1, 1-01, 110-*

ΠœΠΈΠ½ΠΈΡ‚Π΅Ρ€ΠΌΡ‹ 2-Π³ΠΎ Ρ€Π°Π½Π³Π°: -10-.

3) ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈ расстановка ΠΌΠ΅Ρ‚ΠΎΠΊ

Β 
-100 * Β  Β  * Β  Β 
0-11 Β  * Β  Β  Β  * Β  Β 
-011 Β  * Β  Β  Β  Β  * Β 
-101 Β  Β  * Β  Β  Β  Β  *
10-1 Β  Β 
Β 
* Β  Β  * Β 
1-01 Β  Β  Β  * Β  Β  Β  *
-10- * Β  * Β  * Β  Β  *

4) НахоТдСниС сущСствСнных ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚. Π‘Ρ‚ΠΎΠ»Π±Π΅Ρ†, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠΉ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ 0111 содСрТит Π΅Π΄ΠΈΠ½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΠΌΠ΅Ρ‚ΠΊΡƒ. Π‘ΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π°Ρ этой ΠΌΠ΅Ρ‚ΠΊΠ΅ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° являСтся сущСствСнной, поэтому Π²ΠΊΠ»ΡŽΡ‡Π°Π΅ΠΌ Π΅Π΅ Π² ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ДНЀ , Π° ΠΈΠ· Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ согласно ΠΏ.4 ΠΈΡΠΊΠ»ΡŽΡ‡Π°Π΅ΠΌ столбцы ΠΈ строку, послС Ρ‡Π΅Π³ΠΎ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ:

Β 
-100 * Β  Β  * Β  Β 
-011 Β  Β  Β  Β  * Β 
-101 Β  * Β  Β  Β  *
10-1 Β  Β  * Β  * Β 
1-01 Β  Β  * Β  Β  *
-10- * * Β  * Β  *

5) ΠΈ 6) Π’ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π½Π΅Ρ‚ столбцов, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… стоят ΠΌΠ΅Ρ‚ΠΊΠΈ Π² ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… строках ΠΈ Π½Π΅Ρ‚ строк, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠΊ, поэтому ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΈΠΌ ΠΊ ΠΏ.

7.

7) Π’Ρ‹Π±ΠΎΡ€ минимального покрытия. ΠœΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΡŽ соотвСтствуСт Π²Ρ‹Π±ΠΎΡ€ строк -10- ΠΈ 10-1. Π’ΠΎΠ³Π΄Π° минимизированная ДНЀ Π·Π°ΠΏΠΈΡˆΠ΅Ρ‚ΡΡ ΠΊΠ°ΠΊ .

ο»Ώ

ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ β€” БтудопСдия

ПодСлись  

ΠœΠ΅Ρ‚ΠΎΠ΄ ΠšΠ°Ρ€Π½ΠΎ основан Π½Π° Π·Π°ΠΊΠΎΠ½Π΅ склСивания. Π‘ΠΊΠ»Π΅ΠΈΠ²Π°ΡŽΡ‚ΡΡ Π½Π°Π±ΠΎΡ€Ρ‹ , ΠΎΡ‚Π»ΠΈΡ‡Π°ΡŽΡ‰ΠΈΠ΅ΡΡ Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΎΠ΄Π½ΠΎΠ³ΠΎ разряда. Π’Π°ΠΊΠΈΠ΅ Π½Π°Π±ΠΎΡ€Ρ‹ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ сосСдними. ΠšΠ°Ρ€Π½ΠΎ Π·Π°ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π» ΠΊΠ»Π΅Ρ‚ΠΊΠΈ своСй ΠΊΠ°Ρ€Ρ‚Ρ‹ Ρ‚Π°ΠΊ ,Ρ‡Ρ‚ΠΎ Π² сосСдних ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… оказались сосСдниС, Π° Π·Π½Π°Ρ‡ΠΈΡ‚, ΡΠΊΠ»Π΅ΠΈΠ²Π°ΡŽΡ‰ΠΈΠ΅ΡΡ Π½Π°Π±ΠΎΡ€Ρ‹. БосСдними ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΡ‹ Π½Π°Π·ΠΎΠ²Π΅ΠΌ элСмСнтарными ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π°ΠΌΠΈ ΠšΠ°Ρ€Π½ΠΎ, Π½ΠΎ ΠΈ Ρ†Π΅Π»Ρ‹Π΅ Π³Ρ€ΡƒΠΏΠΏΡ‹ сосСдних ΠΊΠ»Π΅Ρ‚ΠΎΠΊ (Π½Π°Π·ΠΎΠ²Π΅ΠΌ ΠΈΡ… ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ°ΠΌΠΈ ΠšΠ°Ρ€Π½ΠΎ). Под ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠΎΠΌ ΠšΠ°Ρ€Π½ΠΎ Π±ΡƒΠ΄Π΅ΠΌ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ, Π·Π°Ρ‡Π°ΡΡ‚ΡƒΡŽ Ρ€Π°Π·Ρ€ΠΎΠ·Π½Π΅Π½Π½ΡƒΡŽ Ρ„ΠΈΠ³ΡƒΡ€Ρƒ покрытия, всС сосСдниС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹ сосСдними Π½Π°Π±ΠΎΡ€Π°ΠΌΠΈ.

НапримСр, Π½Π° Π²Ρ‹ΡˆΠ΅ΠΏΡ€ΠΈΠ²Π΅Π΄Ρ‘Π½Π½ΠΎΠΌ рисункС Π² ΠΏΠΎΠ»Π΅ ΠΊΠ°Ρ€Ρ‚Ρ‹ для 4-Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΡ‘Π½ ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊ ΠšΠ°Ρ€Π½ΠΎ P, состоящий ΠΈΠ· Ρ‡Π΅Ρ‚Ρ‹Ρ€Ρ‘Ρ… элСмСнтарных ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΎΠ² ΠšΠ°Ρ€Π½ΠΎ, описываСмых Π½Π°Π±ΠΎΡ€Π°ΠΌΠΈ x4’x3’x2’x1′ , x4’x3’x2x1′ , x4x3’x2’x1′ , x4x3’x2x1′ . Если Π½Π°Π΄ логичСской суммой этих Ρ‡Π΅Ρ‚Ρ‹Ρ€Ρ‘Ρ… Π½Π°Π±ΠΎΡ€ΠΎΠ² произвСсти ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ склСивания, Ρ‚ΠΎ ΠΌΡ‹ аналитичСски ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π² Π²ΠΈΠ΄Π΅ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Ρ‹ (ΠΏΠΎΠ΄ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ΠΎΠΉ Π±ΡƒΠ΄Π΅ΠΌ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π½Π΅ΠΏΠΎΠ»Π½Ρ‹ΠΉ Π½Π°Π±ΠΎΡ€ x3’x1′. ΠšΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ позволяСт ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ этот Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ графичСски Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ быстрСС ΠΈ ΠΏΡ€ΠΎΡ‰Π΅. Для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ этой Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ графичСской ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ. ΠšΡΡ‚Π°Ρ‚ΠΈ говоря, сам ΠšΠ°Ρ€Π½ΠΎ Π½ΠΈΠΊΠ°ΠΊΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π΅ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠΈΠ».

Π£ΠΏΡ€ΠΎΡ‰Π΅Π½ΠΈΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ (минимизация) основываСтся Π½Π° понятии нСсущСствСнности ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Π°Ρ называСтся нСсущСствСнной Π½Π° ΠΏΠ°Ρ€Π΅ Π½Π°Π±ΠΎΡ€ΠΎΠ², Ссли ΠΏΡ€ΠΈ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΈ Π΅Π΅ значСния Π½Π° ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠ΅ Π±ΡƒΠ»Π΅Π²Π° функция сохраняСт своС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.

НапримСр, для Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‚Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, f (1, 3, 5, 6, 7) = 1 , которая Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Π»Π°ΡΡŒ Π² ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»Π΅ 1.3 «Π’Π΅ΠΎΡ€ΠΈΠΈ ΠΏΠ΅Ρ€Π΅ΠΊΠ»ΡŽΡ‡Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… схСм», 6-я ΠΈ 7-я ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠΌΠ΅ΡŽΡ‚ Π²ΠΈΠ΄ : x1x23, x1x2x3.

По дистрибутивному Π·Π°ΠΊΠΎΠ½Ρƒ :

x1x23 v x1x2x3 = x1x2 ( 3 v x3 ) = x1x2.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π΄Π²Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, содСрТащиС Π½Π΅ΡΡƒΡ‰Π΅ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ, Π·Π°ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ ΠΎΠ΄Π½ΠΎΠΉ, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ нСсущСствСнная пСрСмСнная отсутствуСт.

Π’ кубичСском Π²ΠΈΠ΄Π΅ склСиваниС ΠΈΠΌΠ΅Π΅Ρ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚Π°Ρ†ΠΈΡŽ : 1 1 0 1 1 1 = 1 1 X , Ρ‡Ρ‚ΠΎ соотвСтствуСт ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈΒ x1x2.

ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅ΠΌ основныС опрСдСлСния, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ ΠΏΡ€ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ. Π”Π°Π½Π½Ρ‹Π΅ опрСдСлСния ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ понятия Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… (каноничСских) Ρ„ΠΎΡ€ΠΌ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, Π²Π²Π΅Π΄Π΅Π½Π½Ρ‹Π΅ Π² ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»Π΅ 1.3 .

Число ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, входящих Π² ΡΠ»Π΅ΠΌΠ΅Π½Ρ‚Π°Ρ€Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ (для ДНЀ) ΠΈΠ»ΠΈ Π² ΡΠ»Π΅ΠΌΠ΅Π½Ρ‚Π°Ρ€Π½ΡƒΡŽ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽΒ (для КНЀ) называСтся Π΅Π΅ Ρ€Π°Π½Π³ΠΎΠΌ.

Π’ основС Π»ΡŽΠ±Ρ‹Ρ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π»Π΅ΠΆΠΈΡ‚ опСрация склСивания. Π”Π²Π° элСмСнтарных произвСдСния ΠΎΠ΄Π½ΠΎΠ³ΠΎ Ρ€Π°Π½Π³Π° (для ДНЀ) ΠΈΠ»ΠΈ элСмСнтарных сумм ΠΎΠ΄Π½ΠΎΠ³ΠΎ Ρ€Π°Π½Π³Π° (для КНЀ) ΡΠΊΠ»Π΅ΠΈΠ²Π°ΡŽΡ‚ΡΡ, Ссли ΠΎΠ½ΠΈ Ρ€Π°Π·Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ.

ΠžΠΏΠ΅Ρ€Π°Ρ†ΠΈΡ Аx v A = A называСтся ΠΏΠΎΠ»Π½Ρ‹ΠΌ склСиваниСм, Π° опСрация Аx v A = A v Аx v A — Π½Π΅ΠΏΠΎΠ»Π½Ρ‹ΠΌ склСиваниСм (для ДНЀ).

ΠžΠΏΠ΅Ρ€Π°Ρ†ΠΈΡ ( А v x )Β· ( A v ) = A называСтся ΠΏΠΎΠ»Π½Ρ‹ΠΌ склСиваниСм, Π° опСрация ( А v x )Β· ( A v ) = AΒ· ( А v x )Β· ( A v ) — Π½Π΅ΠΏΠΎΠ»Π½Ρ‹ΠΌ склСиваниСм (для КНЀ).

НапримСр, ΠΏΠΎΠ»Π½ΠΎΠ΅ склСиваниС (x1 v x2 v x3)Β· (x1 v x2 v 3) = x1 v x2 ;

НСполноС склСиваниС x1x2x3 v x1x23 = x1x2 v x1x2x3 v x1x23 .

Π˜ΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ΠΎΠΉΒ Π½Π°Π·Ρ‹Π²Π°Π΅Ρ‚ΡΡ элСмСнтарноС ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅, Ρ€Π°Π²Π½ΠΎΠ΅ 1 Π½Π° ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ»ΠΈ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Π½Π°Π±ΠΎΡ€Π°Ρ…, Π³Π΄Π΅ данная функция Ρ€Π°Π²Π½Π° 1, ΠΈ Ρ€Π°Π²Π½ΠΎΠ΅ 0 Π½Π° всСх Π½Π°Π±ΠΎΡ€Π°Ρ…, Π³Π΄Π΅ данная функция Ρ€Π°Π²Π½Π° 0. Π˜ΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ ΠΎΠ΄ΠΈΠ½ ΠΈΠ»ΠΈ нСсколько ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ² рассматриваСмой Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. ΠžΠ±Ρ‹Ρ‡Π½ΠΎ, ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° — это Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ склСивания ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ² ΠΈΠ»ΠΈ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚.

ΠŸΡ€ΠΎΡΡ‚Π°Ρ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° — это ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°, которая содСрТит хотя Π±Ρ‹ ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Π½ΠΎ пСрСстаСт Π±Ρ‹Ρ‚ΡŒ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ΠΎΠΉ послС удалСния любого Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π° (ΠΈΠ½Ρ‹ΠΌΠΈ словами, это ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°, ΠΊ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π½Π΅ нСльзя ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ склСивания).

БокращСнная ДНЀ — это Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ всСх простых ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚.

БущСствСнная ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π° — это простая ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°, образованная склСиваниСм Ρ‚Π°ΠΊΠΈΡ… ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ², Ρ‡Ρ‚ΠΎ ΠΏΠΎ ΠΊΡ€Π°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅Ρ€Π΅ для ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· Π½ΠΈΡ… эта опСрация Π±Ρ‹Π»Π° СдинствСнной. БущСствСнныС ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Ρ‹ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‚ ядро Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Вупиковая ДНЀ — это Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ простых ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚, ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½ΠΈ ΠΎΠ΄Π½Π° Π½Π΅ являСтся лишнСй.

ΠœΠ”ΠΠ€ (минимальная ДНЀ) — тупиковая ДНЀ с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ числом Π²Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… (ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ числом Π±ΡƒΠΊΠ²) ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹ΠΌΠΈ Ρ„ΠΎΡ€ΠΌΠ°ΠΌΠΈ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Π˜ΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚ΠΎΠΉ называСтся элСмСнтарная логичСская сумма, равная 0 Π½Π° ΠΎΠ΄Π½ΠΎΠΌ ΠΈΠ»ΠΈ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Π½Π°Π±ΠΎΡ€Π°Ρ…, Π³Π΄Π΅ данная функция Ρ€Π°Π²Π½Π° 0, ΠΈ равная 1 Π½Π° всСх Π½Π°Π±ΠΎΡ€Π°Ρ…, Π³Π΄Π΅ данная функция Ρ€Π°Π²Π½Π° 1. Π˜ΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π° ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ ΠΎΠ΄ΠΈΠ½ ΠΈΠ»ΠΈ нСсколько макстСрмов рассматриваСмой Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. ΠžΠ±Ρ‹Ρ‡Π½ΠΎ, ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π° — это Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ склСивания ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… макстСрмов.

ΠŸΡ€ΠΎΡΡ‚Π°Ρ ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π° — это ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π°, которая содСрТит хотя Π±Ρ‹ макстСрм Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Π½ΠΎ пСрСстаСт Π±Ρ‹Ρ‚ΡŒ ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚ΠΎΠΉ послС удалСния любого Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π° (ΠΈΠ½Ρ‹ΠΌΠΈ словами, это ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π°, ΠΊ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π½Π΅ нСльзя ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ склСивания).

БокращСнная КНЀ — это ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ всСх простых ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚.

БущСствСнная ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π° — это простая ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Π°, образованная склСиваниСм Ρ‚Π°ΠΊΠΈΡ… макстСрмов, Ρ‡Ρ‚ΠΎ ΠΏΠΎ ΠΊΡ€Π°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅Ρ€Π΅ для ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· Π½ΠΈΡ… эта опСрация Π±Ρ‹Π»Π° СдинствСнной. БущСствСнныС ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚Ρ‹ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‚ ядро Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Вупиковая КНЀ — это ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ простых ΠΈΠΌΠΏΠ»ΠΈΡ†Π΅Π½Ρ‚, ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½ΠΈ ΠΎΠ΄Π½Π° Π½Π΅ являСтся лишнСй.

МКНЀ (минимальная КНЀ) — тупиковая КНЀ с ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ числом Π²Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… (ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ числом Π±ΡƒΠΊΠ²) ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹ΠΌΠΈ Ρ„ΠΎΡ€ΠΌΠ°ΠΌΠΈ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

ΠŸΡ€Π°Π²ΠΈΠ»Π° ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ с использованиСм ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ

1. Π’ ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ Π³Ρ€ΡƒΠΏΠΏΡ‹ Π΅Π΄ΠΈΠ½ΠΈΡ† (для получСния ДНЀ) ΠΈ Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½ΡƒΠ»Π΅ΠΉ (для получСния КНЀ) Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ обвСсти Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ…ΡƒΠ³ΠΎΠ»ΡŒΠ½Ρ‹ΠΌΠΈ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π°ΠΌΠΈ. Π’Π½ΡƒΡ‚Ρ€ΠΈ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π° Π΄ΠΎΠ»ΠΆΠ½Ρ‹ находится Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎΠΈΠΌΠ΅Π½Π½Ρ‹Π΅ значСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. Π­Ρ‚ΠΎΡ‚ процСсс соотвСтствуСт ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ склСивания ΠΈΠ»ΠΈ нахоТдСния ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚ Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

2. ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ ΠΊΠ»Π΅Ρ‚ΠΎΠΊ Π²Π½ΡƒΡ‚ΠΈ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π° Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ Ρ†Π΅Π»ΠΎΠΉ ΡΡ‚Π΅ΠΏΠ΅Π½ΡŒΡŽ Π΄Π²ΠΎΠΉΠΊΠΈ (1, 2, 4, 8, 16…).

3. ΠŸΡ€ΠΈ ΠΏΡ€ΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠΈ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ² ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ строки ΠΊΠ°Ρ€Ρ‚Ρ‹ (Π²Π΅Ρ€Ρ…Π½ΠΈΠ΅ ΠΈ Π½ΠΈΠΆΠ½ΠΈΠ΅, Π»Π΅Π²Ρ‹Π΅ ΠΈ ΠΏΡ€Π°Π²Ρ‹Π΅), Π° Ρ‚Π°ΠΊΠΆΠ΅ ΡƒΠ³Π»ΠΎΠ²Ρ‹Π΅ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, ΡΡ‡ΠΈΡ‚Π°ΡŽΡ‚ΡΡ сосСдними (для ΠΊΠ°Ρ€Ρ‚ Π΄ΠΎ 4-Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…).

4. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π²ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒ максимально Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ΅ количСство ΠΊΠ»Π΅Ρ‚ΠΎΠΊ. Π’ этом случаС ΠΎΠ½ Π±ΡƒΠ΄Π΅Ρ‚ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ простой ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π΅.

5. ВсС Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ (Π½ΡƒΠ»ΠΈ) Π² ΠΊΠ°Ρ€Ρ‚Π΅ (Π΄Π°ΠΆΠ΅ ΠΎΠ΄ΠΈΠ½ΠΎΡ‡Π½Ρ‹Π΅) Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ ΠΎΡ…Π²Π°Ρ‡Π΅Π½Ρ‹ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π°ΠΌΠΈ. Π›ΡŽΠ±Π°Ρ Π΅Π΄ΠΈΠ½ΠΈΡ†Π° (Π½ΡƒΠ»ΡŒ) ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ Π² ΠΊΠΎΠ½Ρ‚ΡƒΡ€Ρ‹ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠ΅ количСство Ρ€Π°Π·.

6. ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ², ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰ΠΈΡ… всС 1 (0) Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‚ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²ΡƒΡŽ ДНЀ (КНЀ). ЦСлью ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ являСтся Π½Π°Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ минимальной ΠΈΠ· мноТСства Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌ.

7. Π’ элСмСнтарной ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ (Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ), которая соотвСтствуСт ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Ρƒ, ΠΎΡΡ‚Π°ΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π΅ измСняСтся Π²Π½ΡƒΡ‚Ρ€ΠΈ ΠΎΠ±Π²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π°. ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ входят Π² ΡΠ»Π΅ΠΌΠ΅Π½Ρ‚Π°Ρ€Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŒΡŽΠ½ΠΊΡ†ΠΈΡŽ (для Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ 1) Π±Π΅Π· инвСрсии, Ссли ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π½Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π°Ρ… Ρ€Π°Π²Π½ΠΎ 1 ΠΈ с инвСрсиСй — Ссли 0. Для Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Ρ€Π°Π²Π½Ρ‹Ρ… 0, Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ элСмСнтарныС Π΄ΠΈΠ·ΡŒΡŽΠ½ΠΊΡ†ΠΈΠΈ, ΠΊΡƒΠ΄Π° ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ входят Π±Π΅Π· инвСрсии, Ссли ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π½Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π°Ρ… Ρ€Π°Π²Π½ΠΎ 0 ΠΈ с инвСрсиСй — Ссли 1.

Если Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ запись Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π² кубичСском Π²ΠΈΠ΄Π΅, Ρ‚ΠΎ ΠΏΡ€ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½Ρ‹ΠΌ значСниям, ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π½Π³Π° R соотвСтствуСт ΠΊΡƒΠ± Ρ€Π°Π½Π³Π° R, Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π±Π΅Π· инвСрсии соотвСтствуСт 1 Π² ΠΊΡƒΠ±Π΅, ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ с инвСрсиСй — 0, Π° Π½Π° мСстС ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΡ‚Π°Π²ΠΈΡ‚ΡŒΡΡ X . ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠ΅ мноТСство ΠΊΡƒΠ±ΠΎΠ² ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅Ρ‚ Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½ΠΎΠ΅ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ C1 (ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ ДНЀ).

ΠŸΡ€ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎ Π½ΡƒΠ»Π΅Π²Ρ‹ΠΌ значСниям ΠΈ прСдставлСнии Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π² кубичСском Π²ΠΈΠ΄Π΅, Π½ΡƒΠ»Π΅Π²ΠΎΠ΅ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ C0 формируСтся Π½Π° основС ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠΉ ДНЀ , которая являСтся инвСрсной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ КНЀ (способ построСния инвСрсных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ инвСрсных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ для f ( 1,3,5,6,7 ) = 1 рассмотрСн Π² ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»Π΅ 1.3). ΠžΡ‚ΠΌΠ΅Ρ‚ΠΈΠΌ, Ρ‡Ρ‚ΠΎ обратная ДНЀ строится Π½Π° основС КНЀ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π½Π³Π° R (ΠΈΠ· КНЀ) соотвСтствуСт ΠΊΡƒΠ± Ρ€Π°Π½Π³Π° R, Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π±Π΅Π· инвСрсии соотвСтствуСт 0 Π² ΠΊΡƒΠ±Π΅, ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ с инвСрсиСй — 1, Π° Π½Π° мСстС ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΡ‚Π°Π²ΠΈΡ‚ΡŒΡΡ X . ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠ΅ мноТСство ΠΊΡƒΠ±ΠΎΠ² ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅Ρ‚ Π½ΡƒΠ»Π΅Π²ΠΎΠ΅ ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΠΈΠ΅ C0.

ΠŸΡ€ΠΈ Π΄Π°Π½Π½ΠΎΠΌ способС задания Ρ‚Π°Π±Π»ΠΈΡ†Π° истинности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ прСдставляСтся Π² Π²ΠΈΠ΄Π΅ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π½ΠΎΠΉ ΠΊΠ°Ρ€Ρ‚Ρ‹ состояний, которая содСрТит 2n ΠΊΠ»Π΅Ρ‚ΠΎΠΊ (ΠΏΠΎ числу Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π½Π°Π±ΠΎΡ€ΠΎΠ² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…). ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π·Π±ΠΈΠ²Π°ΡŽΡ‚ΡΡ Π½Π° Π΄Π²Π΅ Π³Ρ€ΡƒΠΏΠΏΡ‹ Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎ ΠΎΠ΄Π½Π° Π³Ρ€ΡƒΠΏΠΏΠ° опрСдСляСт ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρ‹ столбца ΠΊΠ°Ρ€Ρ‚Ρ‹, Π° другая — ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρ‹ строки.

ΠŸΡ€ΠΈ Ρ‚Π°ΠΊoΠΌ способС построСния каТдая ΠΊΠ»Π΅Ρ‚ΠΊΠ° опрСдСляСтся значСниями ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌΡƒ Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠΌΡƒ Π½Π°Π±ΠΎΡ€Ρƒ. Π’Π½ΡƒΡ‚Ρ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ ставится Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π½Π° Π΄Π°Π½Π½ΠΎΠΌ Π½Π°Π±ΠΎΡ€Π΅. ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Π² строках ΠΈ столбцах Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ сосСдниС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π°Π»ΠΈΡΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΎΠ΄Π½ΠΎΠΌ разрядС ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Ρ‚.Π΅. Π±Ρ‹Π»ΠΈ сосСдними. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ значСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π² столбцах ΠΈ Π² строках ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‚ сосСдний ΠΊΠΎΠ΄ ГрСя. Π’Π°ΠΊΠΎΠΉ способ прСдставлСния ΠΎΡ‡Π΅Π½ΡŒ ΡƒΠ΄ΠΎΠ±Π΅Π½ для наглядности ΠΏΡ€ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ.

ΠšΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ Π±Ρ‹Π»ΠΈ ΠΈΠ·ΠΎΠ±Ρ€Π΅Ρ‚Π΅Π½Ρ‹ Π² 1952 Π­Π΄Π²Π°Ρ€Π΄ΠΎΠΌ Π’. ВСйч’См ΠΈ ΡƒΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½ΡΡ‚Π²ΠΎΠ²Π°Π½Ρ‹ Π² 1953 ΠœΠΎΡ€ΠΈΡΠΎΠΌ ΠšΠ°Ρ€Π½ΠΎ, Ρ„ΠΈΠ·ΠΈΠΊΠΎΠΌ ΠΈΠ· «Π‘элл Лабс» ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π΄ΠΎ 6-Ρ‚ΠΈ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… (Π΄ΠΎ 4 ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π½Π° плоскости) ΠΈ Π΄ΠΎ 6 — Π² Ρ‚Ρ€Π΅Ρ…ΠΌΠ΅Ρ€Π½ΠΎΠΉ ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚Π°Ρ†ΠΈΠΈ.

Если трСбуСтся ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΊΠ°Ρ€Ρ‚Ρƒ ΠšΠ°Ρ€Π½ΠΎ для ΠΊΠ°ΠΊΠΎΠΉ – Π»ΠΈΠ±ΠΎ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, сначала Π½Π°Π΄ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ эту Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² БДНЀ, – Π² ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΠΎΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅, ΠΈΠ»ΠΈ Π² Π²ΠΈΠ΄Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности.

КаТдоС слагаСмоС Π±ΡƒΠ»Π΅Π²Π° выраТСния Π² БДНЀ, ΠΈΠ»ΠΈ каТдая Π΅Π΄ΠΈΠ½ΠΈΡ†Π° Π² столбцС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности, задаСтся Π½Π° ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅ΠΉ Π² ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ ΠΊΠ»Π΅Ρ‚ΠΊΠ΅. ΠšΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρ‹ этой ΠΊΠ»Π΅Ρ‚ΠΊΠΈ содСрТат Ρ‚Π΅ ΠΆΠ΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ ΠΈ ΠΈΡ… инвСрсии, Ρ‡Ρ‚ΠΎ ΠΈ Π΄Π°Π½Π½ΠΎΠ΅ слагаСмоС БДНЀ Π±ΡƒΠ»Π΅Π²Π° выраТСния ( ΠΈΠ»ΠΈ данная строка Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности ).

TaΠ±Π»ΠΈΡ†Π° истинности для Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ 16 строк, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠΎΡΡ‚ΠΎΡΡ‚ΡŒ ΠΈΠ· 16 ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π½Π° рисункС:

Π£ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ для Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΡ€Π°ΠΉΠ½Π΅Π³ΠΎ Π»Π΅Π²ΠΎΠ³ΠΎ столбца Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒΡΡ ΠΊΠ°ΠΊ сосСдниС для ΠΊΠ»Π΅Ρ‚ΠΎΠΊ ΠΊΡ€Π°ΠΉΠ½Π΅Π³ΠΎ ΠΏΡ€Π°Π²ΠΎΠ³ΠΎ столбца, Π° ΠΊΠ»Π΅Ρ‚ΠΊΠΈ Π²Π΅Ρ€Ρ…Π½Π΅ΠΉ строки, – ΠΊΠ°ΠΊ сосСдниС для ΠΊΠ»Π΅Ρ‚ΠΎΠΊ Π½ΠΈΠΆΠ½Π΅ΠΉ строки. Π”Ρ€ΡƒΠ³ΠΈΠΌΠΈ словами ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ эта ΠΊΠ°Ρ€Ρ‚Π° располоТСна Π½Π° повСрхности Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€Π° (склСили ΠΏΡ€Π°Π²Ρ‹ΠΉ ΠΊΡ€Π°ΠΉ ΠΊΠ°Ρ€Ρ‚Ρ‹ с Π»Π΅Π²Ρ‹ΠΌ ), ΠΈΠ·ΠΎΠ³Π½ΡƒΡ‚ΠΎΠ³ΠΎ ΠΈ растянутого Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎ Π΅Π³ΠΎ Π²Π΅Ρ€Ρ…Π½ΠΈΠΉ срСз соСдиняСтся с Π½ΠΈΠΆΠ½ΠΈΠΌ срСзом; ΠΏΡ€ΠΈ этом Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€ прСвращаСтся Π² Ρ‚ΠΎΡ€ (Π±ΡƒΠ±Π»ΠΈΠΊ).

ΠŸΡ€Π°Π²ΠΈΠ»Π° упрощСния Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½ΠΎΠΉ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ для Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π·Π°ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‚ΡΡ Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ :

– сосСдниС Π΄Π²Π΅, Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅, ΠΈΠ»ΠΈ восСмь Π΅Π΄ΠΈΠ½ΠΈΡ† обводят ΠΎΠ±Ρ‰ΠΈΠΌ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠΌ;

– ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½Ρ‹ΠΌ Π±Π΅Π· ΠΈΠ·Π³ΠΈΠ±ΠΎΠ² ΠΈΠ»ΠΈ Π½Π°ΠΊΠ»ΠΎΠ½ΠΎΠ²;

– ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΏΡ€Π΅Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ всС входящиС Π² Π½Π΅Π³ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ Π² ΠΎΠ΄Π½Ρƒ, Ρ‚. Π΅. ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½Π΅Π½Π½Ρ‹Π΅ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ слагаСмыС БДНЀ Π±ΡƒΠ»Π΅Π²Π° выраТСния Π΄Π°ΡŽΡ‚ ΠΎΠ΄Π½ΠΎ слагаСмоС Π² ΡƒΠΏΡ€ΠΎΡ‰Π΅Π½Π½ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ;

– Ρ‚Π΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ входят Π² ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρ‹ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π° совмСстно со своими инвСрсиями, ΠΈΡΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‚ΡΡ ΠΈΠ· слагаСмого, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π΄Π°Π΅Ρ‚ этот ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π² ΡƒΠΏΡ€ΠΎΡ‰Π΅Π½Π½ΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ упрощСния Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ:

Π’ ΠΏΠ΅Ρ€Π²ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F1 Π½ΠΈΠΆΠ½ΠΈΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΈΠ· Π΄Π²ΡƒΡ… Π΅Π΄ΠΈΠ½ΠΈΡ† 15 ΠΈ 16 , ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ пятому ΠΈ ΡˆΠ΅ΡΡ‚ΠΎΠΌΡƒ слагаСмым Π² исходном Π±ΡƒΠ»Π΅Π²ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ, Π΄Π°Π΅Ρ‚ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ B ΠΈ`B. ПослС этого Π² Π½Π΅ΠΌ остаСтся ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ `A C`D. Π’ Π²Π΅Ρ€Ρ…Π½Π΅ΠΌ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ ΠΈΠ· Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ† 11, 12, 13 ΠΈ 14 , ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ΠΌ слагаСмым Π² исходном Π±ΡƒΠ»Π΅Π²ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ ΠΎΠΏΡƒΡΠΊΠ°ΡŽΡ‚ΡΡ A ΠΈ`A, D ΠΈ`D, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ этого Π²Π΅Ρ€Ρ…Π½ΠΈΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π΄Π°Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ B C.

Π’ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ F2 ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΈΠ· Π΄Π²ΡƒΡ… Π΅Π΄ΠΈΠ½ΠΈΡ† 12 ΠΈ 13 , ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Π²Ρ‚ΠΎΡ€ΠΎΠΌΡƒ ΠΈ Ρ‚Ρ€Π΅Ρ‚ΡŒΠ΅ΠΌΡƒ слагаСмым Π² исходном Π±ΡƒΠ»Π΅Π²ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ, Π΄Π°Π΅Ρ‚ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ А ΠΈ`А. ПослС этого Π² Π½Π΅ΠΌ остаСтся ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ B`C`D. Π’ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ ΠΈΠ· Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ† 11, 12, 14 ΠΈ 15 , ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Π΄Ρ€ΡƒΠ³ΠΈΠΌ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ΠΌ слагаСмым ΠΈΠ· исходного Π±ΡƒΠ»Π΅Π²Π° выраТСния, ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ ΠΎΠΏΡƒΡΠΊΠ°ΡŽΡ‚ΡΡ Π’ ΠΈ`Π’, Π‘ ΠΈ`Π‘, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ этого Π²Π΅Ρ€Ρ…Π½ΠΈΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π΄Π°Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ `A`D.

ΠšΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ прСдставляСтся Π² Π΄Π°Π½Π½ΠΎΠΌ случаС свСрнутой Π² Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Π²Π΅Ρ€Ρ…Π½ΠΈΠΉ ΠΊΡ€Π°ΠΉ совмСщаСтся с Π½ΠΈΠΆΠ½ΠΈΠΌ. Π­Ρ‚ΠΎΡ‚ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ Ρ‚Π°ΠΊΠΆΠ΅, Ρ‡Ρ‚ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π° ΠΌΠΎΠ³ΡƒΡ‚ Π½Π°ΠΊΠ»Π°Π΄Ρ‹Π²Π°Ρ‚ΡŒΡΡ Π΄Ρ€ΡƒΠ³ Π½Π° Π΄Ρ€ΡƒΠ³Π°.

ΠŸΡ€Π°Π²ΠΈΠ»ΠΎ покрытия 1.

Π›ΡŽΠ±ΠΎΠΉ области ΠΈΠ· 2k смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² соотвСтствиС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ (n-k)-Π³ΠΎ Ρ€Π°Π½Π³Π°, ΡΠΎΡΡ‚ΠΎΡΡ‰ΡƒΡŽ ΠΈΠ· ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ постоянноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²ΠΎ всСх Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½Ρ‹Ρ… Π½Π°Π±ΠΎΡ€Π°Ρ…, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΊΠ»Π΅Ρ‚ΠΊΠ°ΠΌ области. ΠŸΡ€ΠΈΡ‡Π΅ΠΌ пСрСмСнная xi Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π² прямом Π²ΠΈΠ΄Π΅, Ссли эта пСрСмСнная ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 1 Π½Π° всСх ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… области.

БоотвСтствСнно пСрСмСнная xi Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π² инвСрсном Π²ΠΈΠ΄Π΅, Ссли ΠΎΠ½Π° ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 0 Π½Π° всСх ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… области. «ΠŸΠΎΠΊΡ€Ρ‹Ρ‚ая» ΠΎΠ±Π»Π°ΡΡ‚ΡŒ Π½Π° ΠΊΠ°Ρ€Ρ‚Π΅ обводится ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠΌ. Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, совмСстно ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰ΠΈΡ… всС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹, Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½Ρ‹Π΅ Π΅Π΄ΠΈΠ½ΠΈΡ†Π°ΠΌΠΈ, Π΅ΡΡ‚ΡŒ ΠΎΠ΄Π½Π° ΠΈΠ· ДНЀ ΠΏΠ΅Ρ€Π΅ΠΊΠ»ΡŽΡ‡Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

ЦСль ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ ПЀ ΠΏΠΎ ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ — «ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΡŒ» всС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, содСрТащиС Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹, наимСньшим числом ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ наимСньшСго Ρ€Π°Π½Π³Π°, Ρ‚. Π΅. «ΠΏΠΎΠΊΡ€Ρ‹Ρ‚ΡŒ» наимСньшим числом ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ², ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΡ…Π²Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π±ΠΎΠ»ΡŒΡˆΡƒΡŽ ΠΎΠ±Π»Π°ΡΡ‚ΡŒ смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, всС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, содСрТащиС Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹. Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π΅ΡΡ‚ΡŒ ΠΎΠ΄Π½Π° ΠΈΠ· Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹Ρ… (Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, минимальная) ДНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

ΠŸΡ€ΠΎΡΡ‚Ρ‹ΠΌ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π°ΠΌ (минималям) Π² ΠΌΠ΅Ρ‚ΠΎΠ΄Π΅ Квайна-Мак-Класки Π½Π° ΠΊΠ°Ρ€Ρ‚Π΅ ΠšΠ°Ρ€Π½ΠΎ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ области смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, Π½Π΅ ΡΠ²Π»ΡΡŽΡ‰ΠΈΠ΅ΡΡ Ρ‡Π°ΡΡ‚ΡŒΡŽ Π½ΠΈΠΊΠ°ΠΊΠΎΠΉ Π΄Ρ€ΡƒΠ³ΠΎΠΉ области смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ.

ΠžΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΉ простой ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Π½Ρ‚Π΅ (экстрСмали) Π² ΠΌΠ΅Ρ‚ΠΎΠ΄Π΅ Квайна-Мак-Класки соотвСтствуСт ΠΎΠ±Π»Π°ΡΡ‚ΡŒ смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, которая ΠΏΠΎΠΊΡ€Ρ‹Π²Π°Π΅Ρ‚ хотя Π±Ρ‹ ΠΎΠ΄Π½Ρƒ Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½ΡƒΡŽ ΠΊΠ»Π΅Ρ‚ΠΊΡƒ, Π½Π΅ Π²Ρ…ΠΎΠ΄ΡΡ‰ΡƒΡŽ Π² состав Π½ΠΈΠΊΠ°ΠΊΠΎΠΉ ΠΈΠ· Π΄Ρ€ΡƒΠ³ΠΈΡ… областСй смСТных ΠΊΠ»Π΅Ρ‚ΠΎΠΊ.

ΠŸΡ€Π°Π²ΠΈΠ»ΠΎ покрытия 2.

Π›ΡŽΠ±ΠΎΠΉ смСТной области 2k ΠΊΠ»Π΅Ρ‚ΠΎΠΊ, Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½Ρ‹Ρ… нулями, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² соотвСтствиС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ (n-k)-Π³ΠΎ Ρ€Π°Π½Π³Π°, ΡΠΎΡΡ‚ΠΎΡΡ‰ΡƒΡŽ ΠΈΠ· ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ постоянноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²ΠΎ всСх Π½ΡƒΠ»Π΅Π²Ρ‹Ρ… Π½Π°Π±ΠΎΡ€Π°Ρ…, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΊΠ»Π΅Ρ‚ΠΊΠ°ΠΌ области, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ пСрСмСнная xi Π²Ρ…ΠΎΠ΄ΠΈΡ‚ Π² Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ Π² прямом Π²ΠΈΠ΄Π΅, Ссли ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 0 Π½Π° всСх ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… области, ΠΈ, соотвСтствСнно Π² инвСрсном Π²ΠΈΠ΄Π΅, Ссли ΠΎΠ½Π° ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 1 Π½Π° всСх ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… области. ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ минимального числа Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ, совмСстно ΠΏΠΎΠΊΡ€Ρ‹Π²Π°ΡŽΡ‰ΠΈΡ… всС ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹, Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½Ρ‹Π΅ нулями, Π΅ΡΡ‚ΡŒ ΠΎΠ΄Π½Π° ΠΈΠ· Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹Ρ… (Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ…) КНЀ ΠΏΠ΅Ρ€Π΅ΠΊΠ»ΡŽΡ‡Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

ο»Ώ

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠΈ ΠšΠ°Ρ€Π½ΠΎ — Fine Art America

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹: 53

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹: 53

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ

5,00 долл. БША

4,00 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° ΠšΠ°Ρ€Π½ΠΎ ΠΎ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠ΅

5,00 долл. БША

4,00 долл. БША

ΠŸΠΎΡ€Ρ‚Ρ€Π΅Ρ‚ Николя Π›Π΅ΠΎΠ½Π°Ρ€Π΄Π° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,00 долл. БША

4,00 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° «ΠŸΠΎΡ€Ρ‚Ρ€Π΅Ρ‚ французского ΠΈΠ½ΠΆΠ΅Π½Π΅Ρ€Π° Π›Π°Π·Π°Ρ€Π° ΠšΠ°Ρ€Π½ΠΎ»

5,00 долл. БША

4,00 долл. БША

ПобСда Π€Ρ€Π°Π½Ρ†ΠΈΠΈ объявлСна β€‹β€‹ΠΏΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠΎΠΉ Telegram

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° «Π’Ρ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ½ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ»

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ

5,00 долл. БША

4,00 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Β«Π’Ρ€Π°ΠΊΡ‚Π°Ρ‚ ΠΎ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠ΅Β» ΠšΠ°Ρ€Π½ΠΎ 1824 Π³.

5,00 долл. БША

4,00 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с ΠΏΠΎΡ€Ρ‚Ρ€Π΅Ρ‚ΠΎΠΌ Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ

5,00 долл. БША

4,00 долл. БША

ΠŸΠΎΡ€Ρ‚Ρ€Π΅Ρ‚ Николя Π›Π΅ΠΎΠ½Π°Ρ€Π΄Π° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

$5,00

$4,00

Π€ΠΎΠ½Ρ‚Π°Π½ с Π±ΡŽΡΡ‚ΠΎΠΌ Нострадамуса ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

7,00 долл. БША

5,60 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° «Π’Ρ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ½ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ»

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° «Π’Ρ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ½ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ»

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° «Π’Ρ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ½ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ»

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Эмиля ΠšΠ»Π°ΠΏΠ΅ΠΉΡ€ΠΎΠ½Π°

5,00 долл. БША

4,00 долл. БША

Π›Π°Π·Π°Ρ€ Николя ΠœΠ°Ρ€Π³Π°Ρ€ΠΈΡ‚Π° ΠšΠ°Ρ€Π½ΠΎ ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

6,95 долл. БША

5,56 долл. БША

Π›Π°Π·Π°Ρ€ Николя ΠœΠ°Ρ€Π³Π°Ρ€ΠΈΡ‚Π° ΠšΠ°Ρ€Π½ΠΎ ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

ΠœΠ°Ρ€ΠΈ-Ѐрансуа-Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ Ѐранцузская ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

ΠŸΡ€Π΅Π·ΠΈΠ΄Π΅Π½Ρ‚ Π€Ρ€Π°Π½Ρ†ΠΈΠΈ ΠšΠ°Ρ€Π½ΠΎ с ΠΏΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠΎΠΉ

5,95 долл. БША

4,76 долл. БША

Π›Π°Π·Π°Ρ€ Π˜ΠΏΠΏΠΎΠ»ΠΈΡ‚ ΠšΠ°Ρ€Π½ΠΎ Ѐранцузская ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

Π›Π°Π·Π°Ρ€ Николя ΠœΠ°Ρ€Π³Π°Ρ€ΠΈΡ‚Π° ΠšΠ°Ρ€Π½ΠΎ ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

Π›Π°Π·Π°Ρ€ Николя ΠœΠ°Ρ€Π³Π°Ρ€ΠΈΡ‚Π° ΠšΠ°Ρ€Π½ΠΎ, 1753-1823 Π³Π³. ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° французского государствСнного дСятСля

4,45 Π΄ΠΎΠ»Π»Π°Ρ€Π°

3,56 Π΄ΠΎΠ»Π»Π°Ρ€Π°

Николя Π›Π΅ΠΎΠ½Π°Ρ€Π΄ Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ, Ѐранцузская ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

6,95 долл. БША

5,56 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° ΠšΠΈΡ€Π°ΡΠ° ΠšΠ°Ρ€Π½ΠΎ

19 Π΄ΠΎΠ»Π»Π°Ρ€ΠΎΠ²

15 Π΄ΠΎΠ»Π»Π°Ρ€ΠΎΠ²

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с Π›Π°Π·Π°Ρ€ΠΎΠΌ ΠšΠ°Ρ€Π½ΠΎ, французским ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠΎΠΌ

6,95 долл. БША

5,56 долл. БША

Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ, ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с французским Ρ„ΠΈΠ·ΠΈΠΊΠΎΠΌ

6,95 долл. БША

5,56 долл. БША

Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ, ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с французским Ρ„ΠΈΠ·ΠΈΠΊΠΎΠΌ

6,95 $

$5,56

ΠŸΠΎΡ€Ρ‚Ρ€Π΅Ρ‚ ΠΌΠ°Π΄Π΅ΠΌΡƒΠ°Π·Π΅Π»ΡŒ ΠšΠ°Ρ€Π½ΠΎ ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

8,95 долл. БША

7,16 долл. БША

Π›ΡƒΠΈ-ΠžΡΠΊΠ°Ρ€ Π ΠΎΡ‚ΠΈ, ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с Ρ‚Π΅Π»ΠΎΠΌ ΠΏΡ€Π΅Π·ΠΈΠ΄Π΅Π½Ρ‚Π° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ Π‘ΠΎΡ€Π½Π΅

4,95 долл. БША

3,96 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° ΠœΠ°Ρ€ΠΈ Π€Ρ€Π°Π½

6,95 долл. БША

5,56 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° ΠœΠ°Ρ€ΠΈ Π€Ρ€Π°Π½

6,95 долл. БША

5,56 долл. БША

Анри Π΄Π΅ Π’ΡƒΠ»ΡƒΠ·-Π›ΠΎΡ‚Ρ€Π΅ΠΊ, Ѐранция, 1864-1901 Π³Π³. ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

4,95 $

$3,96

Π’ΠΎΠ»Π½Π°, Ρ€Π°Π·Π±ΠΈΠ²Π°ΡŽΡ‰Π°ΡΡΡ ΠΎ скалы. ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с мысом ΠšΠ°Ρ€Π½ΠΎ

4,95 долл. БША

3,96 долл. БША

Π‘ΠΎΠ»ΡŒΠ½ΠΎΠΉ ΠšΠ°Ρ€Π½ΠΎ! (ΠšΠ°Ρ€Π½ΠΎ Малад!) ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

4,94 долл. БША

3,95 долл. БША

Francais Portrait de Lazare Carnot 1753-1823 ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

Бронзовая статуя «ΠŸΡƒΡ‚Π΅ΡˆΠ΅ΡΡ‚Π²Π΅Π½Π½ΠΈΠΊ» французского Ρ…ΡƒΠ΄ΠΎΠΆΠ½ΠΈΠΊΠ° Π‘Ρ€ΡƒΠ½ΠΎ ΠšΠ°Ρ‚Π°Π»Π°Π½ΠΎ Π½Π° ΠΏΠ»ΠΎΡ‰Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ, Π‘ΠΎΠ½, Бургундия, Ѐранция ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,45 долл. БША

4,36 долл. БША

ΠŸΠ°Ρ€ΠΈΠΆ Π½Π° Π·Π°ΠΊΠ°Ρ‚Π΅ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

4,95 долл. БША

3,96 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Π½Π° ΡƒΠ³Π»Ρƒ ΠΏΠ»ΠΎΡ‰Π°Π΄ΠΈ Π‘Π΅Π»ΡŒΠΊΡƒΡ€ ΠΈ ΡƒΠ»ΠΈΡ†Ρ‹ Π’ΠΈΠΊΡ‚ΠΎΡ€Π° Π“ΡŽΠ³ΠΎ

7,95 долл. БША

6,36 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с эмоциями

4,95 долл. БША

3,96 долл. БША

Π’Π΅ΠΉΠ½Π°Π½Π΄ ЭссСр — ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ΠΌ НаполСона ΠšΠ°Ρ€Π½ΠΎ, 1815 Π³.

5,95 долл. БША

4,76 долл. БША

ΠšΠ°Ρ€Π½ΠΎ Π±ΠΎΠ»Π΅Π½ ΠΈΠ· Les Vieilles Histoires 1893 ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

8,95 долл. БША

7,16 долл. БША

Le President Sadi Carnot entoure de personnalites de la IIIeme Republique devant lOpera ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,94 долл. БША

4,75 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Carnot cuirasse d’escadre 1907 Π³ΠΎΠ΄Π°

5,94 долл. БША

4,75 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° ΠŸΡ€Π΅Π·ΠΈΠ΄Π΅Π½Ρ‚Π° Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ Π² ΠΎΠΊΡ€ΡƒΠΆΠ΅Π½ΠΈΠΈ пСрсон ΠΈΠ· IIIeme Republique, devant l’ Opera

4,95 долл. БША

3,96 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Ρ‚Π΅Π½ΠΈ

5,95 долл. БША

4,76 долл. БША

ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с ΠΏΡ€ΠΈΡ€ΠΎΠ΄ΠΎΠΉ

4,95 долл. БША

3,96 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° с Π³ΠΎΡ€Π°ΠΌΠΈ

4,95 долл. БША

3,96 долл. БША

ЭлСгантная Π°Ρ€Ρ…ΠΈΡ‚Π΅ΠΊΡ‚ΡƒΡ€Π° Π² стилС ΠΌΠΎΠ΄Π΅Ρ€Π½ Π² ΠšΠ°Π½Π½Π°Ρ… Π½Π° Π±ΡƒΠ»ΡŒΠ²Π°Ρ€Π΅ Greeting Card

6,95 долл. БША

5,56 долл. БША

Π’Ρ‚ΠΎΡ€ΠΎΠΉ Π·Π°ΠΊΠΎΠ½ Ρ‚Π΅Ρ€ΠΌΠΎΠ΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΈ. ΠžΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

5,95 долл. БША

4,76 долл. БША

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Осада ΠŸΠ°Ρ€ΠΈΠΆΠ°

5,94 долл. БША

4,75 долл. БША

НСоновая вывСска Le Cafe Carnot, ΠΏΠ»ΠΎΡ‰Π°Π΄ΡŒ ΠšΠ°Ρ€Π½ΠΎ, НСвСр, ΠΡŒΠ΅Π²Ρ€, Бургундия, ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ° Π€Ρ€Π°Π½Ρ†ΠΈΠΈ

4,95 Π΄ΠΎΠ»Π»Π°Ρ€Π°

3,96 Π΄ΠΎΠ»Π»Π°Ρ€Π°

ΠŸΠ»ΠΎΡ‰Π°Π΄ΡŒ ΠšΠ°Ρ€Π½ΠΎ, НСвСр, ΠΡŒΠ΅Π²Ρ€, Бургундия, Ѐранция ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠ°

4,95 долл. БША

3,96 долл. БША

ΠŸΡ€Π΅Π·ΠΈΠ΄Π΅Π½Ρ‚ Π€Ρ€Π°Π½Ρ†ΠΈΠΈ Π‘Π°Π΄ΠΈ ΠšΠ°Ρ€Π½ΠΎ ΠΈΠ· сСрии Ρ„Π»Π°Π³ΠΎΠ² ΠΈ Π³Π΅Ρ€Π±ΠΎΠ² ΠΏΡ€Π°Π²ΠΈΡ‚Π΅Π»Π΅ΠΉ N126 2, Π²Ρ‹ΠΏΡƒΡ‰Π΅Π½Π½ΠΎΠΉ W Du Greeting Card

4,95 $

3,96 $

Π€ΠΈΠ»ΡŒΡ‚Ρ€Ρ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½Ρ‹0003

Home Decor

Throw PillowsFleece BlanketsDuvet CoversShower CurtainsBath TowelsHand TowelsCoffee MugsOrnaments

Apparel

Men’s T-ShirtsMen’s Tank TopsWomen’s T-ShirtsWomen’s Tank TopsLong Sleeve T-ShirtsSweatshirtsKid’s T-ShirtsBaby OnesiesFace Masks

Phone Cases

iPhone CasesGalaxy CasesPortable Battery Chargers

ΠšΠ°Π½Ρ†Π΅Π»ΡΡ€ΡΠΊΠΈΠ΅ Ρ‚ΠΎΠ²Π°Ρ€Ρ‹

ΠŸΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ открыткиНоутбукиНаклСйки

Lifestyle

ΠšΠΎΠ²Ρ€ΠΈΠΊΠΈ для ΠΉΠΎΠ³ΠΈΠ‘ΡƒΠΌΠΊΠΈΠ‘ΡƒΠΌΠΊΠΈ-Ρ‚ΠΎΡƒΡ‚ WeekenderΠ‘ΡƒΠΌΠΊΠΈ Carry-AllCouchΠšΠΎΡ„Π΅ΠΉΠ½Ρ‹Π΅ ΠΊΡ€ΡƒΠΆΠΊΠΈΠ“ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΊΠΈ

Beach

Beach Totelelsround Beach Totelsweekender Tote Bagscarry-All Coutsportable Bagsweekend

ВсС ΠšΠ°Ρ€Ρ‚ΠΈΠ½Ρ‹ Π€ΠΎΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ Π§Π΅Ρ€Ρ‚Π΅ΠΆΠΈ Π¦ΠΈΡ„Ρ€ΠΎΠ²ΠΎΠ΅ искусство

ВсС ΠΏΠΎΠ·Π΄Ρ€Π°Π²ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΊΠΈ

ΠœΡ‹ ΠΎΡ‚ΠΏΡ€Π°Π²ΠΈΠ»ΠΈ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Ρ‹ Ρ‚ΠΎΠ²Π°Ρ€ΠΎΠ² ΠΏΠΎ всСму ΠΌΠΈΡ€Ρƒ для Π±ΠΎΠ»Π΅Π΅ Ρ‡Π΅ΠΌ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π° Ρ…ΡƒΠ΄ΠΎΠΆΠ½ΠΈΠΊΠΎΠ².

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ

Π’Π°Ρˆ адрСс email Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½. ΠžΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ поля ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Ρ‹ *