Задание 2
тема 2 из 3

Логические операции и выражения

Логическое выражение составляют из высказываний и пяти операций: отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. Значение выражения на наборе переменных находят по таблицам истинности операций в порядке приоритета: сначала отрицание, последней эквивалентность. В Python для операций есть слова not, and, or и сравнения чисел 0 и 1, а импликацию и эквивалентность всегда берут в скобки.

Реже в заданиях215На карте навыков

Как вычислить логическое выражение

Высказывание истинно (1) или ложно (0). Логическая операция по значениям высказываний даёт новое значение 0 или 1.

  • ¬A\neg A (НЕ) меняет значение. A∧BA \land B (И) равна 1, только когда обе части равны 1. A∨BA \lor B (ИЛИ) равна 0, только когда обе части равны 0.
  • A→BA \to B равна 0 только при A=1A = 1, B=0B = 0. A≡BA \equiv B равна 1, когда значения AA и BB совпадают.
  • Порядок действий без скобок: ¬\neg, ∧\land, ∨\lor, →\to, ≡\equiv. Выражение в скобках считают первым.
  • Значение на наборе: подставьте 0 и 1 вместо переменных, считайте от внутренних скобок к внешним, записывайте значение каждой скобки.
  • Python: not, and, or; импликация (a <= b), эквивалентность (a == b), обе всегда в скобках.

Высказывание, переменная и функция

Высказывание — утверждение, о котором можно сказать, истинно оно или ложно. «5 больше 3» — истинное высказывание, «10 делится на 4» — ложное. Истину обозначают 1, ложь — 0. Вопрос или просьба не высказывание: они не истинны и не ложны.

Логическая переменная принимает только значения 0 и 1. В заданиях ЕГЭ это xx, yy, zz, ww или AA, BB, CC. Логическое выражение составляют из переменных, знаков операций и скобок. Выражение задаёт логическую функцию F(x,y,…)F(x, y, \ldots): каждому набору значений переменных, например x=1x = 1, y=0y = 0, она ставит в соответствие одно значение, 0 или 1.

Пример

Какие утверждения — высказывания? Найдите их значения: «2+2=52 + 2 = 5», «17 — простое число», «Решите уравнение», «x>3x > 3».

  1. 1.«2+2=52 + 2 = 5» — высказывание, оно ложно: 0.
  2. 2.«17 — простое число» — высказывание, оно истинно: у 17 только делители 1 и 17. Значение 1.
  3. 3.«Решите уравнение» — просьба, а не высказывание.
  4. 4.«x>3x > 3» — значение зависит от xx. Это не высказывание, а предикат.

Ответ: высказывания — первые два, их значения 0 и 1

Таблицы истинности операций

ABНЕ AA И BA ИЛИ BA → BA ≡ B
0010011
0110110
1000100
1101111

Отрицание, конъюнкция и дизъюнкция

Отрицание (инверсия, логическое НЕ) ¬A\neg A меняет значение: ¬1=0\neg 1 = 0, ¬0=1\neg 0 = 1. Конъюнкция (логическое умножение, И) A∧BA \land B равна 1, только когда обе части равны 1. В условиях ЕГЭ её пишут также A&BA \mathbin{\&} B. Дизъюнкция (логическое сложение, ИЛИ) A∨BA \lor B равна 0, только когда обе части равны 0. Её пишут также A∣BA \mid B.

Для многих частей правило то же. Конъюнкция A∧B∧C∧…A \land B \land C \land \ldots равна 1, только когда все множители равны 1: один ноль делает её нулём. Дизъюнкция A∨B∨C∨…A \lor B \lor C \lor \ldots равна 0, только когда все слагаемые равны 0: одна единица делает её единицей.

Пример

x=1x = 1, y=0y = 0, z=0z = 0. Найдите значение (x∨y)∧¬z∧¬y(x \lor y) \land \neg z \land \neg y.

  1. 1.Скобка: x∨y=1∨0=1x \lor y = 1 \lor 0 = 1.
  2. 2.Отрицания: ¬z=1\neg z = 1, ¬y=1\neg y = 1.
  3. 3.Все три множителя равны 1, конъюнкция равна 1.

Ответ: 11

Импликация

Импликация (следование) A→BA \to B читают «если AA, то BB». AA — посылка, BB — следствие. Импликация ложна только в одном случае: посылка истинна, а следствие ложно, 1→0=01 \to 0 = 0. Во всех остальных случаях она равна 1. При ложной посылке импликация истинна при любом следствии: 0→0=10 \to 0 = 1 и 0→1=10 \to 1 = 1.

Части импликации нельзя менять местами: A→BA \to B и B→AB \to A различаются при A=1A = 1, B=0B = 0. Скобки тоже важны: (x→y)→z(x \to y) \to z и x→(y→z)x \to (y \to z) — разные выражения. Импликацию можно заменить на ¬A∨B\neg A \lor B: это один из законов алгебры логики.

Пример

x=0x = 0, y=1y = 1, z=0z = 0. Найдите значения (x→y)→z(x \to y) \to z и x→(y→z)x \to (y \to z).

  1. 1.Первое выражение: x→y=0→1=1x \to y = 0 \to 1 = 1, затем 1→z=1→0=01 \to z = 1 \to 0 = 0.
  2. 2.Второе выражение: y→z=1→0=0y \to z = 1 \to 0 = 0, затем x→0=0→0=1x \to 0 = 0 \to 0 = 1, потому что посылка ложна.
  3. 3.Значения разные: скобки меняют результат.

Ответ: 00 и 11

Эквивалентность

Эквивалентность (тождество, равносильность) A≡BA \equiv B равна 1, когда значения AA и BB совпадают: оба 0 или оба 1. Когда значения разные, она равна 0. Отрицание эквивалентности ¬(A≡B)\neg(A \equiv B) равно 1 как раз при разных значениях. Эту операцию называют исключающим ИЛИ.

Части эквивалентности можно менять местами: A≡BA \equiv B и B≡AB \equiv A — одно и то же. Выражение ¬x≡¬y\neg x \equiv \neg y равно x≡yx \equiv y: отрицание меняет обе части, а совпадение остаётся.

Пример

x=1x = 1, y=0y = 0, z=1z = 1. Найдите значение ¬(x≡y)≡z\neg(x \equiv y) \equiv z.

  1. 1.x≡y=0x \equiv y = 0: значения 1 и 0 разные.
  2. 2.¬(x≡y)=¬0=1\neg(x \equiv y) = \neg 0 = 1.
  3. 3.1≡z=1≡1=11 \equiv z = 1 \equiv 1 = 1.

Ответ: 11

Порядок действий

Если скобок нет, операции выполняют в порядке приоритета: сначала ¬\neg, затем ∧\land, затем ∨\lor, затем →\to, последней ≡\equiv. Подряд идущие конъюнкции, как и подряд идущие дизъюнкции, можно считать в любом порядке: A∧B∧CA \land B \land C — это (A∧B)∧C(A \land B) \land C. Выражение в скобках считают первым.

Так, A∧B∨C∧DA \land B \lor C \land D означает (A∧B)∨(C∧D)(A \land B) \lor (C \land D). Отрицание относится только к ближайшей переменной или скобке: ¬x∧y\neg x \land y — это (¬x)∧y(\neg x) \land y, а не ¬(x∧y)\neg(x \land y).

Пример

x=1x = 1, y=0y = 0, z=1z = 1, w=0w = 0. Найдите значение ¬x∨y∧z→w≡x\neg x \lor y \land z \to w \equiv x.

  1. 1.Расставляем скобки по приоритету: ((¬x∨(y∧z))→w)≡x((\neg x \lor (y \land z)) \to w) \equiv x.
  2. 2.¬x=0\neg x = 0, y∧z=0∧1=0y \land z = 0 \land 1 = 0.
  3. 3.¬x∨(y∧z)=0∨0=0\neg x \lor (y \land z) = 0 \lor 0 = 0.
  4. 4.0→w=0→0=10 \to w = 0 \to 0 = 1.
  5. 5.1≡x=1≡1=11 \equiv x = 1 \equiv 1 = 1.

Ответ: 11

Значение выражения на наборе

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

Часто всё выражение считать не нужно. Дизъюнкция равна 1, если одно слагаемое равно 1. Конъюнкция равна 0, если один множитель равен 0. Импликация равна 1, если посылка равна 0 или следствие равно 1. Найдите такую часть первой, и значение известно.

Пример

x=0x = 0, y=1y = 1, z=1z = 1, w=0w = 0. Найдите значение (x∨¬y)→(z∧w∨(y≡z))(x \lor \neg y) \to (z \land w \lor (y \equiv z)).

  1. 1.Посылка: x∨¬y=0∨0=0x \lor \neg y = 0 \lor 0 = 0.
  2. 2.Посылка ложна, поэтому импликация равна 1. Следствие можно не считать.
  3. 3.Проверка: z∧w=0z \land w = 0, y≡z=1y \equiv z = 1, следствие 0∨1=10 \lor 1 = 1, и 0→1=10 \to 1 = 1.

Ответ: 11

Логические операции в Python

В Python отрицание, конъюнкцию и дизъюнкцию пишут словами not, and, or. Их приоритет тот же, что в ЕГЭ: not, затем and, затем or. Значения 0 и 1 — обычные числа: 0 считается ложью, 1 — истиной.

Отдельного знака импликации в Python нет. Для чисел 0 и 1 A→BA \to B записывают как a <= b: сравнение ложно только при a = 1, b = 0. Другая запись — (not a) or b. Эквивалентность A≡BA \equiv B — это a == b. Порядок not, and, or в условиях программ разобран в теме сложные условия в Python.

Программа считает значение

Ручной счёт легко проверить программой: присвойте переменным значения и напечатайте выражение. Операции and и or возвращают одну из своих частей, а сравнения возвращают True или False. Функция int превращает результат в 1 или 0.

Пример

x=1x = 1, y=0y = 0, z=1z = 1, w=0w = 0. Найдите значение (x→y)≡(¬z∨w)(x \to y) \equiv (\neg z \lor w).

  1. 1.Вручную: x→y=1→0=0x \to y = 1 \to 0 = 0, ¬z∨w=0∨0=0\neg z \lor w = 0 \lor 0 = 0, 0≡0=10 \equiv 0 = 1.
  2. 2.В программе импликация — (x <= y), эквивалентность — == между двумя скобками. Первая строка печатает 1.
  3. 3.Вторая строка без скобок ошибочна: Python читает x <= y == (not z) как цепочку сравнений и печатает 0.

Ответ: 11

Предикат и кванторы

Предикат (высказывательная форма) — утверждение с переменной, которое становится высказыванием, когда вместо переменной подставляют число. Предикат x>3x > 3 при x=5x = 5 истинен, при x=2x = 2 ложен. В задании 15 встречаются предикаты ДЕЛ(x,A)\text{ДЕЛ}(x, A) («xx делится на AA без остатка») и x∈Dx \in D («точка xx лежит на отрезке DD»). Связь операций с множествами точек разобрана в блоке отрезки и множества.

Квантор всеобщности ∀x\forall x читают «для любого xx». Высказывание ∀x  P(x)\forall x \; P(x) истинно, если предикат истинен при каждом значении xx. Одного значения с P(x)=0P(x) = 0 достаточно, чтобы оно стало ложным. Квантор существования ∃x\exists x читают «существует xx». Высказывание ∃x  P(x)\exists x \; P(x) истинно, если есть хотя бы одно значение xx с P(x)=1P(x) = 1. Выражение, которое истинно при любых значениях переменных, называют тождественно истинным.

Пример

P(x)=ДЕЛ(x,2)→ДЕЛ(x,4)P(x) = \text{ДЕЛ}(x, 2) \to \text{ДЕЛ}(x, 4), xx — натуральное число. Истинны ли высказывания ∀x  P(x)\forall x \; P(x) и ∃x  P(x)\exists x \; P(x)?

  1. 1.x=6x = 6: 6 делится на 2, но не делится на 4. P(6)=1→0=0P(6) = 1 \to 0 = 0, поэтому ∀x  P(x)\forall x \; P(x) ложно.
  2. 2.x=8x = 8: 8 делится и на 2, и на 4. P(8)=1→1=1P(8) = 1 \to 1 = 1, поэтому ∃x  P(x)\exists x \; P(x) истинно.

Ответ: первое ложно, второе истинно

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать