Спирина, М.С. Дискретная математика

Т а б л и ц а 4.1 Виды булевых функций одной переменной X /1 = 0 - «тождествен- ный нуль» / 2(х) = X «тождестве н- ная функция» /з(х) = х — «отрицание, инверсия» / 4 = 1 - «тождествен- ная единица» 0 0 0 1 1 1 0 1 0 1 ментах х ь х2, ..., хт строки значений / (х , ) , / ( х 2), . . . , / ( х 2 л) для раз­ ных функций также можно упорядочить по этому же принципу, то подобным способом упорядочиваются и сами функции (табл. 4.1). Далее можно вообще не выписывать значения в виде таблицы, а задавать их одной строкой. Например, запись F= (11000110) рас­ шифровывается следующим образом. Поскольку значений этой функции восемь, то функция / 'з ав и си т от log 28 = 3 переменных (например, х, у, z ): F(x = 0, у = 0, z = 0) = /"(000) = 1, j F(001) = 1, /Х010) = 0, / ’(011) = 0, /-(100) = 0, / ’(101) = 1, /'(110) = 1, / ’(111) = 0. Если любому значению аргумента ставится в соответствие зна­ чение функции у , то подобное отображение называется тожде- нулем ственным — - ------ —. единицей Такое название справедливо для булевых функций произвольного числа переменных. Если любому значению аргумента ставится в соответствие он сам, то такая логическая функция называется тождественной. Если любому значению аргумента ставится в соответствие про­ тивоположный элемент, то такая функция называется отрицани­ ем или инверсией. Поскольку значение инверсии зависит только от выражения, к которому она применена, то подобная операция является отношением, притом унарным. Не составит труда прове­ рить, что отрицание отрицания есть тождественное отображение, т. е. Vx е В х = (х) = х. Действительно, если х = 0, то х = 1, а х = 0, аналогично при х = 1 х = 0, а х = 1. Более удобно (особенно для громоздких формул) подобные действия, где операции применя­ ются к промежуточным значениям формул, представлять в виде Т а б л и ц а 4.2 Таблица истинности булевых функций одной переменной X у = х х = у М.х) = х 0 1 0 0 1 0 1 1 136