Π”ΠΈΠΏΠ»ΠΎΠΌΡ‹, курсовыС, Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚Ρ‹, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Ρ‹Π΅...
Брочная ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² ΡƒΡ‡Ρ‘Π±Π΅

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

ВсС Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹, ΠΊΡ€ΠΎΠΌΠ΅ ΠΏΠ΅Ρ€Π²ΠΎΠΉ, записаны ΠΏΠ°Ρ€Π°ΠΌΠΈ, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ каТдая ΠΈΠ· Ρ‚Π΅ΠΎΡ€Π΅ΠΌ ΠΏΠ°Ρ€Ρ‹ являСтся двойствСнной Π΄Ρ€ΡƒΠ³ΠΎΠΉ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ ΠΏΠ°Ρ€Ρ‹ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ Π΄Ρ€ΡƒΠ³ΡƒΡŽ Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ гласит, Ρ‡Ρ‚ΠΎ Ссли Π² ΡƒΡΠ»ΠΎΠ²ΠΈΡΡ…, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΠΈΡ… ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ И, значСния всСх ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈ ΡΠ°ΠΌΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π·Π°ΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΈΡ… ΠΈΠ½Π²Π΅Ρ€ΡΠΈΠ΅ΠΉ, Π° Π·Π½Π°ΠΊ логичСского умноТСния — Π·Π½Π°ΠΊΠΎΠΌ логичСского слоТСния, Ρ‚ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

ΠŸΡ€Π°Π²ΠΈΠ»Π° ΠΈΠ»ΠΈ Π·Π°ΠΊΠΎΠ½Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ°ΡŽΡ‚ зависимости, ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρƒ опСрациями, выполняСмыми Π½Π°Π΄ логичСскими ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ. ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅ΠΌ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π²Π°ΠΆΠ½Ρ‹Π΅ ΠΈΠ· Π½ΠΈΡ….

  • 1. Π—Π°ΠΊΠΎΠ½ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ отрицания
  • 2. ΠšΠΎΠΌΠΌΡƒΡ‚Π°Ρ‚ΠΈΠ²Π½Ρ‹Π΅ Π·Π°ΠΊΠΎΠ½Ρ‹
ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

1. 3. Π˜Π΄Π΅ΠΌΠΏΠΎΡ‚Π΅Π½Ρ‚Π½Ρ‹Π΅ Π·Π°ΠΊΠΎΠ½Ρ‹.

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

4. АссоциативныС Π·Π°ΠΊΠΎΠ½Ρ‹.

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

5. ДистрибутивныС Π·Π°ΠΊΠΎΠ½Ρ‹.

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

6.

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.
ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.
ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

7. Π—Π°ΠΊΠΎΠ½Ρ‹ двойствСнности (Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π°, ΠžΠ³Π°ΡΡ‚Π΅Ρ Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½ — ΡˆΠΎΡ‚Π»Π°Π½Π΄ΡΠΊΠΈΠΉ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊ ΠΈ Π»ΠΎΠ³ΠΈΠΊ, 1806−1871 Π³Π³.).

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

8. Π—Π°ΠΊΠΎΠ½Ρ‹ поглощСния.

ΠŸΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

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

БоставлСниС логичСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ

ЛогичСская функция составляСтся ΠΏΠΎ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡŽ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² дСйствий Π½Π°Π΄ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π°ΠΌΠΈ, исходя ΠΈΠ· ΠΏΠΎΡΡ‚Π°Π²Π»Π΅Π½Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡ΠΈ. ΠŸΡ€ΠΈ описании логичСской Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ алгСбраичСским Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ Π΄Π²Π΅ стандартныС Ρ„ΠΎΡ€ΠΌΡ‹ Π΅Π΅ ΠΏΡ€Π΅Π΄ΡΡ‚авлСния.

Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ (ДНЀ) называСтся логичСская сумма элСмСнтарных логичСских ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ, Π² ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ ΠΈΠ»ΠΈ Π΅Π³ΠΎ инвСрсия входят ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·.

ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ (КНЀ) называСтся логичСскоС ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ элСмСнтарных логичСских сумм, Π² ΠΊΠ°ΠΆΠ΄ΡƒΡŽ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ ΠΈΠ»ΠΈ Π΅Π³ΠΎ инвСрсия входят ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·.

ΠŸΠΎΡ€ΡΠ΄ΠΎΠΊ составлСния логичСской Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

a) Π² ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ опрСдСляСтся количСство ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Ρ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² ΠΈ Π΄Π»Ρ Π½ΠΈΡ… записываСтся Ρ‚Π°Π±Π»ΠΈΡ†Π° состояний;

  • Π±) Π² ΡΡ‚ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ с Π»Π΅Π²ΠΎΠΉ стороны Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ сочСтания Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ², Π° Π² ΠΏΡ€Π°Π²ΠΎΠΉ части — значСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠ»ΠΈ, Ссли Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ, значСния Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ;
  • Π²) Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ДНЀ, ΠΈΠ· Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ строки, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… функция Ρ€Π°Π²Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅, для Π½ΠΈΡ… Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ всСх Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² (Ссли Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ, Ρ‚ΠΎ ΠΎΠ½ Π±Π΅Ρ€Ρ‘тся с ΠΈΠ½Π²Π΅Ρ€ΡΠΈΠ΅ΠΉ), Π° Π·Π°Ρ‚Π΅ΠΌ всС ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ произвСдСния (конституСнты Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹) ΡΡƒΠΌΠΌΠΈΡ€ΡƒΡŽΡ‚. Для получСния КНЀ ΠΈΠ· Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Π²Ρ‹Π±ΠΈΡ€Π°ΡŽΡ‚ строки, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… функция Ρ€Π°Π²Π½Π° Π½ΡƒΠ»ΡŽ, для Π½ΠΈΡ… Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ суммы всСх Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² (Ссли Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ Ρ€Π°Π²Π΅Π½ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅, Ρ‚ΠΎ ΠΎΠ½ Π±Π΅Ρ€Ρ‘тся с ΠΈΠ½Π²Π΅Ρ€ΡΠΈΠ΅ΠΉ), Π° Π·Π°Ρ‚Π΅ΠΌ всС ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ суммы (конституСнты нуля) ΡƒΠΌΠ½ΠΎΠΆΠ°ΡŽΡ‚ΡΡ. ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ДНЀ ΠΈ КНЀ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Ρ‹ΠΌΠΈ (БДНЀ ΠΈ БКНЀ).

Π’Π°Π±Π»ΠΈΡ†Π° 1.4 Π’Π°Π±Π»ΠΈΡ†Π° состояний.

x3x2x1

y

0 0 0.

0 0 1.

0 1 0.

0 1 1.

1 0 0.

1 0 1.

1 1 0.

1 1 1.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€. Π—Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ БДНЀ ΠΈ Π‘КНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‚Ρ€Ρ‘Ρ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ², которая Ρ€Π°Π²Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅, ΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΌΠ΅Π½Π΅Π΅ Π΄Π²ΡƒΡ… Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² Ρ€Π°Π²Π½Ρ‹ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅ (Ρ‚Π°Π±Π». 1.4).

РСшСниС. Из ΡƒΡΠ»ΠΎΠ²ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈΠΌΠ΅Π΅ΠΌ Ρ‚Ρ€ΠΈ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π°: x1, x2 ΠΈ x3. ΠŸΠ΅Ρ€Π΅Ρ‡ΠΈΡΠ»ΠΈΠΌ Π² Π»Π΅Π²ΠΎΠΌ столбцС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности всСвозмоТныС ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ², Π° Π² ΠΏΡ€Π°Π²ΠΎΠΌ — ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΈΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ y. Для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строки составим Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ сумму ΠΈΠ»ΠΈ логичСскоС ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ² Π² ΡΠΎΠΎΡ‚вСтствии с ΠΏΡƒΠ½ΠΊΡ‚ΠΎΠΌ Π²) порядка составлСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ (Ρ‚Π°Π±Π». 1.4).

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ