Подпишитесь на наши новости
Вернуться к началу с статьи up
 

МНОГОЗНА́ЧНАЯ ЛО́ГИКА

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 20. Москва, 2012, стр. 541-542

  • image description

    Скопировать библиографическую ссылку:




Авторы: В. Б. Кудрявцев

МНОГОЗНА́ЧНАЯ ЛО́ГИКА, раз­дел ма­те­ма­ти­че­ской ло­ги­ки, изу­чаю­щий ма­те­ма­тич. мо­де­ли ло­ги­ки вы­ска­зы­ва­ний. Эти мо­де­ли от­ра­жа­ют две осн. чер­ты по­след­ней – мно­же­ст­вен­ность зна­че­ний ис­тин­но­сти вы­ска­зы­ва­ний и воз­мож­ность по­строе­ния но­вых, бо­лее слож­ных вы­ска­зы­ва­ний из за­дан­ных при по­мо­щи ло­гич. опе­ра­ций, ко­то­рые по­зво­ля­ют по зна­че­ни­ям ис­тин­но­сти ис­ход­ных вы­ска­зы­ва­ний ус­та­нав­ли­вать зна­че­ние ис­тин­но­сти слож­ных вы­ска­зы­ва­ний. При­ме­ра­ми мно­го­знач­ных вы­ска­зы­ва­ний яв­ля­ют­ся су­ж­де­ния с мо­даль­ным ис­хо­дом («да», «нет», «мо­жет быть») и су­ж­де­ния ве­ро­ят­но­ст­но­го ха­рак­те­ра, а при­ме­ра­ми ло­гич. опе­ра­ций – ло­гич. связ­ки ти­па «и», «или», «ес­ли..., то». В об­щем слу­чае мо­де­ли М. л. пред­став­ля­ют со­бой обоб­ще­ния ал­геб­ры ло­ги­ки. В ал­геб­ре ло­ги­ки вы­ска­зы­ва­ния при­ни­ма­ют толь­ко два зна­че­ния ис­тин­но­сти («да», «нет»), в свя­зи с чем она в об­щем слу­чае не мо­жет от­ра­зить все­го мно­го­об­ра­зия ло­гич. по­строе­ний, встре­чаю­щих­ся на прак­ти­ке. При дос­та­точ­но ши­ро­ком тол­ко­ва­нии М. л. в неё ино­гда вклю­ча­ют так­же ло­ги­че­ские ис­чис­ле­ния.

Ис­то­ри­че­ски пер­вы­ми мо­де­ля­ми М. л. яви­лись дву­знач­ная ло­ги­ка Дж. Бу­ля (на­зы­вае­мая так­же ал­геб­рой ло­ги­ки), трёх­знач­ная ло­ги­ка Я. Лу­ка­се­ви­ча (1920) и $m$-знач­ная ло­ги­ка Э. По­ста (1921). Изу­че­ние этих мо­де­лей со­ста­ви­ло важ­ный этап в соз­да­нии тео­рии М. л. Оп­ре­де­лён­ная спе­ци­фи­ка М. л. со­сто­ит в рас­смот­ре­нии за­дач и под­хо­дов, воз­ни­каю­щих при ис­сле­до­ва­нии М. л. с по­зи­ций ма­те­ма­тич. ло­ги­ки, тео­ре­тич. ки­бер­не­ти­ки и ал­геб­ры. Так, с по­зи­ций тео­ре­тич. ки­бер­не­ти­ки мо­де­ли М. л. рас­смат­ри­ва­ют­ся как язы­ки, опи­сы­ваю­щие функ­цио­ни­ро­ва­ние слож­ных управ­ляю­щих сис­тем, ком­по­нен­ты ко­то­рых мо­гут на­хо­дить­ся в не­ко­то­ром чис­ле разл. со­стоя­ний; с точ­ки зре­ния ал­геб­ры мо­де­ли М. л. пред­став­ля­ют со­бой ал­геб­ра­ич. сис­те­мы, имею­щие, на­ря­ду с при­клад­ным, и чис­то тео­ре­тич. ин­те­рес.

По­строе­ние мо­де­лей М. л. осу­ще­ст­в­ля­ет­ся по ана­ло­гии с по­строе­ни­ем дву­знач­ной ло­ги­ки. Так, ин­ди­ви­ду­аль­ные вы­ска­зы­ва­ния ло­ги­ки, раз­би­тые на клас­сы с од­ним и тем же зна­че­ни­ем ис­тин­но­сти, при­во­дят к по­ня­тию мно­же­ст­ва кон­стант мо­де­ли $E$, ко­то­рые фак­ти­че­ски ото­жде­ст­в­ля­ют все ин­ди­ви­ду­аль­ные вы­ска­зы­ва­ния, за­ме­няя их со­от­вет­ст­ву­ю­щи­ми зна­че­ния­ми ис­тин­но­сти; пе­ре­мен­ные вы­ска­зы­ва­ния – к пе­ре­мен­ным ве­ли­чи­нам $x_1, x_2,...,$ ко­то­рые в ка­че­ст­ве зна­че­ний при­ни­ма­ют эле­мен­ты из мно­же­ст­ва $E$; ло­ги­че­ской связ­ки – к мно­же­ст­ву $M$ эле­мен­тар­ных функ­ций (опе­ра­ций), ко­то­рые, как и их ар­гу­мен­ты, при­ни­ма­ют зна­че­ния из $E$. Слож­ные вы­ска­зы­ва­ния, по­стро­ен­ные из ин­ди­ви­ду­аль­ных и пе­ре­мен­ных вы­ска­зы­ва­ний, а так­же ло­гич. свя­зок, при­во­дят к мно­же­ст­ву $\langle M \rangle$ фор­мул над $M$. Зна­че­ние ис­тин­но­сти (из $E$) слож­но­го вы­ска­зы­ва­ния яв­ля­ет­ся функ­ци­ей от со­от­вет­ст­ву­ю­щих зна­че­ний ис­тин­но­сти вы­ска­зы­ва­ний, вхо­дя­щих в дан­ное слож­ное вы­ска­зы­ва­ние. В мо­де­ли эта функ­ция при­пи­сы­ва­ет­ся фор­му­ле, со­от­вет­ст­вую­щей дан­но­му слож­но­му вы­ска­зы­ва­нию; го­во­рят так­же, что фор­му­ла реа­ли­зу­ет эту функ­цию. Мно­же­ст­во фор­мул $\langle M \rangle$ при­во­дит к мно­же­ст­ву $[M]$ функ­ций, реа­ли­зуе­мых фор­му­ла­ми из $\langle M \rangle$ и на­зы­вае­мых су­пер­по­зи­ция­ми над $M$. Мно­же­ст­во $[M]$ на­зы­ва­ет­ся за­мы­ка­ни­ем мно­же­ст­ва $M$. За­да­ние кон­крет­ной мо­де­ли М. л. счи­та­ет­ся эк­ви­ва­лент­ным ука­за­нию мно­жеств $E, M, \langle M \rangle$ и $[M]$; при этом го­во­рят, что мо­дель по­ро­ж­да­ет­ся мно­же­ст­вом $M$. Эта мо­дель на­зы­ва­ет­ся фор­муль­ной мо­де­лью, а так­же $m$-знач­ной ло­ги­кой, где $m$ – мощ­ность мно­же­ст­ва $E$.

Свое­об­ра­зие под­хо­да ма­те­ма­тич. ки­бер­не­ти­ки к М. л. со­сто­ит в рас­смот­ре­нии мо­де­лей М. л. как управ­ляю­щих сис­тем. Эле­мен­тар­ные функ­ции при этом яв­ля­ют­ся эле­мен­та­ми, про­из­во­дя­щи­ми оп­ре­де­лён­ные опе­ра­ции, а фор­му­лы ин­тер­пре­ти­ру­ют­ся как схе­мы, по­стро­ен­ные из эле­мен­тов и так­же осу­ще­ст­в­ляю­щие пе­ре­ра­бот­ку вход­ной ин­фор­ма­ции в вы­ход­ную. Та­ко­го ро­да управ­ляю­щие сис­те­мы, из­вест­ные в ки­бер­не­ти­ке как схе­мы из функ­цио­наль­ных эле­мен­тов, ши­ро­ко ис­поль­зу­ют­ся в тео­ре­тич. и прак­тич. во­про­сах ки­бер­не­ти­ки. Вме­сте с тем су­ще­ст­ву­ет ряд за­дач ло­ги­ки и ки­бер­не­ти­ки, ко­то­рые свя­за­ны с изу­че­ни­ем со­от­вет­ст­вий ме­ж­ду мно­же­ст­ва­ми $M$ и $[M]$ и при ко­то­ром роль мно­же­ст­ва $\langle M \rangle$ нес­коль­ко за­ту­шё­вы­ва­ет­ся, сво­дясь к спо­со­бу оп­ре­де­ле­ния вто­ро­го мно­же­ст­ва по пер­во­му. В этом слу­чае при­хо­дят к др. мо­де­ли М. л., ко­то­рая пред­став­ля­ет со­бой ал­геб­ру, эле­мен­та­ми ко­то­рой яв­ля­ют­ся функ­ции, при­ни­маю­щие в ка­че­ст­ве зна­че­ний, как и их ар­гу­мен­ты, эле­мен­ты из $E$. В ка­че­ст­ве опе­ра­ций в этих ал­геб­рах обыч­но ис­поль­зу­ет­ся спец. на­бор опе­ра­ций, эк­ви­ва­лент­ный в смыс­ле со­от­вет­ст­вий $M$ и $[M]$ мно­же­ст­ву фор­мул, по­стро­ен­ных из функ­ций мно­же­ст­ва $M$, т. е. по­лу­че­нию слож­ных функ­ций из за­дан­ных пу­тём под­ста­нов­ки од­них функ­ций вме­сто ар­гу­мен­тов дру­гих.

К чис­лу за­дач, ха­рак­тер­ных для фор­муль­ной мо­де­ли М. л., от­но­сит­ся за­да­ча об опи­са­нии, т. е. во­прос об ука­за­нии для за­дан­но­го мно­же­ст­ва $M_2⊆[M_1] $ всех фор­мул из $\langle M_1 \rangle$, реа­ли­зую­щих функ­ции из $M_2$. Ча­ст­ным слу­ча­ем та­кой за­да­чи яв­ля­ет­ся важ­ный во­прос ма­те­ма­тич. ло­ги­ки об ука­за­нии всех фор­мул, реа­ли­зую­щих за­дан­ную кон­стан­ту, что, напр., для ис­чис­ле­ния вы­ска­зы­ва­ний эк­ви­ва­лент­но по­строе­нию всех то­ж­де­ст­вен­но ис­тин­ных вы­ска­зы­ва­ний. По­гра­нич­ным во­про­сом ме­ж­ду ма­те­ма­тич. ло­ги­кой и ал­геб­рой, при­мы­каю­щим к за­да­че об опи­са­нии, яв­ля­ет­ся за­да­ча о то­ж­де­ст­вен­ных пре­об­ра­зо­ва­ни­ях. В ней при за­дан­ном мно­же­ст­ве $M$ тре­бу­ет­ся вы­де­лить в не­ко­то­ром смыс­ле про­стей­шее под­мно­же­ст­во пар рав­ных (т. е. реа­ли­зую­щих од­ну и ту же функ­цию) фор­мул из $\langle M \rangle$, по­зво­ляю­щее пу­тём под­ста­нов­ки вы­де­лен­ных рав­ных фор­мул од­ной вме­сто дру­гой по­лу­чить из лю­бой фор­му­лы все фор­му­лы, рав­ные ей. Ана­ло­гич­ное ме­сто за­ни­ма­ет один из важ­ней­ших во­про­сов для М. л. – т. н. про­бле­ма пол­но­ты, со­стоя­щая в ука­за­нии всех та­ких под­мно­жеств $M_1$ за­дан­но­го замк­ну­то­го, т. е. сов­па­даю­ще­го со сво­им за­мы­ка­ни­ем, мно­же­ст­ва $M$, для ко­то­рых вы­пол­не­но ра­вен­ст­во $[M_1]=M$, т. е. име­ет ме­сто свой­ст­во пол­но­ты $M_1$ в $M$. Гло­баль­ной за­да­чей для М. л. яв­ля­ет­ся опи­са­ние струк­ту­ры замк­ну­тых клас­сов дан­ной мо­де­ли мно­го­знач­ной ло­ги­ки.

Ха­рак­тер­ный для тео­рии управ­ляю­щих сис­тем во­прос о слож­но­сти этих сис­тем ес­те­ст­вен­но воз­ни­ка­ет и по от­но­ше­нию к фор­му­лам и функ­ци­ям из М. л. Ти­пич­ной при та­ком под­хо­де яв­ля­ет­ся сле­дую­щая за­да­ча о слож­но­сти реа­ли­за­ции. На мно­же­ст­ве всех эле­мен­тар­ных фор­мул не­ко­то­рым спо­со­бом вво­дит­ся чи­сло­вая ме­ра (слож­ность фор­мул), ко­то­рая за­тем рас­про­стра­ня­ет­ся на мно­же­ст­во всех фор­мул, напр. пу­тём сум­ми­ро­ва­ния мер всех тех эле­мен­тар­ных фор­мул, ко­то­рые уча­ст­ву­ют в по­строе­нии за­дан­ной фор­му­лы. Для за­дан­ной функ­ции тре­бу­ет­ся ука­зать ту (про­стей­шую) фор­му­лу, ко­то­рая реа­ли­зу­ет эту функ­цию и име­ет наи­мень­шую слож­ность, а так­же вы­яс­нить, как эта слож­ность за­ви­сит от не­ко­то­рых свойств рас­смат­ри­вае­мой функ­ции. Ис­сле­ду­ют­ся разл. обоб­ще­ния этой за­да­чи. Ши­ро­кий круг во­про­сов свя­зан с реа­ли­за­ци­ей функ­ций фор­му­ла­ми с на­пе­рёд за­дан­ны­ми свой­ст­ва­ми. Сю­да от­но­сят­ся: за­да­ча о реа­ли­за­ции функ­ций ал­геб­ры ло­ги­ки дизъ­юнк­тив­ны­ми нор­маль­ны­ми фор­ма­ми и свя­зан­ная с этим за­да­ча о ми­ни­ми­за­ции, а так­же за­да­ча о реа­ли­за­ции функ­ций фор­му­ла­ми в не­ко­то­ром смыс­ле ог­ра­ни­чен­ной глу­би­ны (т. е. та­ки­ми фор­му­ла­ми, в ко­то­рых це­поч­ка под­став­ляе­мых друг в дру­га фор­мул име­ет ог­ра­ни­чен­ную дли­ну, та­кое ог­ра­ни­че­ние свя­за­но с на­дёж­но­стью и ско­ро­стью вы­чис­ле­ний).

Для за­дан­ной мо­де­ли М. л. ре­ше­ния всех пе­ре­чис­лен­ных за­дач су­ще­ст­вен­но за­ви­сят от мощ­но­сти мно­же­ст­ва $E$ и мно­же­ст­ва $M$, по­ро­ж­даю­ще­го эту мо­дель.

К чис­лу наи­бо­лее важ­ных при­ме­ров М. л. от­но­сят­ся ко­неч­но­знач­ные ло­ги­ки (т. е. $m$-знач­ные ло­ги­ки, для ко­то­рых $m$ ко­неч­но). Сре­ди них наи­бо­лее глу­бо­ко ис­сле­до­ван слу­чай $m=$ 2. Важ­ней­шим ре­зуль­та­том здесь яв­ля­ет­ся пол­ное опи­са­ние струк­ту­ры замк­ну­тых клас­сов и по­лу­че­ние для них важ­ной ин­фор­ма­ции по за­да­че о слож­но­сти реа­ли­за­ции. Ус­та­нов­ле­но, что при $m>$ 2 ко­неч­но­знач­ные ло­ги­ки об­ла­да­ют ря­дом осо­бен­но­стей, су­ще­ст­вен­но от­ли­чаю­щих их от дву­знач­но­го слу­чая. Та­ко­вы, напр., кон­ти­ну­аль­ность мно­же­ст­ва замк­ну­тых клас­сов (при $m=$ 2 их счёт­ное чис­ло), осо­бен­но­сти ре­ше­ния за­да­чи о слож­но­сти реа­ли­за­ции и ряд дру­гих. Об­щим ре­зуль­та­том для ко­неч­но­знач­ных ло­гик яв­ля­ет­ся эф­фек­тив­ное ре­ше­ние за­да­чи о пол­но­те для замк­ну­тых клас­сов, со­дер­жа­щих все функ­ции со зна­че­ния­ми в $E$. Ре­ше­ние ос­таль­ных про­блем для ко­неч­но­знач­ных ло­гик про­дви­ну­то в разл. сте­пе­ни. Осо­бая зна­чи­мость ко­неч­но­знач­ных ло­гик свя­за­на ещё и с тем, что они по­зво­ля­ют опи­сы­вать ра­бо­ту разл. ре­аль­ных вы­чис­лит. уст­ройств и ав­то­ма­тов.

При­ме­ра­ми дру­гой М. л. яв­ля­ют­ся счёт­но­знач­ные и кон­ти­ну­ум-знач­ные ло­ги­ки (т. е. та­кие $m$-знач­ные ло­ги­ки, для ко­то­рых мощ­ность $m$ яв­ля­ет­ся со­от­вет­ст­вен­но счёт­ной или кон­ти­ну­аль­ной). Эти мо­де­ли иг­ра­ют важ­ную роль в ма­те­ма­тич. ло­ги­ке, мо­де­лей тео­рии и в ма­те­ма­тич. ана­ли­зе. К М. л. ино­гда от­но­сят и та­кие ал­геб­ры функ­ций, в ко­то­рых за­пас опе­ра­ций нес­коль­ко от­ли­ча­ет­ся от ука­зан­но­го. Как пра­ви­ло, это дос­ти­га­ет­ся пу­тём су­же­ния опи­сан­но­го за­па­са или вве­де­ния в опе­ра­ции не­ко­то­рых функ­ций рас­смат­ри­вае­мой мно­го­знач­ной ло­ги­ки.

Лит.: Яб­лон­ский С. В. Функ­цио­наль­ные по­строе­ния в k-знач­ной ло­ги­ке // Тр. Ма­те­ма­ти­че­ско­го ин­сти­ту­та АН СССР. 1958. Т. 51; Яб­лон­ский С. В., Гав­ри­лов ГП., Куд­ряв­цев В. Б. Функ­ции ал­геб­ры ло­ги­ки и клас­сы По­ста. М., 1966; Куд­ряв­цев В. Б. О функ­цио­наль­ных сис­те­мах. М., 1981; Мно­го­знач­ные ло­ги­ки и их при­ме­не­ния. М., 2008. Т. 1–2.

Вернуться к началу