Практические занятия Методические указания

ɩɨɞɮɨɪɦɭɥɨɣ ɮɨɪɦɭɥɵ X. ɇапример, ɜ ɮɨɪɦɭɥɟ (p & q) o ( r t) ɦɨɠɧɨ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨ ɜɵɞɟɥɢɬɶ ɫɥɟɞɭɸɳɢɟ ɩɨɞɮɨɪɦɭɥɵ: (p & q), ( r t), p, q, r, t, r. ɋɤɨɛɤɢ ɢɫɩɨɥɶɡɭɸɬɫɹ ɞɥɹ ɭɤɚɡɚɧɢɹ ɩɨɪɹɞɤɚ ɜɵɩɨɥɧɟɧɢɹ ɨɩɟɪɚɰɢɣ ɢ ɦɨɝɭɬ ɨɩɭɫɤɚɬɶɫɹ ɫ ɭɱɟɬɨɦ ɩɪɢɧɹɬɨɝɨ ɫɬɚɪɲɢɧɫɬɜɚ ɨɩɟɪɚɰɢɣ: , &, , o, l. ɇɚɩɪɢɦɟɪ, ɩɪɢɜɟɞɟɧɧɚɹ ɜɵɲɟ ɮɨɪɦɭɥɚ ɦɨɠɟɬ ɛɵɬɶ ɡɚɩɢɫɚɧɚ ɜ ɜɢɞɟ p&q or t, ɚ ɮɨɪɦɭɥɚ p l ((q & r) o s) - ɜ ɜɢɞɟ p l q&ros.

ɋɟɦɚɧɬɢɤɚ ɮɨɪɦɭɥ ɨɩɪɟɞɟɥɹɟɬɫɹ ɢɯ ɫɜɨɣɫɬɜɨɦ ɛɵɬɶ ɢɫɬɢɧɧɵɦɢ ɢɥɢ ɥɨɠɧɵɦɢ, ɬɨ ɟɫɬɶ ɩɪɢɧɢɦɚɬɶ ɡɧɚɱɟɧɢɟ T (true) - ɢɫɬɢɧɚ, ɢɥɢ F(false) - ɥɨɠɶ. ɂɧɬɟɪɩɪɟɬɢɪɨɜɚɬɶ ɮɨɪɦɭɥɭ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ, ɡɧɚɱɢɬ ɩɪɢɩɢɫɚɬɶ ɡɧɚɱɟɧɢɹ ɢɫɬɢɧɧɨɫɬɢ ɫɨɫɬɚɜɥɹɸɳɢɦ ɟɟ ɷɥɟɦɟɧɬɚɪɧɵɦ ɜɵɫɤɚɡɵɜɚɧɢɹɦ ɢ ɜɵɱɢɫɥɢɬɶ ɢɫɬɢɧɧɨɫɬɧɨɟ ɡɧɚɱɟɧɢɟ ɜɫɟɣ ɮɨɪɦɭɥɵ. ɉɪɢ ɷɬɨɦ ɥɨɝɢɱɟɫɤɢɟ ɫɜɹɡɤɢ ɪɚɫɫɦɚɬɪɢɜɚɸɬɫɹ ɤɚɤ ɮɭɧɤɰɢɢ ɧɚ ɦɧɨɠɟɫɬɜɟ ɢɫɬɢɧɧɨɫɬɧɵɯ ɡɧɚɱɟɧɢɣ (ɛɭɥɟɜɵ ɮɭɧɤɰɢɢ), ɨɩɪɟɞɟɥɟɧɧɵɟ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫ ɬɚɛɥ. 1.

ɂɧɬɟɪɩɪɟɬɚɰɢɹ, ɩɪɢ ɤɨɬɨɪɨɣ ɮɨɪɦɭɥɚ ɩɪɢɧɢɦɚɟɬ ɡɧɚɱɟɧɢɟ Ɍ,

Ɏɨɪɦɭɥɚ ɧɟɜɵɩɨɥɧɢɦɚ (ɩɪɨɬɢɜɨɪɟɱɢɜɚ, ɬɨɠɞɟɫɬɜɟɧɧɨ ɥɨɠɧɚ), ɟɫɥɢ ɨɧɚ ɧɟ ɢɦɟɟɬ ɧɢ ɨɞɧɨɣ ɦɨɞɟɥɢ, ɬɨ ɟɫɬɶ ɩɪɢ ɜɫɟɯ ɢɧɬɟɪɩɪɟɬɚɰɢɹɯ ɹɜɥɹɟɬɫɹ ɥɨɠɧɨɣ. ɇɚɩɪɢɦɟɪ, ɮɨɪɦɭɥɚ (ɪ& ɪ) ɧɟɜɵɩɨɥɧɢɦɚ.

Ɏɨɪɦɭɥɚ ɨɛɳɟɡɧɚɱɢɦɚ (ɹɜɥɹɟɬɫɹ ɬɚɜɬɨɥɨɝɢɟɣ), ɟɫɥɢ ɨɧɚ ɢɫɬɢɧɧɚ ɜ ɥɸɛɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ. ɇɚɩɪɢɦɟɪ, ɮɨɪɦɭɥɚ (ɪ ɪ) ɨɛɳɟɡɧɚɱɢɦɚ.

Ɏɨɪɦɭɥɵ ɪɚɜɧɨɫɢɥɶɧɵ (ɥɨɝɢɱɟɫɤɢ ɷɤɜɢɜɚɥɟɧɬɧɵ), ɟɫɥɢ ɨɧɢ ɢɦɟɸɬ ɨɞɢɧɚɤɨɜɵɟ ɬɚɛɥɢɰɵ ɢɫɬɢɧɧɨɫɬɢ.

ɉɪɢɦɟɪ. Ɂɚɩɢɫɚɬɶ ɫɥɟɞɭɸɳɟɟ ɭɬɜɟɪɠɞɟɧɢɟ ɜ ɜɢɞɟ ɮɨɪɦɭɥɵ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ ɢ ɨɩɪɟɞɟɥɢɬɶ ɜɵɩɨɥɧɢɦɨɫɬɶ, ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ ɢ ɤɨɥɢɱɟɫɬɜɨ ɦɨɞɟɥɟɣ ɷɬɨɣ ɮɨɪɦɭɥɵ:

«ɋɬɭɞɟɧɬ ɧɟ ɞɨɩɭɫɤɚɟɬɫɹ ɤ ɷɤɡɚɦɟɧɭ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɭ ɧɟɝɨ ɧɟ ɫɞɚɧɚ ɤɭɪɫɨɜɚɹ ɪɚɛɨɬɚ ɢɥɢ ɟɫɬɶ ɡɚɞɨɥɠɟɧɧɨɫɬɢ ɩɨ ɥɚɛɨɪɚɬɨɪɧɵɦ ɪɚɛɨɬɚɦ».

Ɋɟɲɟɧɢɟ. Ɉɛɨɡɧɚɱɢɦ ɜɫɟ ɜɫɬɪɟɬɢɜɲɢɟɫɹ ɷɥɟɦɟɧɬɚɪɧɵɟ ɜɵɫɤɚɡɵɜɚɧɢɹ ɩɪɨɩɨɡɢɰɢɨɧɚɥɶɧɵɦɢ ɩɟɪɟɦɟɧɧɵɦɢ:

p - «ɫɬɭɞɟɧɬ ɞɨɩɭɳɟɧ ɤ ɷɤɡɚɦɟɧɭ»; q - «ɤɭɪɫɨɜɚɹ ɪɚɛɨɬɚ ɫɞɚɧɚ»;

r - «ɟɫɬɶ ɡɚɞɨɥɠɟɧɧɨɫɬɶ ɩɨ ɥɚɛɨɪɚɬɨɪɧɵɦ ɪɚɛɨɬɚɦ».

Ɍɨɝɞɚ ɮɨɪɦɭɥɚ ɡɚɩɢɲɟɬɫɹ ɜ ɫɥɟɞɭɸɳɟɦ ɜɢɞɟ: p l ( q r). ɉɨɫɬɪɨɢɦ ɬɚɛɥɢɰɭ ɢɫɬɢɧɧɨɫɬɢ, ɜɵɱɢɫɥɹɹ ɫɧɚɱɚɥɚ ɡɧɚɱɟɧɢɹ ɩɨɞɮɨɪɦɭɥ (Ɍɚɛɥ. 2).

Ɍɚɛɥɢɰɚ 2

Ɍаким ɨбразом, ɞɚɧɧɚɹ ɮɨɪɦɭɥɚ ɜɵɩɨɥɧɢɦɚ, ɬ.ɤ. ɢɦɟɟɬ ɦɨɞɟɥɢ ɢ ɧɟ ɨɛɳɟɡɧɚɱɢɦɚ, ɬ.ɤ. ɢɦɟɸɬɫɹ ɢɧɬɟɪɩɪɟɬɚɰɢɢ, ɩɪɢ ɤɨɬɨɪɵɯ ɨɧɚ ɥɨɠɧɚ. Ɏɨɪɦɭɥɚ ɢɦɟɟɬ 4 ɦɨɞɟɥɢ.

Ʌɢɬɟɪɨɣ (ɥɢɬɟɪɚɥɨɦ) ɜ ɥɨɝɢɤɟ ɜɵɫɤɚɡɵɜɚɧɢɣ ɧɚɡɵɜɚɟɬɫɹ ɥɸɛɚɹ ɩɪɨɩɨɡɢɰɢɨɧɚɥɶɧɚɹ ɩɟɪɟɦɟɧɧɚɹ ɫ ɨɬɪɢɰɚɧɢɟɦ ɢɥɢ ɛɟɡ ɧɟɝɨ. Ⱦɢɡɴɸɧɤɬ - ɞɢɡɴɸɧɤɰɢɹ ɤɨɧɟɱɧɨɝɨ ɱɢɫɥɚ ɥɢɬɟɪ. ɋɥɟɞɭɸɳɢɟ ɮɨɪɦɭɥɵ ɹɜɥɹɸɬɫɹ ɩɪɢɦɟɪɚɦɢ ɞɢɡɴɸɧɤɬɨɜ: (p q r), t, ( s q). Ʌɸɛɨɣ ɞɢɡɴɸɧɤɬ, ɫɨɞɟɪɠɚɳɢɣ ɯɨɬɹ ɛɵ ɨɞɧɭ ɥɢɬɟɪɭ, ɹɜɥɹɟɬɫɹ ɜɵɩɨɥɧɢɦɨɣ ɮɨɪɦɭɥɨɣ. ȿɞɢɧɫɬɜɟɧɧɵɦ ɧɟɜɵɩɨɥɧɢɦɵɦ ɞɢɡɴɸɧɤɬɨɦ ɹɜɥɹɟɬɫɹ ɩɭɫɬɨɣ ɞɢɡɴɸɧɤɬ, ɬɨ ɟɫɬɶ ɞɢɡɴɸɧɤɬ ɧɟ ɫɨɞɟɪɠɚɳɢɣ ɧɢ ɨɞɧɨɣ ɥɢɬɟɪɵ. ɉɨɷɬɨɦɭ ɟɝɨ ɩɪɢɧɹɬɨ ɨɛɨɡɧɚɱɚɬɶ ɥɨɝɢɱɟɫɤɨɣ ɤɨɧɫɬɚɧɬɨɣ F.

Ʉɨɧɴɸɧɤɬɢɜɧɨɣ ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɨɣ (ɄɇɎ) ɧɚɡɵɜɚɟɬɫɹ ɤɨɧɴɸɧɤɰɢɹ ɤɨɧɟɱɧɨɝɨ ɱɢɫɥɚ ɞɢɡɴɸɧɤɬɨɜ. ɉɪɢɜɟɞɟɧɧîé ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɨɣ ɧɚɡɵɜɚɟɬɫɹ ɧɨɪɦɚɥɶɧɚɹ ɮɨɪɦɚ, ɜ ɤɨɬɨɪɨɣ ɨɩɭɳɟɧɵ ɞɢɡɴɸɧɤɬɵ, ɫɨɞɟɪɠɚɳɢɟ ɤɨɧɬɪɚɪɧɵɟ ɩɚɪɵ (ɬɚɜɬɨɥɨɝɢɢ) ɢ ɩɨɜɬɨɪɟɧɢɹ ɥɢɬɟɪ ɜ ɩɪɟɞɟɥɚɯ ɨɞɧɨɝɨ ɢ ɬɨɝɨ ɠɟ ɞɢɡɴɸɧɤɬɚ.

Ʌɸɛɚɹ ɮɨɪɦɭɥɚ ɦɨɠɟɬ ɛɵɬɶ ɩɪɟɨɛɪɚɡɨɜɚɧɚ ɜ ɥɨɝɢɱɟɫɤɢ ɷɤɜɢɜɚɥɟɧɬɧɭɸ ɟɣ ɄɇɎ ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɫɥɟɞɭɸɳɟɝɨ ɚɥɝɨɪɢɬɦɚ:

1. ɂɫɤɥɸɱɢɬɶ ɢɡ ɮɨɪɦɭɥɵ ɜɫɟ ɫɜɹɡɤɢ ɢɦɩɥɢɤɚɰɢɢ ɢ ɷɤɜɢɜɚɥɟɧɬɧɨɫɬɢ, ɢɫɩɨɥɶɡɭɹ ɫɥɟɞɭɸɳɢɟ ɬɨɠɞɟɫɬɜɚ:

A o B { A B ;

A l B { (A o B) & (B o A) { ( A B) & ( B A).

2. ɋɭɡɢɬɶ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɨɬɪɢɰɚɧɢɣ ɢ ɢɫɤɥɸɱɢɬɶ ɞɜɨɣɧɵɟ ɨɬɪɢɰɚɧɢɹ. Ⱦɥɹ ɷɬɨɝɨ ɢɫɩɨɥɶɡɭɸɬɫɹ ɡɚɤɨɧɵ ɞɟ Ɇɨɪɝɚɧɚ ɢ ɫɧɹɬɢɹ ɞɜɨɣɧɵɯ ɨɬɪɢɰɚɧɢɣ:

(A & B) { A B ;

(A B) { A & B ;

A { A.

3. ɉɪɢɦɟɧɢɬɶ ɧɟɨɛɯɨɞɢɦɨɟ ɱɢɫɥɨ ɪɚɡ ɩɪɚɜɢɥɨ ɞɢɫɬɪɢɛɭɬɢɜɧɨɫɬɢ ɞɢɡɴɸɧɤɰɢɢ ɨɬɧɨɫɢɬɟɥɶɧɨ ɤɨɧɴɸɧɤɰɢɢ:

(A & B) C { (A C) & (B C).

ɉɪɢɦɟɪ. ɉɪɟɨɛɪɚɡɨɜɚɬɶ ɜ ɄɇɎ ɫɥɟɞɭɸɳɭɸ ɮɨɪɦɭɥɭ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ: (p & q) l (q s).

Ɋɟɲɟɧɢɟ. ȼɵɩɨɥɧɢɦ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫ ɩɪɢɜɟɞɟɧɧɵɦ ɜɵɲɟ ɚɥɝɨɪɢɬɦɨɦ.

1. ɂɫɤɥɸɱɟɧɢɟ ɫɜɹɡɤɢ ɷɤɜɢɜɚɥɟɧɬɧɨɫɬɢ:

[(p & q) o (q s)] & [(q s) o (p & q)] = [ (p & q) (q s)] & [ (q s) (p & q)].

2. ɋɭɠɟɧɢɟ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɨɬɪɢɰɚɧɢɣ ɢ ɫɧɹɬɢɟ ɞɜɨɣɧɵɯ ɨɬɪɢɰɚɧɢɣ: [( p q) (q s)] & [( q & s) (p & q)] =

[( p q q s)] & [( q & s) (p & q)] = [( p q s)] & [( q & s) (p & q)].

3. ɉɪɢɦɟɧɟɧɢɟ ɞɢɫɬɪɢɛɭɬɢɜɧɨɫɬɢ, ɢɫɤɥɸɱɟɧɢɟ ɬɚɜɬɨɥɨɝɢɣ: [( p q s)] & [( q p&q) & (s p & q)] =

[( p q s)] & [( q p) & ( q q) & (s p) & (s q)] = ( p q s) & ( q p) & (s p) & (s q).

ɍɩɪɚɠɧɟɧɢɹ 1. Ⱦɥɹ ɩɪɢɜɟɞɟɧɧɵɯ ɮɨɪɦɭɥ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ ɩɨɫɬɪɨɢɬɶ

ɫɨɨɬɜɟɬɫɬɜɭɸɳɢɟ ɢɦ ɥɨɝɢɱɟɫɤɢɟ ɮɭɧɤɰɢɢ ɜ ɜɢɞɟ ɬɚɛɥɢɰ ɢɫɬɢɧɧɨɫɬɢ, ɨɩɪɟɞɟɥɢɬɶ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ, ɜɵɩɨɥɧɢɦɨɫɬɶ (ɧɟɜɵɩɨɥɧɢɦɨɫɬɶ) ɢ ɱɢɫɥɨ ɦɨɞɟɥɟɣ ɮɨɪɦɭɥɵ:

ɚ) s o ( t o r); ɛ) q l (p o r s);

ɜ) p o ((q & p) o (p r));

ɝ) p & (q p) & (( q o p) o q); ɞ) (r & q p) o t;

ɟ) (p & q) l q;

ɠ) (r & t) (p q);

ɡ) (q (p & t)) o ((q & t).

ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ, ɜɵɩɨɥɧɢɦɨɫɬɶ (ɧɟɜɵɩɨɥɧɢɦɨɫɬɶ) ɢ ɱɢɫɥɨ ɦɨɞɟɥɟɣ ɩɨɥɭɱɟɧɧɵɯ ɮɨɪɦɭɥ:

ɚ) ȿɫɥɢ ɋɢɞɨɪɨɜ ɩɨɟɞɟɬ ɧɚ ɚɜɬɨɛɭɫɟ, ɬɨ ɟɝɨ ɭɜɨɥɹɬ ɫ ɪɚɛɨɬɵ, ɟɫɥɢ ɚɜɬɨɛɭɫ ɨɩɨɡɞɚɟɬ.

ɛ) ɇɟɨɛɯɨɞɢɦɨɟ ɢ ɞɨɫɬɚɬɨɱɧɨɟ ɭɫɥɨɜɢɟ ɞɥɹ ɠɢɡɧɢ ɪɚɫɬɟɧɢɣ ɫɨɫɬɨɢɬ ɜ ɧɚɥɢɱɢɢ ɩɢɬɚɬɟɥɶɧɨɣ ɩɨɱɜɵ, ɱɢɫɬɨɝɨ ɜɨɡɞɭɯɚ ɢ ɫɨɥɧɟɱɧɨɝɨ ɫɜɟɬɚ.

ɜ) ȿñëè «Ɍɨɪɩɟɞɨ» ɢɥɢ «Ⱦɢɧɚɦɨ» ɩɪɨɢɝɪɚɸɬ, ɚ «Ʌɨɤɨɦɨɬɢɜ» ɜɵɢɝɪɚɟɬ, ɬɨ «ɋɩɚɪɬɚɤ» ɩɨɬɟɪɹɟɬ ɩɟɪɜɨɟ ɦɟɫɬɨ.

ɝ) ȿɫɥɢ ɪɚɛɨɱɢɟ ɢɥɢ ɚɞɦɢɧɢɫɬɪɚɰɢɹ ɭɩɨɪɫɬɜɭɸɬ, ɬɨ ɡɚɛɚɫɬɨɜɤɚ ɛɭɞɟɬ ɭɪɟɝɭɥɢɪɨɜɚɧɚ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɩɪɚɜɢɬɟɥɶɫɬɜɨ ɞɨɛɶɟɬɫɹ ɫɭɞɟɛɧɨɝɨ ɡɚɩɪɟɳɟɧɢɹ, ɧɨ ɜɨɣɫɤɚ ɧɟ ɛɭɞɭɬ ɩɨɫɥɚɧɵ ɧɚ ɡɚɜɨɞ.

ɞ) ȿɫɥɢ ɜɟɱɟɪɨɦ ɛɭɞɟɬ ɬɭɦɚɧ ɢɥɢ ɫɧɟɝ, ɬɨ Ⱦɠɨɧ ɢɥɢ ɨɫɬɚɧɟɬɫɹ ɞɨɦɚ ɢɥɢ ɞɨɥɠɟɧ ɛɭɞɟɬ ɜɡɹɬɶ ɬɚɤɫɢ.

ɟ) Ʌɢɛɨ ɪɨɫɬ ɢɧɮɥɹɰɢɢ ɷɤɜɢɜɚɥɟɧɬɟɧ ɫɧɢɠɟɧɢɸ ɭɪɨɜɧɹ ɠɢɡɧɢ, ɥɢɛɨ ɪɨɫɬ ɩɪɨɢɡɜɨɞɫɬɜɚ ɜɥɟɱɟɬ ɬɨ, ɱɬɨ ɭɪɨɜɟɧɶ ɠɢɡɧɢ ɧɟ ɫɧɢɠɚɟɬɫɹ.

ɠ) ȿɫɥɢ ɛɭɞɟɬ ɢɞɬɢ ɞɨɠɞɶ ɢɥɢ ɫɧɟɝ, ɬɨ ɮɭɬɛɨɥɶɧɵɣ ɦɚɬɱ ɥɢɛɨ ɧɟ ɫɨɫɬɨɢɬɫɹ, ɥɢɛɨ ɟɝɨ ɪɟɡɭɥɶɬɚɬ ɧɟ ɛɭɞɟɬ ɨɬɪɚɠɚɬɶ ɫɨɨɬɧɨɲɟɧɢɟ ɫɢɥ.

ɡ) ȿɫɥɢ ɠɢɜɨɬɧɨɟ ɦɥɟɤɨɩɢɬɚɸɳɟɟ ɢ ɢɦɟɟɬ ɨɫɬɪɵɟ ɡɭɛɵ ɢ ɢɦɟɟɬ ɤɥɵɤɢ

ɢɧɟ ɟɫɬ ɬɪɚɜɭ, ɬɨ ɷɬɨ ɯɢɳɧɢɤ.

3.ɉɪɟɨɛɪɚɡɨɜɚɬɶ ɫɥɟɞɭɸɳɢɟ ɮɨɪɦɭɥɵ ɜ ɄɇɎ:

ɚ) ( r & t) l (p q);

ɛ) (r & q & t) o (t q r);

â) ((p o q) o (r o p)) o ( q o r);

ɝ) (q o (p o t)) o ((q o t) o (q o p));

ɞ) (r q p) o (t o s); ɟ) (p & q) l (r q);

ɠ) (r & t) (p q).

ɉɊȺɄɌɂɑȿɋɄɈȿ ɁȺɇəɌɂȿ ʋ 2

Ɇɟɬɨɞ ɪɟɡɨɥɸɰɢɣ ɜ ɥɨɝɢɤɟ ɜɵɫɤɚɡɵɜɚɧɢɣ

ɐɟɥɶ ɡɚɧɹɬɢɹ: ɉɪɚɤɬɢɱɟɫɤɨɟ ɨɫɜɨɟɧɢɟ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ ɜ ɥɨɝɢɤɟ ɜɵɫɤɚɡɵɜɚɧɢɣ ɞɥɹ ɪɟɲɟɧɢɹ ɩɪɨɛɥɟɦɵ ɞɟɞɭɤɰɢɢ.

Ɍɟɨɪɟɬɢɱɟɫɤɢɟ ɫɜɟɞɟɧɢɹ

ɉɭɫɬɶ ȿ - ɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ. Ɏɨɪɦɭɥɭ C ɧɚɡɵɜɚɸɬ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ ɢɡ ȿ, ɟɫɥɢ ɩɪɢ ɜɫɟɯ ɢɧɬɟɪɩɪɟɬɚɰɢɹɯ, ɩɪɢ ɤɨɬɨɪɵɯ ɨɞɧɨɜɪɟɦɟɧɧɨ ɢɫɬɢɧɧɵ ɜɫɟ ɮɨɪɦɭɥɵ ɢɡ ȿ, ɮɨɪɦɭɥɚ C ɬɚɤɠɟ ɢɫɬɢɧɧɚ. ɗɬɨɬ ɮɚɤɬ ɡɚɩɢɫɵɜɚɟɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ ȿ»= C.

Ɉɫɧɨɜɧɨɣ ɩɪɨɛɥɟɦɨɣ ɥɨɝɢɤɢ ɹɜɥɹɟɬɫɹ ɩɪɨɛɥɟɦɚ ɞɟɞɭɤɰɢɢ [1, 5], ɤɨɬɨɪɚɹ ɡɚɤɥɸɱɚɟɬɫɹ ɜ ɬɨɦ, ɱɬɨɛɵ ɞɥɹ ɡɚɞɚɧɧɨɣ ɮɨɪɦɭɥɵ C и ɦножества ɮормул E ɨɩɪɟɞɟɥɢɬɶ, ɹɜɥɹɟɬɫɹ ɥɢ ɮɨɪɦɭɥɚ ɋ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ ɢɡ ȿ. ɇɟɩɨɫɪɟɞɫɬɜɟɧɧɨɟ ɪɟɲɟɧɢɟ ɩɪɨɛɥɟɦɵ ɞɟɞɭɤɰɢɢ ɦɟɬɨɞɨɦ ɩɟɪɟɛɨɪɚ ɜɫɟɜɨɡɦɨɠɧɵɯ ɢɧɬɟɪɩɪɟɬɚɰɢɣ ɯɚɪɚɤɬɟɪɢɡɭɟɬɫɹ ɜɵɫɨɤɨɣ ɜɵɱɢɫɥɢɬɟɥɶɧɨɣ ɫɥɨɠɧɨɫɬɶɸ, ɬɚɤ ɤɚɤ ɩɪɢ n ɩɪɨɩɨɡɢɰɢɨɧɚɥɶɧɵɯ ɩɟɪɟɦɟɧɧɵɯ ɱɢɫɥɨ ɢɧɬɟɪɩɪɟɬɚɰɢɣ ɪɚɜɧɨ 2n. ɉɪɨɛɥɟɦɚ ɞɟɞɭɤɰɢɢ ɦɨɠɟɬ ɛɵɬɶ ɫɜɟɞɟɧɚ ɤ ɡɚɞɚɱɟ ɭɫɬɚɧɨɜɥɟɧɢɹ ɧɟɜɵɩɨɥɧɢɦɨɫɬɢ ɦɧɨɠɟɫɬɜɚ ɮɨɪɦɭɥ ɫ ɩɨɦɨɳɶɸ ɩɪɢɧɰɢɩɚ ɞɟɞɭɤɰɢɢ : ɮɨɪɦɭɥɚ ɋ ɹɜɥɹɟɬɫɹ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ ɤɨɧɟɱɧɨɝɨ ɦɧɨɠɟɫɬɜɚ ȿ ɮɨɪɦɭɥ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɦɧɨɠɟɫɬɜɨ ȿ { C} ɧɟɜɵɩɨɥɧɢɦɨ. Ɇɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ ɧɟɜɵɩɨɥɧɢɦɨ, ɟɫɥɢ ɧɟ ɫɭɳɟɫɬɜɭɟɬ ɢɧɬɟɪɩɪɟɬɚɰɢɢ, ɩɪɢ ɤɨɬɨɪɨɣ ɜɫɟ ɟɝɨ ɷɥɟɦɟɧɬɵ ɨɞɧɨɜɪɟɦɟɧɧɨ ɢɫɬɢɧɧɵ, ɬɨ ɟɫɬɶ ɮɨɪɦɭɥɵ ɦɧɨɠɟɫɬɜɚ ɧɟ ɢɦɟɸɬ ɨɛɳɟɣ ɦɨɞɟɥɢ. Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɫ ɬɨɱɤɢ ɡɪɟɧɢɹ ɫɜɨɣɫɬɜɚ ɜɵɩɨɥɧɢɦɨɫɬɢ, ɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ ɷɤɜɢɜɚɥɟɧɬɧɨ ɤɨɧɴɸɧɤɰɢɢ ɫɜɨɢɯ ɷɥɟɦɟɧɬɨɜ.

ȼɦɟɫɬɟ ɫ ɬɟɦ, ɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ ɧɟɜɵɩɨɥɧɢɦɨ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɟɝɨ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ ɹɜɥɹɟɬɫɹ ɤɨɧɫɬɚɧɬɚ F. ɉɨɷɬɨɦɭ ɩɪɢɧɰɢɩ ɞɟɞɭɤɰɢɢ ɦɨɠɧɨ ɡɚɩɢɫɚɬɶ ɜ ɫɢɦɜɨɥɢɱɟɫɤɨɣ ɮɨɪɦɟ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:

{ ɇ1, ..., Hn}»= C l {H1,... Hn, C} »= F.

Ɏɨɪɦɭɥɵ ɇi ɧɚɡɵɜɚɸɬ ɝɢɩɨɬɟɡɚɦɢ ɢɥɢ ɩɨɫɵɥɤɚɦɢ, ɮɨɪɦɭɥɭ ɋ - ɡɚɤɥɸɱɟɧɢɟɦ.

ɇɟɜɵɩɨɥɧɢɦɨɫɬɶ ɦɧɨɠɟɫɬɜɚ ɞɢɡɴɸɧɤɬɨɜ ɦɨɠɟɬ ɛɵɬɶ ɷɮɮɟɤɬɢɜɧɨ ɭɫɬɚɧɨɜɥɟɧɚ ɫ ɩɨɦɨɳɶɸ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ.

Ʌɢɬɟɪɚɥ ɢ ɟɝɨ ɨɬɪɢɰɚɧɢɟ ɧɚɡɵɜɚɸɬ ɤɨɧɬɪɚɪɧɨɣ ɩɚɪɨɣ. ɇɚɩɪɢɦɟɪ, p ɢp - ɤɨɧɬɪɚɪɧɚɹ ɩɚɪɚ.

ɉɪɚɜɢɥɨ ɪɟɡɨɥɸɰɢɣ: ɟɫɥɢ ɞɜɚ ɞɢɡɴɸɧɤɬɚ ɫɨɞɟɪɠɚɬ ɤɨɧɬɪɚɪɧɭɸ ɩɚɪɭ, ɬɨ ɢɯ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ ɹɜɥɹɟɬɫɹ ɞɢɡɴɸɧɤɬ, ɩɨɥɭɱɟɧɧɵɣ ɨɛɴɟɞɢɧɟɧɢɟɦ ɢɫɯɨɞɧɵɯ ɞɢɡɴɸɧɤɬɨɜ, ɢɡ ɤɨɬɨɪɵɯ ɢɫɤɥɸɱɟɧɵ ɥɢɬɟɪɚɥɵ ɤɨɧɬɪɚɪɧɨɣ ɩɚɪɵ. ɗɬɨɬ ɧɨɜɵɣ ɞɢɡɴɸɧɤɬ ɧɚɡɵɜɚɸɬ ɪɟɡɨɥɶɜɟɧɬɨɣ ɢɫɯɨɞɧɵɯ (ɪɨɞɢɬɟɥɶɫɤɢɯ) ɞɢɡɴɸɧɤɬɨɜ.

ɇɚɩɪɢɦɟɪ, ɪɟɡɨɥɶɜɟɧɬɨɣ ɞɢɡɴɸɧɤɬɨɜ (p q r) ɢ ( p s) ɹɜɥɹɟɬɫɹ ɞɢɡɴɸɧɤɬ (q r s).

Ɋɟɡɨɥɶɜɟɧɬɨɣ ɞɜɭɯ ɨɞɧɨɥɢɬɟɪɚɥɶɧɵɯ ɞɢɡɴɸɧɤɬɨɜ ɦɨɠɟɬ ɛɵɬɶ ɬɨɥɶɤɨ ɩɭɫɬɨɣ ɞɢɡɴɸɧɤɬ F. ɂɡɜɟɫɬɧɨ [1, 2], ɱɬɨ ɞɥɹ ɥɸɛɨɝɨ ɧɟɜɵɩɨɥɧɢɦɨɝɨ ɦɧɨɠɟɫɬɜɚ ɞɢɡɴɸɧɤɬɨɜ ɡɚ ɤɨɧɟɱɧɨɟ ɱɢɫɥɨ ɩɪɢɦɟɧɟɧɢɣ ɩɪɚɜɢɥɚ ɪɟɡɨɥɸɰɢɣ ɦɨɠɟɬ ɛɵɬɶ ɩɨɥɭɱɟɧ ɩɭɫɬɨɣ ɞɢɡɴɸɧɤɬ. Ɍɚɤ ɤɚɤ, ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫ ɩɪɢɧɰɢɩɨɦ ɞɟɞɭɤɰɢɢ, ɩɪɨɛɥɟɦɚ ɥɨɝɢɱɟɫɤɨɝɨ ɫɥɟɞɨɜɚɧɢɹ ɫɜɨɞɢɬɫɹ ɤ ɡɚɞɚɱɟ ɭɫɬɚɧɨɜɥɟɧɢɹ ɧɟɜɵɩɨɥɧɢɦɨɫɬɢ ɦɧɨɠɟɫɬɜɚ ɮɨɪɦɭɥ, ɦɟɬɨɞ ɪɟɡɨɥɸɰɢɣ ɩɨɡɜɨɥɹɟɬ ɪɟɲɢɬɶ ɨɫɧɨɜɧɭɸ ɩɪɨɛɥɟɦɭ ɥɨɝɢɤɢ - ɩɪɨɛɥɟɦɭ ɞɟɞɭɤɰɢɢ.

ɉɭɫɬɶ S - ɢɫɯɨɞɧɨɟ ɦɧɨɠɟɫɬɜɨ ɞɢɡɴɸɧɤɬɨɜ, s1 ɢ s2 - ɞɢɡɴɸɧɤɬɵ ɦɧɨɠɟɫɬɜɚ S, l - ɥɢɬɟɪɚɥ. Ɍɨɝɞɚ ɚɥɝɨɪɢɬɦ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɧɟɜɵɩɨɥɧɢɦɨɫɬɢ ɦɧɨɠɟɫɬɜɚ S ɞɢɡɴɸɧɤɬɨɜ ɧɚ ɨɫɧɨɜɟ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ ɜ ɨɛɳɟɦ ɜɢɞɟ ɡɚɩɢɫɵɜɚɟɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:

While F S do

ɜɵɛɪɚɬɶ l, s1, s2 ɬɚɤɢɟ, ɱɬɨ l s1 ɢ l s2;

ɜɵɱɢɫɥɢɬɶ ɪɟɡɨɥɶɜɟɧɬɭ r ɞизɴюнктов s1 ɢ s2 ; ɡɚɦɟɧɢɬɶ S ɧɚ S {r}.

end.

Ⱦɚɧɧɵɣ ɚɥɝɨɪɢɬɦ ɩɪɟɞɩɨɥɚɝɚɟɬ ɩɟɪɟɛɨɪ ɞɢɡɴɸɧɤɬɨɜ. Ⱦɥɹ ɨɪɝɚɧɢɡɚɰɢɢ ɩɟɪɟɛɨɪɚ ɜ ɦɟɬɨɞɟ ɪɟɡɨɥɸɰɢɣ ɢɫɩɨɥɶɡɭɸɬɫɹ ɪɚɡɥɢɱɧɵɟ ɫɬɪɚɬɟɝɢɢ. Ɋɚɫɫɦɨɬɪɢɦ ɬɪɢ ɫɬɪɚɬɟɝɢɢ: ɧɚɫɵɳɟɧɢɹ ɭɪɨɜɧɹ, ɥɢɧɟɣɧɭɸ ɢ ɩɪɟɞɩɨɱɬɟɧɢɹ ɨɞɧɨɱɥɟɧɚɦ.

ɉɭɫɬɶ S - ɢɫɯɨɞɧɨɟ ɦɧɨɠɟɫɬɜɨ ɞɢɡɴɸɧɤɬɨɜ. Ɉɛɨɡɧɚɱɢɦ R(S)=R1(S) - ɨɛɴɟɞɢɧɟɧɢɟ S ɫ ɦɧɨɠɟɫɬɜɨɦ ɜɫɟɯ ɪɟɡɨɥɶɜɟɧɬ ɩɨɪɨɠɞɟɧɧɵɯ ɨɬ ɞɢɡɴɸɧɤɬɨɜ S. Ɍɨɝɞɚ Rn(S)=R(Rn-1(S)), ɡɧɚɱɟɧɢɟ n ɧɚɡɨɜɟɦ ɭɪɨɜɧɟɦ (ɢɥɢ ɝɥɭɛɢɧɨɣ) ɨɩɪɨɜɟɪɠɟɧɢɹ. ɋɬɪɚɬɟɝɢɹ ɧɚɫɵɳɟɧɢɹ ɭɪɨɜɧɹ ɩɪɟɞɩɨɥɚɝɚɟɬ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɟ ɩɨɪɨɠɞɟɧɢɟ ɜɫɟɯ ɪɟɡɨɥɶɜɟɧɬ ɭɪɨɜɧɹ 1, ɡɚɬɟɦ ɭɪɨɜɧɹ 2 ɢ ɬ.ɞ. ɞɨ ɩɨɥɭɱɟɧɢɹ ɩɭɫɬɨɝɨ ɞɢɡɴɸɧɤɬɚ. Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɞɚɧɧɚɹ ɫɬɪɚɬɟɝɢɹ ɹɜɥɹɟɬɫɹ ɩɨ ɫɭɳɟɫɬɜɭ ɫɬɪɚɬɟɝɢɟɣ ɩɨɢɫɤɚ ɜ ɲɢɪɢɧɭ.

ȿɫɥɢ ɪɟɡɨɥɶɜɟɧɬɚ, ɩɨɥɭɱɟɧɧɚɹ ɧɚ i-ɨɦ ɲɚɝɟ ɜɵɜɨɞɚ (i>0), ɜɫɟɝɞɚ ɢɦɟɟɬ ɜ ɤɚɱɟɫɬɜɟ ɨɞɧɨɝɨ ɢɡ ɫɜɨɢɯ ɪɨɞɢɬɟɥɶɫɤɢɯ ɞɢɡɴɸɧɤɬɨɜ (ɧɚɡɵɜɚɟɦɨɝɨ ɥɟɜɵɦ) ɞɢɡɴɸɧɤɬ, ɩɨɥɭɱɟɧɧɵɣ ɧɚ (i-1)-ɨɦ ɲɚɝɟ ɜɵɜɨɞɚ, ɬɨ ɬɚɤɨɣ ɜɵɜɨɞ ɧɚɡɵɜɚɟɬɫɹ ɥɢɧɟɣɧɵɦ.

ȼ ɫɬɪɚɬɟɝɢɢ ɩɪɟɞɩɨɱɬɟɧɢɹ ɨɞɧɨɱɥɟɧɚɦ ɩɟɪɟɛɨɪ ɞɢɡɴɸɧɤɬɨɜɩɪɟɬɟɧɞɟɧɬɨɜ ɧɚ ɪɟɡɨɥɸɰɢɸ ɜɵɩɨɥɧɹɟɬɫɹ ɜ ɩɨɪɹɞɤɟ ɜɨɡɪɚɫɬɚɧɢɹ ɢɯ ɞɥɢɧɵ. ȼɧɚɱɚɥɟ ɞɟɥɚɟɬɫɹ ɩɨɩɵɬɤɚ ɩɨɫɬɪɨɢɬɶ ɪɟɡɨɥɶɜɟɧɬɵ ɦɟɠɞɭ ɨɞɧɨɱɥɟɧɚɦɢ, ɬ.ɟ. ɞɢɡɴɸɧɤɬɚɦɢ, ɫɨɞɟɪɠɚɳɢɦɢ ɟɞɢɧɫɬɜɟɧɧɵɣ ɥɢɬɟɪɚɥ. ȿɫɥɢ ɷɬɨ ɭɞɚɟɬɫɹ, ɬɨ ɫɪɚɡɭ ɩɨɥɭɱɚɟɬɫɹ ɨɩɪɨɜɟɪɠɟɧɢɟ, ɟɫɥɢ ɧɟɬ - ɬɨ ɢɳɭɬɫɹ ɪɟɡɨɥɶɜɟɧɬɵ ɞɥɹ ɩɚɪ ɨɞɧɨɱɥɟɧ-ɞɜɭɱɥɟɧ, ɡɚɬɟɦ ɞɜɭɱɥɟɧ-ɞɜɭɱɥɟɧ ɢ ɬ.ɞ. ɉɟɪɟɛɨɪ ɩɚɪ ɞɢɡɴɸɧɤɬɨɜ ɜ ɞɚɧɧɨɣ ɫɬɪɚɬɟɝɢɢ ɞɨɥɠɟɧ ɜɵɩɨɥɧɹɬɶɫɹ ɬɚɤɢɦ ɨɛɪɚɡɨɦ, ɱɬɨɛɵ ɫɭɦɦɚ ɞɥɢɧ ɪɨɞɢɬɟɥɶɫɤɢɯ ɞɢɡɴɸɧɤɬɨɜ ɜ ɩɪɨɰɟɫɫɟ ɩɟɪɟɛɨɪɚ ɧɟ ɭɛɵɜɚɥɚ.

ɉɨɥɧɨɟ ɪɟɲɟɧɢɟ ɩɪɨɛɥɟɦɵ ɞɟɞɭɤɰɢɢ ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ ɜɤɥɸɱɚɟɬ ɫɥɟɞɭɸɳɢɟ ɲɚɝɢ:

1.Ɂɚɩɢɫɶ ɢɫɯɨɞɧɨɝɨ ɪɚɫɫɭɠɞɟɧɢɹ (ɩɨɫɵɥɨɤ ɢ ɡɚɤɥɸɱɟɧɢɹ) ɜ ɜɢɞɟ ɥɨɝɢɱɟɫɤɢɯ ɮɨɪɦɭɥ.

2.Ⱦɨɛɚɜɥɟɧɢɟ ɨɬɪɢɰɚɧɢɹ ɡɚɤɥɸɱɟɧɢɹ ɤ ɦɧɨɠɟɫɬɜɭ ɩɨɫɵɥɨɤ.

3.ɉɪɟɨɛɪɚɡɨɜɚɧɢɟ ɜɫɟɯ ɮɨɪɦɭɥ ɜ ɄɇɎ.

4.Ⱦɨɤɚɡɚɬɟɥɶɫɬɜɨ ɧɟɜɵɩɨɥɧɢɦɨɫɬɢ ɩɨɥɭɱɟɧɧɨɝɨ ɦɧɨɠɟɫɬɜɚ ɞɢɡɴɸɧɤɬɨɜ ɦɟɬɨɞɨɦ ɪɟɡɨɥɸɰɢɣ.

Ɂɚɞɚɱɚ. Ɂɚɩɢɫɚɬɶ ɮɨɪɦɚɥɶɧɨ ɧɚ ɹɡɵɤɟ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ ɫɥɟɞɭɸɳɟɟ ɪɚɫɫɭɠɞɟɧɢɟ ɢ ɞɨɤɚɡɚɬɶ ɟɝɨ ɫɩɪɚɜɟɞɥɢɜɨɫɬɶ, ɢɫɩɨɥɶɡɭɹ ɦɟɬɨɞ ɪɟɡɨɥɸɰɢɣ:

ɉɨɫɵɥɤɢ: ȿɫɥɢ ɧɚɥɨɝɢ ɜ ɛɸɞɠɟɬ ɧɟ ɫɨɛɪɚɧɵ, ɬɨ ɥɢɛɨ ɫɟɤɜɟɫɬɢɪɭɟɬɫɹ ɛɸɞɠɟɬ, ɥɢɛɨ ɩɪɚɜɢɬɟɥɶɫɬɜɨ ɭɯɨɞɢɬ ɜ ɨɬɫɬɚɜɤɭ. ȿɫɥɢ ɫɟɤɜɟɫɬɢɪɭɟɬɫɹ ɛɸɞɠɟɬ, ɬɨ ɩɚɞɚɟɬ ɭɪɨɜɟɧɶ ɠɢɡɧɢ. ɇɚɥɨɝɢ ɜ ɛɸɞɠɟɬ ɧɟ ɫɨɛɪɚɧɵ.

Ɂɚɤɥɸɱɟɧɢɟ: Ʌɢɛɨ ɩɚɞɚɟɬ ɭɪɨɜɟɧɶ ɠɢɡɧɢ, ɥɢɛɨ ɭɪɨɜɟɧɶ ɠɢɡɧɢ ɧɟ ɩɚɞɚɟɬ ɢ ɩɪɚɜɢɬɟɥɶɫɬɜɨ ɭɯɨɞɢɬ ɜ ɨɬɫɬɚɜɤɭ.

Ɋɟɲɟɧɢɟ.

1. ȼɜɟɞɟɦ ɫɢɦɜɨɥɢɱɟɫɤɢɟ ɨɛɨɡɧɚɱɟɧɢɹ ɷɥɟɦɟɧɬɚɪɧɵɯ ɜɵɫɤɚɡɵɜɚɧɢɣ: h - «ɧɚɥɨɝɢ ɜ ɛɸɞɠɟɬ ɧɟ ɫɨɛɪɚɧɵ»;

p - «ɛɸɞɠɟɬ ɫɟɤɜɟɫɬɢɪɭɟɬɫɹ»;

q - «ɩɪɚɜɢɬɟɥɶɫɬɜɨ ɭɯɨɞɢɬ ɜ ɨɬɫɬɚɜɤɭ»; r - «ɭɪɨɜɟɧɶ ɠɢɡɧɢ ɩɚɞɚɟɬ».

Ɂɚɩɢɲɟɦ ɞɚɧɧɨɟ ɪɚɫɫɭɠɞɟɧɢɟ ɮɨɪɦɚɥɶɧɨ ɜ ɜɢɞɟ ɥɨɝɢɱɟɫɤɨɝɨ ɫɥɟɞɨɜɚɧɢɹ:

{ho(p q), por, h } »= (r r&q)

2.Ⱦɨɛɚɜɢɦ ɨɬɪɢɰɚɧɢɟ ɰɟɥɟɜɨɝɨ ɭɬɜɟɪɠɞɟɧɢɹ ɤ ɦɧɨɠɟɫɬɜɭ ɩɨɫɵɥɨɤ:

{ho(p q), por, h, (r r&q) }

3.ɉɪɟɨɛɪɚɡɭɟɦ ɜɫɟ ɮɨɪɦɭɥɵ ɜ ɄɇɎ:

ho(p q) = h p q; por = p r;

(r r&q) = r & ( r&q) = r & (r q). ɉолучили ɫɥɟɞɭɸɳɟɟ ɦножество ɞизъюнктов:

{( h p q), ( p r), h, r , (r q)}.

4. ɉрименим ɦетод ɪезолюций ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɫɬɪɚɬɟɝɢɢ ɩɪɟɞɩɨɱɬɟɧɢɹ ɨɞɧɨɱɥɟɧɚɦ. ȼ ɧɚɱɚɥɟ ɜɵɩɢɲɟɦ ɢ ɩɪɨɧɭɦɟɪɭɟɦ ɞɢɡɴɸɧɤɬɵ ɢɫɯɨɞɧɨɝɨ ɦɧɨɠɟɫɬɜɚ:

1)h p q

2)p r

3)h

4)r

5)r q

ɋɩɪɚɜɟɞɥɢɜɨɫɬɶ ɪɚɫɫɭɠɞɟɧɢɹ ɞɨɤɚɡɚɧɚ. Ɋɚɫɫɦɨɬɪɢɦ ɬɟɩɟɪɶ ɜɵɜɨɞ ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɥɢɧɟɣɧɨɣ ɫɬɪɚɬɟɝɢɢ:

ɍɩɪɚɠɧɟɧɢɹ

1. ɂɫɩɨɥɶɡɭɹ ɦɟɬɨɞ ɪɟɡɨɥɸɰɢɣ ɞɨɤɚɡɚɬɶ ɧɟɜɵɩɨɥɧɢɦɨɫɬɶ (ɢɥɢ ɜɵɩɨɥɧɢɦɨɫɬɶ) ɫɥɟɞɭɸɳɢɯ ɦɧɨɠɟɫɬɜ ɞɢɡɴɸɧɤɬɨɜ. ɉɪɢɦɟɧɹɬɶ ɩɪɨɢɡɜɨɥɶɧɵɣ ɩɨɪɹɞɨɤ ɩɟɪɟɛɨɪɚ ɞɢɡɴɸɧɤɬɨɜ, ɚ ɬɚɤɠɟ, ɩɨ ɭɤɚɡɚɧɢɸ ɩɪɟɩɨɞɚɜɚɬɟɥɹ, ɨɞɧɭ ɢɡ ɫɥɟɞɭɸɳɢɯ ɫɬɪɚɬɟɝɢɣ: ɩɪɟɞɩɨɱɬɟɧɢɟ ɨɞɧɨɱɥɟɧɚɦ, ɥɢɧɟɣɧɭɸ, ɧɚɫɵɳɟɧɢɟ ɭɪɨɜɧɹ.

ɚ) {(p q s), (p q), s, p}; ɛ) {(q r), (q r), (r q), r};

ɜ) {(p q s), (q p), ( q s), s};

ɝ) {(q r), ( q r), (q r), ( p r), q};

ɞ) {(p r), (p r), ( p r), (q p r), p}; ɟ) {(r q s), ( q r s), (q s), s, r} ; ɠ) {(q s p), (s q), ( p s), (r p), p};

ɡ) {(p q r), (p r q), (r p q), ( q r), q}; ɢ) {(p s), (p r s), (r p s), ( r s), s};

ɤ) {(q p r), ( p q), (p q), (q r), q}.

2. Ɂɚɩɢɫɚɬɶ ɮɨɪɦɚɥɶɧɨ ɫɥɟɞɭɸɳɟɟ ɪɚɫɫɭɠɞɟɧɢɟ ɧɚ ɹɡɵɤɟ ɥɨɝɢɤɢ ɜɵɫɤɚɡɵɜɚɧɢɣ ɢ ɞɨɤɚɡɚɬɶ ɟɝɨ ɫɩɪɚɜɟɞɥɢɜɨɫɬɶ, ɢɫɩɨɥɶɡɭɹ ɦɟɬɨɞ ɪɟɡɨɥɸɰɢɣ.

ɚ) ɉɨɫɵɥɤɢ: ȿɫɥɢ ɢɞɟɬ ɞɨɠɞɶ, ɬɨ ɧɟɠɚɪɤɨ. ȿɫɥɢ ɫɜɟɬɢɬ ɫɨɥɧɰɟ, ɬɨ ɠɚɪɤɨ. ɂɞɟɬ ɞɨɠɞɶ.

Ɂɚɤɥɸɱɟɧɢɟ : ɇɟɠɚɪɤɨ ɢ ɧɟ ɫɜɟɬɢɬ ɫɨɥɧɰɟ.

ɛ) ɉɨɫɵɥɤɢ: ɗɤɡɚɦɟɧ ɫɞɚɧ ɜɨɜɪɟɦɹ ɢɥɢ ɫɟɫɫɢɹ ɩɪɨɞɥɟɧɚ. ȿɫɥɢ ɫɟɫɫɢɹ ɩɪɨɞɥɟɧɚ, ɬɨ ɧɟ ɫɞɚɧɚ ɤɭɪɫɨɜɚɹ ɪɚɛɨɬɚ ɢɥɢ ɧɟ ɡɚɱɬɟɧɵ ɥɚɛɨɪɚɬɨɪɧɵɟ ɪɚɛɨɬɵ. Ʉɭɪɫɨɜɚɹ ɪɚɛɨɬɚ ɫɞɚɧɚ. ɗɤɡɚɦɟɧ ɜɨɜɪɟɦɹ ɧɟ ɫɞɚɧ.

Ɂɚɤɥɸɱɟɧɢɟ: ɇɟɜɟɪɧɨ, ɱɬɨ ɟɫɥɢ ɤɭɪɫɨɜɚɹ ɪɚɛɨɬɚ ɫɞɚɧɚ, ɬɨ ɥɚɛɨɪɚɬɨɪɧɵɟ ɪɚɛɨɬɵ ɡɚɱɬɟɧɵ.

ɜ) ɉɨɫɵɥɤɢ: ȿɫɥɢ ɢɦɟɟɬ ɦɟɫɬɨ ɞɟɧɟɠɧɚɹ ɷɦɢɫɫɢɹ, ɬɨ ɪɚɫɬɟɬ ɤɭɪɫ ɞɨɥɥɚɪɚ. ȿɫɥɢ ɷɦɢɫɫɢɢ ɧɟɬ ɢ ɢɧɮɥɹɰɢɹ ɧɟ ɪɚɫɬɟɬ, ɬɨ ɤɭɪɫ ɞɨɥɥɚɪɚ ɧɟ ɪɚɫɬɟɬ. ɂɧɮɥɹɰɢɹ ɧɟ ɪɚɫɬɟɬ.

Ɂɚɤɥɸɱɟɧɢɟ: ɂɦɟɟɬ ɦɟɫɬɨ ɷɦɢɫɫɢɹ ɢ ɪɚɫɬɟɬ ɤɭɪɫ ɞɨɥɥɚɪɚ ɢɥɢ ɧɟɬ ɷɦɢɫɫɢɢ ɢ ɤɭɪɫ ɞɨɥɥɚɪɚ ɧɟ ɪɚɫɬɟɬ.

ɝ) ɉɨɫɵɥɤɢ: Ɂɚɪɚɛɨɬɧɚɹ ɩɥɚɬɚ ɜɨɡɪɚɫɬɟɬ ɬɨɥɶɤɨ, ɟɫɥɢ ɛɭɞɟɬ ɢɧɮɥɹɰɢɹ. ȿɫɥɢ ɛɭɞɟɬ ɢɧɮɥɹɰɢɹ, ɬɨ ɭɜɟɥɢɱɢɬɫɹ ɫɬɨɢɦɨɫɬɶ ɠɢɡɧɢ. Ɂɚɪɚɛɨɬɧɚɹ ɩɥɚɬɚ ɜɨɡɪɚɫɬɟɬ.

Ɂɚɤɥɸɱɟɧɢɟ: ɋɬɨɢɦɨɫɬɶ ɠɢɡɧɢ ɭɜɟɥɢɱɢɬɫɹ.

ɞ) ɉɨɫɵɥɤɢ: ȿɫɥɢ 2 - ɩɪɨɫɬɨɟ ɱɢɫɥɨ, ɬɨ ɷɬɨ ɧɚɢɦɟɧɶɲɟɟ ɩɪɨɫɬɨɟ ɱɢɫɥɨ. ȿɫɥɢ 2 - ɧɚɢɦɟɧɶɲɟɟ ɩɪɨɫɬɨɟ ɱɢɫɥɨ, ɬɨ 1 ɧɟ ɟɫɬɶ ɩɪɨɫɬɨɟ ɱɢɫɥɨ. ɑɢɫɥɨ 1 ɧɟ ɟɫɬɶ ɩɪɨɫɬɨɟ ɱɢɫɥɨ.

Ɂɚɤɥɸɱɟɧɢɟ: 2 - ɩɪɨɫɬɨɟ ɱɢɫɥɨ.

ɟ) ɉɨɫɵɥɤɢ: Ⱦɠɨɧ ɢɥɢ ɩɟɪɟɭɬɨɦɢɥɫɹ ɢɥɢ ɨɧ ɛɨɥɟɧ. ȿɫɥɢ ɨɧ ɩɟɪɟɭɬɨɦɢɥɫɹ, ɬɨ ɨɧ ɪɚɡɞɪɚɠɚɟɬɫɹ. Ɉɧ ɧɟ ɪɚɡɞɪɚɠɚɟɬɫɹ.

Ɂɚɤɥɸɱɟɧɢɟ: Ⱦɠɨɧ ɛɨɥɟɧ.

ɠ) ɉɨɫɵɥɤɢ: ȿɫɥɢ ɡɚɜɬɪɚ ɛɭɞɟɬ ɯɨɥɨɞɧɨ, ɹ ɧɚɞɟɧɭ ɬɟɩɥɨɟ ɩɚɥɶɬɨ, ɟɫɥɢ ɪɭɤɚɜ ɛɭɞɟɬ ɩɨɱɢɧɟɧ. Ɂɚɜɬɪɚ ɛɭɞɟɬ ɯɨɥɨɞɧɨ, ɚ ɪɭɤɚɜ ɧɟ ɛɭɞɟɬ ɩɨɱɢɧɟɧ.

Ɂɚɤɥɸɱɟɧɢɟ: ə ɧɟ ɧɚɞɟɧɭ ɬɟɩɥɨɟ ɩɚɥɶɬɨ.

ɡ) ɉɨɫɵɥɤɢ: ȿɫɥɢ ɢɫɯɨɞ ɫɤɚɱɟɤ ɛɭɞɟɬ ɩɪɟɞɪɟɲɟɧ ɫɝɨɜɨɪɨɦ ɢɥɢ ɜ ɢɝɨɪɧɵɯ ɞɨɦɚɯ ɛɭɞɭɬ ɨɪɭɞɨɜɚɬɶ ɲɭɥɟɪɵ, ɬɨ ɞɨɯɨɞɵ ɨɬ ɬɭɪɢɡɦɚ ɭɩɚɞɭɬ ɢ ɝɨɪɨɞ ɩɨɫɬɪɚɞɚɟɬ. ȿɫɥɢ ɞɨɯɨɞɵ ɨɬ ɬɭɪɢɡɦɚ ɭɩɚɞɭɬ, ɩɨɥɢɰɢɹ ɛɭɞɟɬ ɞɨɜɨɥɶɧɚ. ɉɨɥɢɰɢɹ ɧɢɤɨɝɞɚ ɧɟ ɛɵɜɚɟɬ ɞɨɜɨɥɶɧɚ.

Ɂɚɤɥɸɱɟɧɢɟ: ɂɫɯɨɞ ɫɤɚɱɟɤ ɧɟ ɩɪɟɞɪɟɲɟɧ ɫɝɨɜɨɪɨɦ.

ɢ) ɂɥɢ ɋɷɥɥɢ ɢ Ȼɨɛ ɨɞɧɨɝɨ ɜɨɡɪɚɫɬɚ, ɢɥɢ ɋɷɥɥɢ ɫɬɚɪɲɟ Ȼɨɛɚ. ȿɫɥɢ ɋɷɥɥɢ ɢ Ȼɨɛ ɨɞɧɨɝɨ ɜɨɡɪɚɫɬɚ, ɬɨ ɇɷɧɫɢ ɢ Ȼɨɛ ɧɟ ɨɞɧɨɝɨ ɜɨɡɪɚɫɬɚ. ȿɫɥɢ ɋɷɥɥɢ ɫɬɚɪɲɟ Ȼɨɛɚ, ɬɨ Ȼɨɛ ɫɬɚɪɲɟ ɍɨɥɬɟɪɚ.

Ɂɚɤɥɸɱɟɧɢɟ: ɂɥɢ ɇɷɧɫɢ ɢ Ȼɨɛ ɧɟ ɨɞɧɨɝɨ ɜɨɡɪɚɫɬɚ, ɢɥɢ Ȼɨɛ ɫɬɚɪɲɟ ɍɨɥɬɟɪɚ.