ΠšΠ½Ρ„ ΠΈ Π΄Π½Ρ„ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹: Π΄Π½Ρ„, ΠΊΠ½Ρ„, сднф, скнф ΠŸΡ€ΠΈΠΌΠ΅Ρ€ построСния скнф для ΠΌΠ΅Π΄ΠΈΠ°Π½Ρ‹

Π’Π΅ΠΌΠ° 3 ΠΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ„ΠΎΡ€ΠΌΡ‹

3.1 Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΏΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ

3.2 АлгСбра Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°

Π’Ρ‹ΡˆΠ΅ ΠΌΡ‹ ΠΏΠΎΠΊΠ°Π·Π°Π»ΠΈ, Ρ‡Ρ‚ΠΎ любая Π±ΡƒΠ»Π΅Π²Π° функция ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π·Π°Π΄Π°Π½Π° с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. Π’ настоящСм Ρ€Π°Π·Π΄Π΅Π»Π΅ излагаСтся ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ ΠΎΡ‚ Ρ‚Π°Π±Π»ΠΈΡ‡Π½ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Π° задания Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΊ аналитичСскому.

3.1 Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΏΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ. ΠŸΡƒΡΡ‚ΡŒ G – ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€, Ρ€Π°Π²Π½Ρ‹ΠΉ 0 ΠΈΠ»ΠΈ 1. Π’Π²Π΅Π΄Π΅ΠΌ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.

ΠŸΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΎΠΉ Π»Π΅Π³ΠΊΠΎ ΡƒΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ XG=1, Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° X=G. ΠžΡ‚ΡΡŽΠ΄Π° слСдуСт, ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Ρ€Π°Π²Π½Π° 1 (здСсь G Ρ€Π°Π²Π΅Π½ 0 ΠΈΠ»ΠΈ 1) Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° . НапримСр, ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ (Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ G2=G1=0, G3=G4=1) Ρ€Π°Π²Π½Π° 1 Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² случаС, ΠΊΠΎΠ³Π΄Π° X1=X2=0, X3=X4=1.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 1. Всякая Π±ΡƒΠ»Π΅Π²Π° функция F(X1,X2,…,Xn) ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ прСдставлСна Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΠ΅:

(1)

Π“Π΄Π΅ 1≀K≀N, Π² Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ бСрСтся ΠΏΠΎ всСм Π½Π°Π±ΠΎΡ€Π°ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Π­Ρ‚ΠΎ прСдставлСниС носит Π½Π°Π·Π²Π°Π½ΠΈΠ΅ разлоТСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ . НапримСр, ΠΏΡ€ΠΈ n=4, k=2 Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (1) ΠΈΠΌΠ΅Π΅Ρ‚ Π²ΠΈΠ΄:

.

Π”ΠΎΠΊΠ°ΠΆΠ΅ΠΌ ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ разлоТСния (1). Для этого возьмСм ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΉ Π½Π°Π±ΠΎΡ€ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… . ПокаТСм, Ρ‡Ρ‚ΠΎ лСвая ΠΈ правая части ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡ (1) ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‚ ΠΏΡ€ΠΈ Π½Π΅ΠΌ ΠΎΠ΄Π½ΠΎ ΠΈ Ρ‚ΠΎ ΠΆΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Π”Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ XG=1 Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° X=G, Ρ‚ΠΎ срСди 2К ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΏΡ€Π°Π²ΠΎΠΉ части (1) Π² Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ обращаСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½Π°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ . ВсС ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π²Π½Ρ‹ Π½ΡƒΠ»ΡŽ.

ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ . Π’ качСствС слСдствия ΠΈΠ· разлоТСния (1) ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π΄Π²Π° ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… разлоТСния.

Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΏΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ XN:

(2)

Если Π±ΡƒΠ»Π΅Π²Π° функция Π½Π΅ Π΅ΡΡ‚ΡŒ константа 0, Ρ‚ΠΎ справСдливо Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅

Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΏΠΎ всСм ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ:

, (3)

Π“Π΄Π΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ бСрСтся ΠΏΠΎ всСм Π½Π°Π±ΠΎΡ€Π°ΠΌ , ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π²Π½ΠΎ 1.

Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (3) называСтся ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΠΎΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ (сокращСнная запись БДНЀ) Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (3) Π΄Π°Π΅Ρ‚ способ построСния БДНЀ. Для этого Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности ΠΎΡ‚ΠΌΠ΅Ρ‡Π°Π΅Ρ‚ всС строки , Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… . Для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Ρ‚Π°ΠΊΠΎΠΉ строки ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅ΠΌ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ ΠΈ Π·Π°Ρ‚Π΅ΠΌ всС ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ соСдиняСм Π·Π½Π°ΠΊΠΎΠΌ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, сущСствуСт Π²Π·Π°ΠΈΠΌΠ½ΠΎ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ΅ соотвСтствиС ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ истинности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈ Π΅Π΅ БДНЀ. А это Π·Π½Π°Ρ‡ΠΈΡ‚, Ρ‡Ρ‚ΠΎ БДНЀ для Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ СдинствСнна.

Единая Π±ΡƒΠ»Π΅Π²Π° функция, Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‰Π°Ρ БДНЀ, Π΅ΡΡ‚ΡŒ константа 0.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1. Найти ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ .

Боставим Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности для Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

0

0

0

1

1

0

0

0

1

1

1

1

0

1

0

0

1

0

0

1

1

0

1

1

1

0

0

1

1

0

1

0

1

1

1

1

1

1

0

0

0

1

1

1

1

0

0

1

ΠžΡ‚ΡΡŽΠ΄Π° ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ: ==.

Π’Π°ΠΆΠ½ΡƒΡŽ Ρ€ΠΎΠ»ΡŒ Π² Π°Π»Π³Π΅Π±Ρ€Π΅ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΈΠ³Ρ€Π°Π΅Ρ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π΅ Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 2. Всякая Π±ΡƒΠ»Π΅Π²Π° функция ΠœΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ прСдставлСна Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΠ΅:

(4)

Π“Π΄Π΅ 1≀k≀n, Π° ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ бСрСтся По всСм 2K Π½Π°Π±ΠΎΡ€Π°ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Π”Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ, ΠΏΡƒΡΡ‚ΡŒ – ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΉ Π½Π°Π±ΠΎΡ€ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. ПокаТСм, Ρ‡Ρ‚ΠΎ любая ΠΈ правая части ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡ (4) ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‚ ΠΏΡ€ΠΈ Π½Π΅ΠΌ ΠΎΠ΄Π½ΠΎ ΠΈ Ρ‚ΠΎ ΠΆΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Π’Π°ΠΊ ΠΊΠ°ΠΊ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° , Ρ‚ΠΎ срСди 2k Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ ΠΏΡ€Π°Π²ΠΎΠΉ части (4) Π² 0 обращаСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½Π°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ . ВсС ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π²Π½Ρ‹ 1.

ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ==.

НСпосрСдствСнно ΠΈΠ· разлоТСния (4) ΡΠ»Π΅Π΄ΡƒΡŽΡ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ разлоТСния Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ:

(5)

, (6)

ПослСднСС Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ носит Π½Π°Π·Π²Π°Π½ΠΈΠ΅ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΠΎΠΉ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡ‹ (БКНЀ). Π Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (6) Π΄Π°Π΅Ρ‚ способ построСния БКНЀ. Для этого Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности ΠΎΡ‚ΠΌΠ΅Ρ‡Π°Π΅ΠΌ всС строки , Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… . Для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Ρ‚Π°ΠΊΠΎΠΉ строки ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅ΠΌ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ ΠΈ Π·Π°Ρ‚Π΅ΠΌ всС ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ соСдиняСм Π·Π½Π°ΠΊΠΎΠΌ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, сущСствуСт Π²Π·Π°ΠΈΠΌΠ½ΠΎ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ΅ соотвСтствиС ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ истинности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈ Π΅Π΅ БКНЀ. А это Π·Π½Π°Ρ‡ΠΈΡ‚, Ρ‡Ρ‚ΠΎ БКНЀ для Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ СдинствСнна.

ЕдинствСнная Π±ΡƒΠ»Π΅Π²Π° функция, Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‰Π°Ρ БКНЀ, Π΅ΡΡ‚ΡŒ константа 1.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2. Найти ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ .

Боставим Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности для Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

0

0

0

1

1

1

0

0

1

1

1

1

0

1

0

1

0

0

0

1

1

1

1

1

1

0

0

0

1

0

1

0

1

0

1

0

1

1

0

1

0

0

1

1

1

1

1

1

ΠžΡ‚ΡΡŽΠ΄Π° ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ БКНЀ

.

Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π²ΠΈΠ΄Π° (краткая запись ), Π³Π΄Π΅ — ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ называСтся Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ.

Π’ силу ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ опрСдСлСния ДНЀ Π±ΡƒΠ΄ΡƒΡ‚, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, выраТСния: , .

Как ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½ΠΎ Π² ΠΏΡƒΠ½ΠΊΡ‚Π΅ 2.2, всС логичСскиС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ свСсти ΠΊ Ρ‚Ρ€Π΅ΠΌ: ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΈ отрицания. ΠŸΡ€ΠΈΡ‡Π΅ΠΌ, Π²Π²ΠΈΠ΄Ρƒ Π·Π°ΠΊΠΎΠ½Π° Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π°, Π·Π½Π°ΠΊ отрицания ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Ρ‚ΡŒ отнСсСнным Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΊ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ дистрибутивный Π·Π°ΠΊΠΎΠ½, раскрываСм скобки ΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ. Π˜Ρ‚Π°ΠΊ, справСдлива ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 3. Для любой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ сущСствуСт Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π°Ρ Π΅ΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°.

Π”ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ Π΄Π°Π΅Ρ‚ способ построСния Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡ‹ для любой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 3. Найти Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ для ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹:

.

Π˜ΡΠΊΠ»ΡŽΡ‡Π°Ρ Π·Π½Π°ΠΊ ΠΏΠΎ Π·Π°ΠΊΠΎΠ½Ρƒ ΠΈ примСняя Π·Π°ΠΊΠΎΠ½Ρ‹ Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π° ΠΈ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ отрицания, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ:

Π—Π°Ρ‚Π΅ΠΌ, примСняя Π·Π°ΠΊΠΎΠ½ дистрибутивности, раскроСм скобки

ПослСднСС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π΅ΡΡ‚ΡŒ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°.

Π€ΠΎΡ€ΠΌΠ° Π²ΠΈΠ΄Π°

(краткая запись ), Π³Π΄Π΅ — Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ называСтся ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ (сокращСнно КНЀ).

Π’ силу ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ опрСдСлСния КНЀ Π±ΡƒΠ΄ΡƒΡ‚, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, выраТСния:

, .

Как ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π²Ρ‹ΡˆΠ΅, для любой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ сущСствуСт Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π°Ρ Π΅ΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°. Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ дистрибутивный Π·Π°ΠΊΠΎΠ½ , ΠΈΠ· Π΄Π°Π½Π½ΠΎΠΉ ДНЀ Π»Π΅Π³ΠΊΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ КНЀ.

Π˜Ρ‚Π°ΠΊ, справСдлива ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 4. Для любой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ сущСствуСт Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π°Ρ Π΅ΠΉ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°.

Π”ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ Π΄Π°Π΅Ρ‚ способ построСния ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡ‹ для любой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 4. Найти Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ ΠΈ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ„ΠΎΡ€ΠΌΡ‹ для ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹: .

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π·Π°ΠΊΠΎΠ½ , ΠΈΡΠΊΠ»ΡŽΡ‡Π°Π΅ΠΌ Π·Π½Π°ΠΊ .

ΠŸΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ .

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π·Π°ΠΊΠΎΠ½ Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π°, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ .

Раскрывая скобки, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ

.

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ, ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ ΠΊ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅

Дистрибутивный Π·Π°ΠΊΠΎΠ½, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ:

ПослСднСС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ являСтся ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ. Π’Π°ΠΊ ΠΊΠ°ΠΊ ΠΈ , Ρ‚ΠΎ получСнная КНЀ Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ КНЀ:

.

Π‘Ρ€Π΅Π΄ΠΈ всСх Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌΡƒΠ» Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π²Ρ‹Π΄Π΅Π»ΠΈΠΌ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ ΠΊΠ°ΠΊ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ, Ρ‚Π°ΠΊ ΠΈ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ. Учитывая Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (3), Π½Π΅Ρ‚Ρ€ΡƒΠ΄Π½ΠΎ Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Π°Ρ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ, содСрТащСй Ρ€ΠΎΠ²Π½ΠΎ n Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Π΅ΡΡ‚ΡŒ Π΅Π΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ:

1) всС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹;

2) каТдая ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ содСрТит Ρ€ΠΎΠ²Π½ΠΎ n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…;

3) Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‚ΡΡ всС n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

На ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ 1 ΠΌΡ‹ рассмотрСли ΠΎΠ΄ΠΈΠ½ ΠΈΠ· способов построСния БДНЀ, основанный Π½Π° составлСнии Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. Π‘Π»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ способ построСния БДНЀ основан Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ Π·Π°ΠΊΠΎΠ½ΠΎΠ² Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 5. Найти ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ .

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ, Ρ‡Ρ‚ΠΎ , ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ . Π’Π²ΠΈΠ΄Ρƒ Π·Π°ΠΊΠΎΠ½ΠΎΠ² Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π° ΠΈ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ отрицания ΠΈΠΌΠ΅Π΅ΠΌ:

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ. Данная ДНЀ Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π° Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ .

Раскрывая скобки, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ:

.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π·Π°ΠΊΠΎΠ½ идСмпотСнтности, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Ρ‚Ρ€Π΅Π±ΡƒΠ΅ΠΌΡƒΡŽ БДНЀ:

.

Учитывая Ρ€Π°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ (6), Π½Π΅Ρ‚Ρ€ΡƒΠ΄Π½ΠΎ Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Π°Ρ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ, содСрТащСй Ρ€ΠΎΠ²Π½ΠΎ N Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Π΅ΡΡ‚ΡŒ Π΅Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ:

1) всС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹;

2) каТдая Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ содСрТит Ρ€ΠΎΠ²Π½ΠΎ n Ρ‡Π»Π΅Π½ΠΎΠ²;

3) Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‚ΡΡ всС n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

На ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ 2 ΠΌΡ‹ рассмотрСли ΠΎΠ΄ΠΈΠ½ ΠΈΠ· способов построСния БКНЀ, основанный Π½Π° составлСнии Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. Π‘Π»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ способ построСния БКНЀ основан Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ Π·Π°ΠΊΠΎΠ½ΠΎΠ² Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 6. Найти ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹

.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ, Ρ‡Ρ‚ΠΎ , ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ

.

Данная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° являСтся ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ. Она Ρ€Π°Π²Π½ΠΎΡΠΈΠ»ΡŒΠ½Π° Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅

.

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π·Π°ΠΊΠΎΠ½ дистрибутивности, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ:

ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΡ Π·Π°ΠΊΠΎΠ½ идСмпотСнтности, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Ρ‚Ρ€Π΅Π±ΡƒΠ΅ΠΌΡƒΡŽ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΡƒΡŽ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΡƒΡŽ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ

.

Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ называСтся ВоТдСствСнно истинной, Ссли ΠΎΠ½Π° ΠΏΡ€ΠΈ всСх значСниях входящих Π² Π½Π΅Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ истинно.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ тоТдСствСнно истинных Ρ„ΠΎΡ€ΠΌΡƒΠ» ΡΠ²Π»ΡΡŽΡ‚ΡΡ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹:

Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ называСтся ВоТдСствСнно Π»ΠΎΠΆΠ½ΠΎΠΉ, Ссли ΠΎΠ½Π° ΠΏΡ€ΠΈ всСх значСниях, входящих Π² Π½Π΅Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π›ΠΎΠΆΡŒ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ тоТдСствСнно Π»ΠΎΠΆΠ½Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌΡƒΠ» ΡΠ²Π»ΡΡŽΡ‚ΡΡ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹:

,

Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ называСтся Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΠΎΠΉ, Ссли ΠΎΠ½Π° ΠΏΡ€ΠΈ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… значСниях, входящих Π² Π½Π΅Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π˜ΡΡ‚ΠΈΠ½Π½ΠΎ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΡ‹Ρ… Ρ„ΠΎΡ€ΠΌΡƒΠ» ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹:

, .

Π’ Π°Π»Π³Π΅Π±Ρ€Π΅ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ: ΡƒΠΊΠ°Π·Π°Ρ‚ΡŒ способ (Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ), ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‰ΠΈΠΉ для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ Π²Ρ‹ΡΡΠ½ΠΈΡ‚ΡŒ, являСтся ΠΎΠ½Π° тоТдСствСнно истинной ΠΈΠ»ΠΈ Π½Π΅Ρ‚. ΠŸΠΎΡΡ‚Π°Π²Π»Π΅Π½Π½Π°Ρ Π·Π°Π΄Π°Ρ‡Π° носит Π½Π°Π·Π²Π°Π½ΠΈΠ΅ ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ Ρ€Π°Π·Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ.

Рассмотрим ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π΄Π²Π° способа Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ этой Π·Π°Π΄Π°Ρ‡ΠΈ.

Бпособ 1 (Ρ‚Π°Π±Π»ΠΈΡ‡Π½Ρ‹ΠΉ). Для Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, являСтся Π»ΠΈ данная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° тоТдСствСнно истинной ΠΈΠ»ΠΈ Π½Π΅Ρ‚, достаточно ΡΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π΅Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности.

Однако Π΄Π°Π½Π½Ρ‹ΠΉ способ, хотя ΠΈ Π΄Π°Π΅Ρ‚ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΠΈ, ΠΎΠ½ довольно Π³Ρ€ΠΎΠΌΠΎΠ·Π΄ΠΊΠΈΠΉ.

Бпособ 2 основан Π½Π° ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠΈ Ρ„ΠΎΡ€ΠΌΡƒΠ» ΠΊ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 4. Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π° являСтся тоТдСствСнно истинной, ΠΊΠΎΠ³Π΄Π° каТдая Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π² Π΅Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ содСрТит Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ вмСстС с Π΅Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ.

Π”Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ, Ссли каТдая Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π² ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ содСрТит ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ вмСстС с Π΅Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ, Ρ‚ΠΎ всС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π²Π½Ρ‹ 1, ΠΈΠ±ΠΎ , . ΠžΡ‚ΡΡŽΠ΄Π° слСдуСт, Ρ‡Ρ‚ΠΎ КНЀ являСтся тоТдСствСнно истинной.

ΠŸΡƒΡΡ‚ΡŒ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ данная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° являСтся тоТдСствСнно истинной, ΠΈ ΠΏΡƒΡΡ‚ΡŒ Π΅ΡΡ‚ΡŒ нСкоторая Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π² КНЀ Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹. Допустим, Ρ‡Ρ‚ΠΎ данная Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π½Π΅ содСрТит ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ вмСстС с Π΅Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ. Π’ Ρ‚Π°ΠΊΠΎΠΌ случаС ΠΌΡ‹ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ, Π½Π΅ стоящСй ΠΏΠΎΠ΄ Π·Π½Π°ΠΊΠΎΠΌ отрицания, Π΄Π°Ρ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 0, Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ, стоящСй ΠΏΠΎΠ΄ Π·Π½Π°ΠΊΠΎΠΌ отрицания – Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 1. ПослС ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠΉ подстановки всС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ станут Ρ€Π°Π²Π½Ρ‹ 0, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° Π½Π΅ являСтся тоТдСствСнно истинной. ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΡ€Π΅Ρ‡ΠΈΠ΅.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 7. Π’Ρ‹ΡΡΠ½ΠΈΡ‚ΡŒ, Π±ΡƒΠ΄Π΅Ρ‚ Π»ΠΈ тоТдСствСнно истинной Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ, Ρ‡Ρ‚ΠΎ , ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ

.

ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΡ Π·Π°ΠΊΠΎΠ½ дистрибутивности, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ КНЀ:

.

Π’Π°ΠΊ ΠΊΠ°ΠΊ каТдая Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ содСрТит Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ вмСстС с Π΅Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ, Ρ‚ΠΎ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° тоТдСствСнно истинна.

Аналогично ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅ΠΉ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ΅ доказываСтся Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°:

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 5. Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π° являСтся тоТдСствСнно Π»ΠΎΠΆΠ½ΠΎΠΉ, ΠΊΠΎΠ³Π΄Π° каТдая ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π² Π΅Π΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ содСрТит Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ вмСстС с Π΅Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ.

3.2 АлгСбра Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°. ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, рассматриваСм вмСстС с опСрациями ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΈ слоТСния (ΠΏΠΎ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ Π΄Π²Π°), Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ Π°Π»Π³Π΅Π±Ρ€ΠΎΠΉ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°.

НСпосрСдствСнно ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΎΠΉ (с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Ρ‚Π°Π±Π»ΠΈΡ† истинности) ΡƒΡΡ‚Π°Π½Π°Π²Π»ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π·Π°ΠΊΠΎΠ½Ρ‹:

— Π·Π°ΠΊΠΎΠ½ коммутативности;

— Π·Π°ΠΊΠΎΠ½ ассоциативности;

— Π·Π°ΠΊΠΎΠ½ дистрибутивности;

Π’ Π°Π»Π³Π΅Π±Ρ€Π΅ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° Ρ€ΠΎΠ»ΡŒ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Ρ‹Ρ… Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Ρ„ΠΎΡ€ΠΌ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Ρ‹ ΠΈΠ³Ρ€Π°ΡŽΡ‚ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΡ‹ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°.

Полиномом Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° называСтся ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Π²ΠΈΠ΄Π°

ΠŸΡ€ΠΈΡ‡Π΅ΠΌ Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ Π½Π°Π±ΠΎΡ€Π΅ всС ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρ‹ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹, Π° суммированиС вСдСтся ΠΏΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ мноТСству Ρ‚Π°ΠΊΠΈΡ… Π½Π΅ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡŽΡ‰ΠΈΡ… Π½Π°Π±ΠΎΡ€ΠΎΠ², А – константа 0 ΠΈΠ»ΠΈ 1.

НапримСр, Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ являСтся ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°, Π° выраТСния ΠΈ Π½Π΅Ρ‚, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π² ΠΏΠ΅Ρ€Π²ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ имССтся ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ, содСрТащая Π΄Π²Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ y, Π° Π²Ρ‚ΠΎΡ€ΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ содСрТит Π΄Π²Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… слагаСмых ΠΈ .

Если Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° Ρ€Π°ΡΠΊΡ€Ρ‹Ρ‚ΡŒ скобки ΠΈ произвСсти всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ упрощСния ΠΏΠΎ ΡƒΠΊΠ°Π·Π°Π½Π½Ρ‹ΠΌ Π²Ρ‹ΡˆΠ΅ Π·Π°ΠΊΠΎΠ½Π°ΠΌ ΠΈ Π·Π°ΠΊΠΎΠ½Ρƒ идСмпотСнтности, Ρ‚ΠΎ получится Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°, ΡΠ²Π»ΡΡŽΡ‰Π°ΡΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°.

Рассмотрим Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ взаимосвязь, ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΡƒΡŽ ΠΌΠ΅ΠΆΠ΄Ρƒ опСрациями Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Ρ‹ ΠΈ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°. НСпосрСдствСнной ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΎΠΉ устанавливаСтся

(1)

Π Π°Π½Π΅Π΅ ΠΌΡ‹ ΠΏΠΎΠΊΠ°Π·Π°Π»ΠΈ, Ρ‡Ρ‚ΠΎ любая Π±ΡƒΠ»Π΅Π²Π° функция ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° Π² Π²ΠΈΠ΄Π΅ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Ρ‡Π΅Ρ€Π΅Π· ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅, ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ ΠΈ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ. Богласно Π·Π°ΠΊΠΎΠ½Π°ΠΌ (1) ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ любая Π±ΡƒΠ»Π΅Π²Π° функция ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° Π² Π²ΠΈΠ΄Π΅ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, сущСствованиС ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° Π΄ΠΎΠΊΠ°Π·Π°Π½ΠΎ для любой Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

Число Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… слагаСмых (ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ) ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° ΠΎΡ‚ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Ρ€Π°Π²Π½ΠΎ числу всСх подмноТСств ΠΈΠ· n элСмСнтов, Ρ‚. Π΅. 2n. Число Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΠ· этих ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ, Ρ€Π°Π²Π½ΠΎ числу всСх подмноТСств мноТСства Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ, Ρ‚. Π΅. . Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, число всСх ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠ² Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π° ΠΎΡ‚ n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Ρ€Π°Π²Π½ΠΎ числу всСх Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΎΡ‚ n ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. ΠžΡ‚ΡΡŽΠ΄Π° слСдуСт СдинствСнноС прСдставлСниС Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ посрСдством ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°. Π˜Ρ‚Π°ΠΊ, справСдлива ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ° 6. КаТдая Π±ΡƒΠ»Π΅Π²Π° функция ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ СдинствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 8. Π’Ρ‹Ρ€Π°Π·ΠΈΡ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π–Π΅Π³Π°Π»ΠΊΠΈΠ½Π°.

1 способ. Π˜Ρ‰Π΅ΠΌ Ρ‚Ρ€Π΅Π±ΡƒΠ΅ΠΌΡ‹ΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π½Π΅ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… коэффициСнтов: .

ΠŸΡ€ΠΈ X=y=0 ΠΈΠΌΠ΅Π΅ΠΌ: d=1;

ΠŸΡ€ΠΈ X=0, y=1 ΠΈΠΌΠ΅Π΅ΠΌ: a=0;

ΠŸΡ€ΠΈ X=1, y=0 ΠΈΠΌΠ΅Π΅ΠΌ: b=1;

ΠŸΡ€ΠΈ X=1, y=0 ΠΈΠΌΠ΅Π΅ΠΌ: 1=a+b+c+d =a+1+0+1=a, Ρ‚. Π΅. Π°=1.

ΠžΡ‚ΡΡŽΠ΄Π°

2 способ.


< ΠŸΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π°Ρ Β  Π‘Π»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ >

ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΊ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅.

Заглавная страница
Π˜Π·Π±Ρ€Π°Π½Π½Ρ‹Π΅ ΡΡ‚Π°Ρ‚ΡŒΠΈ
Блучайная ΡΡ‚Π°Ρ‚ΡŒΡ
ΠŸΠΎΠ·Π½Π°Π²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΡΡ‚Π°Ρ‚ΡŒΠΈ
НовыС добавлСния
ΠžΠ±Ρ€Π°Ρ‚Π½Π°Ρ связь

ΠšΠΠ’Π•Π“ΠžΠ Π˜Π˜:

АрхСология
Биология
Π“Π΅Π½Π΅Ρ‚ΠΈΠΊΠ°
ГСография
Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ°
Π˜ΡΡ‚ΠΎΡ€ΠΈΡ
Π›ΠΎΠ³ΠΈΠΊΠ°
ΠœΠ°Ρ€ΠΊΠ΅Ρ‚ΠΈΠ½Π³
ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ°
ΠœΠ΅Π½Π΅Π΄ΠΆΠΌΠ΅Π½Ρ‚
ΠœΠ΅Ρ…Π°Π½ΠΈΠΊΠ°
ПСдагогика
РСлигия
Боциология
Π’Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΈ
Π€ΠΈΠ·ΠΈΠΊΠ°
Ѐилософия
Ѐинансы
Π₯имия
Экология

ВОП 10 Π½Π° сайтС

ΠŸΡ€ΠΈΠ³ΠΎΡ‚ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ Π΄Π΅Π·ΠΈΠ½Ρ„ΠΈΡ†ΠΈΡ€ΡƒΡŽΡ‰ΠΈΡ… растворов Ρ€Π°Π·Π»ΠΈΡ‡Π½ΠΎΠΉ ΠΊΠΎΠ½Ρ†Π΅Π½Ρ‚Ρ€Π°Ρ†ΠΈΠΈ

Π’Π΅Ρ…Π½ΠΈΠΊΠ° Π½ΠΈΠΆΠ½Π΅ΠΉ прямой ΠΏΠΎΠ΄Π°Ρ‡ΠΈ мяча.

Π€Ρ€Π°Π½ΠΊΠΎ-прусская Π²ΠΎΠΉΠ½Π° (ΠΏΡ€ΠΈΡ‡ΠΈΠ½Ρ‹ ΠΈ послСдствия)

ΠžΡ€Π³Π°Π½ΠΈΠ·Π°Ρ†ΠΈΡ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½ΠΎΠ³ΠΎ ΠΊΠ°Π±ΠΈΠ½Π΅Ρ‚Π°

БмысловоС ΠΈ мСханичСскоС Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°Π½ΠΈΠ΅, ΠΈΡ… мСсто ΠΈ Ρ€ΠΎΠ»ΡŒ Π² усвоСнии Π·Π½Π°Π½ΠΈΠΉ

ΠšΠΎΠΌΠΌΡƒΠ½ΠΈΠΊΠ°Ρ‚ΠΈΠ²Π½Ρ‹Π΅ Π±Π°Ρ€ΡŒΠ΅Ρ€Ρ‹ ΠΈ ΠΏΡƒΡ‚ΠΈ ΠΈΡ… прСодолСния

ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ΠΈΠ·Π΄Π΅Π»ΠΈΠΉ мСдицинского назначСния ΠΌΠ½ΠΎΠ³ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎΠ³ΠΎ примСнСния

ΠžΠ±Ρ€Π°Π·Ρ†Ρ‹ тСкста публицистичСского стиля

Π§Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ‚ΠΈΠΏΠ° измСнСния баланса

Π—Π°Π΄Π°Ρ‡ΠΈ с ΠΎΡ‚Π²Π΅Ρ‚Π°ΠΌΠΈ для ВсСроссийской ΠΎΠ»ΠΈΠΌΠΏΠΈΠ°Π΄Ρ‹ ΠΏΠΎ ΠΏΡ€Π°Π²Ρƒ



ΠœΡ‹ ΠΏΠΎΠΌΠΎΠΆΠ΅ΠΌ Π² написании Π²Π°ΡˆΠΈΡ… Ρ€Π°Π±ΠΎΡ‚!

ЗНАЕВЕ Π›Π˜ Π’Π«?

ВлияниС общСства Π½Π° Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊΠ°

ΠŸΡ€ΠΈΠ³ΠΎΡ‚ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ Π΄Π΅Π·ΠΈΠ½Ρ„ΠΈΡ†ΠΈΡ€ΡƒΡŽΡ‰ΠΈΡ… растворов Ρ€Π°Π·Π»ΠΈΡ‡Π½ΠΎΠΉ ΠΊΠΎΠ½Ρ†Π΅Π½Ρ‚Ρ€Π°Ρ†ΠΈΠΈ

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΠΎ Π³Π΅ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ для 6 класса

ΠžΡ€Π³Π°Π½ΠΈΠ·Π°Ρ†ΠΈΡ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½ΠΎΠ³ΠΎ ΠΊΠ°Π±ΠΈΠ½Π΅Ρ‚Π°

ИзмСнСния Π² Π½Π΅ΠΆΠΈΠ²ΠΎΠΉ ΠΏΡ€ΠΈΡ€ΠΎΠ΄Π΅ осСнью

Π£Π±ΠΎΡ€ΠΊΠ° ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π½ΠΎΠ³ΠΎ ΠΊΠ°Π±ΠΈΠ½Π΅Ρ‚Π°

Π‘ΠΎΠ»ΡŒΡ„Π΅Π΄ΠΆΠΈΠΎ. ВсС ΠΏΡ€Π°Π²ΠΈΠ»Π° ΠΏΠΎ ΡΠΎΠ»ΡŒΡ„Π΅Π΄ΠΆΠΈΠΎ

Π‘Π°Π»ΠΎΡ‡Π½Ρ‹Π΅ систСмы. ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Ρ€Π΅Π°ΠΊΡ†ΠΈΠΉ ΠΎΠΏΠΎΡ€ ΠΈ ΠΌΠΎΠΌΠ΅Π½Ρ‚ΠΎΠ² защСмлСния

⇐ ΠŸΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π°ΡΠ‘Ρ‚Ρ€ 4 ΠΈΠ· 6Π‘Π»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ β‡’

ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠΎΠΉ (КНЀ) называСтся ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ элСмСнтарных Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ. ΠŸΡ€ΠΈΠΌΠ΅Ρ€ КНЀ: ( )( )( ).

ΠŸΡƒΡΡ‚ΡŒ ДНЀ F ΠΈΠΌΠ΅Π΅Ρ‚ Π²ΠΈΠ΄ F= , Π³Π΄Π΅  – элСмСнтарныС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ.

ΠŸΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° привСдСния ДНЀ ΠΊ КНЀ:

1. ΠŸΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΊ F ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ Π΄Π²ΠΎΠΉΠ½ΠΎΠ³ΠΎ отрицания F= Β ΠΈ привСсти Β ΠΊ ДНЀ , Π³Π΄Π΅  – элСмСнтарныС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ. Π’ΠΎΠ³Π΄Π°

F= = = .

2. Π‘ ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΏΡ€Π°Π²ΠΈΠ» Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π° ΠΎΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ ΠΎΡ‚ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ отрицания ΠΈ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ отрицания элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π² элСмСнтарныС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ . Π’ΠΎΠ³Π΄Π°

F= = Γ— Γ—…Γ— = Γ— Γ—…Γ—

5. Π”Π²ΠΎΠΉΡΡ‚Π²Π΅Π½Π½ΠΎΡΡ‚ΡŒ. Ѐункция f*( ,…, ) называСтся двойствСнной ΠΊ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f ( ,…, ), Ссли f*( ,…, )= ( ,…, ).

ΠžΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠ΅ двойствСнности ΠΌΠ΅ΠΆΠ΄Ρƒ функциями симмСтрично, Ρ‚. Π΅. Ссли f* двойствСнна ΠΊ f, Ρ‚ΠΎ f двойствСнна ΠΊ f*:

( ,…, )= ( ,…, )=f*( ,…, ).

Ѐункция, двойствСнная ΠΊ самой сСбС, называСтся самодвойствСнной.

ΠŸΡ€ΠΈΠ½Ρ†ΠΈΠΏ двойствСнности: Ссли Π² Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ F, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅ΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ f, всС Π·Π½Π°ΠΊΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π·Π°ΠΌΠ΅Π½ΠΈΡ‚ΡŒ соотвСтствСнно Π½Π° Π·Π½Π°ΠΊΠΈ двойствСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, Ρ‚ΠΎ получСнная Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° F* Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ f*, Π΄Π²ΠΎΠΉΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ f.

ΠŸΡ€ΠΈΠ½Ρ†ΠΈΠΏ двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅: Ссли Π² Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ F, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰Π΅ΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ f, всС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π·Π°ΠΌΠ΅Π½ΠΈΡ‚ΡŒ Π½Π° Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ Π½Π° ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, 1 Π½Π° 0, 0 Π½Π° 1, Ρ‚ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ F*, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‰ΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ f*, Π΄Π²ΠΎΠΉΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ f.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1. Π”ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ ΠΎΠ±ΠΎΠ±Ρ‰Π΅Π½Π½ΠΎΠ³ΠΎ склСивания ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ эквивалСнтных ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ.

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌ эквивалСнтныС прСобразования:

Γ—1 .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2. ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ БДНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ эквивалСнтныС ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡ: f (x,y,z,u)=xy Ú xz Ú zu.

Β 

f( x,y,z,u)

= .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 3. Π£ΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Π±ΡƒΠ»Π΅Π²Ρ‹ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹:

Π°) ( , , ) ;

Π±) f (x,y,z) .

Β 

Π°) ( , , )

Γ—1 ;

Π±) f (x,y,z)

0Γ— Ú 0Γ—z Ú xΓ—0Ú xyz Ú Ú xzz .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 4. ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π±ΡƒΠ»Π΅Π²Ρƒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ Β Π² базисС {&,Ø} ΠΈ {Ú,Ø}.

Β 

Π°) ;

Π±) .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 5. Π£ΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ БДНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ

f (x,y,z,u)

Β 

Для эффСктивного упрощСния БДНЀ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π‘Π»Π΅ΠΉΠΊΠ°-ΠŸΠΎΡ€Π΅Ρ†ΠΊΠΎΠ³ΠΎ. ΠœΠ΅Ρ‚ΠΎΠ΄ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎΠΌ склСивании всСх элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ БДНЀ ΠΌΠ΅ΠΆΠ΄Ρƒ собой, Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… Π² процСссС склСивания элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ мСньшСго числа ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈ Π·Π°Ρ‚Π΅ΠΌ – ΠΏΠΎΠ³Π»ΠΎΡ‰Π΅Π½ΠΈΠΈ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡΠΌΠΈ мСньшСго числа ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ большСго числа ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Рассмотрим ΠΌΠ΅Ρ‚ΠΎΠ΄ Π‘Π»Π΅ΠΉΠΊΠ°-ΠŸΠΎΡ€Π΅Ρ†ΠΊΠΎΠ³ΠΎ β€œΠ² дСйствии”, для Ρ‡Π΅Π³ΠΎ ΠΏΡ€ΠΎΠ½ΡƒΠΌΠ΅Ρ€ΡƒΠ΅ΠΌ элСмСнтарныС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ БДНЀ:

1Β Β Β Β  2Β Β Β Β  3Β Β Β Β  4Β Β Β Β  5Β Β Β Β  6Β Β Β Β  7

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΏΠΎΠΏΠ°Ρ€Π½Ρ‹Π΅ склСивания элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π² БДНЀ (ΠΏΠΎΠ΄ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ склСивания проставим Π½ΠΎΠΌΠ΅Ρ€Π° склСиваСмых ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ):

1,6 1,7 2,3 2,4 2,5 3,7 4,6 4,7 5,6

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΏΠΎΠΏΠ°Ρ€Π½Ρ‹Π΅ склСивания ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Ρ‚Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…:

1,6 1,7 2,3 2,4 2,4 2,5

4,7 4,6 4,7 3,7 5,6 4,6

ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ дальнСйшСС склСиваниС Π² Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ. ОбъСдиним символом Ú всС ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎΠ³ΠΎ склСивания ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ:

f (x,y,z,u)

.

Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Π² этом Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ ΠΏΠΎΠ³Π»ΠΎΡ‰Π΅Π½ΠΈΠ΅, Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ Ρ‡Π΅Π³ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ: f (x,y,z,u)=

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 6. ΠŸΡ€ΠΈΠ²Π΅ΡΡ‚ΠΈ ΠΊ ДНЀ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ:

f (x,y,z)= .

Β 

f (x,y,z) .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 7. ΠŸΡ€ΠΈΠ²Π΅ΡΡ‚ΠΈ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ ΠΊ КНЀ:

f (x,y,z) .

f (x,y,z) .

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 8. ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ БКНЀ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f (x,y,z,u) ΠΈΠ· ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° 2.

Β 

Π’ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ 2 для Π·Π°Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f (x,y,z,u)=xyÚxzÚzu Π±Ρ‹Π»Π° ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π° БДНЀ:

f (x,y,z,u) .

Π’ΠΎΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡΡ этими Π΄Π°Π½Π½Ρ‹ΠΌΠΈ для получСния БКНЀ, для Ρ‡Π΅Π³ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΠΌ Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½ΠΎΠ΅ мноТСство Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f (x,y,z,u), Ρ‚.Π΅. мноТСство Π½Π°Π±ΠΎΡ€ΠΎΠ², Π½Π° ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… f =1:{(1111),(1101),(1110),(1100),(1011),(1010), (0111),(0011)}.

ВсСго Π½Π°Π±ΠΎΡ€ΠΎΠ² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… 24=16. ΠžΠΏΡ€Π΅Π΄Π΅Π»ΠΈΠΌ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Π½ΡƒΠ»Π΅Π²ΠΎΠ΅ мноТСство для f (x,y,z,u), Ρ‚.Π΅. мноТСство Π½Π°Π±ΠΎΡ€ΠΎΠ², Π½Π° ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… f =0: {(0000),(0001),(0010),(0100),(0101),(0110),(1000), (1001)}. ΠžΡ‚ΡΡŽΠ΄Π° ΠΏΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ построСния БКНЀ ΠΈΠ· Π½ΡƒΠ»Π΅Π²ΠΎΠ³ΠΎ мноТСства Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

f (x,y,z,u)

.

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 9. Π”ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅, исходя ΠΈΠ· ΠΎΠ±Ρ‰Π΅Π³ΠΎ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности.

Β 

НайдСм для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Ρ‹ ( ; &, Ú, Ø) двойствСнныС ΠΈΠΌ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ.

Π°) ΠŸΡƒΡΡ‚ΡŒ f (x,y)=xΓ—y. Π’ΠΎΠ³Π΄Π° f*(x,y) xÚy.

Π±) ΠŸΡƒΡΡ‚ΡŒ f (x,y)=xÚy. Π’ΠΎΠ³Π΄Π° f*(x,y) xΓ—y.

Π²) ΠŸΡƒΡΡ‚ΡŒ f (x) . Π’ΠΎΠ³Π΄Π° f*(x) .

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ двойствСнна Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ – ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ, Π° ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ самодвойствСнно.

НаконСц, константы 0 ΠΈ 1 ΠΏΡ€ΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°Ρ‚ мноТСству логичСских Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ , поэтому 0 ΠΈ 1 ΠΌΠΎΠ³ΡƒΡ‚ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒΡΡ Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ ΠΈ ΡΠ²Π»ΡΡŽΡ‚ΡΡ двойствСнными Π΄Ρ€ΡƒΠ³ ΠΊ Π΄Ρ€ΡƒΠ³Ρƒ: Ссли ( ,…, )=0, Ρ‚ΠΎ f*( ,…, ) ( ,. .., ) 1. Аналогично, Ссли f =1, Ρ‚ΠΎ f*=0.

ΠžΡ‚ΡΡŽΠ΄Π° слСдуСт ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅.

Β 

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 10. ΠŸΡƒΡΡ‚ΡŒ f (x,y,z) . Найти ДНЀ двойствСнной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f*(x,y,z), исходя ΠΈΠ·:

Π°) опрСдСлСния двойствСнности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ;

Π±) ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅.

Β 

Π°) f*(x,y,z) xz;

Π±) f*(x,y,z) xz.

Β 

Β 

Вопросы для самопровСрки ΠΈ упраТнСния.

1. Π”ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ эквивалСнтных ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠΉ ΠΏ.11, ΠΏ.12, ΠΏ.13.

2. Π£ΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ БДНЀ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π¨Π΅Ρ„Ρ„Π΅Ρ€Π°, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ эквивалСнтныС ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡ.

3. ЛогичСская функция ( , , ) прСдставлСна Ρ„ΠΎΡ€ΠΌΡƒΠ»ΠΎΠΉ ( , , ) . Π£ΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ БДНЀ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ:

Π°) Ρ‚Π°Π±Π»ΠΈΡ‡Π½ΠΎΠ΅ прСдставлСниС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f ;

Π±) расщСплСниС (ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠ΅ склСиваниС).

4. Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… Π² Π²ΠΈΠ΄Π΅ ДНЀ, ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ БДНЀ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ эквивалСнтныС прСобразования, ΠΈ ΡƒΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ БДНЀ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π‘Π»Π΅ΠΉΠΊΠ°-ΠŸΠΎΡ€Π΅Ρ†ΠΊΠΎΠ³ΠΎ, описанный Π² ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ 5.

Π°) f (x,y,z) ;Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β  Π³) f (x,y,z) ;

Π±) f (x,y,z) ;Β Β Β Β Β Β Β Β  Π΄) f (x,y,z) .

Π²) f (x,y,z) ;

5. ΠŸΡ€ΠΈΠ²Π΅ΡΡ‚ΠΈ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ ΠΊ ДНЀ:

Π°) ( , , ) ;

Π±) ( , , ) ;

Π²) ( , , ) ;

Π³) ( , , ) .

6. Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ( , , ), Π·Π°Π΄Π°Π½Π½Ρ‹Ρ… Π² ΡƒΠΏΡ€Π°ΠΆΠ½Π΅Π½ΠΈΠΈ 5:

1) ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ КНЀ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ привСдСния ДНЀ ΠΊ КНЀ;

2) Π½Π°ΠΉΡ‚ΠΈ БДНЀ ΠΈ БКНЀ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Ρ‚Π°Π±Π»ΠΈΡ‡Π½ΠΎΠ΅ прСдставлСниС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

7. ΠŸΠΎΠ΄Ρ‚Π²Π΅Ρ€Π΄ΠΈΡ‚ΡŒ ΡΠ°ΠΌΠΎΠ΄Π²ΠΎΠΉΡΡ‚Π²Π΅Π½Π½ΠΎΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f (x,y,z)= , ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏ двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅.

8. Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ( , , ) Π½Π°ΠΉΡ‚ΠΈ ДНЀ двойствСнной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ f*( , , ), исходя ΠΈΠ·:

1) опрСдСлСния двойствСнной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ;

2) ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ° двойствСнности Π² Π±ΡƒΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±Ρ€Π΅:

Π°) ( , , ) ;

Π±) ( , , ) ;

Π²) ( , , ) .

9. ΠœΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ эквивалСнтных ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ ΠΏΠΎΠ΄Ρ‚Π²Π΅Ρ€Π΄ΠΈΡ‚ΡŒ ΡΠΏΡ€Π°Π²Π΅Π΄Π»ΠΈΠ²ΠΎΡΡ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ» 9, 12 Β§1.2 логичСски ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½Ρ‹Ρ… рассуТдСний.

10. Π£Π±Π΅Π΄ΠΈΡ‚ΡŒΡΡ Π² Π½Π΅ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΡΡ‚ΠΈ рассуТдСний Π°)–в), ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Ρ‹Ρ… Π² Β§1.2:

Π°) стандартным ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ;

Π±) ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ эквивалСнтных ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ.

Β 

Β 

⇐ ΠŸΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π°Ρ123456Π‘Π»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ β‡’


Π§ΠΈΡ‚Π°ΠΉΡ‚Π΅ Ρ‚Π°ΠΊΠΆΠ΅:

ο»Ώ

Π“Π΄Π΅ Π²ΠΎΠ·Π½ΠΈΠΊΠ»Π° философия ΠΈ ΠΏΠΎΡ‡Π΅ΠΌΡƒ?

ΠžΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ высота сТатой Π·ΠΎΠ½Ρ‹ Π±Π΅Ρ‚ΠΎΠ½Π°

Π‘ΡƒΡ‰Π½ΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΎΠ΅ΠΊΡ†ΠΈΠΈ Гаусса-ΠšΡ€ΡŽΠ³Π΅Ρ€Π° ΠΈ использованиС Π΅Π΅ Π² Π³Π΅ΠΎΠ΄Π΅Π·ΠΈΠΈ

Π’Π°Ρ€ΠΈΡ„Ρ‹ Π½Π° ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ·ΠΊΡƒ пассаТиров

ο»Ώ

ПослСднСС ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ этой страницы: 2021-06-14; просмотров: 350; ΠΠ°Ρ€ΡƒΡˆΠ΅Π½ΠΈΠ΅ авторского ΠΏΡ€Π°Π²Π° страницы; ΠœΡ‹ ΠΏΠΎΠΌΠΎΠΆΠ΅ΠΌ Π² написании вашСй Ρ€Π°Π±ΠΎΡ‚Ρ‹!

infopedia. su ВсС ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ прСдставлСнныС Π½Π° сайтС ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ с Ρ†Π΅Π»ΡŒΡŽ ознакомлСния читатСлями ΠΈ Π½Π΅ ΠΏΡ€Π΅ΡΠ»Π΅Π΄ΡƒΡŽΡ‚ коммСрчСских Ρ†Π΅Π»Π΅ΠΉ ΠΈΠ»ΠΈ Π½Π°Ρ€ΡƒΡˆΠ΅Π½ΠΈΠ΅ авторских ΠΏΡ€Π°Π². ΠžΠ±Ρ€Π°Ρ‚Π½Π°Ρ связь — 161.97.168.212 (0.004 с.)

Π»ΠΎΠ³ΠΈΠΊΠ° — ΠŸΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ CNF Π² DNF

спросил

ИзмСнСно 3 года назад

ΠŸΡ€ΠΎΡΠΌΠΎΡ‚Ρ€Π΅Π½ΠΎ 675 Ρ€Π°Π·

$\begingroup$

Π£ мСня Π΅ΡΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°

$(L\Leftrightarrow (A\vee J))$

ΠΈ я Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΡ€Π΅Π²Ρ€Π°Ρ‚ΠΈΡ‚ΡŒ Π΅Π΅ Π² DNF ΠΈ CNF. Когда я ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽ ΠΏΡ€Π°Π²ΠΈΠ»Π° Π΄Π΅ ΠœΠΎΡ€Π³Π°Π½Π° ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅, Ρ„ΠΎΡ€ΠΌΡƒΠ»Π° выглядит ΠΊΠ°ΠΊ

$(L\Π‘Ρ‚Ρ€Π΅Π»ΠΊΠ° Π²ΠΏΡ€Π°Π²ΠΎ (A\vee J))\ΠΊΠ»ΠΈΠ½ ((A\vee J)\Π‘Ρ‚Ρ€Π΅Π»ΠΊΠ° Π²ΠΏΡ€Π°Π²ΠΎ L)$

$(\lnot L\vee (A\vee J))\ΠΊΠ»ΠΈΠ½ ((\lnot A\wedge \lnot J)\vee L)$

CNF довольно просто Π΅Π³ΠΎ

$(\lnot L \vee A\vee J)\wedge (L\vee \lnot A)\wedge (L\vee \lnot J)$

Но ΠΊΠ°ΠΊ ΠΌΠ½Π΅ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ ΠΈΠ· этой Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ ДНЀ?

  • Π»ΠΎΠ³ΠΈΠΊΠ°
  • исчислСниС высказываний
  • ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°
  • Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°

$\endgroup$

5

$\begingroup$

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ способ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ДНЀ, логичСски ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ $L \Leftrightarrow (A \lor J)$, состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Π½Π° Π΅Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности ΠΈ Β«ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒΒ» Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΡƒΡŽ Β«Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈΒ» строк, для ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… $ L \Leftrightarrow (A \lor J)$ Π²Π΅Ρ€Π½ΠΎ.

$\begin{массив}{ccccc} A & J & L & A \lor J & L \Leftrightarrow (A \lor J) \\ \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{t} & \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{t} & \mathtt{f} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{f} & \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{f} & \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{f} & \mathtt{f} & \mathtt{t} & \mathtt{f} & \mathtt{f} \\ \mathtt{f} & \mathtt{f} & \mathtt{f} & \mathtt{f} & \mathtt{t} \\ \end{массив}$

Π€ΠΎΡ€ΠΌΡƒΠ»Π° $L \Leftrightarrow (A \lor J)$ Π²Π΅Ρ€Π½Π° Π² строкС 1 (Ρ‡Ρ‚ΠΎ соотвСтствуСт Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ $A \land J \land L$), строкС 3 (Ρ‡Ρ‚ΠΎ соотвСтствуСт Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ $A \land \ lnot J \land L$), строка 5 (соотвСтствуСт Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ $\lnot A \land J \land L$) ΠΈ строка 8 (соотвСтствуСт Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ $\lnot A \land \lnot J \land \ Π½Π΅ L$). Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ДНЀ, логичСски эквивалСнтная $L \Leftrightarrow (A \lor J)$, Π΅ΡΡ‚ΡŒ \begin{ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅*} (A \land J \land L) \lor (A \lnot J \land L) \lor (\lnot A \land J \land L) \lor (\lnot A \land \lnot J \land \lnot Π»). \end{ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅*}

$\endgroup$

Π—Π°Ρ€Π΅Π³ΠΈΡΡ‚Ρ€ΠΈΡ€ΡƒΠΉΡ‚Π΅ΡΡŒ ΠΈΠ»ΠΈ Π²ΠΎΠΉΠ΄ΠΈΡ‚Π΅ Π² систСму

Π—Π°Ρ€Π΅Π³ΠΈΡΡ‚Ρ€ΠΈΡ€ΡƒΠΉΡ‚Π΅ΡΡŒ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Google

Π—Π°Ρ€Π΅Π³ΠΈΡΡ‚Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒΡΡ Ρ‡Π΅Ρ€Π΅Π· Facebook

Π—Π°Ρ€Π΅Π³ΠΈΡΡ‚Ρ€ΠΈΡ€ΡƒΠΉΡ‚Π΅ΡΡŒ, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΡΠ»Π΅ΠΊΡ‚Ρ€ΠΎΠ½Π½ΡƒΡŽ ΠΏΠΎΡ‡Ρ‚Ρƒ ΠΈ ΠΏΠ°Ρ€ΠΎΠ»ΡŒ

ΠžΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΊ Π³ΠΎΡΡ‚ΡŒ

ЭлСктронная ΠΏΠΎΡ‡Ρ‚Π°

ВрСбуСтся, Π½ΠΎ Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ отобраТаСтся

ΠžΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Ρ‚ΡŒ ΠΊΠ°ΠΊ Π³ΠΎΡΡ‚ΡŒ

ЭлСктронная ΠΏΠΎΡ‡Ρ‚Π°

ВрСбуСтся, Π½ΠΎ Π½Π΅ отобраТаСтся

НаТимая Β«ΠžΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Ρ‚ΡŒ свой ΠΎΡ‚Π²Π΅Ρ‚Β», Π²Ρ‹ ΡΠΎΠ³Π»Π°ΡˆΠ°Π΅Ρ‚Π΅ΡΡŒ с нашими условиями обслуТивания, ΠΏΠΎΠ»ΠΈΡ‚ΠΈΠΊΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ΄Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΈ ΠΏΠΎΠ»ΠΈΡ‚ΠΈΠΊΠΎΠΉ использования Ρ„Π°ΠΉΠ»ΠΎΠ² cookie

. Π›ΠΎΠ³ΠΈΠΊΠ°

— ΠŸΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ DNF Π² CNF

спросил

ИзмСнСно 9 мСсяцСв Π½Π°Π·Π°Π΄

ΠŸΡ€ΠΎΡΠΌΠΎΡ‚Ρ€Π΅Π½ΠΎ 36 тысяч Ρ€Π°Π·

$\begingroup$

Π― Π½Π΅ понимаю, ΠΊΠ°ΠΊ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ DNF Π² CNF. Π’ Π±Π»Π°Π½ΠΊΠ΅ для ΠΎΡ‚Π²Π΅Ρ‚ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠ½Π΅ Π΄Π°Π»Π° моя ΡƒΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΈΡ†Π°, ΠΎΠ½Π° сразу ΠΆΠ΅ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π»Π° Π΅Π³ΠΎ Π±Π΅Π· ΠΊΠ°ΠΊΠΈΡ…-Π»ΠΈΠ±ΠΎ объяснСний. Π›ΡŽΠ±Π°Ρ ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ Π·Π΄ΠΎΡ€ΠΎΠ²ΠΎ.

Мой ΡƒΡ‡ΠΈΡ‚Π΅Π»ΡŒ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π» $F: (A \wedge \neg B) \vee (B \wedge D)$ Π² CNF-Ρ„ΠΎΡ€ΠΌΡƒ $(A \vee B) \wedge (\neg B \vee D)$. Как это происходит? Π•ΡΡ‚ΡŒ Π»ΠΈ способ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π³ΠΎ Π±Π΅Π· рисования Ρ‚Π°Π±Π»ΠΈΡ† истинности?

  • Π»ΠΎΠ³ΠΈΠΊΠ°
  • исчислСниС высказываний
  • ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°
  • Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ°

$\endgroup$

0

$\begingroup$

Π—Π°ΠΊΠΎΠ½ Π”Π΅ ΠœΠΎΡ€Π³Π°Π½Π° гласит: $\neg(a + b) \equiv \neg a\neg b $ ΠΈ $\neg(ab) \equiv \neg a + \neg b$. $$\begin{equation} \begin{aligned}A\neg B + BD \equiv & \neg(\neg(A\neg B)\neg(BD)) \text{ Π”Π΅ ΠœΠΎΡ€Π³Π°Π½ снаруТи} \\ \equiv & \neg((\neg A + B)(\neg B + \neg D)) \text{ Π’Π½ΡƒΡ‚Ρ€ΠΈ Π”Π΅ ΠœΠΎΡ€Π³Π°Π½Π°} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D + B \neg D) \text{ Π”ΠΈΡΡ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D (\neg B + B) + B \neg D) \text{ Π”ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅} \\ \neg & \neg(\neg A \neg B + \neg A \neg D \neg B + \neg A \neg D B + B \neg D) \text{ РаспрСдСлСниС} \\ \equiv & \neg(\neg A \neg B(1 + \neg D) + B \neg D (1 + \neg A)) \text{ РаспрСдСлСниС} \\ \equiv & \neg(\neg A \neg B + B \neg D) \ text{ Аннигилятор} \\ \equiv & (A + B)(\neg B + D) \text{ Π‘Π½Π°Ρ€ΡƒΠΆΠΈ Π”Π΅ ΠœΠΎΡ€Π³Π°Π½Π°}\end{aligned}\end{equation} $$

Π’Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΈΠ·ΡƒΡ‡ΠΈΡ‚ΡŒ К-ΠΊΠ°Ρ€Ρ‚Ρ‹.

$\endgroup$

5

$\begingroup$

Π― Π΄ΡƒΠΌΠ°ΡŽ, Ρ‡Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ простой способ, Ρ‡Π΅ΠΌ принятый ΠΎΡ‚Π²Π΅Ρ‚:

$$\begin{equation} \begin{aligned}A\neg B \vee BD \equiv & (A \vee B)(A \vee D)(\neg B \vee B)(\neg B \vee D) \text{ Π”ΠΈΡΡ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ} \\ \equiv & (A \vee B)(A \vee D) 1 (\neg B \vee D) \text{ Tertium non datur} \\ \equiv & (A \vee B)(A \vee D)(\neg B \vee D) \text{ ΠΠ΅ΠΉΡ‚Ρ€Π°Π»ΡŒΠ½Ρ‹ΠΉ элСмСнт $\wedge$} \\ \equiv & (A \vee B)(\neg B \vee D) \text{ срСдний Ρ‚Π΅Ρ€ΠΌΠΈΠ½ лишний*} \end{Π²Ρ‹Ρ€Π°Π²Π½ΠΈΠ²Π°Π½ΠΈΠ΅}\end{ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠ΅} $$

* $A\vee D$ Π»ΠΎΠΆΠ½ΠΎ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² Ρ‚ΠΎΠΌ случаС, Ссли ΠΈ A, ΠΈ D Π»ΠΎΠΆΠ½Ρ‹, Π½ΠΎ Ρ‚ΠΎΠ³Π΄Π° вСсь Ρ‚Π΅Ρ€ΠΌΠΈΠ½ Π² любом случаС Π»ΠΎΠΆΠ΅Π½, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ ΠΎΠ½ сводится ΠΊ $(B)(A \vee D)(\neg B)$.

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

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