Элементарные булевы функции
Решение задачОпределение. Булевой (логической) переменной называется переменная, принимающая лишь два значения « 0 » и «1».
Определение. Булевой функцией от n логических переменных называется функция, прини мающая также лишь два значения « 0 » и «1».
Из определения логической функции следует, что функция n переменных – это отображение из множества En = E × E × ... × E (декартово произведение множества E = {0;1} самого на себя n раз) в E . Это отображение можно задать непосредственно таблицей, которая называется таблицей истинности данной функции.
Все функции n переменных можно перенумеровать. Число таких функций равно 22n . Однако, некоторые из них являются по существу функциями меньшего числа переменных, а две - вообще константами.
Определение. Если функция не зависит от некоторой переменной, то такую переменную будем называть фиктивной (несущественной).
Определения этих функций легко могут быть перенесены на любое число переменных.
Определение. Конъюнкцией n переменных f = x1 x2 ...xn называется функция, которая принимает значение 1, тогда и только тогда, когда все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).
Определение. Дизъюнкцией n переменных f = x1v x2v ... v xn называется такая функция, которая равна 0 тогда и только тогда, когда все переменные равны 0 (и, значит, равна 1, когда хотя бы одна из этих переменных равна 1).
Будем обозначать через f(x1,x2,...,xn) но вуюфункцию, которая на наборе переменных (x1 ,x2 ,..., xn) принимает значение ,противоположное f (x1, x2 ,..., xn).
Основные свойства этих функций:
1) Закон двойного отрицания 
2) Ассоциативность конъюнкции и дизъюнкции
x ∨ (y ∨ z) = (x ∨ y) ∨ z = x ∨ y ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z.
3) Коммутативность x ∧ y = y ∧ x, x ∨ y = y ∨ x.
4) Дистрибутивность x (y ∨ z) = xy ∨ xz; x ∨ (yz) = (x ∨ y) (x ∨ z).
5) Идемпотентность x ∧ x = x, x ∨ x = x.
6) Свойства констант 0 и 1 x ∧ 1 = x, x ∨ 1 = 1, x ∧ 0 = 0, x ∨ 0 = x, 0 = 1, 1 = 0.
7)Правила де Моргана x ∧ y = x ∨ y; x ∨ y = x ∧ y.
8) Закон противоречия x ∧ x = 0 .
9)Закон исключённого третьего x ∨ x = 1.
Наряду с основными соотношениями для упрощения формул часто используют следующие эквивалентные соотношения, выводимые из основных с помощью эквивалентных преобразований, а именно:
1) Поглощение («Целое поглощает часть») x ∨ xy = x; x (x ∨ y) = x .
2) Склеивание xy ∨ xy = x .
3) Обобщённое склеивание xz ∨ yz ∨ xy = xz ∨ yz .
Задача 1.1. С помощью формул логики высказываний докажите справедливость тождества
((a ↓ b) ∨ ( a ↔ b)) - ((c - d) ↓ (c ↔ d)) = (( a → d) ∧ ( d → b)) →((c → a) | (c→ b)).
Решение.
а) Преобразуем левую часть выражения
б) Преобразуем правую часть выражения
в) получили тождество
Задачи для самостоятельного решения
С помощью формул логики высказываний докажите справедливость тождеств:
