ΠΡΠ»Π΅Π²Π° Π°Π»Π³Π΅Π±ΡΠ° Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (Π°Π»Π³Π΅Π±ΡΠ° Π»ΠΎΠ³ΠΈΠΊΠΈ)
![Π Π΅ΡΠ΅ΡΠ°Ρ: ΠΡΠ»Π΅Π²Π° Π°Π»Π³Π΅Π±ΡΠ° Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (Π°Π»Π³Π΅Π±ΡΠ° Π»ΠΎΠ³ΠΈΠΊΠΈ)](https://gugn.ru/work/8736923/cover.png)
ΠΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡ, Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΎΠΆΠ΄Π΅ΡΡΠ²Π΅Π½Π½ΡΠΌΠΈ ΠΈΠ»ΠΈ ΡΠ°Π²Π½ΠΎΡΠΈΠ»ΡΠ½ΡΠΌΠΈ. ΠΠΈΠ·ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ — Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅, ΠΈΡΡΠΈΠ½Π½ΠΎΠ΅ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΡΡΠΈΠ½Π½ΠΎ Ρ ΠΎΡΡ Π±Ρ ΠΎΠ΄Π½ΠΎ ΠΈΠ· Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ. Π‘Π»Π΅Π΄ΡΡΠ²ΠΈΠ΅. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ»Π°ΡΡΠΎΠ² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ Π±ΡΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±ΡΠΎΠΉ. ΠΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π½Π°Π΄ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡΠΌΠΈ ΠΠΈΠ·ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (V, ΠΠΠ, OR). ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ»Π°ΡΡΠΎΠ² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΡΠ»Π΅Π²Π° Π°Π»Π³Π΅Π±ΡΠ° Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (Π°Π»Π³Π΅Π±ΡΠ° Π»ΠΎΠ³ΠΈΠΊΠΈ) (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΎΠ± ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° U Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π»ΡΠ±ΠΎΠ΅ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΎΠ± ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° U, ΠΊΠΎΡΠΎΡΠΎΠ΅ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π»ΠΈΠ±ΠΎ ΠΈΡΡΠΈΠ½Π½ΠΎ, Π»ΠΈΠ±ΠΎ Π»ΠΎΠΆΠ½ΠΎ.
U = {1 2 3 4 5 6 7 8 9}.
A = «ΡΠΈΡΠ»ΠΎ ΡΠ΅ΡΠ½ΠΎΠ΅».
B = «ΡΠΈΡΠ»ΠΎ, ΠΌΠ΅Π½ΡΡΠ΅Π΅ ΠΏΡΡΠΈ».
ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΡ Π²ΡΠ΅Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ ΡΡΠΎ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅ ΠΈΡΡΠΈΠ½Π½ΠΎ.
SA = {2 4 6 8}.
SB = {1 2 3 4}.
ΠΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ ΠΏΡΡΡΠΎ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠΆΠ΄Π΅ΡΡΠ²Π΅Π½Π½ΠΎ Π»ΠΎΠΆΠ½ΡΠΌ, Π° Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ SB = U Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠΆΠ΄Π΅ΡΡΠ²Π΅Π½Π½ΠΎ ΠΈΡΡΠΈΠ½Π½ΡΠΌ.
ΠΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡ, Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΎΠΆΠ΄Π΅ΡΡΠ²Π΅Π½Π½ΡΠΌΠΈ ΠΈΠ»ΠΈ ΡΠ°Π²Π½ΠΎΡΠΈΠ»ΡΠ½ΡΠΌΠΈ.
Π Π°Π²Π½ΠΎΡΠΈΠ»ΡΠ½ΡΠ΅ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ ΠΎΠ±ΡΠ΅Π΄ΠΈΠ½ΠΈΠΌ Π² ΠΎΠ΄ΠΈΠ½ ΠΊΠ»Π°ΡΡ Π .Π. ΠΈ Π½Π΅ Π±ΡΠ΄Π΅ΠΌ ΠΈΡ ΡΠ°Π·Π΄Π΅Π»ΡΡΡ, Ρ.ΠΊ. Π²ΡΠ΅ ΠΎΠ½ΠΈ ΠΈΠΌΠ΅ΡΡ ΠΎΠ΄Π½ΠΎ ΠΈ ΡΠΎ ΠΆΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ.
ΠΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π½Π°Π΄ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡΠΌΠΈ ΠΠΈΠ·ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (V, ΠΠΠ, OR).
ΠΠΈΠ·ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ — Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅, ΠΈΡΡΠΈΠ½Π½ΠΎΠ΅ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΡΡΠΈΠ½Π½ΠΎ Ρ ΠΎΡΡ Π±Ρ ΠΎΠ΄Π½ΠΎ ΠΈΠ· Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ.
ΠΠΎΠ½ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (&, Π, AND).
ΠΠΎΠ½ΡΡΠ½ΠΊΡΠΈΠ΅ΠΉ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅, ΠΈΡΡΠΈΠ½Π½ΠΎΠ΅ ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΡΡΠΈΠ½Π½Ρ Π²ΡΠ΅ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ.
ΠΡΡΠΈΡΠ°Π½ΠΈΠ΅ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ (- Π½Π°Π΄ Π±ΡΠΊΠ²ΠΎΠΉ, ΠΠ, NOT).
ΠΡΡΠΈΡΠ°Π½ΠΈΠ΅ΠΌ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅, ΠΈΡΡΠΈΠ½Π½ΠΎΠ΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ΅ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅ Π»ΠΎΠΆΠ½ΠΎ.
A B. | A & B. | A V B. | Not A. |
Π Π. | Π. | Π. | Π. |
Π Π. | Π. | Π. | Π. |
Π Π. | Π. | Π. | Π. |
Π Π. | Π. | Π. | Π. |
Π — Π»ΠΎΠΆΠ½ΠΎ.
Π — ΠΈΡΡΠΈΠ½Π½ΠΎ.
Π£ΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ (ΠΎΡΠ½ΠΎΠ²Π° Π²ΡΠ΅ΠΉ Π°Π»Π³Π΅Π±ΡΡ Π»ΠΎΠ³ΠΈΠΊΠΈ).
ΠΠ΅ΠΆΠ΄Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ Π²ΡΠ΅Ρ ΠΊΠ»Π°ΡΡΠΎΠ² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ ΠΎΠ± ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° U ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ P (U) ΠΌΠΎΠΆΠ½ΠΎ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π²Π·Π°ΠΈΠΌΠ½ΠΎ ΠΎΠ΄Π½ΠΎΠ·Π½Π°ΡΠ½ΠΎΠ΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ Π΄ΠΈΠ·ΡΡΠ½ΠΊΡΠΈΠΈ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΎΠ±ΡΠ΅Π΄ΠΈΠ½Π΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² ΠΈΡΡΠΈΠ½Π½ΠΎΡΡΠΈ, Π° ΠΊΠΎΠ½ΡΡΠ½ΠΊΡΠΈΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΠΏΠ΅ΡΠ°ΡΠΈΡ ΠΎΡΡΠΈΡΠ°Π½ΠΈΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ.
Π‘Π»Π΅Π΄ΡΡΠ²ΠΈΠ΅. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ»Π°ΡΡΠΎΠ² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ Π±ΡΠ»Π΅Π²ΠΎΠΉ Π°Π»Π³Π΅Π±ΡΠΎΠΉ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° Π‘ΡΡΠ΅ΡΡΠ²ΡΡΡ 3 Π±ΡΠ»Π΅Π²ΡΡ Π°Π»Π³Π΅Π±ΡΡ:
P (U).
Bn.
ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΊΠ»Π°ΡΡΠΎΠ² ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½ΡΡ Π²ΡΡΠΊΠ°Π·ΡΠ²Π°Π½ΠΈΠΉ.
Π’ΡΠΈ Π±ΡΠ»Π΅Π²ΡΡ Π°Π»Π³Π΅Π±ΡΡ ΡΠ²Π»ΡΡΡΡΡ ΠΈΠ·ΠΎΠΌΠΎΡΡΠ½ΡΠΌΠΈ, Π΅ΡΠ»ΠΈ ΠΌΠ΅ΠΆΠ΄Ρ ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ ΡΠ°ΠΊΠΎΠ΅ ΠΎΠ΄Π½ΠΎΠ·Π½Π°ΡΠ½ΠΎΠ΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅, ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΡΠΎΡ ΡΠ°Π½ΡΡΡΡΡ.
ΠΠΎΠ³ΠΎΠ²ΠΎΡΠΈΠΌΡΡ ΠΊΠΎΠ½ΡΡΠ½ΠΊΡΠΈΡ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡ ΡΠΎΡΠΊΠΎΠΉ (ΠΊΠ°ΠΊ Π·Π½Π°ΠΊ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ Π² Π°Π»Π³Π΅Π±ΡΠ΅ ΡΠΈΡΠ΅Π»). ΠΠΎΠ½ΡΡΠ½ΠΊΡΠΈΡ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠ°Π½ΡΡΠ΅ Π΄ΠΈΠ·ΡΡΠ½ΠΊΡΠΈΠΈ (Π°Π½Π°Π»ΠΎΠ³ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΠΈ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ Π² Π°Π»Π³Π΅Π±ΡΠ΅ ΡΠΈΡΠ΅Π»).