А́ЛГЕБРА ЛО́ГИКИ

А́ЛГЕБРА ЛО́ГИКИ, раз­дел ма­те­ма­тич. ло­ги­ки, изу­чаю­щий вы­ска­зы­ва­ния с точ­ки зре­ния их ло­гич. зна­че­ний (ис­тин­но­сти или лож­но­сти) и ло­гич. опе­ра­ции над вы­ска­зы­ва­ния­ми.

А. л. воз­ник­ла в сер. 19 в. в тру­дах Дж. Бу­ля. Соз­да­ние А. л. пре­сле­до­ва­ло цель ре­шать тра­ди­ци­он­ные ло­гич. за­да­чи ал­геб­ра­ич. ме­то­да­ми. В А. л. под вы­ска­зы­ва­ния­ми по­ни­ма­ют­ся пред­ло­же­ния, от­но­си­тель­но ко­то­рых име­ет смысл ут­вер­ждать, ис­тин­ны они или лож­ны. Упот­реб­ляе­мые в обыч­ной ре­чи ло­гич. связ­ки, та­кие, как «и», «или», «ес­ли..., то...», «эк­ви­ва­лент­но», час­ти­ца «не», по­зво­ля­ют из уже за­дан­ных вы­ска­зы­ва­ний стро­ить но­вые, бо­лее слож­ные вы­ска­зы­ва­ния. Ис­тин­ность или лож­ность по­лу­чае­мых та­ким об­ра­зом вы­ска­зы­ва­ний за­ви­сит от ис­тин­но­сти или лож­но­сти ис­ход­ных вы­ска­зы­ва­ний и со­ответ­ст­вую­щей трак­тов­ки свя­зок как опе­ра­ций над вы­ска­зы­ва­ния­ми. Для обо­зна­че­ния ис­тин­но­сти ис­поль­зо­вал­ся сим­вол «И», а для лож­но­сти – сим­вол «Л». За­тем вме­сто этих сим­во­лов ста­ли упот­реб­лять чис­ла 1 и 0. Связ­ки «и», «или», «ес­ли..., то...», «эк­ви­ва­лент­но» обо­зна­ча­ют­ся со­от­вет­ст­вен­но зна­ка­ми $\&$ (конъ­юнк­ция), $∨$ (дизъ­юнк­ция), $\rightarrow$ (им­пли­ка­ция), $∼$ (эк­ви­ва­лент­ность); от­ри­ца­ние (час­ти­ца «не») обо­зна­ча­ет­ся зна­ком $¬$ или чер­той свер­ху. На­ря­ду с ин­ди­ви­ду­аль­ны­ми вы­ска­зы­ва­ния­ми ста­ли ис­поль­зо­вать­ся так­же пе­ре­мен­ные вы­ска­зы­ва­ния, зна­че­ния­ми ко­то­рых мо­гут быть лю­бые на­пе­рёд за­дан­ные ин­ди­ви­ду­аль­ные вы­ска­зы­ва­ния. По­ня­тие фор­му­лы, яв­ляю­щее­ся фор­ма­ли­за­ци­ей по­ня­тия слож­но­го вы­ска­зы­ва­ния, вво­дит­ся ин­дук­тив­но. Пусть $A, B, C, \ldots$ – ин­ди­ви­ду­аль­ные, а $x, y, z, \ldots$ – пе­ре­мен­ные вы­ска­зы­ва­ния. Ка­ж­дая из этих букв назы­ва­ет­ся фор­му­лой. Ес­ли знак $*$ обо­зна­ча­ет лю­бую из пе­ре­чис­лен­ных вы­ше свя­зок, а $U$ и $V$ суть фор­му­лы, то $(U*V)$ и $\overline U$ суть фор­му­лы, напр. ($(x\&y)\rightarrow z)$. Связ­ки (в т. ч. и от­ри­ца­ние) рас­смат­ри­ва­ют­ся как опе­ра­ции над ве­ли­чи­на­ми, при­ни­маю­щи­ми зна­че­ния 0 и 1, ре­зуль­та­том при­ме­не­ния этих опе­ра­ций так­же яв­ля­ют­ся чис­ла 0 и 1. Конъ­юнк­ция $x \& y$ рав­на 1 точ­но то­гда, ко­гда и $x$, и $y$ рав­ны 1; дизъ­юнк­ция $x∨y$ рав­на 0 точ­но то­гда, ко­гда и $x$, и $y$ рав­ны 0; им­пли­ка­ция $x \rightarrow y$ рав­на 0 точ­но то­гда, ко­гда $x$ ра­вен 1, а $y$ ра­вен 0; эк­ви­ва­лент­ность $x∼y$ рав­на 1 точ­но то­гда, ко­гда зна­че­ния $x$ и $y$ сов­па­да­ют; от­ри­ца­ние $x$ рав­но 1 точ­но то­гда, ко­гда $x$ ра­вен 0. Вве­дён­ные опе­ра­ции по­зво­ля­ют ка­ж­дой фор­му­ле при за­дан­ных зна­че­ни­ях вхо­дя­щих в неё вы­ска­зы­ва­ний при­пи­сать од­но из двух зна­че­ний 0 или 1. Тем са­мым ка­ж­дая фор­му­ла мо­жет од­но­вре­мен­но рас­смат­ри­вать­ся как не­ко­то­рый спо­соб за­да­ния (реа­ли­за­ции) функ­ций А. л., т. е. та­ких функ­ций, ко­то­рые оп­ре­де­ле­ны на на­бо­рах из ну­лей и еди­ниц и зна­че­ния­ми ко­то­рых яв­ля­ют­ся так­же 0 или 1. При этом фор­му­лы $U$ и $V$ на­зы­ва­ют­ся рав­ны­ми, ес­ли они реа­ли­зу­ют рав­ные функ­ции, в этом слу­чае пи­шут $U=V$. Вна­ча­ле объ­ек­том изу­че­ния А. л. бы­ли функ­ции А. л. и разл. опе­ра­ции над ни­ми. В по­сле­дую­щем класс функ­ций А. л. был рас­ши­рен до клас­са функ­ций, ар­гу­мен­ты ко­то­рых и са­ми функ­ции при­ни­ма­ют в ка­че­ст­ве зна­че­ний эле­мен­ты не­ко­то­ро­го фик­си­ро­ван­но­го ко­неч­но­го мно­же­ст­ва $E$; рас­ши­рил­ся так­же за­пас опе­ра­ций над функ­ция­ми. Ино­гда под А. л. по­ни­ма­ет­ся имен­но по­след­няя кон­цеп­ция. Для при­ло­же­ний наи­боль­шее зна­че­ние име­ет слу­чай, ко­гда мно­же­ст­во $E$ со­сто­ит из двух эле­мен­тов.

Мно­же­ст­во всех фор­мул, в по­строе­нии ко­то­рых уча­ст­ву­ют пе­ре­мен­ные вы­ска­зы­ва­ния и не­ко­то­рые из сим­во­лов $\&, ∨, →, ∼, ¬$ и кон­стант 0 и 1, на­зы­вается язы­ком над дан­ны­ми сим­во­ла­ми и кон­стан­та­ми. Для вся­кой фор­му­лы в язы­ке над $\{ \&, ∨, →, ∼, ¬ \}$ най­дёт­ся рав­ная ей фор­му­ла в язы­ке над $\{ \&, ∨, ¬, 0, 1 \}$. Осо­бую роль в по­след­нем язы­ке иг­ра­ет класс фор­мул, ко­торые мо­гут быть за­пи­са­ны в ви­де $U_1∨U_2∨\ldots∨U_s$, 0 или 1, где $s⩾1$ и каж­дое $U_i$ – ли­бо пе­ре­мен­ное вы­ска­зы­ва­ние, ли­бо его от­ри­ца­ние, ли­бо конъ­юнк­ция пе­ре­мен­ных вы­ска­зы­ва­ний и от­ри­ца­ний пе­ре­мен­ных вы­ска­зы­ва­ний; при этом ка­ж­дое $U_i$ не со­дер­жит оди­на­ко­вых со­мно­жи­те­лей и не со­дер­жит со­мно­жи­те­лей ви­да $x$ и од­но­вре­мен­но и все $U_i$ по­пар­но не рав­ны. В этой за­пи­си скоб­ки опус­ка­ют­ся, т. к. пред­по­ла­гает­ся, что опе­ра­ция конъ­юнк­ции силь­нее дизъ­юнк­ции, т. е. при вы­чис­ле­нии по за­дан­ным зна­че­ни­ям пе­ре­мен­ных сле­ду­ет сна­ча­ла вы­чис­лять зна­че­ния $U_1, \ldots , U_s$. Эти вы­ра­же­ния на­зы­ва­ют­ся дизъ­юнк­тив­ны­ми нор­маль­ны­ми фор­ма­ми. Ка­ж­дую фор­му­лу $U$ в язы­ке над $\{ \&, ∨, →, ∼, ¬, 0, 1 \}$, реа­ли­зую­щую функ­цию А. л., от­лич­ную от 0, мож­но при­вес­ти к рав­ной ей дизъ­юнк­тив­ной нор­маль­ной фор­ме, со­дер­жа­щей все пе­ре­мен­ные фор­му­лы и лю­бое чис­ло дру­гих пе­ре­мен­ных, при­чём ка­ж­дое $U_i$ в этой дизъ­юнк­тив­ной нор­маль­ной фор­ме со­дер­жит од­ни и те же пе­ре­мен­ные. Та­кая дизъ­юнк­тив­ная нор­маль­ная фор­ма на­зы­ва­ет­ся со­вер­шен­ной дизъ­юнк­тив­ной нор­маль­ной фор­мой фор­му­лы $U$; для 0 со­вер­шен­ной дизъ­юнк­тив­ной нор­маль­ной фор­мой яв­ля­ет­ся са­ма фор­му­ла 0. Воз­мож­ность при­ве­де­ния к со­вер­шен­ной дизъ­юнк­тив­ной нор­маль­ной фор­ме ле­жит в ос­но­ве ал­го­рит­ма, ус­та­нав­ли­ваю­ще­го ра­вен­ст­во или не­ра­вен­ст­во двух за­дан­ных фор­мул.

Важ­ную роль в А. л. и её при­ло­же­ни­ях иг­ра­ет со­кра­щён­ная дизъ­юнк­тив­ная нор­маль­ная фор­ма, т. е. та­кая, для ко­то­рой вы­пол­не­ны сле­дую­щие ус­ло­вия: в ней нет пар сла­гае­мых $U_i$ и $U_j$ та­ких, что вся­кий со­мно­жи­тель из $U_i$ име­ет­ся и в $U_j$; для вся­ких двух сла­гае­мых $U_i$ и $U_j$, из ко­то­рых од­но со­дер­жит со­мно­жи­те­лем не­ко­то­рое пе­ре­мен­ное, а дру­гое – от­ри­ца­ние это­го пе­ре­мен­но­го (при ус­ло­вии, что дру­го­го пе­ре­мен­но­го, для ко­то­ро­го это же име­ет ме­сто, в дан­ной па­ре сла­гае­мых нет), име­ет­ся (в этой же дизъ­юнк­тив­ной нор­маль­ной фор­ме) сла­гае­мое $U_k$, рав­ное конъ­юнк­ции ос­таль­ных со­мно­жи­те­лей этих двух сла­гае­мых. Вся­кая дизъ­юнк­тив­ная нор­маль­ная фор­ма мо­жет быть при­ве­де­на к рав­ной ей со­кра­щён­ной дизъ­юнк­тив­ной нор­маль­ной фор­ме. Кро­ме дизъ­юнк­тив­ных нор­маль­ных форм упот­реб­ля­ют­ся так­же конъ­юнк­тив­ные нор­маль­ные фор­мы, т. е. вы­ра­же­ния, ко­то­рые мож­но по­лу­чить из дизъ­юнк­тив­ных нор­маль­ных форм пу­тём за­ме­ны в них зна­ков $∨$ на $\&$, а $\&$ на $∨$ и 0 на 1. Опе­ра­ция (или функ­ция) $f^*$ на­зы­ва­ет­ся двой­ст­вен­ной для опе­ра­ции $f$, ес­ли таб­ли­ца, за­даю­щая функ­цию $f^*$, по­лу­ча­ет­ся из таб­ли­цы для $f$ за­ме­ной в ней 0 на 1, а 1 на 0 (вклю­чая за­ме­ну зна­че­ний функ­ций). Напр., конъ­юнк­ция и дизъ­юнк­ция двой­ст­вен­ны ме­ж­ду со­бой, от­ри­ца­ние двой­ст­вен­но са­мо­му се­бе, кон­стан­ты 1 и 0 двой­ст­вен­ны друг дру­гу. Пре­об­ра­зо­ва­ние фор­мул, при ко­то­ром зна­ки всех опе­ра­ций в вы­ра­же­нии за­ме­ня­ют­ся на зна­ки двой­ст­вен­ных им опе­ра­ций, кон­стан­та 0 за­ме­ня­ет­ся на 1, а 1 на 0, на­зы­ва­ет­ся пре­об­ра­зо­ва­ни­ем двой­ст­вен­но­сти. Т. н. прин­цип двой­ст­вен­но­сти фор­му­ли­ру­ет­ся сле­дую­щим об­ра­зом: ес­ли $U=V$ и $U^*$ двой­ствен­но $U$, а $V^*$ двой­ст­вен­но $V$, то $U^*=V^*$.

Со­вер­шен­ные и со­кра­щён­ные дизъ­юнк­тив­ные нор­маль­ные фор­мы и конъ­юнк­тив­ные нор­маль­ные фор­мы ис­поль­зу­ют­ся для ре­ше­ния за­да­чи об­зо­ра всех ги­по­тез и всех след­ст­вий за­дан­ной форму­лы. Под ги­по­те­зой фор­му­лы $U$ по­нима­ет­ся та­кая фор­му­ла $V$, что $(V \rightarrow U)= 1$, а под след­ст­ви­ем фор­му­лы $U$ – та­кая фор­му­ла $V$, что $(U \rightarrow V)=1$. Ги­по­те­за фор­му­лы $U$ на­зы­ва­ет­ся про­стой, ес­ли она есть конъ­юнк­ция пе­ре­мен­ных или их от­ри­ца­ний и по­сле от­бра­сы­ва­ния лю­бо­го из её со­мно­жи­те­лей пе­ре­ста­ёт быть ги­по­те­зой фор­му­лы $U$. Ана­ло­гич­но, след­ст­вие фор­му­лы $U$ на­зы­ва­ет­ся про­стым, ес­ли оно есть дизъ­юнк­ция пе­ре­мен­ных или их от­ри­ца­ний и по­сле от­бра­сы­ва­ния лю­бо­го из её сла­гае­мых пе­ре­ста­ёт быть след­ст­ви­ем фор­му­лы $U$. Ре­ше­ние за­да­чи об­зо­ра ги­по­тез и след­ст­вий мож­но по­лу­чить, ука­зав ал­го­ритм, строя­щий все про­стые ги­по­те­зы и след­ст­вия для за­дан­ной фор­му­лы, из ко­то­рых за­тем по­лу­ча­ют­ся все ос­таль­ные ги­по­те­зы и след­ст­вия.

В язы­ке над $\{ \&, +, 0, 1 \}$, где $+$ обо­зна­ча­ет сло­же­ние по мо­ду­лю 2, вы­ра­же­ние на­зы­ва­ет­ся при­ве­дён­ным по­ли­но­мом, ес­ли оно ли­бо име­ет вид $U_1+U_2+ \ldots +U_s$, где $U_i$ есть или 0, или 1, или пе­ре­мен­ное, или конъ­юнк­ция разл. пе­ре­мен­ных без от­ри­ца­ний, $U_i \neq U_j$ при $i \neq j,\,i,\,j=1, \ldots ,\,s,\,s⩾1$. Вся­кую фор­му­лу А. л. мож­но пред­ста­вить и един­ст­вен­ным об­ра­зом в ви­де при­ве­дён­но­го по­ли­но­ма, на­зы­вае­мо­го так­же по­ли­но­мом Же­гал­ки­на (изу­чал­ся И. И. Же­гал­ки­ным в 1927).

Кро­ме рас­смот­рен­ных язы­ков, су­ще­ст­ву­ют и др. язы­ки, рав­но­силь­ные им (два язы­ка на­зы­ва­ют­ся рав­но­силь­ны­ми, ес­ли при по­мо­щи не­ко­то­рых пра­вил пре­об­ра­зо­ва­ния ка­ж­дая фор­му­ла од­но­го из этих язы­ков пе­ре­во­дит­ся в рав­ную ей фор­му­лу в дру­гом язы­ке и об­рат­но). В ос­но­ву та­ко­го язы­ка дос­та­точ­но по­ло­жить лю­бую сис­те­му опе­ра­ций и кон­стант, об­ла­даю­щую тем свой­ст­вом, что че­рез опе­ра­ции и кон­стан­ты этой сис­те­мы мож­но пред­ста­вить вся­кую функ­цию А. л. Та­кие сис­те­мы на­зы­ва­ют­ся функ­цио­наль­но пол­ны­ми. При­ме­ра­ми пол­ных сис­тем яв­ля­ют­ся $\{ \overline{x∨y} \} \{{x∨y} , \overline x \} $, $\{ x+y, 1, x\,\&\,y \}$ и т. п. Су­ще­ст­ву­ет алго­ритм, ко­то­рый по про­из­воль­ной конеч­ной сис­те­ме функ­ций А. л. ус­та­нав­ли­вает её пол­но­ту или не­пол­но­ту. Сис­те­ма функ­ций А. л. яв­ля­ет­ся пол­ной точ­но то­гда, ко­гда она со­дер­жит функ­ции $f_1, ..., f_5$ та­кие, что $f_1(0, 0, \ldots, 0)=1,\,f_2(1, 1, \ldots, 1)=0,\,f_3 \neq f^*_3,\,f_4$ – не мо­но­тон­на, а для $f_5$ при­ве­дён­ный по­ли­ном со­дер­жит сла­гае­мое $U$, в ко­то­ром боль­ше од­но­го со­мно­жи­те­ля. При этом на­бор $(a_1, ..., a_n)$ не пре­вос­хо­дит на­бо­ра $(b_1, ..., b_n)$, ес­ли все­гда $a_i⩽b_i$, а функ­ция $f(x_1, ..., x_n)$ мо­но­тон­на, ес­ли её зна­че­ния $a$ и $b$ на та­ких на­бо­рах все­гда свя­за­ны так, что $a⩽b$. Рас­смат­ри­ва­ют­ся и та­кие язы­ки, в ос­но­ве ко­то­рых ле­жат сис­те­мы опе­ра­ций, не яв­ляю­щие­ся функ­цио­наль­но пол­ны­ми. Сре­ди них име­ет­ся бес­ко­неч­но мно­го по­пар­но не­срав­ни­мых язы­ков, т. е. нет пе­ре­во­ди­мо­сти с од­но­го язы­ка на дру­гой при по­мо­щи то­ж­де­ст­вен­ных пре­об­ра­зо­ва­ний. Для вся­ко­го язы­ка, по­стро­ен­но­го на осно­ве тех или иных опе­ра­ций А. л., су­ще­ст­ву­ет та­кая ко­неч­ная сис­те­ма ра­венств это­го язы­ка, что вся­кое ра­венст­во вы­во­ди­мо при по­мо­щи то­ж­де­ст­вен­ных пре­об­ра­зо­ва­ний из ра­венств этой сис­те­мы. Та­кая сис­те­ма на­зы­ва­ет­ся де­дук­тив­но пол­ной сис­те­мой ра­венств дан­но­го язы­ка.

Рас­смат­ри­вая тот или иной из упо­мя­ну­тых вы­ше язы­ков вме­сте с не­ко­то­рой пол­ной сис­те­мой ра­венств это­го язы­ка, ино­гда от­вле­ка­ют­ся от таб­лич­но­го за­да­ния опе­ра­ций, ле­жа­щих в ос­но­ве язы­ка, и от то­го, что зна­че­ния­ми его пе­ре­мен­ных яв­ля­ют­ся вы­ска­зы­ва­ния. Вме­сто это­го до­пус­ка­ют­ся разл. ин­тер­пре­та­ции язы­ка, со­стоя­щие из той или иной со­во­куп­но­сти объ­ек­тов (слу­жа­щих зна­че­ния­ми пе­ре­мен­ных) и сис­те­мы опе­ра­ций над объ­ек­та­ми это­го мно­же­ст­ва, удов­ле­тво­ряю­щих ра­вен­ст­вам из пол­ной сис­те­мы ра­венств язы­ка. Так, язык над $\{ \&, ∨, ¬, 0, 1 \}$ в ре­зуль­та­те та­ко­го ша­га пре­вра­ща­ет­ся в язык бу­ле­вой ал­геб­ры; язык над $\{ \&, +, 1 \}$ пре­вра­ща­ет­ся в язык бу­ле­ва коль­ца (с еди­ни­цей), язык над $\{ \&, ∨, ¬ \}$ пре­вра­ща­ет­ся в язык ди­ст­ри­бу­тив­ной ре­шёт­ки.

А. л. раз­ви­ва­ет­ся гл. обр. под влия­нием при­клад­ных за­дач, сре­ди ко­то­рых важ­ную роль иг­ра­ют за­да­чи тео­рии элек­трич. схем. Для опи­са­ния та­ких за­дач ино­гда при­хо­дит­ся от­ка­зы­вать­ся от ис­поль­зо­ва­ния обыч­ной дву­знач­ной А. л. и рас­смат­ри­вать те или иные её мно­го­знач­ные обоб­ще­ния.