Построение таблиц истинности для логических функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b). Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции. При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:инверсия;конъюнкция;дизъюнкция;

импликация и эквивалентность.

Определение

Логической формулой является:

1)любая логическая переменная, а также каждая из двух логических констант — 0 (ложь) и 1 (истина);

2)если А и В — формулы, то В и А*В — тоже формулы, где знак «*» означает любую из логических бинарных операций.

Пример:

(х & у) z

Формуле приписывается одно из двух значений

— 0 или 1.

Определение

Формулы А и B, зависящие от одного и того же набора переменных x1, х2, х3, … xn, называют равносильными или

эквивалентными, если на любом наборе значений переменных x1, х2, х3, … xn они имеют одинаковые значения.

Пример:

А = В

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, v и отрицание.

Законы алгебры логики

Законы коммутативности

x & у = y & x x v у = y v x

Законы ассоциативности

(x & у) & z = x & (у & z) (x v у) v z = x v (у v z)

Законы поглощения (нуля и единицы)

x v 0 = x x & 1 = x

Законы дистрибутивности

x & (у v z) = (x & у) v (x & z) x v (у & z) = (x v у) & (x v z)

Закон противоречия

x & x = 0