Занятие 2. Составление таблиц истинности для выражений

Формулы алгебры логики обозначаются большими буквами латинского ал­фавита А, В, С,... При этом скобки можно опускать, придерживаясь следую­щих правил: конъюнкция выполняется прежде всего, дизъюнкция выполня­ется второй, импликация и эквиваленция равноправны и выполняются последними. Каждая формула алгебры логики принимает свое логическое значение, которое определяется логическими значениями входящих в нее элементарных высказываний. Например, составим таблицу истинности для формулы, воспользовавшись определением отрицания, импликации, дизъюнкции и конъюнкции. Порядок действий определяется следующим образом: отрицание, действия в скобках, конъюнкция, дизъюнкция, импликация, эквиваленция.

.

Получим таблицу:

Если формула состоит из п элементов, то ее таблица истинности состоит из

2n строк. Соответственно, если формула содержит две переменные, то логических возможностей будет 22=4, если три переменные – 23=8.

АЛГОРИТМ ЗАПОЛНЕНИЯ ТАБЛИЦЫ ИСТИННОСТИ

(На примере n = 3)

Пусть сложное высказывание состоит из n простых. Тогда число строк в таблице истинности 2n (так как каждое высказывание может принимать лишь два значения - 0 или 1). Число столбцов в таблице равно сумме числа переменных и числа различных логических операций, входящих в высказывание.

Имеем 23 = 8 строк.

  1. 8 : 2 = 4
  2. 4 : 2 = 2
  3. 2 : 2 = 1
В столбце А чередуем 4 нуля и 4 единицы. В столбце В чередуем 2 нуля и 2 единицы. В столбце С чередуем 1 ноль и 1 единицу.

Таким образом, все возможные варианты учтены и никакие два не совпадают. Фактически такое заполнение столбцов соответствует двоичной записи чисел от 0 до 7. Столбцы с 4-го по 7-й заполняются в соответствии с таблицами истинности соответствующих логических операций, причём при заполнении каждого столбца операции выполняются над значениями одного или двух столбцов, указанных в строке заголовка таблицы.

A B C 1 V 4 6 Þ 5

Если в формулу входят 4 переменные, то таблица истинности для этой формулы, включающая все возможные комбинации истинности или ложности ее переменных в таблице, будет состоять из 24 = 16 строк; при 5 переменных в таблице имеем 25 = 32 строки; при n переменных - 2n строк.

Для любого сложного высказывания можно построить его таблицу истинности. Это следует из того, что число входящих в него переменных конечно и каждое из них может принимать всего два значения. Заметим, что для всех натуральных чисел, например, такую таблицу построить нельзя.

Приписывание значений истинности или ложности высказываниям, входя­щим в формулу, называется интерпретацией этих высказываний. Под интер­претацией формулы понимается приписывание значений истинности выска­зываниям, входящим в эту формулу.

1. Составить таблицу истинности для формулы

x y

Учитывая порядок, действий мы разбили формулу на простые составляющие. Еще раз подчеркнем, что порядок действий определяется следующим образом: отрицание, действия в скобках, конъюнкция, дизъюнкция, импликация, эквиваленция.

2. Составить таблицу истинности для формулы

x y z

3. Составить таблицу истинности для формулы

4. Составить таблицу истинности для формулы

5. Составить таблицу истинности для формулы

Наши рекомендации