Если две формулы А и В одновременно, т.е. при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными, условное обозначение («=» или «º»). Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений (таб.1).
Таблица 8. Основные законы алгебры логики
Закон
| Для ИЛИ
| Для И
|
Переместительный
|
|
|
Сочетательный
|
|
|
Распределительный
|
|
|
Правила де Моргана
|
|
|
Идемпотенции
|
|
|
Поглощения
|
|
|
Склеивания
|
|
|
Операция переменной с ее инверсией
|
|
|
Операция с константами
|
|
|
Двойного отрицания
|
|
Составление таблицы истинности для логической формулы
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (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).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая, кроме значений переменных и значений формулы, также и значения промежуточных формул.
Задание на СРС