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

Законы алгебры логики

Законы алгебры логики — тождества, которые заменяют часть логического выражения на равносильную и не меняют его значения. Главные из них: импликация через ИЛИ, законы де Моргана, распределительные законы и поглощение. С ними упрощают выражения в заданиях 2 и 15, а ответ проверяют таблицей истинности или программой.

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

Законы алгебры логики

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

  • Импликация: A→B=¬A∨BA \to B = \neg A \lor B, ¬(A→B)=A∧¬B\neg(A \to B) = A \land \neg B.
  • Эквивалентность: A≡B=(A∧B)∨(¬A∧¬B)A \equiv B = (A \land B) \lor (\neg A \land \neg B).
  • Де Морган: ¬(A∧B)=¬A∨¬B\neg(A \land B) = \neg A \lor \neg B, ¬(A∨B)=¬A∧¬B\neg(A \lor B) = \neg A \land \neg B. Двойное отрицание: ¬¬A=A\neg \neg A = A.
  • A∧¬A=0A \land \neg A = 0, A∨¬A=1A \lor \neg A = 1. Поглощение: A∨(A∧B)=AA \lor (A \land B) = A.
  • Упрощение: уберите →\to и ≡\equiv, внесите отрицания в скобки, раскройте скобки или вынесите общую часть, сократите, проверьте программой.

Равносильные выражения и тождество

Два выражения равносильны, если их значения совпадают при любых значениях переменных. Так, A→BA \to B и ¬A∨B\neg A \lor B равносильны, а A∨BA \lor B и A∧BA \land B нет: при A=1A = 1, B=0B = 0 первое равно 1, второе 0. Равенство двух равносильных выражений называют логическим тождеством. Законы алгебры логики — тождества, по которым одну часть выражения заменяют другой. Такая замена — равносильное преобразование: значение на любом наборе не меняется.

Равносильность проверяют таблицей: постройте таблицу истинности обоих выражений и сравните столбцы. Одного набора с разными значениями хватит, чтобы выражения не были равносильны. В программе перебор делает product, а функция all проверяет, что значения совпали на каждом наборе.

Пример

Равносильны ли выражения x→(y→z)x \to (y \to z) и (x∧y)→z(x \land y) \to z?

  1. 1.Левое выражение равно 0, только когда x=1x = 1 и y→z=0y \to z = 0, то есть при x=1x = 1, y=1y = 1, z=0z = 0.
  2. 2.Правое равно 0, только когда x∧y=1x \land y = 1 и z=0z = 0: это тот же набор.
  3. 3.На остальных семи наборах оба выражения равны 1. Программа перебирает 8 наборов и печатает True.

Ответ: да, равносильны

Законы для И и ИЛИ

ЗаконДля ИДля ИЛИ
ПереместительныйA∧B=B∧AA \land B = B \land AA∨B=B∨AA \lor B = B \lor A
Сочетательный(A∧B)∧C=A∧(B∧C)(A \land B) \land C = A \land (B \land C)(A∨B)∨C=A∨(B∨C)(A \lor B) \lor C = A \lor (B \lor C)
РаспределительныйA∧(B∨C)=(A∧B)∨(A∧C)A \land (B \lor C) = (A \land B) \lor (A \land C)A∨(B∧C)=(A∨B)∧(A∨C)A \lor (B \land C) = (A \lor B) \land (A \lor C)
ПовторенияA∧A=AA \land A = AA∨A=AA \lor A = A
Противоречия и исключённого третьегоA∧¬A=0A \land \neg A = 0A∨¬A=1A \lor \neg A = 1
Операции с константамиA∧1=AA \land 1 = A, A∧0=0A \land 0 = 0A∨0=AA \lor 0 = A, A∨1=1A \lor 1 = 1
ПоглощенияA∧(A∨B)=AA \land (A \lor B) = AA∨(A∧B)=AA \lor (A \land B) = A
Де Моргана¬(A∧B)=¬A∨¬B\neg(A \land B) = \neg A \lor \neg B¬(A∨B)=¬A∧¬B\neg(A \lor B) = \neg A \land \neg B

Импликация через ИЛИ

A→B=¬A∨BA \to B = \neg A \lor B: обе части равны 0 только при A=1A = 1, B=0B = 0. Отрицание импликации: ¬(A→B)=A∧¬B\neg(A \to B) = A \land \neg B, это следует из закона де Моргана. Импликация равна своей контрапозиции: A→B=¬B→¬AA \to B = \neg B \to \neg A.

Замена импликации — первый шаг любого упрощения: после неё в выражении остаются только ¬\neg, ∧\land и ∨\lor, и к ним применимы законы из таблицы. В задании 15 так переписывают условие (x∈D)→(x∈A)(x \in D) \to (x \in A): получается ¬(x∈D)∨(x∈A)\neg(x \in D) \lor (x \in A), то есть точка не лежит на DD или лежит на AA.

Пример

Упростите выражение ¬(x→y)∨y\neg(x \to y) \lor y.

  1. 1.Отрицание импликации: ¬(x→y)=x∧¬y\neg(x \to y) = x \land \neg y. Получаем (x∧¬y)∨y(x \land \neg y) \lor y.
  2. 2.Распределительный закон для ИЛИ: (x∨y)∧(¬y∨y)(x \lor y) \land (\neg y \lor y).
  3. 3.¬y∨y=1\neg y \lor y = 1, а (x∨y)∧1=x∨y(x \lor y) \land 1 = x \lor y.

Ответ: x∨yx \lor y

Эквивалентность через И и ИЛИ

A≡B=(A∧B)∨(¬A∧¬B)A \equiv B = (A \land B) \lor (\neg A \land \neg B): обе части равны 1 или обе равны 0. Другая запись: A≡B=(A→B)∧(B→A)A \equiv B = (A \to B) \land (B \to A). Отрицание эквивалентности: ¬(A≡B)=(A∧¬B)∨(¬A∧B)\neg(A \equiv B) = (A \land \neg B) \lor (\neg A \land B), значения частей разные.

Пример

Упростите выражение (x≡y)∨(x∧¬y)(x \equiv y) \lor (x \land \neg y).

  1. 1.Заменяем эквивалентность: (x∧y)∨(¬x∧¬y)∨(x∧¬y)(x \land y) \lor (\neg x \land \neg y) \lor (x \land \neg y).
  2. 2.Выносим xx из первого и третьего слагаемых: x∧(y∨¬y)=xx \land (y \lor \neg y) = x. Остаётся x∨(¬x∧¬y)x \lor (\neg x \land \neg y).
  3. 3.Распределительный закон для ИЛИ: (x∨¬x)∧(x∨¬y)=x∨¬y(x \lor \neg x) \land (x \lor \neg y) = x \lor \neg y.

Ответ: x∨¬yx \lor \neg y, то есть y→xy \to x

Законы де Моргана

¬(A∧B)=¬A∨¬B\neg(A \land B) = \neg A \lor \neg B и ¬(A∨B)=¬A∧¬B\neg(A \lor B) = \neg A \land \neg B. Чтобы внести отрицание в скобку, отрицают каждую часть и меняют ∧\land на ∨\lor, а ∨\lor на ∧\land. Для многих частей правило то же: ¬(A∨B∨C)=¬A∧¬B∧¬C\neg(A \lor B \lor C) = \neg A \land \neg B \land \neg C. Два отрицания подряд снимаются: ¬¬A=A\neg \neg A = A.

Знак операции меняется обязательно: ¬(A∧B)\neg(A \land B) не равно ¬A∧¬B\neg A \land \neg B, они различаются при A=1A = 1, B=0B = 0. Отрицание сравнения меняет знак сравнения: ¬(x<5)\neg(x < 5) — это x≥5x \ge 5. Так упрощают условия задания 15 с неравенствами: Тождественная истинность: неравенства.

Пример

Запишите без отрицания перед скобками: ¬((x<5)∨¬(y≥3))\neg((x < 5) \lor \neg(y \ge 3)).

  1. 1.Закон де Моргана: ¬(x<5)∧¬¬(y≥3)\neg(x < 5) \land \neg \neg(y \ge 3).
  2. 2.Двойное отрицание снимается: ¬¬(y≥3)=(y≥3)\neg \neg(y \ge 3) = (y \ge 3).
  3. 3.¬(x<5)\neg(x < 5) — это x≥5x \ge 5.

Ответ: (x≥5)∧(y≥3)(x \ge 5) \land (y \ge 3)

Раскрытие скобок, поглощение и склеивание

Распределительный закон для И раскрывает скобки как в алгебре: A∧(B∨C)=(A∧B)∨(A∧C)A \land (B \lor C) = (A \land B) \lor (A \land C). Для ИЛИ есть второй закон, которого в обычной алгебре нет: A∨(B∧C)=(A∨B)∧(A∨C)A \lor (B \land C) = (A \lor B) \land (A \lor C). Справа налево те же законы выносят общую часть за скобки.

Из них следуют два сокращения. Поглощение: A∨(A∧B)=AA \lor (A \land B) = A и A∧(A∨B)=AA \land (A \lor B) = A. Склеивание: (A∧B)∨(A∧¬B)=A(A \land B) \lor (A \land \neg B) = A и (A∨B)∧(A∨¬B)=A(A \lor B) \land (A \lor \neg B) = A.

Пример

Упростите выражение (x∨y)∧(x∨¬y)∨x∧z(x \lor y) \land (x \lor \neg y) \lor x \land z.

  1. 1.По приоритету конъюнкции выполняются раньше: ((x∨y)∧(x∨¬y))∨(x∧z)((x \lor y) \land (x \lor \neg y)) \lor (x \land z).
  2. 2.Склеивание: (x∨y)∧(x∨¬y)=x(x \lor y) \land (x \lor \neg y) = x. Остаётся x∨(x∧z)x \lor (x \land z).
  3. 3.Поглощение: x∨(x∧z)=xx \lor (x \land z) = x.

Ответ: xx

Порядок упрощения

Упрощают по шагам. 1) Замените →\to и ≡\equiv на ¬\neg, ∧\land, ∨\lor. 2) Внесите отрицания в скобки по законам де Моргана. 3) Раскройте скобки или вынесите общую часть. 4) Уберите A∧¬AA \land \neg A, A∨¬AA \lor \neg A и константы, примените поглощение. 5) Проверьте ответ таблицей истинности или программой: значения исходного и нового выражений совпадают на всех наборах.

Пример

Упростите выражение (x→y)∧(¬y→x)(x \to y) \land (\neg y \to x).

  1. 1.Импликации через ИЛИ: x→y=¬x∨yx \to y = \neg x \lor y, ¬y→x=¬¬y∨x=y∨x\neg y \to x = \neg \neg y \lor x = y \lor x.
  2. 2.Выносим общее yy: (¬x∨y)∧(x∨y)=y∨(¬x∧x)(\neg x \lor y) \land (x \lor y) = y \lor (\neg x \land x).
  3. 3.¬x∧x=0\neg x \land x = 0, остаётся yy.
  4. 4.Программа печатает для каждого набора значение выражения и yy: третий и четвёртый столбцы совпадают.

Ответ: yy

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

00

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

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

Решать