Урок №8

Определение истинности составного высказывания.

  На уроках алгебры вы составляете, преобразуете и вычисляете значения арифметических выражений, состоящих из чисел, переменных, знаков арифметических операций и скобок. Точно так же из логических значений, логических переменных, логических операций и скобок можно составлять логические выражения.

    Любое составное высказывание можно записать в виде логического выражения — выражения, содержащего логические переменные, логические значения, знаки логических операций и скобки.

Логическое выражение — это запись составного высказывания, составленная из логических переменных, логических значений, знаков логических операций и скобок.

    Логические операции в логическом выражении выполняются в следующей очерёдности: инверсия, конъюнкция, дизъюнкция. Изменить порядок выполнения операций можно с помощью расстановки скобок.

Логические операции при выполнении имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция.

    Для вычисления значения логического выражения необходимо:

1. 1. вычислить значения выражений в скобках (при наличии скобок);
   2. выполнить логические операции в соответствии с их приоритетом.

    Рассмотрим некоторые логические выражения и вычислим их значения:

1. 1. (0 v 1) ∧ 1 = 1 ∧ 1 = 1;
   2. ¬(0 v 1 ∧ 1) = ¬(0 ∨ 1) = ¬1 = 0;
   3. (1 v 1) ∧ (0 v 1) = 1 ∧ 1 = 1;
   4. 1 v 1 ∧ 0 v 1 = 1 v 0 v 1 = 1;
   5. ¬(0 ∧ 1) ∧ ¬1 = ¬0 ∧ ¬1 = 1 ∧ 0 = 0.

    Ни одно из рассмотренных выше логических выражений 1-5 не содержало логических переменных, поэтому их можно было вычислить с помощью таблиц истинности логических операций.

    Рассмотрим примеры логических выражений, содержащих логические переменные.

1) A v 0 = А — нулевой операнд не может повлиять на результат логического сложения, который будет полностью зависеть от значения А;

2) А ∧ 0 = 0 — так как один из операндов равен 0, то результат логического умножения тоже будет равен 0, независимо от того, чему равно А;

3) A v 1 = 1 — так как один из операндов равен 1, то логическая сумма будет равна 1 при любом значении А;

4) А ∧ 1 = А — единичный операнд не может повлиять на результат логического умножения, который будет полностью зависеть от значения А.

    Равенства 1-4 называют иначе законами операций с константами 0 к 1; они бывают полезны при определении истинности логических высказываний.

Пример 

    Определим истинность высказывания (X < 13) И НЕ (X < 2) при X = 0.

    Вначале определим истинность простых высказываний:

0 < 13— истинное высказывание;

0 < 2 — истинное высказывание.

    Запишем логическое выражение, соответствующее исходному высказыванию, и вычислим его значение:

1 ∧ ¬1 = 1 ∧ 0 = 0.

Пример

    Определим, при каких целых значениях X высказывание (X < 13) И НЕ (X < 2) будет истинным.

    Для этого, в первую очередь, избавимся от отрицания: вместо НЕ (Х<2) запишем (Х>=2).

    Перейдём от записи (X < 13) И (X >= 2) к принятой в математике записи системы неравенств:

Изобразим решение этой системы неравенств графически:

    Решением системы неравенств является множество из следующих одиннадцати чисел {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; минимальным из них является 2, максимальным — 12.

    При всех перечисленных значениях X исходное высказывание будет истинным.

Задачи, в которых требуется определить истинность или ложность некоторых высказываний, принято называть логическими. Существуют разные способы решения логических задач, в том числе путём преобразования логических выражений.

    Для логических операций справедливы многие законы, аналогичные законам для арифметических операций:

    Покажем, как эти законы могут быть использованы при решении логических задач.

Задача

    В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

1) Сима будет первой. Валя — второй;

2) Сима будет второй, Даша — третьей;

3) Алла будет второй, Даша — четвёртой.

    По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое — ложно. Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах?

Решение

    Рассмотрим простые высказывания:

С₁ = «Сима заняла первое место»;

В₂ = «Валя заняла второе место»;

С₂ = «Сима заняла второе место»;

Д₃= «Даша заняла третье место»;

А₂ = «Алла заняла второе место»;

Д₄ = «Даша заняла четвёртое место».

    Так как в каждом из трёх предположений одно из высказываний истинно, а другое ложно, то можно заключить следующее:

1) C₁ + В₂ = 1,       С₁ • В₂= 0;

2) С₂ + Д₃ = 1,      С₂ •  Д₃ = 0;

3) А₂ + Д₄ = 1,      А₂ • Д₄ = 0.

    Логическое произведение истинных высказываний будет истинным:

(C₁ + В₂) • (С₂ + Д3) • (А₂ + Д₄) = 1.

    На основании распределительного закона преобразуем левую часть этого выражения:

(С1 • С₂ + C₁ • Д₃ + В₂ • С₂ + В₂ • _Д3) • (А₂ + Д₄) = 1.

    Высказывание С₁ • С₂ означает, что Сима заняла и первое, и второе место. Согласно условию задачи, это высказывание ложно. Ложным является и высказывание В₂ • С₂. Учитывая закон операций с константой 0, запишем:

(С₁ • Д₃+ В₂ • Д₃) • (А₂ + Д₄)= 1.

    Дальнейшее преобразование левой части этого равенства и исключение заведомо ложных высказываний дают:

С₁ • Д₃ • А₂ + С₁ • Д₃ • Д₄ + В₂ • Д₃ • А₂ + В₂ • Д₃ • Д₄ ⁼ 1

С₁ • Д₃ • А₂ = 1.

Из последнего равенства следует, что С₁ = 1, Д₃ = 1, А₂ = 1. Это означает, что Сима заняла первое место, Алла — второе, Даша — третье. Следовательно, Валя заняла четвёртое место.

ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ