В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:
ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
| Закон | Для ИЛИ | Для И |
| Переместительный | 
| 
|
| Сочетательный | 
| 
|
| Распределительный | 
| 
|
| Правила де Моргана | 
| 
|
| Идемпотенции | 
| 
|
| Поглощения | 
| 
|
| Склеивания | 
| 
|
| Операция переменной с ее инверсией | 
| 
|
| Операция с константами | 
| 
|
| Двойного отрицания | 
|
Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0), (0, 1), (1, 0), (1, 1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Примеры.
1. Составим таблицу истинности для формулы 
, которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:
| Переменные | Промежуточные логические формулы | Формула | |||||
| 
| 
| 
| 
| 
| 
|
|
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.
2. Таблица истинности для формулы 
:
| Переменные | Промежуточные логические формулы | Формула | ||||
|
|
|
| 
| 
| 
|
|
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.
3. Таблица истинности для формулы 
:
| Переменные | Промежуточные логические формулы | Формула | ||||||
|
|
| 
|
| 
| 
|
| 
|
|
Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.
