Формулы алгебры логики обозначаются большими буквами латинского алфавита А, В, С,... При этом скобки можно опускать, придерживаясь следующих правил: конъюнкция выполняется прежде всего, дизъюнкция выполняется второй, импликация и эквиваленция равноправны и выполняются последними. Каждая формула алгебры логики принимает свое логическое значение, которое определяется логическими значениями входящих в нее элементарных высказываний. Например, составим таблицу истинности для формулы, воспользовавшись определением отрицания, импликации, дизъюнкции и конъюнкции. Порядок действий определяется следующим образом: отрицание, действия в скобках, конъюнкция, дизъюнкция, импликация, эквиваленция.
.
Получим таблицу:
Если формула состоит из п элементов, то ее таблица истинности состоит из
2n строк. Соответственно, если формула содержит две переменные, то логических возможностей будет 22=4, если три переменные – 23=8.
АЛГОРИТМ ЗАПОЛНЕНИЯ ТАБЛИЦЫ ИСТИННОСТИ
(На примере n = 3)
Пусть сложное высказывание состоит из n простых. Тогда число строк в таблице истинности 2n (так как каждое высказывание может принимать лишь два значения - 0 или 1). Число столбцов в таблице равно сумме числа переменных и числа различных логических операций, входящих в высказывание.
Имеем 23 = 8 строк.
| В столбце А чередуем 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. Составить таблицу истинности для формулы
