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

Так, булевы функции вида 5, = {v, л, -.} образуют булеву алгеб­ ру, а операции дизъюнкции, конъюнкции и отрицания образуют базис булевой алгебры. Множество булевых функций в базисе S6 = {®, л, 1} образуют алгебру Жегалкина, а операции М2, л и 1 образуют базис Жегалки- на. Достоинством алгебры Жегалкина является арифметизация логики, благодаря чему двузначная аристотелева логика нашла свое практическое применение. Поскольку в ней справедлив за­ кон исключенного третьего, то алгебра Жегалкина обладает од­ ной существенной особенностью: она непротиворечива, так как непротиворечива ее система аксиом. Анализ построения различных алгебр с помощью выбора соот­ ветствующего языка дает возможность увидеть принципы постро­ ения любой науки вообще. Выбирая, например, язык будущей системы, примем во вни­ мание структуру любой науки, будь то алгебра, геометрия, мате­ матическая логика или языки программирования. В конце попытаемся ответить на некоторые любопытные воп­ росы. Что значит говорить с наукой на одном языке? К чему приведет эффект Вавилонской башни? Что такое формализация языка ?Какова роль математики в си­ стеме знаний как способе формализации ? Все ли знания поддаются формализации ?Достаточно ли законов логики, чтобы формализовать все знания, известные науке на сегод­ ня, и получать новые? Как должна быть построена теория, чтобы в ней не возникало противоречий ? Какими свойствами должны обладать методы доказательств, чтобы считаться достаточно строгими? Упражнения 4.1. Проверьте, являются ли булевы функции F{ и F2 эквива­ лентными: а) Fi = X -> (Y= Z ) и F2= (X -> Y) = (X -> Z); б ) Fx = X - (Y= Z ) и F2= (XY) = (XZ); в) f i = X ^ ( Y v Z ) _ и F2= (. X_^ Y)_v (X -* Z); r) f i = XZ v X Y v XZ и F2= XYZ v XZ; Д) f i = X = Z и F2= ( X v Y v Z ) - » ( I v Y ) (Y v Z); e) f , = (ЛГ-> Z) и F2= X —» (XY -* ( (X -> Y) -» Y)Z). 4.2. Вычислите значение функции F(xb x2, x3) при заданных зна­ чениях аргументов х, = 0, х2= 0, х 3 = 0 и при хх = 1, х2 = 1, х 3 = 1 ; затем приведите функцию к минимальной ДНФ: a) F(x\, х2, х3) = х2хъ v х 3 v (х, •х 2 -> х3); 199