Занятие 2 (часть 1) Логические формулы. Законы алгебры логики

Определение 1 Логической переменной называется переменная, значением которой может быть любое высказывание. Пример: x, у, x 1, y 1, x k, у n

Определение 2 Логической формулой является: 1) любая логическая переменная, а также каждая из двух логических констант 0 (ложь) и 1 (истина); 2) если А и В формулы, то В и А*В тоже формулы, где знак «*» означает любую из логических бинарных операций. Пример: (х & у) z Формуле приписывается одно из двух значений 0 или 1.

Определение 3 Формулы А и B, зависящие от одного и того же набора переменных x 1, х 2, х 3, … x n, называют равносильными или эквивалентными, если на любом наборе значений переменных x 1, х 2, х 3, … x n они имеют одинаковые значения. Пример: А = В

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, 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

Закон исключенного третьего x v x = 1

Законы идемпотентности (равносильности) x & x = x x v x = x

Закон двойного отрицания x = x

Законы де Моргана x & у = x v y x v у = x & у

Законы поглощения x v (x & y) = x x & (x v y) = x

Любой из законов алгебры логики может быть доказан с помощью таблиц истинности.

Доказательство первого закона де Моргана x & у = x v y xyx & у xyx v y

Законы алгебры логики можно доказать путем логических рассуждений.

Доказательство первого закона поглощения x v (x & у )= x Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна по определению дизъюнкции. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула x, или формула (x & у), или обе эти формулы одновременно. Если x ложна, тогда (x & у) ложна, следовательно, x может быть только истинной.

Законы алгебры логики можно доказать путем тождественных преобразований.

Доказательство первого закона поглощения x v (x & у )= x x v (x & у ) = (x & 1 ) v (x & у ) = x & (1 v y) = x

Определение. Формула А называется тавтологией (или тождественно истинной), если она истинна при любых значениях своих переменных. Пример: х v х (закон исключенного третьего)

Определение. Формула А называется тождественно ложной, если она ложна при любых значениях своих переменных. Пример: х & х

Приоритет логических операций 1. Отрицание. 2. Конъюнкция. 3. Дизъюнкция (строгая и нестрогая). 4. Импликация и эквивалентность.

Задачи

Рассмотрите два сложных высказывания: F 1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3}; F 2 = {если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3}. Формализуйте эти высказывания, постройте таблицы истинности для каждой из полученных формул и убедитесь, что результирующие столбцы совпадают.

Решение x = {одно слагаемое делится на 3}; y = {сумма делится на 3}; z = {другое слагаемое делится на 3}. F 1 = x & y z F 2 = x & z y

xyzx & yF1F1 x & zyF2F

Формализуйте высказывания и постройте таблицы истинности: F 1 = {если все стороны четырехугольника равны и один из его углов прямой, то этот четырехугольник является квадратом}; F 2 = {если все стороны четырехугольника равны, а он не является квадратом, то один из его углов не является прямым}.

Решение x = {все стороны четырехугольника равны}; y = {один угол четырехугольника прямой}; z = {четырехугольник является квадратом}. F 1 = x & y z F 2 = x & z y

xyzx & yF1F1 x & zyF2F

Докажите следующие соотношения: 1) a b = a v b 2) a ~ b = a & b v a & b 3) a b = a & b v a & b 4) a b = b a 5) a ~ b = (a b) & (b a) 6) a b = a ~ b

a b = a v b

ab a b aa v b a b = a v b

a ~ b = a & b v a & b

aba ~ ba & b a & b v a & b a ~ b = a & b v a & b

a b = a & b v a & b

ab a b a & b a & b v a & b a b = a & b v a & b

a b = b a

ab a b ab b a a b = b a

a ~ b = (a b) & (b a)

aba ~ b a bb aa b & b a

a b = a ~ b

aba ba ~ b a b = a ~ b

Найдите x, если (x v a) v (x v a) = b

Решение (x v a) v (x v a) = = (x & a) v (x & a) = = (x & x) v (a & a) = = x & 1 = x x = b

Какие формулы являются тавтологиями? 1) a & a 2) a (b a) 3) (a & b) a

a & a aa

a (b a) ab b aa (b a)

(a & b) a abb & a (a & b) a

Является ли формула тождественно ложной? a & (a b) & (a b)

ab a b b a & (a b) & (a b)