Таблицы истинности. Решения.
№1 Постройте таблицы истинности для следующих выражений:
1) x∧y∧z; 2) x∧¬y∧z; 3) x∧y∧¬z; 4) ¬x∧¬y∧¬z;
5) x∨y∨z; 6) x∨¬y∨z; 7) x∨y∨¬z; 8) ¬x∨¬y∨¬z;
9) ¬( x∧y∧z ); 10) ¬(x∧¬y∧z); 11) ¬(x∨y∨z); 12) ¬( x∨¬y∨z).
Решение
А. В задачах 1) - 4) выражение - это конъюнкция переменных или их отрицаний. Такие выражения принимают значение 1 только при одном наборе переменных. В этом наборе переменная принимает значение 1, если в выражение она входит без отрицания и 0 в противном случае. Таблицы истинности приведены ниже.
1) x ∧ y ∧ z
x | y | z | x ∧ y ∧ z | x | y | z | x ∧ y ∧ z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
2) x∧¬y∧z
x | y | z | x ∧ ¬y ∧ z | x | y | z | x ∧ ¬y ∧ z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
3) x∧y∧¬z
x | y | z | x ∧ y ∧ ¬z | x | y | z | x ∧ y ∧ ¬z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
4) ¬x∧¬y∧¬z
x | y | z | ¬x∧ ¬y∧¬z | x | y | z | ¬x∧ ¬y∧¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Б. В задачах 5) - 8) выражение - это дизъюнкция переменных или их отрицаний. Такие выражения принимают значение 0 только при одном наборе переменных. В этом наборе переменная принимает значение 1, если в выражение она входит с отрицанием и 0 в противном случае. Таблицы истинности приведены ниже.
5) x∨y∨z
x | y | z | x ∨ y ∨ z | x | y | z | x ∨ y ∨ z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6) x∨¬y∨z
x | y | z | x ∨ ¬y∨z | x | y | z | x ∨ ¬y∨z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
7) x∨y∨¬z
x | y | z | x∨y∨¬z | x | y | z | x∨y∨¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
8) ¬x∨¬y∨¬z
x | y | z | ¬x∨¬y∨¬z | x | y | z | ¬x∨¬y∨¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
В. В задачах 9) - 12) выражение - это отрицание конъюнкции или дизъюнкции. При построении таблицы истинности можно воспользоваться правилами А и Б, заменив потом значения выражения на противоположные.
9) ¬( x∧y∧z )
x | y | z | ¬(x∧y∧z) | x | y | z | ¬(x∧y∧z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
10) ¬(x∧¬y∧z)
x | y | z | ¬(x∧¬y∧z) | x | y | z | ¬(x∧¬y∧z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
11) ¬(x∨y∨z)
x | y | z | ¬(x∨y∨z) | x | y | z | ¬(x∨y∨z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
12) ¬( x∨¬y∨z)
x | y | z | ¬(x∨¬y∨z) | x | y | z | ¬(x∨¬y∨z) | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
№2 Постройте таблицы истинности для следующих выражений:
1) ¬x∨y; 2) x∨¬y; 3) x→y; 4) y→x;
5) ¬x→y; 6) x→¬y; 7) ¬x→¬y; 8) ¬y→¬x.
Укажите, для каких выражений таблицы истинности совпадают.
Решение.
Построим соответствующие таблицы истинности.
1) ¬x∨y
x | y | ¬x ∨ y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
2) x∨¬y
x | y | x ∨ ¬y |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
3) x→y
x | y | x → y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
4) y→x
x | y | y → x |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
5) ¬x→y
x | y | ¬x → y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
6) x→¬y
x | y | x → ¬y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
7) ¬x→¬y
x | y | ¬x → ¬y |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
8) ¬y→¬x
x | y | ¬y → ¬x |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
Одинаковые таблицы истинности – это таблицы, в которых одинаковому набору значений переменных и выражения в одной соответствует одинаковые в другой.
Тогда сравнив все таблицы, имеем совпадающие: 1-3-8, 2-4-7.
№3 Постройте таблицы истинности для следующих выражений:
1) (x → y) → z; 2) x → (y → z); 3) ( ¬x → y) → z; 4) ¬x → (y → z);
5) (x → y) → ¬z; 6) x → (y → ¬z); 7) ( ¬x → y) → ¬z; 8) ¬x → (y → ¬z).
Для каждого выражения укажите, сколько есть наборов значений переменных, для которых выражение истинно.
Решение
Для решения этих задач нужно знать определение истинности импликации: через связь с дизъюнкцией
x → y = ¬x∨ y
или непосредственно через таблицу истинности:
x | y | x → y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
При построении таблицы истинности для конкретного выражения удобно сначала выписать все 8 возможных наборов значений аргументов, а затем по очереди вычислять значение выражения для каждого набора. При желании можно использовать вспомогательную таблицу, в которой будет дополнительный столбец для подвыражения (см. №№ 9 и 10 ниже). Например, для задачи 3.1 вспомогательная таблица будет выглядеть так:
x | y | z | x → y | (x → y) → z | x | y | z | x → y | (x → y) → z | |
0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | |
0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ниже приведены ответы для всех выражений.
1) (x → y) → z
x | y | z | (x → y) → z | x | y | z | (x → y) → z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 5.
2) x → (y → z)
x | y | z | x → (y → z) | x | y | z | x → (y → z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 7.
3) ( ¬x → y) → z
x | y | z | ( ¬x → y) → z | x | y | z | ( ¬x → y) → z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 5.
4) ¬x → (y → z)
x | y | z | ¬x →(y →z) | x | y | z | ¬x → (y →z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 7.
5) (x → y) → ¬z
x | y | z | (x →y) →¬z | x | y | z | (x →y) → ¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 5.
6) x → (y → ¬z)
x | y | z | x → (y→¬z) | x | y | z | x → (y →¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 7.
7) ( ¬x → y) → ¬z
x | y | z | (¬x→y)→¬z | x | y | z | (¬x→y)→¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 5.
8) ¬x → (y → ¬z)
x | y | z | ¬x→(y→¬z) | x | y | z | ¬x→(y→¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Посмотрев на таблицу истинности, получим, что истинных наборов: 7.
№4 Разбейте эти выражения на группы так, чтобы выражения, попавшие а одну группу имели одинаковые таблицы истинности, а выражения, попавшие в разные группы, - разные таблицы истинности.
1) x → (y → z); 2) ¬x → (y → z); 3) x → ( ¬y → z); 4) x → (y → ¬z);
5) x ∨ y ∨ z; 6) ¬x ∨ y ∨ z; 7) x ∨ ¬y ∨ z; 8) x ∨ y ∨ ¬z;
9) ¬x ∨ ¬y ∨ z; 10) x ∨ ¬y ∨ ¬z; 11) ¬x ∨ y ∨ ¬z; 12) ¬x ∨ ¬y ∨ ¬z.
Укажите, для каких выражений таблицы истинности совпадают.
Решение
Задачу можно решить двумя способами. Один способ - построить таблицы истинности для всех выражений и посмотреть, какие таблицы совпадают (см. ниже Решение Б). Этот способ простой по идее, но трудоемкий. Есть и другое решение, требующее меньше вычислений (см. Решение А).
Решение А. Выражения 5) - 12) - элементарные дизъюнкции, т.е. дизъюнкции простых переменных или их отрицаний. Два разных выражения такого вида не могут быть эквивалентными, т.е. иметь одинаковые таблицы истинности, см. решение задачи 1, пп. 5- 8. Выражения 1) - 4) тоже могут быть записаны в виде элементарных дизъюнкций, см. решения задач №№2 и 3. Поэтому для решения задачи достаточно записать каждое из выражений 1) - 4) в виде элементарной дизъюнкции и посмотреть, не совпадает ли эта дизъюнкция с одной из дизъюнкций 5) - 12).
Имеем:
x→ (y → z) = ¬x ∨ (y → z) = ¬x ∨ (¬y∨z) = ¬x ∨ ¬y ∨ z - это выражение 9).
¬x→ (y → z) = x ∨ (y → z) = x ∨ (¬y∨z) = x ∨ ¬y ∨ z - это выражение 7).
x→ (¬y → z) = ¬x ∨ (¬y → z) = ¬x ∨ (y∨z) = ¬x ∨ y ∨ z - это выражение 6).
x→ (y → ¬z) = ¬x ∨ (y → ¬z) = ¬x ∨ (¬y∨¬z) = ¬x ∨ ¬y ∨ ¬z - это выражение 12).
Ответ. Таблицы истинности совпадают для выражений 1 и 9, 2 и 7, 3 и 6, 4 и 12. Для выражений 5, 8, 10 и 11 нет других выражений с той же таблицей истинности.
Решение Б.
Построим соответствующие таблицы истинности.
1) x → (y → z)
x | y | z | x → (y → z) | x | y | z | x→(y→z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2) ¬x → (y → z)
x | y | z | ¬x →(y→ z) | x | y | z | ¬x→(y → z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3) x → (¬y → z)
x | y | z | x→( ¬y→ z) | x | y | z | x→( ¬y→ z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4) x → (y → ¬z)
x | y | z | x→(y →¬z) | x | y | z | x →(y →¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
5) x ∨ y ∨ z
x | y | z | x ∨ y ∨ z | x | y | z | x ∨ y ∨ z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6) ¬x ∨ y ∨ z
x | y | z | ¬x ∨ y ∨ z | x | y | z | ¬x ∨ y ∨ z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
7) x ∨ ¬y ∨ z
x | y | z | x ∨ ¬y ∨ z | x | y | z | x ∨ ¬y ∨ z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
8) x ∨ y ∨ ¬z
x | y | z | x ∨ y ∨ ¬z | x | y | z | x ∨ y ∨ ¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
9) ¬x ∨ ¬y ∨ z
x | y | z | ¬x ∨¬y ∨ z | x | y | z | ¬x ∨¬y ∨ z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
10) x ∨ ¬y ∨ ¬z
x | y | z | x ∨¬y ∨ ¬z | x | y | z | x ∨¬y ∨ ¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
11) ¬x ∨ y ∨ ¬z
x | y | z | ¬x ∨ y ∨¬z | x | y | z | ¬x ∨ y ∨¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
12) ¬x ∨ ¬y ∨ ¬z
x | y | z | ¬x∨¬y∨¬z | x | y | z | ¬x∨¬y ∨¬z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Одинаковые таблицы истинности – это таблицы, в которых одинаковому набору значений переменных и выражения в одной соответствует одинаковые в другой.
Тогда сравнив все таблицы, имеем совпадающие: 1-9, 2-7, 3-6, 4-12.
Ответ. Таблицы истинности совпадают для выражений 1 и 9, 2 и 7, 3 и 6, 4 и 12. Для выражений 5, 8, 10 и 11 нет других выражений с той же таблицей истинности
№5 Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):
1) x ∨ y ∨ z; 2) ¬x ∨ y ∨ z; 3) x ∨ ¬y ∨ z 4) x ∨ y ∨ ¬z;
5) ¬x ∨ ¬y ∨ z; 6) x ∨ ¬y ∨ ¬z; 7) ¬x ∨ y ∨ ¬z 8) ¬x ∨ ¬y ∨ ¬z.
Решение этой задачи основано на тождестве
x → y = ¬x ∨ y
Преобразуем каждое из выражений. Для проверки приводим таблицы истинности.
1) x ∨ y ∨ z = ¬x → (y ∨ z) = ¬x → ( ¬y → z)
x | y | z | ¬x→(¬y→z) | x | y | z | ¬x→(¬y→z) | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2) ¬x ∨ y ∨ z = x → (y ∨ z) = x → ( ¬y → z)
x | y | z | x →(¬y →z) | x | y | z | x →(¬y →z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3) x ∨ ¬y ∨ z = ¬x → (¬y ∨ z) = ¬x → (y → z)
x | y | z | ¬x→(y →z) | x | y | z | ¬x→(y →z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4) x ∨ y ∨ ¬z = ¬x → (y ∨ ¬z) = ¬x → ( ¬y → ¬z)
x | y | z | ¬x→(¬y→¬z) | x | y | z | ¬x→(¬y→¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
5) ¬x ∨ ¬y ∨ z = x → (¬y ∨ z) = x → (y → z)
x | y | z | x→(y→z) | x | y | z | x→(y→z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6) x ∨ ¬y ∨ ¬z = ¬x → (¬y ∨ ¬z) = ¬x → (y → ¬z)
x | y | z | ¬x→(y→¬z) | x | y | z | ¬x→(y→¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
7) ¬x ∨ y ∨ ¬z = x → (y ∨ ¬z) = x → ( ¬y → ¬z)
x | y | z | x→(¬y→¬z) | x | y | z | x→(¬y→¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
8) ¬x ∨ ¬y ∨ ¬z = x → (¬y ∨ ¬z) = x → (y → ¬z)
x | y | z | x →(y→¬z) | x | y | z | x →(y→¬z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
№6. Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):
1) ¬(x ∨ y) ∨ z; 2) ¬(x ∧ y) ∨ z; 3) x ∨ ¬(y ∨ z); 4) ¬(x ∨ y ∨ z);
5) ¬(x ∨ ¬y) ∨ z; 6) ¬(¬x ∧ ¬y) ∨ z; 7) ¬x ∨ ¬(¬y ∨ z); 8) ¬(x ∨ y ∨ ¬z).
Решение
этой задачи основано на тождестве
x → y = ¬x ∨ y
Преобразуем каждое из выражений. Для проверки приводим таблицы истинности.
1) ¬(x ∨ y) ∨ z = (x ∨ y) → z = (¬x → y) → z
x | y | z | (¬x→y)→z | x | y | z | (¬x→y)→z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2) ¬(x ∧ y) ∨ z
Здесь требуется применить закон Де Моргана:
¬(x ∧ y) = ¬x ∨ ¬y, тогда
¬(x ∧ y) ∨ z = ¬x ∨¬y ∨ z = (x →¬y) ∨ z = ¬(x →¬y) → z
x | y | z | ¬(x→¬y)→z | x | y | z | ¬(x→¬y)→z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3) x ∨ ¬(y ∨ z) = ¬(y ∨ z) ∨ x = (y ∨ z) → x = (¬y → z) → x
x | y | z | x ∨ ¬(y ∨ z) | x | y | z | x ∨ ¬(y ∨ z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
4) ¬(x ∨ y ∨ z) = ¬((¬x → y) ∨ z) = ¬(¬(¬x → y) → z)
x | y | z | ¬(¬(¬x→y)→z) | x | y | z | ¬(¬(¬x→y)→z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
5) ¬(x ∨ ¬y) ∨ z = (x ∨ ¬y) → z = (¬y ∨ x) → z = (y → x) → z
x | y | z | (y → x) → z | x | y | z | (y → x) → z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6) ¬(¬x ∧ ¬y) ∨ z
Здесь требуется применить закон Де Моргана:
¬(x ∧ y) = ¬x ∨ ¬y, тогда
¬(¬x ∧ ¬y) ∨ z = x ∨ y ∨ z = (¬x→y) ∨ z = ¬(¬x→y) → z
x | y | z | ¬(¬x→y)→z | x | y | z | ¬(¬x→y)→z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
7) ¬x ∨ ¬(¬y ∨ z) = ¬(¬y ∨ z) ∨ ¬x = (¬y ∨ z) → ¬x = (y → z) → ¬x
x | y | z | (y→z)→¬x | x | y | z | (y→z)→¬x | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
8) ¬(x ∨ y ∨ ¬z) = ¬((¬x→y) ∨ ¬z) = ¬(¬z ∨ (¬x→y)) = ¬(¬z → (¬x→y))
x | y | z | ¬(¬z→ (¬x→y)) | x | y | z | ¬(¬z→ (¬x→y)) | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
№7. Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):
1) ¬x ∧ ¬y ∧ z; 2) ¬x ∨ y ∧ ¬z; 3) x ∨ y ∨ z; 4) ¬x ∧ y ∨ z;
5) ¬ x ∧ ¬y ∧ ¬z; 6) x ∨ ¬y ∧ ¬z; 7) ¬x ∨ ¬y ∨ z; 8) ¬x ∧ ¬y ∨ z.
Решение
1) ¬x ∧ ¬y ∧ z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
¬x ∧ ¬y ∧ z = ¬(x ∨ y) ∧ z = ¬(¬(x ∨ y) ∨ ¬z) = ¬((x ∨ y) → ¬z) = ¬((¬x → y) → ¬z)
x | y | z | ¬((¬x→y)→¬z) | x | y | z | ¬((¬x→y)→¬z) | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
2) ¬x ∨ y ∧ ¬z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
¬x ∨ y ∧ ¬z = ¬x ∨ ¬(¬y ∨ z) = x → ¬(y → z)
x | y | z | x→¬(y→z) | x | y | z | x→¬(y→z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
3) x ∨ y ∨ z = (¬x → y) ∨ z = (¬x → y) → z
x | y | z | (¬x→y)→z | x | y | z | (¬x→y)→z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4) ¬x ∧ y ∨ z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
¬x ∧ y ∨ z = ¬(x ∨ ¬y) ∨ z = (x ∨ ¬y) → z = (¬y ∨ x) → z = (y → x) → z
x | y | z | (y → x) → z | x | y | z | (y → x) → z | |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
5) ¬x ∧ ¬y ∧ ¬z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
¬x ∧ ¬y ∧ ¬z = ¬(x ∨ y ) ∧ ¬z = ¬((x ∨ y) ∨ z) = ¬((¬x → y) ∨ z) = ¬(¬(¬x→y)→z)
x | y | z | ¬(¬(¬x→y)→z) | x | y | z | ¬(¬(¬x→y)→z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
6) x ∨ ¬y ∧ ¬z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
x ∨ ¬y ∧ ¬z = x ∨ ¬(y ∨ z) = ¬(y ∨ z) ∨ x = (y ∨ z) → x = (¬y → z) → x
x | y | z | (¬y→z)→x | x | y | z | (¬y→z)→x | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
7) ¬x ∨ ¬y ∨ z = ¬x ∨ z ∨ ¬y = (x → z) ∨ ¬y = ¬y ∨ (x → z) = y → (x → z)
x | y | z | y → (x → z) | x | y | z | y → (x → z) | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
8) ¬x ∧ ¬y ∨ z
Здесь требуется применить закон Де Моргана:
¬x ∧ ¬y = ¬(x ∨ y), тогда
¬x ∧ ¬y ∨ z = ¬(x ∨ y) ∨ z = (x ∨ y) → z = (¬x → y) → z
x | y | z | (¬x →y)→z | x | y | z | (¬x →y)→z | |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
№8. Сравните формулы из задач №6 и №7. Какие из них эквивалентны?
Решение
Чтобы преобразовать формулы из задачи №6 к виду из задачи №7 нужно раскрыть скобки. Для этого нужно использовать законы Де Моргана:
¬(x ∧ y) = ¬x ∨ ¬y,
¬(x ∨ y) = ¬x ∧ ¬y.
После этого находим для каждой формулы из задачи №6 эквивалентную ей формулу в задаче №7. Рассмотрим, например, формулу 1) из задачи №6. Имеем:
¬(x ∨ y) ∨ z = ¬x ∧ ¬y ∨ z
Последняя формула – это формула 8) задачи №7
Ответ. Для каждой формулы задачи №6 указана эквивалентная ей формула задачи №7.
1) = 8); 2) = 7); 3) = 6); 4) = 5); 5) = 4); 6) = 3); 7) = 2); 8) = 1)
№9. Постройте таблицу истинности для следующего выражения:
D∧A→(A∧D⇔¬(D∨A∧C))∧A∨¬(D∧C→A∧C)
Решение
Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F. Для этого выделим в выражении F его подвыражения.
1) Выражение F можно записать в виде S1 → S2, где
S1 = D∧A;
S2 = (A∧D⇔¬(D∨A∧C))∧A∨¬(D∧C→A∧C)
2) Выделяем подвыражения в выражении S2: S2 = S3∨S4, где
S3 = (A∧D⇔¬(D∨A∧C))∧A
S4 = ¬(D∧C→A∧C)
3) Продолжаем разбор. Разбираем выражение S3 (выражением S4 займемся позже):
S3 = S5∧A, где
S5 = (A∧D⇔¬(D∨A∧C));
4) Выражение S5 можно записать в виде:
S5 = S6⇔S7, где
S6 = D∧A (это выражение эквивалентно S1);
S7 = ¬(D∨A∧C);
5) Выражение S7 = ¬S8, где
S8 = D∨A∧C;
6) Это выражение представим следующим образом:
S8 = D∨S9, где
S9 = A∧C;
7) Вернемся теперь к разбору выражения S4:
S4 = ¬S10, где
S10 = (D∧C→A∧C);
8) Представим выражение S10 как:
S10 = S11→S12, где
S11 = D∧C;
S12 = A∧C (это выражение эквивалентно S9).
Разбор закончен!
Значения выражения F и всех промежуточных подвыражений показаны в таблице. В верхней строке указан порядок, в котором мы заполняем столбцы. Эта строка, а также формулы, выражающие одни выражения через другие, приведены только для удобства читателей. При самостоятельной работе их можно не писать.
Порядок выполнения | 12 | 11 | 10 | 5 | 9 | 8 | 7 | 6 | 4 | 3 | 2 | 1 | 13 | ||
A | C | D | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | S11 | S12 | F |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
В результате получаем таблицу истинности для выражения F:
A | C | D | D∧A→(A∧D⇔¬(D∨A∧C))∧A∨¬(D∧C→A∧C) |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
№10. Постройте таблицу истинности для следующего выражения:
F∨(A∧¬(D∧A)→¬(A∨D∧F))⇔A∧F∨A→¬(D∧F)
Решение
Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F.
1) Выражение F можно записать в виде S1 ⇔ S2, где
S1 = C ∨ (A∧¬(D∧A)→¬(A∨D∧C));
S2 = A∧C∨A → ¬(D∧C);
2) Продолжим с разбора выражения S1. Его можно представить в виде S1 = C ∨ S3, где
S3 = A∧¬(D∧A) → ¬(A∨D∧C);
3) Выделим подвыражения S4 и S5 из S3: S3 = S4 → S5, где
S4 = A ∧ ¬(D∧A);
S5 = ¬(A ∨ D∧C);
4) Выражение S4 можно представить следующим образом соответственно:
S4 = A ∧ S6, где
S6 = ¬S7, где
S7 = D ∧ A.
5) Аналогично рассмотрим выражение S5: S5 = ¬S8, где
S8 = A ∨ S9, где
S9 = D ∧ C.
6) Теперь рассмотрим выражение S2: S2 = S10 → S11, где
S10 = A∧C ∨ A;
S11 = ¬(D∧C).
7) Выражение S10 представим в виде: S10 = S12 ∨ A, где
S12 = A ∧ C.
8) Выражение S11: S11 = ¬S13, где
S13 = D ∧ C (это выражение эквивалентно S9).
Разбор закончен!
Значения выражения F и всех промежуточных подвыражений показаны в таблице. В верхней строке указан порядок, в котором мы заполняем столбцы. Эта строка, а также формулы, выражающие одни выражения через другие, приведены только для удобства читателей. При самостоятельной работе их можно не писать.
Порядок выполнения | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 14 | ||
A | C | D | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | S11 | S12 | S13 | F |
0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
В результате получаем таблицу истинности для выражения F:
A | C | D | C∨(A∧¬(D∧A)→¬(A∨D∧C))⇔A∧C∨A→¬(D∧C) |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
№11. Постройте таблицу истинности для следующего выражения:
¬(A∧B)∨(C∧B∧A→¬(A∧¬C⇔B∧C))∧¬A∧C∧B∨A
Решение
Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F.
1) Выражение F можно записать в виде S1 ∨ S2 ∨ A, где
S1 = ¬(A∧D);
S2 = (C∧D∧A→¬(A∧¬C⇔D∧C)) ∧ ¬A∧C∧D;
2) Представим сначала выражение S1 в виде: S1 = ¬S3, где
S3 = A ∧ D.
3) Теперь разобьем на подвыражения S2: S2 = S4 ∧ S5, где
S4 = C∧D∧A → ¬(A∧¬C⇔D∧C);
S5 = ¬A ∧ C ∧ D;
4) Выражение S4 представим в виде: S4 = S6 → S7;
S6 = C ∧ D ∧ A;
S7 = ¬(A∧¬C⇔D∧C);
5) Аналогично преобразуем выражение S7: S7 = ¬S8, где
S8 = A∧¬C ⇔ D∧C;
6) Это выражение представим в вид: S8 = S9 ⇔ S10, где
S9 = A ∧ ¬C;
S10 = D ∧ C;
Разбор закончен!
Значения выражения F и всех промежуточных подвыражений показаны в таблице. В верхней строке указан порядок, в котором мы заполняем столбцы. Эта строка, а также формулы, выражающие одни выражения через другие, приведены только для удобства читателей. При самостоятельной работе их можно не писать.
Порядок выполнения | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 11 | ||
A | C | D | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | F |
0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
В результате получаем таблицу истинности для выражения F:
A | C | D | ¬(A∧D) ∨ (C∧D∧A→¬(A∧¬C⇔D∧C))∧¬A∧C∧D ∨ A |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
2 комментария
spasibo, ochen pomoqli))
Пожалуйста!