Site Loader

Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅

ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ БКНЀ ΠΈ БДНЀ ΠΏΠΎ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности

ΠΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° логичСской Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹ Π½Π΅ содСрТит Π·Π½Π°ΠΊΠΎΠ² ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΠΈ, эквивалСнтности ΠΈ отрицания нСэлСмСнтарных Ρ„ΠΎΡ€ΠΌΡƒΠ».

ΠΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° сущСствуСт Π² Π΄Π²ΡƒΡ… Π²ΠΈΠ΄Π°Ρ…:

  1. ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° (КНЀ) — ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, $\left(A\vee \overline{B}\vee C\right)\wedge \left(A\vee C\right)$;

  2. Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° (ДНЀ) — Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, $\left(A\wedge \overline{B}\wedge C\right)\vee \left(B\wedge C\right)$.

БКНЀ

Π‘ΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Π°Ρ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° (БКНЀ) — это КНЀ, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰Π°Ρ Ρ‚Ρ€Π΅ΠΌ условиям:

  • Π½Π΅ содСрТит ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… элСмСнтарных Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ;

  • Π½ΠΈ ΠΎΠ΄Π½Π° ΠΈΠ· Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π½Π΅ содСрТит ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…;

  • каТдая элСмСнтарная Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ содСрТит ΠΊΠ°ΠΆΠ΄ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ΠΈΠ· входящих Π² Π΄Π°Π½Π½ΡƒΡŽ КНЀ.

Π›ΡŽΠ±Π°Ρ Π±ΡƒΠ»Π΅Π²Π° Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°, которая Π½Π΅ являСтся тоТдСствСнно истинной, ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ прСдставлСна Π² БКНЀ.

ΠŸΡ€Π°Π²ΠΈΠ»Π° построСния БКНЀ ΠΏΠΎ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности

Для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π°Π±ΠΎΡ€Π° ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ функция Ρ€Π°Π²Π½Π° 0, записываСтся сумма, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 1, бСрутся с ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ.

БДНЀ

Π‘ΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½Π°Ρ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½Π°Ρ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Π°Ρ Ρ„ΠΎΡ€ΠΌΠ° (БДНЀ) — это ДНЀ, ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‰Π°Ρ Ρ‚Ρ€Π΅ΠΌ условиям:

  • Π½Π΅ содСрТит ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… элСмСнтарных ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ;

  • Π½ΠΈ ΠΎΠ΄Π½Π° ΠΈΠ· ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π½Π΅ содСрТит ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…;

  • каТдая элСмСнтарная ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ содСрТит ΠΊΠ°ΠΆΠ΄ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ΠΈΠ· входящих Π² Π΄Π°Π½Π½ΡƒΡŽ ДНЀ, ΠΊ Ρ‚ΠΎΠΌΡƒ ΠΆΠ΅ Π² ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΌ порядкС.

Π›ΡŽΠ±Π°Ρ Π±ΡƒΠ»Π΅Π²Π° Ρ„ΠΎΡ€ΠΌΡƒΠ»Π°, которая Π½Π΅ являСтся тоТдСствСнно Π»ΠΎΠΆΠ½ΠΎΠΉ, ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ прСдставлСна Π² БДНЀ, ΠΊ Ρ‚ΠΎΠΌΡƒ ΠΆΠ΅ СдинствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ.

ΠŸΡ€Π°Π²ΠΈΠ»Π° построСния БДНЀ ΠΏΠΎ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности

Для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π°Π±ΠΎΡ€Π° ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ функция Ρ€Π°Π²Π½Π° 1, записываСтся ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠΌΠ΅ΡŽΡ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ 0 Π±Π΅Ρ€ΡƒΡ‚ с ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ΠΌ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ нахоТдСния БКНЀ ΠΈ БДНЀ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1

Π—Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ ΠΏΠΎ Π΅Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности:

Рисунок 1.

РСшСниС:

Π’ΠΎΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡΡ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ построСния БДНЀ:

Рисунок 2.

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠΌ БДНЀ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\right)\vee \left(\overline{x_1}\wedge \overline{x_2}\wedge x_3\right)\vee \left(x_1\wedge \overline{x_2}\wedge \overline{x_3}\right)\vee \left(x_1\wedge \overline{x_2}\wedge x_3\right)\vee \left(x_1\wedge x_2\wedge x_3\right)\]

Π’ΠΎΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡΡ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ построСния БКНЀ:

Рисунок 3.

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠΌ БКНЀ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline{x_2}\vee x_3\right)\wedge \left(x_1\vee \overline{x_2}\vee \overline{x_3}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\right)\]

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2

Ѐункция Π·Π°Π΄Π°Π½Π° Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ истинности:

Рисунок 4.

ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ эту Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² Π²ΠΈΠ΄Π΅ БДНЀ ΠΈ БКНЀ.

РСшСниС:

  1. Π—Π°ΠΏΠΈΡˆΠ΅ΠΌ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² БДНЀ. Для удобства Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π΄ΠΎΠ±Π°Π²ΠΈΠΌ ΠΊ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ столбСц.

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

    Рисунок 5.

    ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Π²ΠΎ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΌ столбцС ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ соСдиним Π·Π½Π°ΠΊΠΎΠΌ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΈΡΠΊΠΎΠΌΡƒΡŽ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² Π²ΠΈΠ΄Π΅ БДНЀ:

    \[F\left(x_1,x_2,x_3,x_4\right)=\left(\overline{x}\wedge \overline{y}\wedge z\wedge f\right)\vee \left(\overline{x_1}\wedge x_2\wedge \overline{x_3}\wedge \overline{x_4}\right)\vee \left(\overline{x_1}\wedge x_2\wedge x_3\wedge x_4\right)\vee \left(x_1\wedge \overline{x_2}\wedge \overline{x_3}\wedge \overline{x_4}\right).\]
  2. Π—Π°ΠΏΠΈΡˆΠ΅ΠΌ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² БКНЀ.

    Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ составлСния БКНЀ Π½Π΅ Π·Π°Π±Ρ‹Π²Π°Π΅ΠΌ Π²Π²ΠΎΠ΄ΠΈΡ‚ΡŒ Π·Π½Π°ΠΊ отрицания для ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… со Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ 1. Π˜Π½Π²Π΅Ρ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π΅Π΄ΠΈΠ½ΠΈΡ‡Π½Ρ‹Π΅ значСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΎΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, Ρ‚.ΠΊ. ΠΈΠ½Π°Ρ‡Π΅ ΠΎΠ½ΠΈ прСвратят значСния Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΉ Π² Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ основной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

    Рисунок 6.

    ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Π²ΠΎ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΌ столбцС Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ соСдиним Π·Π½Π°ΠΊΠΎΠΌ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΈΡΠΊΠΎΠΌΡƒΡŽ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² Π²ΠΈΠ΄Π΅ БКНЀ:

    \[F\left(x_1,x_2,x_3,x_4\right)=\left(x_1\vee x_2\vee x_3\vee x_4\right)\wedge \left(x_1\vee x_2\vee x_3\vee \overline{x_4}\right)\wedge \left(x_1\vee x_2\vee \overline{x_3}\vee x_4\right)\wedge \left(x_1\vee \overline{x_2}\vee x_3\vee \overline{x_4}\right)\wedge \left(x_1\vee \overline{x_2}\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee x_2\vee x_3\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee x_2\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee x_2\vee \overline{x_3}\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\vee x_4\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee x_3\vee \overline{x_4}\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee \overline{x_3}\vee x_4\right)\wedge \left(\overline{x_1}\vee \overline{x_2}\vee \overline{x_3}\vee \overline{x_4}\right).\]

ΠŸΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… логичСских Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ

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

Для любого «Π°Π»Π³Π΅Π±Ρ€Π°ΠΈΡ‡Π΅ΡΠΊΠΎΠ³ΠΎ» дСйствия Π½Π°Π΄ ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ΠΌ задаётся ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ опрСдСлСния истинности ΠΈΠ»ΠΈ лоТности ΠΈΠ·ΠΌΠ΅Π½Π΅Π½Π½ΠΎΠ³ΠΎ утвСрТдСния, исходя ΠΈΠ· истинности ΠΈΠ»ΠΈ лоТности исходного утвСрТдСния. Π­Ρ‚ΠΈ ΠΏΡ€Π°Π²ΠΈΠ»Π° Π·Π°ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ Ρ‡Π΅Ρ€Π΅Π· Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности выраТСния. ΠŸΡ€Π΅ΠΆΠ΄Π΅, Ρ‡Π΅ΠΌ ΡΠΎΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности, Π½Π°Π΄ΠΎ ΠΏΠΎΠ±Π»ΠΈΠΆΠ΅ ΠΏΠΎΠ·Π½Π°ΠΊΠΎΠΌΠΈΡ‚ΡŒΡΡ с Π°Π»Π³Π΅Π±Ρ€ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ.

АлгСбраичСскиС прСобразования логичСских Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ

Π›ΡŽΠ±ΠΎΠ΅ логичСскоС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅, ΠΊΠ°ΠΊ ΠΈ Π΅Π³ΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ (утвСрТдСния), ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‚ Π΄Π²Π° значСния: лоТь ΠΈΠ»ΠΈ истина. Π›ΠΎΠΆΡŒ обозначаСтся Π½ΡƒΠ»Ρ‘ΠΌ, Π° истина — Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅ΠΉ. Π Π°Π·ΠΎΠ±Ρ€Π°Π²ΡˆΠΈΡΡŒ с ΠΎΠ±Π»Π°ΡΡ‚ΡŒΡŽ опрСдСлСния ΠΈ ΠΎΠ±Π»Π°ΡΡ‚ΡŒΡŽ допустимых Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ дСйствия Π°Π»Π³Π΅Π±Ρ€Ρ‹ Π»ΠΎΠ³ΠΈΠΊΠΈ.

ΠžΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅

ΠžΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ ΠΈ инвСрсия

— самоС простоС логичСскоС ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅. Π•ΠΌΡƒ соотвСтствуСт частица «Π½Π΅.» Π­Ρ‚ΠΎ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ просто мСняСт ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ Π½Π° ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠ΅. БоотвСтствСнно, Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ утвСрТдСния Ρ‚ΠΎΠΆΠ΅ мСняСтся Π½Π° ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠ΅. Если ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ А истинно, Ρ‚ΠΎ «Π½Π΅ А» — Π»ΠΎΠΆΠ½ΠΎ. НапримСр, ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ «ΠΏΡ€ΡΠΌΠΎΠΉ ΡƒΠ³ΠΎΠ» — это ΡƒΠ³ΠΎΠ», Ρ€Π°Π²Π½Ρ‹ΠΉ дСвяносто градусов» — истина. Π’ΠΎΠ³Π΄Π° Π΅Π³ΠΎ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ «ΠΏΡ€ΡΠΌΠΎΠΉ ΡƒΠ³ΠΎΠ» Π½Π΅ Ρ€Π°Π²Π΅Π½ дСвяноста градусам» — лоТь.

Π’Π°Π±Π»ΠΈΡ†Π° инвСрсии

Π’Π°Π±Π»ΠΈΡ†Π° истинности для отрицания Π±ΡƒΠ΄Π΅Ρ‚ Ρ‚Π°ΠΊΠΎΠ²Π°:

ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ

ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Π° ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡŽ ΠΈ соотвСтствуСт ΡΠΎΡŽΠ·Ρƒ «ΠΈ». Π’Π°ΠΊΠΎΠ΅ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π±ΡƒΠ΄Π΅Ρ‚ Π²Π΅Ρ€Π½ΠΎ, Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ссли Π²Π΅Ρ€Π½Ρ‹ всС утвСрТдСния, ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½Ρ‘Π½Π½Ρ‹Π΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠ΅ΠΉ. Π’ΠΎ Π΅ΡΡ‚ΡŒ, ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ «Π ΠΈ Π‘» Π±ΡƒΠ΄Π΅Ρ‚ истинным, Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ссли А — истина ΠΈ Π‘ — истина. Π’ΠΎ всСх ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ… случаях Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ «Π ΠΈ Π‘» Π»ΠΎΠΆΠ½ΠΎ. НапримСр, высказываниС «Π—Смля круглая ΠΈ плоская» Π±ΡƒΠ΄Π΅Ρ‚ Π»ΠΎΠΆΠ½ΠΎ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ пСрвая Ρ‡Π°ΡΡ‚ΡŒ истина, Π° вторая — лоТь.

Π’Π°Π±Π»ΠΈΡ†Π° истинности ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ

А Π‘ А ΠΈ Π‘
Π› Π› Π›
Π› И Π›
И Π› Π›
И И И

Π”ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ

Π­Ρ‚Π° опСрация ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ

ΠΎΠ±Ρ‹Ρ‡Π½ΠΎΠΉ ΠΈΠ»ΠΈ строгой, ΠΈΡ… Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ Π±ΡƒΠ΄ΡƒΡ‚ Ρ€Π°Π·Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ.

ΠžΠ±Ρ‹Ρ‡Π½Π°Ρ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ ΠΈΠ»ΠΈ логичСскоС слоТСниС соотвСтствуСт ΡΠΎΡŽΠ·Ρƒ «ΠΈΠ»ΠΈ». Она Π±ΡƒΠ΄Π΅Ρ‚ истинной Ссли хотя Π±Ρ‹ ΠΎΠ΄Π½ΠΎ ΠΈΠ· ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠΉ, входящих Π² Π½Π΅Ρ‘ — истина. НапримСр, Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ «Π—Смля круглая ΠΈΠ»ΠΈ стоит Π½Π° Ρ‚Ρ€Ρ‘Ρ… ΠΊΠΈΡ‚Π°Ρ…» Π±ΡƒΠ΄Π΅Ρ‚ истинным, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠ΅Ρ€Π²ΠΎΠ΅ ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ — истинно, Ρ…ΠΎΡ‚ΡŒ Π²Ρ‚ΠΎΡ€ΠΎΠ΅ ΠΈ Π»ΠΎΠΆΠ½ΠΎ.Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ это Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Ρ‚Π°ΠΊ:

А Π‘ А ΠΈΠ»ΠΈ Π‘
Π› Π› Π›
Π› И И
И Π› И
И И И

Π‘Ρ‚Ρ€ΠΎΠ³ΡƒΡŽ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ ΠΈΠ»ΠΈ слоТСниС ΠΏΠΎ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ Ρ‚Π°ΠΊΠΆΠ΅ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ «ΠΈΡΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰ΠΈΠΌ ΠΈΠ»ΠΈ». Π­Ρ‚Π° опСрация ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π²ΠΈΠ΄ грамматичСской конструкции «ΠΎΠ΄Π½ΠΎ ΠΈΠ· Π΄Π²ΡƒΡ…: Π»ΠΈΠ±ΠΎ …, Π»ΠΈΠ±ΠΎ …». Π—Π΄Π΅ΡΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ логичСского выраТСния Π±ΡƒΠ΄Π΅Ρ‚ Π»ΠΎΠΆΠ½Ρ‹ΠΌ, Ссли всС утвСрТдСния, входящиС Π² Π½Π΅Π³ΠΎ, ΠΈΠΌΠ΅ΡŽΡ‚ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡƒΡŽ ΠΈΡΡ‚ΠΈΠ½Π½ΠΎΡΡ‚ΡŒ. Π’ΠΎ Π΅ΡΡ‚ΡŒ, ΠΎΠ±Π° утвСрТдСния Π»ΠΈΠ±ΠΎ вмСстС истинны, Π»ΠΈΠ±ΠΎ вмСстС Π»ΠΎΠΆΠ½Ρ‹.

Π’Π°Π±Π»ΠΈΡ†Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΡΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‰Π΅Π³ΠΎ ΠΈΠ»ΠΈ

А Π‘ Π»ΠΈΠ±ΠΎ А, Π»ΠΈΠ±ΠΎ Π‘
Π› Π› Π›
Π› И И
И Π› И
И
И
Π›

Π˜ΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΡ ΠΈ ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΠΎΡΡ‚ΡŒ

Π˜ΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΡ прСдставляСт собой слСдствиС ΠΈ грамматичСски ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° ΠΊΠ°ΠΊ «ΠΈΠ· А слСдуСт Π‘». Π—Π΄Π΅ΡΡŒ ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ А Π±ΡƒΠ΄Π΅Ρ‚ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒΡΡ прСдпосылкой, Π° Π‘ — слСдствиСм. Π˜ΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π»ΠΎΠΆΠ½ΠΎΠΉ, Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΎΠ΄Π½ΠΎΠΌ случаС: Ссли прСдпосылка истинна, Π° слСдствиС Π»ΠΎΠΆΠ½ΠΎ. Π’ΠΎ Π΅ΡΡ‚ΡŒ, лоТь Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΠ· истины. Π’ΠΎ всСх ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ… случаях импликация истинна. Π’Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹, ΠΊΠΎΠ³Π΄Π° ΠΎΠ±Π° утвСрТдСния ΠΈΠΌΠ΅ΡŽΡ‚ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡƒΡŽ ΠΈΡΡ‚ΠΈΠ½Π½ΠΎΡΡ‚ΡŒ, вопросов Π½Π΅ Π²Ρ‹Π·Ρ‹Π²Π°ΡŽΡ‚. Но ΠΏΠΎΡ‡Π΅ΠΌΡƒ Π²Π΅Ρ€Π½ΠΎΠ΅ слСдствиС ΠΈΠ· Π½Π΅Π²Π΅Ρ€Π½ΠΎΠΉ прСдпосылки β€” истина? Π”Π΅Π»ΠΎ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ ΠΈΠ· Π»ΠΎΠΆΠ½ΠΎΠΉ прСдпосылки ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚ΡŒ Ρ‡Ρ‚ΠΎ ΡƒΠ³ΠΎΠ΄Π½ΠΎ. Π­Ρ‚ΠΎ ΠΈ ΠΎΡ‚Π»ΠΈΡ‡Π°Π΅Ρ‚ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΡŽ ΠΎΡ‚ эквивалСнтности.

Π’ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ΅ (ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΡ… Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… дисциплинах) импликация ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для указания Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ³ΠΎ условия. НапримСр, ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ А — «Ρ‚ΠΎΡ‡ΠΊΠ° О — экстрСмум Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ», ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ Π‘ — «ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄Π½Π°Ρ Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π² Ρ‚ΠΎΡ‡ΠΊΠ΅ О обращаСтся Π² ноль». Если О, Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ, Ρ‚ΠΎΡ‡ΠΊΠ° экстрСмума Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Ρ‚ΠΎ производная Π² этой Ρ‚ΠΎΡ‡ΠΊΠ΅ Π±ΡƒΠ΄Π΅Ρ‚, ΠΈ Π²ΠΏΡ€Π°Π²Π΄Ρƒ, Ρ€Π°Π²Π½Π° Π½ΡƒΠ»ΡŽ. Если ΠΆΠ΅ О Π½Π΅ являСтся Ρ‚ΠΎΡ‡ΠΊΠΎΠΉ экстрСмума, Ρ‚ΠΎ производная Π² этой Ρ‚ΠΎΡ‡ΠΊΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½ΡƒΠ»Π΅Π²ΠΎΠΉ, Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π΅ Π±Ρ‹Ρ‚ΡŒ. Π’ΠΎ Π΅ΡΡ‚ΡŒ Π‘ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ для А, Π½ΠΎ Π½Π΅ достаточно.

Π’Π°Π±Π»ΠΈΡ†Π° ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΠΈ

Π’Π°Π±Π»ΠΈΡ†Π° истинности для ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΠΈ выглядит ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

А Π‘ ΠΈΠ· А слСдуСт Π‘
Π› Π› И
Π› И И
И Π› Π›
И И И

ЛогичСская опСрация ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΠΎΡΡ‚ΡŒ, ΠΏΠΎ сути, являСтся Π²Π·Π°ΠΈΠΌΠ½ΠΎΠΉ ΠΈΠΌΠΏΠ»ΠΈΠΊΠ°Ρ†ΠΈΠ΅ΠΉ. «Π эквивалСнтно Π‘» ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ «ΠΈΠ· А слСдуСт Π‘» ΠΈ «ΠΈΠ· Π‘ слСдуСт А» ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ. Π­ΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΠΎΡΡ‚ΡŒ Π²Π΅Ρ€Π½Π°, ΠΊΠΎΠ³Π΄Π° ΠΎΠ±Π° утвСрТдСния Π»ΠΈΠ±ΠΎ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ Π²Π΅Ρ€Π½Ρ‹Π΅, Π»ΠΈΠ±ΠΎ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ Π½Π΅Π²Π΅Ρ€Π½Ρ‹Π΅.

А Π‘ А эквивалСнтно Π‘
Π› Π› И
Π› И Π›
И Π› Π›
И И И

Π’ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ΅ ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΠΎΡΡ‚ΡŒ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для опрСдСлСния Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ³ΠΎ ΠΈ достаточного условия. НапримСр, ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ А — «Π’ΠΎΡ‡ΠΊΠ° О являСтся Ρ‚ΠΎΡ‡ΠΊΠΎΠΉ экстрСмума Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ», ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅ Π‘ — «Π’ Ρ‚ΠΎΡ‡ΠΊΠ΅ О производная Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ обращаСтся Π² ноль ΠΈ мСняСт Π·Π½Π°ΠΊ». Π­Ρ‚ΠΈ Π΄Π²Π° утвСрТдСния эквивалСнтны. Π‘ содСрТит Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ ΠΈ достаточноС условиС для А. ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ Π² Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠΉ Π‘ Π½Π° самом Π΄Π΅Π»Π΅ являСтся ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠ΅ΠΉ Π΄Π²ΡƒΡ… Π΄Ρ€ΡƒΠ³ΠΈΡ…: «ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄Π½Π°Ρ Π² Ρ‚ΠΎΡ‡ΠΊΠ΅ О обращаСтся Π² ноль» ΠΈ «ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄Π½Π°Ρ Π² Ρ‚ΠΎΡ‡ΠΊΠ΅ О мСняСт Π·Π½Π°ΠΊ».

Π’Π°Π±Π»ΠΈΡ†Π° эквивалСнтности

ΠŸΡ€ΠΎΡ‡ΠΈΠ΅ логичСскиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ

Π’Ρ‹ΡˆΠ΅ Π±Ρ‹Π»ΠΈ рассмотрСны основныС логичСскиС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ часто ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ. Π•ΡΡ‚ΡŒ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ:

  • Π¨Ρ‚Ρ€ΠΈΡ… Π¨Π΅Ρ„Ρ„Π΅Ρ€Π° ΠΈΠ»ΠΈ Π½Π΅ΡΠΎΠ²ΠΌΠ΅ΡΡ‚ΠΈΠΌΠΎΡΡ‚ΡŒ прСдставляСт собой ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ А ΠΈ Π‘
  • Π‘Ρ‚Ρ€Π΅Π»ΠΊΠ° ΠŸΠΈΡ€ΡΠ° прСдставляСт сбой ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ.

ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ Ρ‚Π°Π±Π»ΠΈΡ† истинности

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности для ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Π»ΠΈΠ±ΠΎ логичСского выраТСния, Π½Π°Π΄ΠΎ Π΄Π΅ΠΉΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ Π² соотвСтствии с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ:

  1. Π Π°Π·Π±ΠΈΡ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π½Π° простыС утвСрТдСния ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΡ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΈΠ· Π½ΠΈΡ… ΠΊΠ°ΠΊ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ.
  2. ΠžΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ логичСскиС прСобразования.
  3. Π’Ρ‹ΡΠ²ΠΈΡ‚ΡŒ порядок дСйствий этих ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ.
  4. Π‘ΠΎΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ строки Π² Π±ΡƒΠ΄ΡƒΡ‰Π΅ΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅. Π˜Ρ… количСство Ρ€Π°Π²Π½ΠΎ Π΄Π²Π° Π² стСпСни N, Π³Π΄Π΅ N — число ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, плюс ΠΎΠ΄Π½Π° строка для шапки Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹.
  5. ΠžΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ число столбцов. Оно Ρ€Π°Π²Π½ΠΎ суммС количСства ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈ количСства дСйствий. МоТно ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ дСйствия Π² Π²ΠΈΠ΄Π΅ Π½ΠΎΠ²ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ, Ссли Ρ‚Π°ΠΊ Π±ΡƒΠ΄Π΅Ρ‚ понятнСй.
  6. Π¨Π°ΠΏΠΊΠ° заполняСтся ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, сначала всС ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΏΠΎΡ‚ΠΎΠΌ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ дСйствий Π² порядкС ΠΈΡ… выполнСния.
  7. Π—Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Π½Π°Π΄ΠΎ Π½Π°Ρ‡Π°Ρ‚ΡŒ с ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ. Для Π½Π΅Ρ‘ количСство строк дСлится ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ. Одна ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Π° заполняСтся нулями, вторая — Π΅Π΄ΠΈΠ½ΠΈΡ†Π°ΠΌΠΈ.
  8. Для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π½ΡƒΠ»ΠΈ ΠΈ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ Ρ‡Π΅Ρ€Π΅Π΄ΡƒΡŽΡ‚ΡΡ Π²Π΄Π²ΠΎΠ΅ Ρ‡Π°Ρ‰Π΅.
  9. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ всС столбцы с ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ ΠΈ для послСднСй ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ мСняСтся Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строкС.
  10. ΠŸΠΎΡ‚ΠΎΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ всСх дСйствий.

Π’ ΠΈΡ‚ΠΎΠ³Π΅ послСдний столбСц ΠΎΡ‚ΠΎΠ±Ρ€Π°Π·ΠΈΡ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ всСго выраТСния Π² зависимости ΠΎΡ‚ значСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Π’Π°Π±Π»ΠΈΡ†Π° стрСлки ΠŸΠΈΡ€ΡΠ°

ΠžΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎ слСдуСт ΡΠΊΠ°Π·Π°Ρ‚ΡŒ ΠΎ порядкС логичСских дСйствий. Как Π΅Π³ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ? Π—Π΄Π΅ΡΡŒ, ΠΊΠ°ΠΊ ΠΈ Π² Π°Π»Π³Π΅Π±Ρ€Π΅, Π΅ΡΡ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»Π°, Π·Π°Π΄Π°ΡŽΡ‰ΠΈΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ дСйствий. Они Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ порядкС:

  1. выраТСния Π² скобках;
  2. ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ ΠΈΠ»ΠΈ инвСрсия;
  3. ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ;
  4. строгая ΠΈ обычная Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ;
  5. импликация;
  6. ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½Ρ‚Π½ΠΎΡΡ‚ΡŒ.

Π’Π°Π±Π»ΠΈΡ†Π° ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹

Для закрСплСния ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Π° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠΏΡ€ΠΎΠ±ΠΎΠ²Π°Ρ‚ΡŒ ΡΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности для Ρ€Π°Π½Π΅Π΅ упомянутых логичСских Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ. Рассмотрим Ρ‚Ρ€ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°:

  • Π¨Ρ‚Ρ€ΠΈΡ… Π¨Π΅Ρ„Ρ„Π΅Ρ€Π°.
  • Π‘Ρ‚Ρ€Π΅Π»ΠΊΠ° ΠŸΠΈΡ€ΡΠ°.
  • ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ эквивалСнтности.

Π¨Ρ‚Ρ€ΠΈΡ… Π¨Π΅Ρ„Ρ„Π΅Ρ€Π°

Π¨Ρ‚Ρ€ΠΈΡ… Π¨Π΅Ρ„Ρ„Π΅Ρ€Π° — это логичСскоС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ Π² Π²ΠΈΠ΄Π΅ «Π½Π΅ (А ΠΈ Π‘)». Π—Π΄Π΅ΡΡŒ Π΄Π²Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΈ Π΄Π²Π° дСйствия. ΠšΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ Π² скобках, Π·Π½Π°Ρ‡ΠΈΡ‚, ΠΎΠ½Π° выполняСтся ΠΏΠ΅Ρ€Π²ΠΎΠΉ. Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π±ΡƒΠ΄Π΅Ρ‚ шапка ΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ строки со значСниями ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Π° Ρ‚Π°ΠΊΠΆΠ΅ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ столбца. Π—Π°ΠΏΠΎΠ»Π½ΠΈΠΌ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ:

А Π‘ А ΠΈ Π‘ Π½Π΅ (А ΠΈ Π‘)
Π› Π› Π› И
Π› И Π› И
И Π› Π› И
И И И Π›

ΠžΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ выглядит ΠΊΠ°ΠΊ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠΉ. Π­Ρ‚ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, Ссли ΡΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности для выраТСния «Π½Π΅ А ΠΈΠ»ΠΈ Π½Π΅ Π‘». ΠŸΡ€ΠΎΠ΄Π΅Π»Π°ΠΉΡ‚Π΅ это ΡΠ°ΠΌΠΎΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΈ ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ здСсь Π±ΡƒΠ΄Π΅Ρ‚ ΡƒΠΆΠ΅ Ρ‚Ρ€ΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ.

Π‘Ρ‚Ρ€Π΅Π»ΠΊΠ° ΠŸΠΈΡ€ΡΠ°

Рассматривая Π‘Ρ‚Ρ€Π΅Π»ΠΊΡƒ ΠŸΠΈΡ€ΡΠ°, которая прСдставляСт собой ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΠΈ «Π½Π΅ (А ΠΈΠ»ΠΈ Π‘)», сравним Π΅Ρ‘ с ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΠ΅ΠΉ ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠΉ «Π½Π΅ А ΠΈ Π½Π΅ Π‘». Π—Π°ΠΏΠΎΠ»Π½ΠΈΠΌ Π΄Π²Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹:

А Π‘ А ΠΈΠ»ΠΈ Π‘ Π½Π΅ (А ΠΈΠ»ΠΈ Π‘)
Π› Π› Π› И
Π› И И Π›
И Π› И И
И И И Π›
А Π‘ Π½Π΅ А Π½Π΅ Π‘ Π½Π΅ А ΠΈ Π½Π΅ Π‘
Π› Π› И И И
Π› И И Π› Π›
И Π› Π› И И
И И Π› Π› Π›

ЗначСния Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ совпали. Π˜Π·ΡƒΡ‡ΠΈΠ² Π΄Π²Π° эти ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠΉΡ‚ΠΈ ΠΊ Π²Ρ‹Π²ΠΎΠ΄Ρƒ, ΠΊΠ°ΠΊ Ρ€Π°ΡΠΊΡ€Ρ‹Π²Π°Ρ‚ΡŒ скобки послС отрицания: ΠΎΡ‚Ρ€ΠΈΡ†Π°Π½ΠΈΠ΅ примСняСтся ΠΊΠΎ всСм ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌ Π² скобках, ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ мСняСтся Π½Π° Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ, Π° Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ†ΠΈΡ — Π½Π° ΠΊΠΎΠ½ΡŠΡŽΠ½ΠΊΡ†ΠΈΡŽ.

ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ эквивалСнтности

ΠŸΡ€ΠΎ утвСрТдСния А ΠΈ Π‘ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΈ эквивалСнтны, Ρ‚ΠΎΠ³Π΄Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΠ· А слСдуСт Π‘ ΠΈ ΠΈΠ· Π‘ слСдуСт А. Π—Π°ΠΏΠΈΡˆΠ΅ΠΌ это ΠΊΠ°ΠΊ логичСскоС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΈ построим для Π½Π΅Π³ΠΎ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности. «(А эквивалСнтно Π‘) эквивалСнтно (ΠΈΠ· А слСдуСт Π‘) ΠΈ (ΠΈΠ· Π‘ слСдуСт А)».

Π—Π΄Π΅ΡΡŒ Π΄Π²Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈ ΠΏΡΡ‚ΡŒ дСйствий. Π‘Ρ‚Ρ€ΠΎΠΈΠΌ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ:

А Π‘ Π’ = (ΠΈΠ· А слСдуСт Π‘) Π“ = (ΠΈΠ· Π‘ слСдуСт А) Π” = А эквивалСнтно Π‘ Π• = Π’ ΠΈ Π“ Π” эквивалСнтно Π•
Π› Π› И И И И И
Π› И И Π› Π› Π› И
И Π› Π› И Π› Π› И
И И И И И И И

Π’ послСднСм столбцС всС значСния истинныС. Π­Ρ‚ΠΎ Π·Π½Π°Ρ‡ΠΈΡ‚, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠ΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ эквивалСнтности Π²Π΅Ρ€Π½ΠΎ ΠΏΡ€ΠΈ Π»ΡŽΠ±Ρ‹Ρ… значСниях А ΠΈ Π‘. Π—Π½Π°Ρ‡ΠΈΡ‚, ΠΎΠ½ΠΎ всСгда истинно. ИмСнно Ρ‚Π°ΠΊ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎΡΡ‚ΡŒ Π»ΡŽΠ±Ρ‹Ρ… ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠΉ ΠΈ логичСских построСний.

НОУ ИНВУИВ | ЛСкция | ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ логичСских схСм

Аннотация: РассматриваСтся взаимосвязь Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… способов описания Ρ€Π°Π±ΠΎΡ‚Ρ‹ логичСских схСм ΠΈ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡ‹ ΠΈΡ… ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ.

БоставлСниС логичСских Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΏΠΎ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности

ΠšΠ°Π½ΠΎΠ½ΠΈΡ‡Π΅ΡΠΊΠ°Ρ сумма ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ²

ΠœΠΈΠ½Ρ‚Π΅Ρ€ΠΌ — это ΠΏΠΎΠ»Π½ΠΎΠ΅ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ всСх Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ ΠΎΠ΄Π½ΠΎΠΉ строкС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²Ρ‹Ρ…ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ (Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ) Ρ€Π°Π²Π½ΠΎ логичСской 1. ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Π°Ρ Π²Ρ…ΠΎΠ΄ΠΈΡ‚ Π² ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌ с инвСрсиСй, Ссли Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π² Π΄Π°Π½Π½ΠΎΠΉ строкС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Ρ€Π°Π²Π½ΠΎ 0, ΠΈ Π±Π΅Π· инвСрсии, Ссли Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π² Π΄Π°Π½Π½ΠΎΠΉ строкС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Ρ€Π°Π²Π½ΠΎ 1.

ΠšΠ°Π½ΠΎΠ½ΠΈΡ‡Π΅ΡΠΊΠ°Ρ сумма ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ² — это логичСская сумма всСх ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ², которая прСдставляСт собой максимальноС логичСскоС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности.Она составляСтся Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ:

  1. Π’ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности подсчитываСтся — количСство строк Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ€Π°Π²Π½ΠΎ 1.
  2. Π—Π°Ρ‚Π΅ΠΌ записываСтся логичСская сумма ΠΏΠΎΠ»Π½Ρ‹Ρ… ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ.
  3. Π”Π°Π»Π΅Π΅ Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΈ Ρ€Π°ΡΡΡ‚Π°Π²Π»ΡΡŽΡ‚ΡΡ инвСрсии Π½Π°Π΄ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ Π² соотвСтствии с ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ Π² строкС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹.

Для ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°, прСдставлСнного Π½Π° рис. 1.6, каноничСская сумма ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ² Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Ρ‚Π°ΠΊ:

( 2.1)

Из сравнСния (1.1) ΠΈ (2.1) Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ ΠΎΠ΄Π½ΠΎΠΉ ΠΈ Ρ‚ΠΎΠΉ ΠΆΠ΅ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности (рис. 1.6,Π±) ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π΄Π²Π° Ρ€Π°Π·Π½Ρ‹Ρ… логичСских выраТСния, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ (1.1) записываСтся Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΠΌΠΏΠ°ΠΊΡ‚Π½ΠΎ, Π½ΠΎ возмоТности ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ для Π½Π΅Π³ΠΎ Π΅Ρ‰Π΅ Π΅ΡΡ‚ΡŒ. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, Π΅ΡΡ‚ΡŒ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΈ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ схСму, ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»Π΅Π½Π½ΡƒΡŽ Π½Π° рис. 1.6, a.

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

ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠ°Ρ€Ρ‚ ΠšΠ°Ρ€Π½ΠΎ

ΠšΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ — графичСскоС прСдставлСниС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. КаТдой ΠΊΠ»Π΅Ρ‚ΠΊΠ΅ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ соотвСтствуСт строка Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. По осям ΠΊΠ°Ρ€Ρ‚Ρ‹ Ρ€Π°ΡΡΡ‚Π°Π²Π»ΡΡŽΡ‚ΡΡ сочСтания ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Π° Π²Π½ΡƒΡ‚Ρ€ΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹ — значСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

НазначСниС ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ — Π½Π°ΠΉΡ‚ΠΈ логичСскиС суммы прямого ΠΈ инвСрсного значСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…. Для любой ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, , такая сумма Ρ€Π°Π²Π½Π° ΠΏΡ€ΠΈ любом Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΈ : ΠΏΡ€ΠΈ это Π±ΡƒΠ΄Π΅Ρ‚ , ΠΏΡ€ΠΈ это . ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΡ€ΠΈ вынСсСнии Π·Π° скобки Π² Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ:

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

  1. Π’Π΅Ρ€Ρ‚ΠΈΠΊΠ°Π»ΡŒΠ½Π°Ρ ось размСчаСтся нСзависимо ΠΎΡ‚ Π³ΠΎΡ€ΠΈΠ·ΠΎΠ½Ρ‚Π°Π»ΡŒΠ½ΠΎΠΉ.
  2. ΠΠ°Ρ‡ΠΈΠ½Π°Ρ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΡƒ ΠΌΠΎΠΆΠ½ΠΎ с любого сочСтания ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….
  3. ВсС сочСтания ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ пСрСчислСны.
  4. Для сосСдних ΠΊΠ»Π΅Ρ‚ΠΎΠΊ ΠΊΠ°Ρ€Ρ‚Ρ‹ сочСтаниС ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ Ρ‡Π΅ΠΌ ΠΎΠ΄Π½ΠΈΠΌ Π·Π½Π°ΠΊΠΎΠΌ, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ сосСдними ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ строки (столбца).

Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π΄Π²ΡƒΡ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ — это ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ 2×2 ΠΊΠ»Π΅Ρ‚ΠΊΠΈ. Π’ этих ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… Ρ€Π°Π·ΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ 4 значСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠ· послСднСго столбца Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности (рис. 2.2).


Рис. 2.2. Π’Π°Π±Π»ΠΈΡ†Π° истинности (Π°) ΠΈ ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ (Π±) для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ 2 ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‚Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ — это ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊ 2×4 ΠΈΠ»ΠΈ 4×2 ΠΊΠ»Π΅Ρ‚ΠΊΠΈ. Π’ этих ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… Ρ€Π°Π·ΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ 8 Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠ· послСднСго столбца Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности (рис. 2.3). ΠŸΡ€ΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠ΅ большСй ΠΈΠ· осСй Π½ΡƒΠΆΠ½ΠΎ Ρ‡Π΅Ρ‚ΠΊΠΎ ΠΏΡ€ΠΈΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°Ρ‚ΡŒΡΡ послСднСго, Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚ΠΎΠ³ΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Π° Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠΈ ΠΈ ΡΠ»Π΅Π΄ΠΈΡ‚ΡŒ Π·Π° Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ сосСдними Π½Π΅ оказались сочСтания ΠΈ , Π»ΠΈΠ±ΠΎ ΠΈ , Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ ΠΎΠ±Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅.

Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ — это ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ 4×4 ΠΊΠ»Π΅Ρ‚ΠΊΠΈ. Π’ этих ΠΊΠ»Π΅Ρ‚ΠΊΠ°Ρ… Ρ€Π°Π·ΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ 16 Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠ· послСднСго столбца Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности (рис. 2.4). ΠŸΡ€ΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠ΅ ΠΎΠ±Π΅ΠΈΡ… осСй Π½ΡƒΠΆΠ½ΠΎ Ρ‚Π°ΠΊΠΆΠ΅ Ρ‡Π΅Ρ‚ΠΊΠΎ ΠΏΡ€ΠΈΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°Ρ‚ΡŒΡΡ послСднСго, Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚ΠΎΠ³ΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Π° Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠΈ ΠΈ ΡΠ»Π΅Π΄ΠΈΡ‚ΡŒ Π·Π° Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ оси сосСдними Π½Π΅ оказались сочСтания ΠΈ , Π»ΠΈΠ±ΠΎ ΠΈ , Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ ΠΎΠ±Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅.

Для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ пяти ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΊΠ°Ρ€Ρ‚Π° ΠšΠ°Ρ€Π½ΠΎ прСдставляСт собой ΡƒΠΆΠ΅ ΠΎΠ±ΡŠΠ΅ΠΌΠ½ΡƒΡŽ Ρ„ΠΈΠ³ΡƒΡ€Ρƒ — ΠΊΡƒΠ± 4x4x4 ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, поэтому для ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ логичСских Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΎΠ½Π° Π½Π΅ примСняСтся.


ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΡ‚ΡŒ ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅
Рис. 2.3. Π’Π°Π±Π»ΠΈΡ†Π° истинности (Π°) ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ заполнСния ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ (Π±, Π², Π³, Π΄) для логичСской Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ 3 ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….
ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΡ‚ΡŒ ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅
Рис. 2.4. Π’Π°Π±Π»ΠΈΡ†Π° истинности (Π°) ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ заполнСния ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ (Π±, Π²) для логичСской Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ 4 ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Π’ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Ρ… случаях вмСсто Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π² ΠΎΠ±Ρ‰Π΅ΠΌ Π²ΠΈΠ΄Π΅ Π² ΠΊΠ»Π΅Ρ‚ΠΊΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠΏΡ€ΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ΡΡ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Π΅ значСния (логичСскиС 0 ΠΈ 1) ΠΈΠ· ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… строк Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности. Π—Π°Ρ‚Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°ΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚Π΅ ΠΊΠ»Π΅Ρ‚ΠΊΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Ρ‹ Π΅Π΄ΠΈΠ½ΠΈΡ†Π°ΠΌΠΈ. ВсС эти Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ ΠΎΠ±Π²Π΅Π΄Π΅Π½Ρ‹ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π°ΠΌΠΈ ΠΏΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌ составлСния ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ²:

  1. ΠšΠΎΠ½Ρ‚ΡƒΡ€Ρ‹ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ ΠΏΡ€ΡΠΌΠΎΡƒΠ³ΠΎΠ»ΡŒΠ½Ρ‹ΠΌΠΈ ΠΈ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ количСство Π΅Π΄ΠΈΠ½ΠΈΡ†, Ρ€Π°Π²Π½ΠΎΠ΅ , Π³Π΄Π΅ — Ρ†Π΅Π»ΠΎΠ΅ число. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π² ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π»ΠΈΠ±ΠΎ ΠΎΠ΄Π½Π°, Π»ΠΈΠ±ΠΎ Π΄Π²Π΅, Π»ΠΈΠ±ΠΎ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅, Π»ΠΈΠ±ΠΎ восСмь Π΅Π΄ΠΈΠ½ΠΈΡ†.
  2. ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡ† Π² ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, ΠΏΡ€ΠΈ этом ΠΊΠΎΠ½Ρ‚ΡƒΡ€Ρ‹ ΠΌΠΎΠ³ΡƒΡ‚ ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°Ρ‚ΡŒΡΡ ΠΌΠ΅ΠΆΠ΄Ρƒ собой. НуТно ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ строки ΡΠ²Π»ΡΡŽΡ‚ΡΡ сосСдними ΠΈ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ столбцы Ρ‚Π°ΠΊΠΆΠ΅ ΡΠ²Π»ΡΡŽΡ‚ΡΡ сосСдними, поэтому ΠΊΠΎΠ½Ρ‚ΡƒΡ€Ρ‹ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ «Ρ€Π°Π·ΠΎΡ€Π²Π°Π½Π½Ρ‹ΠΌΠΈ».
  3. ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ² Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, Π½ΠΎ всС Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ ΠΎΡ…Π²Π°Ρ‡Π΅Π½Ρ‹ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π°ΠΌΠΈ. НСльзя Π·Π°Π±Ρ‹Π²Π°Ρ‚ΡŒ ΠΎΠ± ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎ стоящих Π΅Π΄ΠΈΠ½ΠΈΡ†Π°Ρ…. КаТдая такая Π΅Π΄ΠΈΠ½ΠΈΡ†Π° — это ΠΊΠΎΠ½Ρ‚ΡƒΡ€, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ соотвСтствуСт ΠΏΠΎΠ»Π½ΠΎΠ΅ логичСскоС ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ всСх ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

ПослС обвСдСния ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ² Π½ΡƒΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ минимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ ΠΊΠ°ΠΊ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ сумму логичСских ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ. ΠšΠ°ΠΆΠ΄ΠΎΠΌΡƒ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡŽ соотвСтствуСт ΠΎΠ΄ΠΈΠ½ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ. Π’ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ входят Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΎΡΡ‚Π°ΡŽΡ‚ΡΡ Π² Π΄Π°Π½Π½ΠΎΠΌ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ Π½Π΅ΠΈΠ·ΠΌΠ΅Π½Π½Ρ‹ΠΌΠΈ.ΠŸΡ€ΠΈ этом пСрСмСнная Π²Ρ…ΠΎΠ΄ΠΈΡ‚ Π² ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ с инвСрсиСй, Ссли Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π² Π΄Π°Π½Π½ΠΎΠΌ ΠΊΠΎΠ½Ρ‚ΡƒΡ€Π΅ Ρ€Π°Π²Π½ΠΎ 0, ΠΈ Π±Π΅Π· инвСрсии, Ссли Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ€Π°Π²Π½ΠΎ 1.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1. ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ минимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ для Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности, прСдставлСнной Π½Π° рис. 2.5,Π° ΠΈ Π½Π°Ρ€ΠΈΡΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎ Π½Π΅ΠΌΡƒ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ схСму.

ΠŸΡ€ΠΈ ΠΎΠ΄Π½ΠΎΠΌ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π΅ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠΈ осСй (рис. 2.5,Π±) ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€, состоящий ΠΈΠ· Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ†, получаСтся Ρ€Π°Π·ΠΎΡ€Π²Π°Π½Π½Ρ‹ΠΌ. Если ΠΆΠ΅ ΠΏΡ€ΠΈΠ½ΡΡ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΡƒ, ΠΏΠΎΠΊΠ°Π·Π°Π½Π½ΡƒΡŽ Π½Π° рис. 2.5,Π², Ρ‚ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ очСртания, Π° Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅, Π΅ΠΌΡƒ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅, останСтся Π±Π΅Π· ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ. Учитывая, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈ Π΄Π°Π½Π½ΠΎΠΌ Π³ΠΎΡ€ΠΈΠ·ΠΎΠ½Ρ‚Π°Π»ΡŒΠ½ΠΎΠΌ Π½Π°Ρ‡Π΅Ρ€Ρ‚Π°Π½ΠΈΠΈ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠšΠ°Ρ€Π½ΠΎ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ столбцы ΡΠ²Π»ΡΡŽΡ‚ΡΡ сосСдними, Π΅Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ сСбС ΠΊΠ°ΠΊ Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€, Ρ€Π°Π·Π²Π΅Ρ€Π½ΡƒΡ‚Ρ‹ΠΉ Π½Π° плоскости. На рис. 2.5,Π± прСдставлСна Ρ€Π°Π·Π²Π΅Ρ€Ρ‚ΠΊΠ° Ρ‚Π°ΠΊΠΎΠ³ΠΎ Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€Π°, «Ρ€Π°Π·Ρ€Π΅Π·Π°Π½Π½Π°Ρ» ΠΌΠ΅ΠΆΠ΄Ρƒ комбинациями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ . А Π½Π° рис. 2.5,Π² прСдставлСна Ρ€Π°Π·Π²Π΅Ρ€Ρ‚ΠΊΠ° этого ΠΆΠ΅ Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€Π°, «Ρ€Π°Π·Ρ€Π΅Π·Π°Π½Π½Π°Ρ» ΠΌΠ΅ΠΆΠ΄Ρƒ произвСдСниями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ .

ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΎΡ…Π²Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹, Π΅ΠΌΡƒ соотвСтствуСт сумма ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ²: , Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π½Π΅ измСняСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ пСрСмСнная . Π’Ρ‚ΠΎΡ€ΠΎΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ ΠΎΡ…Π²Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ Π΄Π²Π΅ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρ‹. Π•ΠΌΡƒ соотвСтствуСт сумма ΠΌΠΈΠ½Ρ‚Π΅Ρ€ΠΌΠΎΠ² , Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ пСрСмСнная ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ ΠΎΠ±Π° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… значСния, Π° ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ остаСтся Π½Π΅ΠΈΠ·ΠΌΠ΅Π½Π½Ρ‹ΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ минимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅:

( 2.2)

Π•ΠΌΡƒ соотвСтствуСт логичСская схСма Π½Π° рис. 2.5,Π³.



Рис. 2.5. ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‚Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…

Для сравнСния запишСм максимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅:

( 2.3)

Π Π°Π·Π½ΠΈΡ†Π° ΠΌΠ΅ΠΆΠ΄Ρƒ (2.2) ΠΈ (2.3) ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Π° ΠΈ Π² коммСнтариях Π½Π΅ нуТдаСтся, Π·Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ΠΌ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ схСма, рСализованная ΠΏΠΎ (2.3), Π±ΡƒΠ΄Π΅Ρ‚ Π½Π° порядок слоТнСС ΠΈ, соотвСтствСнно, ΠΌΠ΅Π½Π΅Π΅ Π½Π°Π΄Π΅ΠΆΠ½Π°, Ρ‡Π΅ΠΌ схСма, показанная Π½Π° рис. 2.5,Π³.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2. ΠΠ°ΠΏΠΈΡΠ°Ρ‚ΡŒ минимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ для Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности, прСдставлСнной Π½Π° рис. 2.6,Π°, ΠΈ Π½Π°Ρ€ΠΈΡΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎ Π½Π΅ΠΌΡƒ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ схСму.


Рис. 2.6. ΠœΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…

ΠŸΡ€ΠΈ ΠΏΠ΅Ρ€Π²ΠΎΠ½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎ Π²Ρ‹Π±Ρ€Π°Π½Π½ΠΎΠΉ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΠ΅ осСй (рис. 2.6,Π±) ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚ΡƒΡ€, состоящий ΠΈΠ· Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… Π΅Π΄ΠΈΠ½ΠΈΡ† с Π½ΠΎΠΌΠ΅Ρ€Π°ΠΌΠΈ 1.1, 1.2, 1.3 ΠΈ 1.4, располоТСнных ΠΏΠΎ ΡƒΠ³Π»Π°ΠΌ ΠΊΠ°Ρ€Ρ‚Ρ‹, получаСтся Ρ€Π°Π·ΠΎΡ€Π²Π°Π½Π½Ρ‹ΠΌ. Если ΠΆΠ΅ ΠΏΡ€ΠΈΠ½ΡΡ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ‚ΠΊΡƒ, ΠΏΠΎΠΊΠ°Π·Π°Π½Π½ΡƒΡŽ Π½Π° рис. 2.7, Ρ‚ΠΎ ΠΊΠΎΠ½Ρ‚ΡƒΡ€ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ очСртания ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π°, Π° Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅, Π΅ΠΌΡƒ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅, останСтся Π±Π΅Π· ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ. Учитывая, Ρ‡Ρ‚ΠΎ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ столбцы ΡΠ²Π»ΡΡŽΡ‚ΡΡ сосСдними ΠΈ ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ строки ΡΠ²Π»ΡΡŽΡ‚ΡΡ сосСдними, ΠΊΠ°Ρ€Ρ‚Ρƒ ΠšΠ°Ρ€Π½ΠΎ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ сСбС ΠΊΠ°ΠΊ Ρ‚ΠΎΡ€Ρ€ΠΎΠΈΠ΄, Ρ€Π°Π·Π²Π΅Ρ€Π½ΡƒΡ‚Ρ‹ΠΉ Π½Π° плоскости. ΠŸΡ€ΠΎΡ‰Π΅ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ сСбС ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ процСсс получСния Ρ‚ΠΎΡ€Ρ€ΠΎΠΈΠ΄Π° ΠΈΠ· плоской Ρ„ΠΈΠ³ΡƒΡ€Ρ‹ — ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π°. Для этого Π½Π°Π΄ΠΎ сначала ΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ мыслСнно ΠΊΡ€Π°ΠΉΠ½ΠΈΠ΅ строки — ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€. ПослС этого основания Ρ†ΠΈΠ»ΠΈΠ½Π΄Ρ€ΠΎΠ² Π½Π°Π΄ΠΎ мыслСнно ΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ. ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡΡ Ρ‚ΠΎΡ€Ρ€ΠΎΠΈΠ΄. На рис. 2.6,Π± прСдставлСна Ρ€Π°Π·Π²Π΅Ρ€Ρ‚ΠΊΠ° Ρ‚Π°ΠΊΠΎΠ³ΠΎ Ρ‚ΠΎΡ€Ρ€ΠΎΠΈΠ΄Π°, «Ρ€Π°Π·Ρ€Π΅Π·Π°Π½Π½Π°Ρ» ΠΌΠ΅ΠΆΠ΄Ρƒ комбинациями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ сочСтаниями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ . А Π½Π° рис. 2.7 прСдставлСна Ρ€Π°Π·Π²Π΅Ρ€Ρ‚ΠΊΠ° этого ΠΆΠ΅ Ρ‚ΠΎΡ€Ρ€ΠΎΠΈΠ΄Π°, «Ρ€Π°Π·Ρ€Π΅Π·Π°Π½Π½Π°Ρ» ΠΌΠ΅ΠΆΠ΄Ρƒ комбинациями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ произвСдСниями , Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ ΠΈ . ПослС Π°Π½Π°Π»ΠΈΠ·Π° ΠΊΠΎΠ½Ρ‚ΡƒΡ€ΠΎΠ² ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ минимальноС Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ . Π‘ΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π°Ρ Π΅ΠΌΡƒ схСма ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° Π½Π° рис. 2.8.


Рис. 2.7. К ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ логичСской Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…
Рис. 2.8. ЛогичСская схСма для ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ логичСского выраТСния

ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности online | ПолСзная информация

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ Ρ‚Π°Π±Π»ΠΈΡ†Π° истинности?

Π’Π°Π±Π»ΠΈΡ†Π°, ΠΎΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‰Π°Ρ Π»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ, называСтся Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ истинности.

Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ истинности пСрСчислСны всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Π½Π°Π±ΠΎΡ€Ρ‹ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ….

Π’ послСднСм столбцС Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ истинности выводится число, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, ΠΏΠΎ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΡΡ‚Ρ€ΠΎΠΈΠ»Π°ΡΡŒ данная Ρ‚Π°Π±Π»ΠΈΡ†Π° истинности.

Β 

Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€:

Допустим, Ρƒ нас Π΅ΡΡ‚ΡŒ Π΄Π²Π΅ Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… x1 ΠΈ x2. ΠžΡ‚ этих ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… зависит логичСская функция f(x1,x2)

Для ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° возьмСм f(x1,x2)=x1∧x2∨x1.

Π’Π°ΠΊ ΠΊΠ°ΠΊΒ x1,Β x2Β Π±ΡƒΠ»Π΅Π²Ρ‹, Ρ‚ΠΎ ΠΎΠ½ΠΈ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‚ значния 0 ΠΈΠ»ΠΈ 1 (Π˜ΡΡ‚ΠΈΠ½Π° ΠΈΠ»ΠΈ Π›ΠΎΠΆΡŒ, True ΠΈΠ»ΠΈ False, сокращСнно ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΈΡΠ°Ρ‚ΡŒ T ΠΈΠ»ΠΈ F).

ВсС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… x1 ΠΈ x2 ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅:

x1x2f(x1,x2)
0 0 Β 
0 1 Β 
1 0 Β 
1 1 Β 

Β 

ΠŸΠΎΠ΄ΡΡ‚Π°Π²ΠΈΠΌ значСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… x1 ΠΈ x2 Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строчкС Π² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ f(x1,x2).

f(0,0)= 0∧0∨0=0

f(0,1)= 0∧1∨0=0

f(1,0)= 1∧0∨1=1

f(1,1)= 1∧1∨1=1

Β 

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠ²ΡˆΠΈΠ΅ΡΡ значСния запишСм Π² послСдний столбСц нашСй Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹:

x1x2f(x1,x2)
0 0 0
0 1 0
1 0 1
1 1 1

Β 

ΠœΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈΒ f(x1,x2)=x1∧x2∨x1.

Β 

На нашСм сайтС Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ истинности online.

Для этого Π²Π°ΠΌ всСго лишь Π½ΡƒΠΆΠ½ΠΎ ввСсти Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π² ΠΏΠΎΠ»Π΅ ΠΈ Π½Π°ΠΆΠ°Ρ‚ΡŒ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ.

Β 


Β 

Π’Π°Π±Π»ΠΈΡ†Ρ‹ истинности основных Π±ΡƒΠ»Π΅Π²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ:

Β 

Π£Π½Π°Ρ€Π½Ρ‹Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

Π‘ΠΈΠ½Π°Ρ€Π½Ρ‹Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ


alexxlab

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

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