Основные законы алгебры логики и их использование в упрощении выражений

Содержание

Введение в равносильности алгебры высказываний
Основные законы алгебры логики
Преобразование логических выражений, упрощение формул
Доказательство равносильности формул
Тождественно истинные и ложные формулы
Решение задач по алгебре высказываний

Введение в равносильности алгебры высказываний

Знаете ли вы, что даже самые сложные логические выражения можно превратить в простые и понятные формулы? Алгебра высказываний — это не просто абстрактная математика, а мощный инструмент для анализа, оптимизации и доказательства истинности утверждений. Равносильности алгебры высказываний — ключевые законы, которые позволяют заменять одни логические конструкции на другие, сохраняя их смысл, но делая их проще и эффективнее.

Представьте, что вы программист, разрабатывающий алгоритм, или студент, решающий задачу по дискретной математике. Умение применять законы де Моргана, дистрибутивность, идемпотентность и другие правила алгебры логики сэкономит вам часы работы. Например, как доказать, что формула тождественно истинна? Как упростить выражение с импликацией или строгой дизъюнкцией? Ответы — в этой статье.

Здесь вы найдете:

— пошаговые примеры преобразований сложных логических конструкций;

— сводную таблицы законов алгебры логики для быстрого ориентирования в правилах алгебры высказываний;

— практические задачи с решениями, чтобы закрепить навыки.

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

Основные законы алгебры логики

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

Таблица 2.5.1 — Основные законы алгебры логики

1	закон двойного отрицания $\overline{\overline{A}} = A$
2	идемпотентность
	конъюнкция 2.1. $A \land A \equiv A$	дизъюнкция 2.2. $A \vee A \equiv A$
3	закон инверсии (отрицания)
	конъюнкция 3.1. $\overline{A} \land A = 0$	дизъюнкция 3.2. $\overline{A} \vee A = 1$
4	операции с константами
	конъюнкция 4.1. $A \land 0 \equiv 0$ 4.3. $A \land 1 \equiv A$	дизъюнкция 4.2. $A \vee 0 \equiv A$ 4.4. $A \vee 1 \equiv 1$
5	коммутативность
	конъюнкция 5.1. $A \land B \equiv B \land A$	дизъюнкция 5.2. $A \vee B \equiv B \vee A$
6	ассоциативность
	конъюнкция 6.1. $A \land (B \land C) \equiv (A \land B) \land C$	дизъюнкция 6.2. $A \vee (B \vee C) \equiv (A \vee B) \vee C$
7	дистрибутивность
	конъюнкция 7.1. $A \vee (B \land C) \equiv (A \vee B) \land (A \vee C)$	дизъюнкция 7.2. $A \land (B \vee C) \equiv (A \land B) \vee (A \land C)$
8	закон де Моргана
	конъюнкция 8.1. $\overline{A \land B} \equiv \overline{A} \vee \overline{B}$	дизъюнкция 8.2. $\overline{A \vee B} \equiv \overline{A} \land \overline{B}$
9	следствия закона де Моргана
	9.1. $A \land B \equiv \overline{\overline{A} \vee \overline{B}}$	9.2. $A \vee B \equiv \overline{\overline{A} \land \overline{B}}$
10	поглощение
	конъюнкция	дизъюнкция
	10.1. $A \land (A \vee B) \equiv A$	10.2. $A \vee (A \land B) \equiv A$
	10.3. $A \land \left( \overline{A} \vee B \right) \equiv A \land B$	10.4. $A \vee \left( \overline{A} \land B \right) \equiv A \vee B$
11	законы склеивания
	конъюнкция 11.1. $(A \vee B) \land \left( A \vee \overline{B} \right) \equiv A$ 11.3. $(A \vee B) \land \left( \overline{A} \vee B \right) \equiv B$	дизъюнкция 11.2. $(A \land B) \vee \left( A \land \overline{B} \right) \equiv A$ 11.4. $(A \land B) \vee \left( \overline{A} \land B \right) \equiv B$
12	снятие импликации
	$A \rightarrow B \equiv \overline{A} \vee B$
13	снятие эквиваленции
	13.1. $A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)$	13.2. $A \leftrightarrow B \equiv (A \land B) \vee \left( \overline{A} \land \overline{B} \right)$
14	снятие строгой дизъюнкции
	14.1. $A \oplus B \equiv \left( \overline{A} \land B \right) \vee \left( A \land \overline{B} \right)$ 14.2. $A \oplus B \equiv \left( \overline{A \rightarrow B} \right) \vee \left( \overline{B \rightarrow A} \right)$
15	снятие стрелки Пирса
	$A \downarrow B \equiv \overline{A \vee B}$
16	снятие штриха Шеффера
	$A \| B \equiv \overline{A \land B}$

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

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

Преобразование логических выражений, упрощение формул

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

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

2.5.1. С помощью эквивалентных преобразований упростить выражение $x \vee (x \rightarrow y)$ .

Решение.

Для упрощения данного выражения с помощью 12 закона перейдем от импликации к дизъюнкции:

$x \vee \left( \overline{x} \vee y \right).$

Теперь согласно закону об ассоциативности для дизъюнкции (6.2) изменим порядок скобок:

$(x \vee \overline{x}) \vee y.$

Применив закон 3.2 к выражению в скобках, получим

$1 \vee y.$

Воспользовавшись 5.2 и 4.4, будем иметь

$1 \vee y \equiv y \vee 1 \equiv 1.$

Таким образом, выражение $x \vee (x \rightarrow y)$ равносильно 1 и записывается это следующим образом

$x \vee (x \rightarrow y) \equiv 1.$

Для обозначения равносильности, как было отмечено ранее, будем использовать знак $\equiv$ . Обратите внимание, что в результате преобразований мы получили 1, это позволяет сделать вывод, что выражение $x \vee (x \rightarrow y)$ — тождественно истинно.

В дальнейшем при упрощении выражений будем все преобразования записывать в строчку, а используемые законы подписывать над знаком равносильности.

2.5.2. С помощью эквивалентных преобразований упростить выражение $(x \vee y) \rightarrow (x \oplus y)$ .

Решение.

$(x \lor y) \rightarrow (x \oplus y) \mathop{\equiv}\limits^{14.1} (x \lor y) \rightarrow \big( (\overline{x} \land y) \lor (x \land \overline{y}) \big) \mathop{\equiv}\limits^{12}$

$\mathop{\equiv}\limits^{12} \mathop{\underbrace{\overline{(x \lor y)}}}\limits_{8.2} \lor \big( (\overline{x} \land y) \lor (x \land \overline{y}) \big) \mathop{\equiv}\limits^{8.2} \mathop{\underbrace{\big( (\overline{x} \land \overline{y}) \lor (\overline{x} \land y) \big)}}\limits_{7.2} \lor (x \land \overline{y}) \mathop{\equiv}\limits^{7.2}$

$\mathop{\equiv}\limits^{7.2} \overline{x} \land \mathop{\underbrace{(\overline{y} \lor y)}}\limits_{3.2} \lor (x \land \overline{y}) \mathop{\equiv}\limits^{3.2} \mathop{\underbrace{(\overline{x} \land 1)}}\limits_{4.3} \lor (x \land \overline{y}) \mathop{\equiv}\limits^{4.3}$

$\mathop{\equiv}\limits^{4.3} \overline{x} \lor (x \land \overline{y}) \mathop{\equiv}\limits^{7.1} \mathop{\underbrace{(\overline{x} \lor x)}}\limits_{3.2} \land (\overline{x} \lor \overline{y}) \mathop{\equiv}\limits^{3.2} 1 \land (\overline{x} \lor \overline{y}) \mathop{\equiv}\limits^{4.3} \overline{x} \lor \overline{y}.$

2.5.3. С помощью эквивалентных преобразований упростить выражение

$x \land \left( y \oplus \overline{x} \right).$

2.5.4. С помощью эквивалентных преобразований упростить выражение

$\overline{(x \vee y)} \downarrow \left( \overline{y} \rightarrow x \right).$

2.5.5. С помощью эквивалентных преобразований упростить выражение

$\left( x | y \right) \land (y \leftrightarrow x).$

2.5.6. С помощью эквивалентных преобразований упростить выражение

$\overline{(x \rightarrow y)} \land (z \rightarrow x).$

2.5.7. С помощью эквивалентных преобразований упростить выражение

$\left( \overline{x \land z} \right) \leftrightarrow \left( y \vee \overline{x} \right).$

2.5.8. С помощью эквивалентных преобразований упростить выражение

$\left( x \vee \overline{y} \right) \downarrow \left( \overline{z} \land x \right).$

2.5.9. С помощью эквивалентных преобразований упростить выражение

$\left( \overline{x} \leftrightarrow y \right) \oplus \left( z \oplus \overline{y} \right).$

2.5.10. С помощью эквивалентных преобразований упростить выражение

$\overline{(x \leftrightarrow y)} \vee (z \vee k).$

2.5.11. С помощью эквивалентных преобразований упростить выражение

$\left( x \land \overline{y} \right) \rightarrow (z \oplus k).$

2.5.12. С помощью эквивалентных преобразований упростить выражение

$(x \downarrow y) \vee (z \land k).$

2.5.13. С помощью эквивалентных преобразований упростить выражение

$\left( x | y \right) \oplus (z \oplus k).$

Доказательство равносильности формул

2.5.14. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул: $(x \leftrightarrow y) \vee (x \rightarrow y)$ и $(x \downarrow y) \vee \overline{x} \vee y$ .

Решение.

С помощью эквивалентных преобразований приведем первое выражение ко второму.

$\mathop{\underbrace{(x \leftrightarrow y)}}\limits_{13.2} \lor (x \rightarrow y) \mathop{\equiv}\limits^{13.2} (x \land y) \lor (\overline{x} \land \overline{y}) \lor \mathop{\underbrace{(x \rightarrow y)}}\limits_{12} \mathop{\equiv}\limits^{12}$

$\mathop{\equiv}\limits^{12} (x \land y) \lor \mathop{\underbrace{(\overline{x} \land \overline{y})}}\limits_{8.2} \lor (\overline{x} \lor y) \mathop{\equiv}\limits^{8.2} (x \land y) \lor \mathop{\underbrace{\overline{(x \lor y)}}\limits_{15} \lor (\overline{x} \lor y) \mathop{\equiv}\limits^{15}$

$\mathop{\equiv}\limits^{15} \mathop{\underbrace{\bigg( \mathop{\underbrace{(x \land y)}} \lor \mathop{\underbrace{(x \downarrow y)}} \bigg)}}\limits_{5.2} \lor (\overline{x} \lor y) \mathop{\equiv}\limits^{5.2} (x \downarrow y) \lor \mathop{\underbrace{(x \land y) \lor \overline{x}}}\limits_{7.1} \lor y \mathop{\equiv}\limits^{7.1}$

$\mathop{\equiv}\limits^{7.1} (x \downarrow y) \lor \mathop{\underbrace{(\overline{x} \lor x)}}\limits_{3.2} \land (y \lor \overline{x}) \lor y \mathop{\equiv}\limits^{3.2} (x \downarrow y) \lor \mathop{\underbrace{1 \land (y \lor \overline{x})}}\limits_{4.3} \lor y \mathop{\equiv}\limits^{4.3}$

$\mathop{\equiv}\limits^{4.3} (x \downarrow y) \lor y \lor \overline{x} \lor y \mathop{\equiv}\limits^{5.2} (x \downarrow y) \lor \overline{x} \lor \mathop{\underbrace{(y \lor y)}}\limits_{2.2} \mathop{\equiv}\limits^{2.2} (x \downarrow y) \lor \overline{x} \lor y.$

Таким образом формулы равносильны:

$(x \leftrightarrow y) \vee (x \rightarrow y) \equiv (x \downarrow y) \vee \overline{x} \vee y.$

2.5.15. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$\left( x \vee \left( \overline{x} \land y \right) \right) \land \left( (x \land y) \vee \overline{y} \right)$ и $\left( x \land \overline{y} \right) \vee \left( y \land \left( x \vee \overline{x} \right) \right)$ .

2.5.16. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \rightarrow b) \oplus (b \rightarrow a)$ и $\left( a \land \overline{b} \right) \vee \left( \overline{a} \land b \right)$ .

2.5.17. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \oplus b) \rightarrow (a \downarrow b)$ и $\overline{\left( a \land \overline{b} \right) \vee \left( \overline{a} \land b \right)} \vee \overline{a \vee b}$ .

2.5.18. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \leftrightarrow b) | (c \downarrow a)$ и $\overline{(a \land b) \vee \left( \overline{a} \land \overline{b} \right)} \vee \overline{\overline{c} \vee a}$ .

2.5.19. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$a \rightarrow (b \rightarrow c)$ и $\overline{a} \vee \left( \overline{b} \vee c \right)$ .

2.5.20. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$\left( a | b \right) \downarrow \left( b | c \right)$ и $\overline{\overline{a \land b} \vee \overline{b \land c}}$ .

2.5.21. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$\left( a | b \right) \oplus (c \leftrightarrow a)$ и $\overline{a \land b} \oplus \left( (a \land c) \vee \left( \overline{a} \land \overline{c} \right) \right)$ .

2.5.22. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \vee b) \downarrow (c \leftrightarrow d)$ и $\overline{(a \vee b) \vee (c \leftrightarrow d)}$ .

2.5.23. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$\left( (a \rightarrow b) \oplus (c \land d) \right) \leftrightarrow (a \vee b)$ и $\left( \overline{a} \vee b \oplus (c \land d) \right) \leftrightarrow (a \vee b)$ .

2.5.24. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \land b) | (c \rightarrow d)$ и $\left( \overline{a \land b} \land (\overline{c} \vee d) \right)$ .

2.5.25. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \downarrow b) \leftrightarrow (c \downarrow d)$ и $\overline{\overline{a \vee b} \vee \overline{c \vee d}}$ .

Тождественно истинные и ложные формулы

2.5.26. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \vee \overline{a} \right) \land \left( b \vee \overline{b} \right)\overset{3.2}{\equiv}1 \land 1\overset{4.3}{\equiv}1.$

2.5.27. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \rightarrow a) \vee \left( b \land \overline{b} \right)$ .

2.5.28. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \leftrightarrow a) \oplus (b \oplus b)$ .

2.5.29. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \downarrow b) \land \left( a | b \right)$ .

2.5.30. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \vee \overline{a} \right) \land \left( b \vee \overline{b} \right) \land \left( c \vee \overline{c} \right)\overset{3.2}{\equiv}1 \land 1 \land 1\overset{4.3}{\equiv}1.$

2.5.31. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \rightarrow a) \land (b \leftrightarrow b) \land (c \rightarrow c)$ .

2.5.32. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \downarrow a) \vee \left( b | b \right) \vee (c \downarrow c)$ .

2.5.33. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \oplus \overline{a} \right) \land \left( \overline{\overline{b}} \vee \overline{b} \right) \land \left( c \oplus \overline{c} \right)$ .

2.5.34. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\mathop{\underbrace{(a \downarrow a)}}\limits_{15} \lor a \lor \mathop{\underbrace{(b \mid b)}}\limits_{16} \lor b \lor \mathop{\underbrace{(c \downarrow c)}}\limits_{15} \lor c \lor \mathop{\underbrace{(d \mid d)}}\limits_{16} \lor d \equiv$

$\equiv \mathop{\underbrace{\overline{(a \lor a)}}}\limits_{8.2} \lor a \lor \mathop{\underbrace{\overline{(b \land b)}}}\limits_{8.1} \lor b \lor \mathop{\underbrace{\overline{(c \lor c)}}}\limits_{8.2} \lor c \lor \mathop{\underbrace{\overline{(d \land d)}}}\limits_{8.1} \lor d \equiv$

$\equiv \mathop{\underbrace{(\overline{a} \land \overline{a})}}\limits_{2.1} \lor a \lor \mathop{\underbrace{(\overline{b} \lor \overline{b})}}\limits_{2.2} \lor b \lor \mathop{\underbrace{(\overline{c} \land \overline{c})}}\limits_{2.1} \lor c \lor \mathop{\underbrace{(\overline{d} \lor \overline{d})}}\limits_{2.2} \lor d \equiv$

$\equiv \mathop{\underbrace{(\overline{a} \lor a)}}\limits_{3.2} \lor \mathop{\underbrace{(\overline{b} \lor b)}}\limits_{3.2} \lor \mathop{\underbrace{(\overline{c} \lor c)}}\limits_{3.2} \lor \mathop{\underbrace{(\overline{d} \lor d)}}\limits_{3.2} \equiv$

$\equiv 1 \lor 1 \lor 1 \lor 1 \mathop{\equiv}\limits^{4.4} 1.$

2.5.35. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \vee \overline{a} \right) \land \left( b \vee \overline{b} \right) \land \left( c \vee \overline{c} \right) \land \left( d \vee \overline{d} \right)$ .

2.5.36. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \leftrightarrow a) \land (b \rightarrow b) \land (c \leftrightarrow c) \land (d \rightarrow d)$ .

2.5.37. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \oplus \overline{a} \right) \land \left( \overline{\overline{b}} \vee \overline{b} \right) \land \left( c \oplus \overline{c} \right) \land \left( d \oplus \overline{d} \right)$ .

2.5.38. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\mathop{\underbrace{(a \land \overline{a})}\limits_{3.1} \lor \mathop{\underbrace{(b \land \overline{b})}\limits_{3.1} \equiv 0 \lor 0 \mathop{\equiv}\limits^{4.2} 0.$

2.5.39. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\left( \left( a \rightarrow \overline{a} \right) \oplus \left( b \rightarrow \overline{b} \right) \right) \land \left( a | b \right)$ .

2.5.40. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\left( a | a \right) \land (b \downarrow b)$ .

2.5.41. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\overline{a \leftrightarrow b} \land \overline{b \leftrightarrow a}$ .

2.5.42. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\left( a \land \overline{a} \right) \vee \left( b \land \overline{b} \right) \vee \left( c \land \overline{c} \right)$ .

2.5.43. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$(a \oplus b) \vee (b \oplus c)$ .

2.5.44. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\overline{(a \leftrightarrow b \leftrightarrow c)}$ .

2.5.45. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$(a \rightarrow b) \vee (a \leftrightarrow c) \vee (b \vee c)$ .

2.5.46. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$(a \leftrightarrow b) \rightarrow (c \land d)$ .

2.5.47. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\overline{(a \rightarrow b)} \vee (c \vee d)$ .

2.5.48. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$(a \oplus b) \land (c \oplus d)$ .

2.5.49. С помощью эквивалентных преобразований докажите, что формула тождественно ложна

$\overline{\left( a \land \overline{a} \right) \land \left( b \land \overline{b} \right)} \vee (c \vee d)$ .

Решение задач по алгебре высказываний

2.7.16. С помощью эквивалентных преобразований упростить выражение

$\left( x \middle| y \right) \oplus (x \oplus y).$

2.7.17. С помощью эквивалентных преобразований упростить выражение

$\left( x \land \overline{y} \right) \rightarrow \left( \overline{x} \oplus \overline{y} \right).$

2.7.18. С помощью эквивалентных преобразований упростить выражение

$\left( x \land \overline{y} \right) \rightarrow \left( y\mid x \right).$

2.7.19. С помощью эквивалентных преобразований упростить выражение

$\left( x\mid y \right) \mid \left( x\mid z \right).$

2.7.20. С помощью эквивалентных преобразований упростить выражение

$\overline{(x \oplus y) \land \overline{\left( z\mid x \right)}} \vee \left( \overline{y} \leftrightarrow (z \downarrow x) \right).$

2.7.21. С помощью эквивалентных преобразований упростить выражение

$\left( x \rightarrow \overline{y \vee z} \right) \land \left( \overline{x \oplus z} \rightarrow \left( y\mid x \right) \right).$

2.7.22. С помощью эквивалентных преобразований упростить выражение

$(x \leftrightarrow y) \oplus (z \oplus k).$

2.7.23. С помощью эквивалентных преобразований упростить выражение

$\overline{(x \leftrightarrow y)} \rightarrow (z \land k).$

2.7.24. С помощью эквивалентных преобразований упростить выражение

$(x \downarrow y) \rightarrow (z \leftrightarrow k).$

2.7.25. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \vee b) \rightarrow \left( \overline{b} \land a \right)$ и $b \vee \overline{a}.$

2.7.26. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$a \oplus \overline{b}$ и $(a \land b) \vee \left( \overline{a} \land \overline{b} \right).$

2.7.27. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a\ |\ b)\ |\ (a\ |\ b)$ и $a \land b.$

2.7.28. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$a\ |\ (b\ \downarrow c)$ и $\overline{a \land \left( \overline{b \vee c} \right)}.$

2.7.29. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \leftrightarrow b) \downarrow (b \oplus c)$ и $\overline{(a \leftrightarrow b) \vee \left( \overline{b} \oplus \overline{c} \right)}.$

2.7.30. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$\left( a \middle| b \right) \downarrow \left( \overline{c} \middle| \overline{a} \right)$ и $\overline{\overline{a \land b} \vee (c \land a)}.$

2.7.31. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \leftrightarrow b) \oplus (c \downarrow d)$ и $(a \land b) \vee \left( \overline{a} \land \overline{b} \right) \oplus \overline{c \vee d}.$

2.7.32. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a\ \land b)\ |\ (\overline{c}\ \leftrightarrow d)$ и $\overline{(a \land b)}\ \land ((c\ \land \overline{d})\ \vee (d\ \land \overline{c})).$

2.7.33. Проводя эквивалентные преобразования, доказать или опровергнуть равносильность следующих формул:

$(a \land b) \downarrow (c \vee d)$ и $\overline{\overline{a \land b} \vee \overline{c \vee d}}.$

2.7.34. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \leftrightarrow a) \land (b \leftrightarrow b).$

2.7.35. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a \downarrow a) \downarrow (b \downarrow b).$

2.7.36. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$(a\ |\ a)\ |\ (b\ |\ b).$

2.7.37. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( \left( a \land \overline{a} \right) \vee \left( b \land \overline{b} \right) \right) \vee \left( c \vee \overline{c} \right).$

2.7.38. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( (a \rightarrow a) \leftrightarrow (b \rightarrow b) \right) \land (c \leftrightarrow c).$

2.7.39. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \rightarrow \overline{a} \right) \vee \left( \overline{b} \rightarrow b \right) \vee \left( c \vee \overline{c} \right).$

2.7.40. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( \left( a \land \overline{a} \right) \vee \left( b \land \overline{b} \right) \right) \vee \left( c \vee \overline{c} \right) \vee \left( d \vee \overline{d} \right).$

2.7.41. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( (a \rightarrow a) \leftrightarrow (b \rightarrow b) \right) \land (c \leftrightarrow c) \land (d \leftrightarrow d).$

2.7.42. С помощью эквивалентных преобразований докажите, что формула тождественно истинна

$\left( a \rightarrow \overline{a} \right) \vee \left( \overline{b} \rightarrow b \right) \vee \left( c \vee \overline{c} \right) \vee \left( d \vee \overline{d} \right).$