1.Основные понятия булевой алгебры Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата, объектом исследования которого являются функции, принимающие, так же как и их аргументы, только два значения - “0” и “1”.
Таким аппаратом является математическая логика (алгебра логики, булева алгебра).
Логика - это наука о законах и формах мышления.
Математическая логика занимается изучением возможностей применения формальных методов для решения логических задач. Один из разделов математической логики является алгебра логики.
Основное понятие алгебры логики - высказывание. Высказывание - это некоторое предложение, о котором можно утверждать, что оно истинно или ложно.
Любое высказывание можно обозначить символом х и считать, что х=1, если высказывание истинно, а х=0 - если высказывание ложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию - утверждение - “Нет”.
Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.
Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х=1 при любых условиях.
Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение х=0 при любых условиях.
Функция f, зависящая от n переменных x1,x2,...,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.
2.Способы задания булевых функций Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.
При матричном способе булева функция f(x1,...,xn) задается таблицей истинности (табл. 1 и 2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.
Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.
Таблица 1 Таблица 3
х1 х2 х3 f(х1,х2,,х3)
Номер
набора
f(х1,х2,,х3) 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 2 0 0 1 1 0 3 0 1 0 0 1 4 1 1 0 1 1 5 1 1 1 0 0 6 0 1 1 1 1 7 1
Таблица 2 Таблица 4.
x1 x2 x3 x4 f(х1..х4) x1,x2,...,xj-1 xj,xj+1,...,xn 00..0 0...1 ... 11..1 0 0 0 0 1 0 0 0 1 0 00...0 ... 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 00...1 ... 0 1 1 0 1 f(х1...хn) 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 ... ... ... ... ... 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 11...1 1 1 1 0 1 1 1 1 1 0
Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. ............
