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

что все равномощные множества эквивалентны. Более того, если существует бинарная операция на них, сохраняющая свой вид при переходе от одного множества к другому, то эти множества изоморфны. Поскольку мы стремимся придать высказываниям вид исчислений и создать алгебру высказываний, то уместно развить аппарат на более понятном (например, числовом) множестве. За­ тем, построив биекцию на семантическое множество (истина, ложь}, получим алгебру логики. Таким образом, мы должны выбрать числовое множество, где числовые символы будут соответствовать истине и лжи. Очевидно, что наиболее подходящим множеством будет (0, 1}. Во-первых, эти символы занимают мало места, во-вторых, удобна техниче­ ская реализация: есть сигнал — ( 1 ), нет сигнала — ( 0 ). 4.2. Булевы функции Мы употребляем знаки не только для того, чтобы передавать наши мыс­ ли другим людям, но и для того, что­ бы облегчить сам процесс нашего мышления. Г. В. Лейбниц Логические функции. Алгебра логики, выстроенная в XIX в., долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX в. оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в на­ стоящее время служит основой для описания логики работы ап­ паратных и программных средств ЭВМ. Дело в том, что алгебра логики использует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично ЭВМ, используя лишь сиг­ налы 0 и 1 , воспринимает их как двоичные числа или логические переменные. Итак, рассмотрим множество (0, 1}, которое будем обозначать буквой В. Отображение / : В” -> В назовем булевой функцией п пе­ ременных. Областью определения булевой функции являются кортежи дли­ ной я, состоящие из символов 0 и 1. При этом каждому варианту кортежа должен быть поставлен в соответствие единственный эле­ мент из В — значение булевой функции, например / (0 , 1, 1, 0) = = 0. Поскольку в В всего два элемента, то снятие разделяющих запятых не нарушит однозначного восприятия кортежа, напри­ мер / (0 , 1, 1, 0) = /(ОНО) = 0. Аргумент булевой функции факти­ чески представляет собой целое двоичное число (см. подразд. 6 . 2 ). По этому принципу соответствующие аргументы можно упорядо­ 133