Главная / Банк задач. Информатика. / Таблицы истинности. Решения.

Таблицы истинности. Решения.

 

 

№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 =  ¬xy

или непосредственно через таблицу истинности:

 

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 комментария

  1. fato:

    spasibo, ochen pomoqli))

 
 

Ответить fato

 




 
 

 
 
Яндекс.Метрика