4. Составить таблицы истинности для следующих формул:
1) \(x \text{ & } y\)
2) \(x \text{ & } y \to (x \lor y \to z)\)
Решение:
1) Таблица истинности для \(x \text{ & } y\):
| \(x\) | \(y\) | \(x \text{ & } y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2) Таблица истинности для \(x \text{ & } y \to (x \lor y \to z)\):
| \(x\) | \(y\) | \(z\) | \(x \text{ & } y\) | \(x \lor y\) | \(x \lor y \to z\) | \(x \text{ & } y \to (x \lor y \to z)\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
5. Составить таблицы истинности для следующих формул:
1) \(x \text{ & } y \lor z\)
2) \(x \to y \to x \lor y \text{ & } z\)
Решение:
1) Таблица истинности для \(x \text{ & } y \lor z\):
| \(x\) | \(y\) | \(z\) | \(x \text{ & } y\) | \(x \text{ & } y \lor z\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
2) Таблица истинности для \(x \to y \to x \lor y \text{ & } z\):
| \(x\) | \(y\) | \(z\) | \(y \text{ & } z\) | \(x \lor (y \text{ & } z)\) | \(y \to (x \lor (y \text{ & } z))\) | \(x \to (y \to (x \lor (y \text{ & } z)))\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6. Упростить выражение с помощью формул равносильности: \(x \lor x' \text{ & } y\)
Решение:
Используем закон поглощения (или дистрибутивности):
\[x \lor (x' \text{ & } y) \equiv (x \lor x') \text{ & } (x \lor y)\]Так как \(x \lor x' \equiv 1\) (закон исключенного третьего), получаем:
\[1 \text{ & } (x \lor y) \equiv x \lor y\]Ответ: \(x \lor y\)
7. Упростить выражение с помощью формул равносильности: \(x \to (x \to y)\)
Решение:
Используем определение импликации: \(A \to B \equiv A' \lor B\)
\[x \to (x \to y) \equiv x \to (x' \lor y)\]Применим определение импликации еще раз:
\[x' \lor (x' \lor y)\]По закону ассоциативности и идемпотентности:
\[(x' \lor x') \lor y \equiv x' \lor y\]Ответ: \(x' \lor y\) (или \(x \to y\))
8. Упростить выражение с помощью формул равносильности: \((x \lor y') \text{ & } (x \lor y)\)
Решение:
Используем закон дистрибутивности:
\[(x \lor y') \text{ & } (x \lor y) \equiv x \lor (y' \text{ & } y)\]Так как \(y' \text{ & } y \equiv 0\) (закон противоречия), получаем:
\[x \lor 0 \equiv x\]Ответ: \(x\)
9. Упростить выражение с помощью формул равносильности: \((x \leftrightarrow y) \text{ & } (x \lor y)\)
Решение:
Используем определение эквивалентности: \(A \leftrightarrow B \equiv (A \to B) \text{ & } (B \to A) \equiv (A' \lor B) \text{ & } (B' \lor A)\)
\[(x \leftrightarrow y) \text{ & } (x \lor y) \equiv ((x' \lor y) \text{ & } (y' \lor x)) \text{ & } (x \lor y)\]Раскроем скобки, используя дистрибутивность и поглощение:
Рассмотрим часть \((x' \lor y) \text{ & } (x \lor y)\):
\[(x' \lor y) \text{ & } (x \lor y) \equiv y \lor (x' \text{ & } x) \equiv y \lor 0 \equiv y\]Теперь подставим это обратно в исходное выражение:
\[y \text{ & } (y' \lor x)\]Применим дистрибутивность:
\[(y \text{ & } y') \lor (y \text{ & } x)\]Так как \(y \text{ & } y' \equiv 0\):
\[0 \lor (y \text{ & } x) \equiv y \text{ & } x\]Ответ: \(x \text{ & } y\)
10. Упростить выражение с помощью формул равносильности: \(((x \lor y') \to (x \lor y)) \text{ & } y\)
Решение:
Сначала упростим импликацию \((x \lor y') \to (x \lor y)\):
\[(x \lor y') \to (x \lor y) \equiv (x \lor y')' \lor (x \lor y)\]По закону де Моргана \((A \lor B)' \equiv A' \text{ & } B'\):
\[(x' \text{ & } y'') \lor (x \lor y) \equiv (x' \text{ & } y) \lor (x \lor y)\]Применим закон дистрибутивности:
\[(x' \lor x) \text{ & } y \equiv 1 \text{ & } y \equiv y\]Теперь подставим это обратно в исходное выражение:
\[y \text{ & } y \equiv y\]Ответ: \(y\)
11. Упростить выражение с помощью формул равносильности: \((x' \text{ & } y')' \lor (x \to y) \text{ & } x\)
Решение:
Упростим \((x' \text{ & } y')'\) по закону де Моргана:
\[(x' \text{ & } y')' \equiv x'' \lor y'' \equiv x \lor y\]Упростим \((x \to y) \text{ & } x\):
\[(x \to y) \text{ & } x \equiv (x' \lor y) \text{ & } x\]Применим закон дистрибутивности:
\[(x' \text{ & } x) \lor (y \text{ & } x) \equiv 0 \lor (y \text{ & } x) \equiv y \text{ & } x\]Теперь объединим упрощенные части:
\[(x \lor y) \lor (y \text{ & } x)\]По закону поглощения \(A \lor (A \text{ & } B) \equiv A\):
\[x \lor y\]Ответ: \(x \lor y\)
12. Упростить выражение с помощью формул равносильности: \((x \lor y') \to (z \lor y' \lor x)) \text{ & } x \to y\)
Решение:
Сначала упростим импликацию \((x \lor y') \to (z \lor y' \lor x)\):
\[(x \lor y') \to (z \lor y' \lor x) \equiv (x \lor y')' \lor (z \lor y' \lor x)\]По закону де Моргана:
\[(x' \text{ & } y) \lor (z \lor y' \lor x)\]Перегруппируем члены в правой части: \(z \lor y' \lor x \equiv x \lor y' \lor z\)
\[(x' \text{ & } y) \lor x \lor y' \lor z\]Применим закон поглощения \(A \lor (A' \text{ & } B) \equiv A \lor B\):
\[x \lor y \lor y' \lor z\]Так как \(y \lor y' \equiv 1\):
\[x \lor 1 \lor z \equiv 1\]Теперь подставим это обратно в исходное выражение:
\[1 \text{ & } (x \to y)\]По закону тождества \(1 \text{ & } A \equiv A\):
\[x \to y\]Ответ: \(x \to y\)
13. Доказать тождественную истинность следующих формул: \(x \text{ & } y \to x\)
Решение:
Докажем тождественную истинность, построив таблицу истинности:
| \(x\) | \(y\) | \(x \text{ & } y\) | \(x \text{ & } y \to x\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Все значения в последнем столбце равны 1, следовательно, формула тождественно истинна.
Альтернативный способ (с помощью формул равносильности):
\[x \text{ & } y \to x \equiv (x \text{ & } y)' \lor x\]По закону де Моргана:
\[(x' \lor y') \lor x\]По закону ассоциативности и коммутативности:
\[(x' \lor x) \lor y'\]По закону исключенного третьего \(x' \lor x \equiv 1\):
\[1 \lor y' \equiv 1\]Так как выражение равно 1, оно тождественно истинно.
14. Доказать тождественную истинность следующих формул: \(x \to (y \to x)\)
Решение:
Докажем тождественную истинность, построив таблицу истинности:
| \(x\) | \(y\) | \(y \to x\) | \(x \to (y \to x)\) |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Все значения в последнем столбце равны 1, следовательно, формула тождественно истинна.
Альтернативный способ (