Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Таблицы истинности сложных высказываний

Теоретические сведения

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

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

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

Задача 3.12. Построить таблицу истинности для формулы

з-

Дх,, х2, х3) = (Xj —» х2) х

Решение.

Определим значение наборов переменных. Их восемь — 000, 001,

010,011, 100, 101, 110, 111. Каждому из них можно поставить в соответствие десятичный эквивалент (0, 1,..., 7). Построим таблицу истинности рассматриваемой функции.

На первом шаге выписываем значение наборов переменных.

На втором шаге определяем порядок выполнения элементарных высказываний и заполняем ими заголовки столбцов.

На третьем шаге вычисляем значение х, —> х2.

На четвертом шаге вычисляем значение х3.

На пятом шаге вычисляем значение (xt —>х2) —> х3, зная значения

Х[ —> х2 и х3 на каждом возможном наборе (табл. 3.4). Таблица истинности построена.

Таблица 3.4

Решение задачи 3.12

ХХХ2*3

хх —>х2

*3

(Х| —»х2) —> х3

000

1

1

1

001

1

0

0

010

1

1

1

011

1

0

0

100

0

1

1

101

0

0

1

по

1

1

1

111

1

0

0

Задачи

Задача 3.13. Построить таблицу истинности для следующей формулы: (а ®Ь)& с.

Решение.

Главным для решения задачи является правильный порядок выполнения операций. Отрицание — самая старшая операция, поэтому в первую очередь мы находим отрицание. Затем выполняем жегал-кинское сложение и только потом результат этого сложения логически умножаем на с. Таблица истинности выглядит следующим образом (табл. 3.5).

Таблица 3.5

Решение задачи 3.13

аЬс

Ь

а@Ь

® Ь) & с

000

1

1

0

001

1

1

1

010

0

0

0

011

0

0

0

100

1

0

0

101

1

0

0

ПО

0

1

0

111

0

1

1

Задача 3.14. Построить таблицу истинности для следующей формулы: —> Ь)> с.

Решение.

В первую очередь определяем порядок применения операций: отрицание над а, импликация, отрицание над выражением в скобках, импликация. Таблица истинности выглядит следующим образом (табл. 3.6).

Таблица 3.6

Решение задачи 3.14

аЬс

а

а —> Ь

-> Ь)

—> Ь) —> с

000

1

0

1

0

001

1

0

1

1

010

1

1

0

1

011

1

1

0

1

100

0

1

0

1

101

0

1

0

1

ПО

0

1

0

1

111

0

1

0

1

Рассматривая высказывания, как простые, так и сложные, мы должны определить понятие равносильности.

Две формулы Ли В называются равносильными, если на одинаковых наборах они принимают одинаковые значения (Л = В). Таким

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

Задача 3.15. Сравнить следующие логические формулы и определить, являются ли они равносильными:/, = (Х] © х2) & х3 и/2 = —»

—^ х2) —^ *з ?

Решение.

Определим значение наборов переменных и построим таблицу истинности для функций/І и/2 (табл. 3.7).

Таблица 3.7

Таблица истинности функций для задачи 3.15

*1*2*3

х, © х2

(х, © х2) & х3

Ху х2

*3

(Х] —> х2) —> х3

000

0

0

і

1

1

001

0

0

і

0

0

010

1

0

і

1

1

011

1

1

і

0

0

100

1

0

0

1

1

101

1

1

0

0

1

по

0

0

1

1

1

111

0

0

1

0

0

Функции/[ и/2 не являются равносильными, так как их значения различны на противоположных наборах 000, 010,011, 110 и 100.

Следующее понятие, которое вводится для логических формул, — двойственность.

Две формулы Ли В называются двойственными, если на противоположных наборах они принимают противоположные значения

(/4(х) = В(х)). Формула, двойственная Л, обозначается как Л*.

Например, для формулы из задачи 3.14, двойственная ей формула имеет таблицу истинности, представленную в табл. 3.8.

Задача 3.16. Построить таблицу истинности для следующей формулы: (а ®Ь) & с.

Задача 3.17. Построить таблицу истинности для следующей формулы: —> Ь) —> с.

Задача 3.18. Построить таблицу истинности для следующей функции: а ? Ь + а -Ь.

Задача 3.19. Даны две функции Р1 и Р2. Определить, являются ли они равносильными друг другу:

Двойственная формула для задачи 3.15

аЬс

—> Ь) —> с

((а -> Ь) -> с)*

000

0

0

001

1

0

010

1

0

011

1

0

100

1

0

101

1

0

ПО

1

0

111

1

1

  • • ^(я, Ь, с) = 1{000,001,011, 101, 100, 111};
  • /^(й, Ь, с) = Ь —> с.
 
<<   СОДЕРЖАНИЕ   >>