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

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

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

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

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

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

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

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

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

8 : 2 = 4
4 : 2 = 2
2 : 2 = 1

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

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


A	B	C	1 V 4	6 Þ 5

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

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

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

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

x	y

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

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