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

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

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

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

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

Р(х12, х3) = (х, —» х2) —» Ху

Решение.

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

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

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

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

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

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

На пятом шаге вычисляем значение (л^ —2) —> х3, зная значения —> х2 и 3 на каждом возможном наборе (табл. 3.4). Таблица истинности построена.

Таблица 3.4

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

*1

*2

*3

х ~^х2

*3

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

0

0

0

1

1

1

0

0

1

1

0

0

0

1

0

1

1

1

0

1

1

1

0

0

1

0

0

0

1

1

1

0

1

0

0

1

1

1

0

1

1

1

1

1

1

1

0

0

Рассмотрим несколько примеров.

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

Решение.

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

Таблица 3.5

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

а b с

ъ

а ®Ь

® Ь) & с

0 0 0

1

1

0

0 0 1

1

1

1

0 1 0

0

0

0

0 1 1

0

0

0

1 0 0

1

0

0

1 0 1

1

0

0

1 1 0

0

1

0

1 1 1

0

1

1

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

Решение.

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

Таблица 3.6

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

а Ь с

а

а —> Ь

Ь)

—> Ь) —> с

0 0 0

1

0

1

0

0 0 1

1

0

1

1

0 1 0

1

1

0

1

0 1 1

1

1

0

1

1 0 0

0

1

0

1

1 0 1

0

1

0

1

1 1 0

0

1

0

1

1 1 1

0

1

0

1

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

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

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

Решение.

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

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

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

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

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

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

Х

*2

*3

Ху © х2

(Х| ®х2) &х3

X, —»х2

*3

(ЛГ! —> х2) —»х3

0

0

0

0

0

1

1

1

0

0

1

0

0

1

0

0

0

1

0

1

0

1

1

1

0

1

1

1

1

1

0

0

1

0

0

1

0

0

1

1

1

0

1

1

1

0

0

1

1

1

0

0

0

1

1

1

1

1

1

0

0

1

0

0

Таблица 3.8

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

а Ь с

—> Ь) —» с

((а —» Ь) —> с)*

0 0 0

0

0

0 0 1

1

0

0 1 0

1

0

0 1 1

1

0

1 0 0

1

0

1 0 1

1

0

1 1 0

1

0

1 1 1

1

1

Задача 3.8. По подозрению в совершении преступления задержали Иванова, Петрова и Кузнецова. Один из них — уважаемый депутат, другой — малоизвестный чиновник, третий — известный мошенник. В процессе следствия депутат говорил правду, мошенник лгал, третий задержанный в одном случае говорил правду, во втором — лгал. Их показания:

  • Иванов: «Ясовершил это. Петров не виновен»',
  • Петров: «Иванов не виноват. Преступление совершил Кузнецов»;
  • Кузнецов: «Я не виноват, виновен Иванов».

Определить, как звали депутата, мошенника и чиновника и кто совершил преступление, если известно, что преступник один.

Решение.

Обозначим следующие высказывания и заменим их буквами: «Виновен Иванов» — Л, «Виновен Петров» — В, «Виновен Кузнецов» — С.

Формализуем первое сложное высказывание: Л & В.

Формализуем второе сложное высказывание: А & С.

Формализуем третье сложное высказывание: А & С.

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

Л = А&ВчА&Сч А&С = 1.

Таблица истинности этой формулы представлена ниже (табл. 3.9).

Таблица 3.9

Таблица истинности для задачи 3.8

АВС

А&В

А&С

А&С

Я = А& В/А&СуА&С

0 0 0

0

0

0

0

0 0 1

0

1

0

1

0 1 0

0

0

0

0

0 1 1

0

1

0

1

1 0 0

1

0

1

1

1 0 1

1

0

0

1

1 1 0

0

0

1

1

1 1 1

0

0

0

0

Формула Я истинна в пяти из восьми наборах. Набор 100 нужно исключить, так как два сложных высказывания равны единице.

На наборах 011, 101 и ПО по два простых высказывания А, В или С равны единице, что тоже противоречит условиям задачи.

Остается набор 001, на котором условия задачи выполняются. При этом высказывания А и Сложны, а С — истинно.

Таким образом, преступление совершил Кузнецов. Его сложное

высказывание и оба простых равны нулю, А = 0, С = 0, А & С = 0. Следовательно, Кузнецов — известный мошенник.

Для Петрова оба простых высказывания истины, т.е. А = 1, С = 1, А & С = 1, т.е. он является депутатом.

Для Иванова одно высказывание ложно, другое истинно, т.е. А = 0, В = , А & В = 0. Следовательно, он — малоизвестный чиновник.

 
< Пред   СОДЕРЖАНИЕ     След >