1.1.4. Алгебра (логика) высказываний

в повседневной жизни можно найти примеры утверждений, содержащие переменные параметры, значения которых не фиксируется. Например, утверждение

содержит параметр X. Пока переменной X не придано значение, скажем, 2, мы не можем ничего сказать о справедливости приведенного утверждения.

В логике переменным параметрам, входящим в утверждения, естественно приписывать значение Т или L, получая при этом высказывания. Назовем такие переменные параметры, следуя традиции, пропозицитадьными переменными. Как правило, для краткости пропозициональные переменные именуют просто переменными. Будем обозначать их как Х\, Х,..., Хп,...

Поскольку логика под влиянием математики превратилась в математическую логику, то естественным было использование в логике терминологии, принятой в математике. В частности, утверждение А, содержащее переменные, стали называть формулой. Для того чтобы быть точным, логик обязан был дать строгое определение того утверждения, которое он хотел бы назвать формулой. Отсюда следующее индуктивное определение формулы:

1) пропозициональная переменная есть (атомарная) формула;

2) если Лив формулы, тю [Ак.В), [АУ В), [А В) формулы;

3) если А формула, то ~A формула.

Как видим, при построении формул используются скобки ( и ). Однако, как часто делается, лишние скобки опускают. К примеру, формулу ((.Л V В)к.С) пишут как (.Л V В)к.С, а (ALB) как ALB. Существуют и другие правила, позволяющие не ставить лишних скобок.

Формулу А, содержащую пропозициональные переменные Xi, Х2,Хп, будем обозначать как A{X-i , Xi,Х).

Теория, которая изучает формулы, определенные выше, называется алгеброй высказываний. В алгебре высказываний каждая пропозициональная переменная, каждая формула принимает одно из двух значений - Т (истина) или L (ложь).

функция f(Xi,Хп) такая, что ее переменные и она сама могут принимать только два значения - Т или L - называется булевой функцией. Иначе говоря, булева функция - это отображение

/:{±,Т}х х{±,Т}{±,Т}.

ге-раз

Теорема 1.2. Пусть f(X\,...,Xn) - произвольная булева функция. Тогда

= [/(T,...,T)&Xi&...&X„]V V[/(T,T, L)&Xi&...&X„ i&--nX„] V ... ... V [/( L, L)&~nXi&...&~nX„].

Доказательство. См. [32, с.56].

Таким образом, каждая (двузначная) булева функция является формулой логики (алгебры) высказываний.

1.1.5. Релейно-контактные схемы

Каждой булевой функции можно поставить в соответствие так называемую релейно-контактную схему.

Релейно-контактная схема строится в предположении, что пропозициональная переменная X - это замыкающий контакт в электрической схеме, который замкнут при подаче (управляющего) тока X, т.е. X = Т, ш разомкнут при его отсутствии - X = L. Далее, формуле -iX отвечает размыкающий контакт, который замкнут, т.е. -iX = Т, пока нет тока {X = L), и размыкается - -iX = L, когда ток есть {X = Т).

Удобно вместо символа Т писать символ 1 (ток проходит), а вместо L - О (ток не проходит). Дизъюнкции X У Y соответствует параллельное соединение (зaмыкaюLTJx) контактов (рис.1.1, Ь)), а конъюнкции - последовательное соединение (рис.1.1, а)). На рис.1.1 символ Е означает «вход», а S - ток на «выходе».

Из простейших схем легко собираются произвольные релейно-контактные схемы. Например, на рис.1.2 приведена схема для булевой функции f{X, У, Z, и, W) = {X&iW&i{~Z V У)) V {U&i~X).

Е-Х-Y-S Е-I ~ 1-S

f(X,Y)=X&Y f(X,Y)=XvY

а) b)

Рис. 1.1: Простейшие релейно-контактные схемы.

f(X,Y,Z,U,W) = (X & W & (nZ V Y )) V (U &пХ)

Рис. 1.2: Релейно-контактная схема для булевой функции /(X, Y, Z, и, W) = (X&M/&(-.Z V Y)) V ((7&-.Х).