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

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

.

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

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

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

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

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

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

Имеем 2³ = 8 строк.

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

A	B	C			1 V 4	6 Þ 5

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

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

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

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

x	y

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

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

x	y	z

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

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

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