Приведем таблицы истинности,
(3) Аналитический способ задания
Замечание. Очевидно, что область определения булевой функции n аргументов w=f(x1,x2,…,xn) составляется из наборов координат точек вершин единичного n-мерного куба.
Рассмотрим графическое представление булевой функции трех аргументов w=f(x,y,z), заданной таблично (табл. 1.3). Заметим, что множество наборов области определения функции D={(x,y,z) , | x,y,z {0,1}} является множеством координат точек вершин единичного трехмерного куба (рис. 1.2). Очевидный способ графического представления булевой функции — это отметитьPкаким-то образом вершины куба, в которых функция принимает значение 1. Именно так на рис. 1.2 и сделано. В соответствии с таблицей значений (табл. 1.3) отмечены вершины, в которых булева функция равна 1.
(2) Графический способ задания
Определение. Таблицы значений булевых функций, подобные табл. 1.3, называются таблицами истинности булевых функций. Название таблиц происходит от интерпретации значений 1 — истина (TRUE), 0 — ложь (FALSE).
В таблицах, аналогичных табл. 1.3 обычно употребляется расположение наборов, соответствующих порядку естественного роста двоичных чисел 0,1,…2^n-1, в
В качестве примера рассмотрим табличное представление булевой функции трех аргументов w=f(x,y,z), где w,x,y,z P P{0,1}. Область определения функции — это множество двоичных наборов D={(x,y,z), | Px,y,z P{0,1}}. Их число есть |D|=2^3=8, а количество таких функций равно 2^|D|=2^2^3=256. Значения функции f(x,y,z) удобно представить в виде табл. 1.3, где перечислены всевозможные наборы из нулей и единиц длины 3 и для каждогонабора указано значение функции fi P{0,1} на этом наборе.
Пусть w=f(x1,x2,…,xn) — булева функция n аргументов. Область определения данной функции можно рассматривать и как множество упорядоченныхPнаборов (или векторов, или двоичных наборов) D={x1,x2,…,xn |Pxi {0,1}, i=1,2,…,n}, на каждом из которых функция принимает одно из двух значений: w {0,1}. Количество таких наборовP(x1,x2,…,xn), согласно правилу прямого произведения, равноP|D|=
(1) Табличный способ задания
3) аналитический.
Способы задания булевых функций не отличаются от способов задания обычных функций анализа. К таковым способам задания стандартно относятся:
Способы задания булевых функций
Определение. Функция f(x1,x2,…,xn) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x1,x2,…,xn обозначают через P2.
Определение. Переменная x называется булевой, если она способна принимать только два значения 0 и 1. В качестве примера интерпретации такого рода переменных может выступать обычный настенный выключатель света на два положения. Здесь 1Pсоответствует положению переключателя вверх и 0 — положению вниз.
Прежде формального введения в булеву алгебру удобно познакомиться с неформальным изложением данного вопроса. Это означает, что необходимо рассмотреть различного рода понятия, определения и, конечно же, объекты алгебры, возможные операции и их свойства.
Под алгеброй в современной математике понимают множество объектов произвольной природы с определенными на них операциями и свойствами этих операций, даваемых в форме аксиом. Запишем основные требования, предъявляемые к алгебре. Операции алгебры должны быть применимы ко всем объектам множества. В результате выполнения операций должны получаться объекты той же природы, что и исходные. В этом случае говорят, что множество объектов замкнуто относительно операций. Операций в алгебре должно быть конечное число и каждая операция должна быть конечноместной и т.д.
Алгоритмы на графах
Математическая логика
Булева алгебра, булевы функции
Комментариев нет:
Отправить комментарий