Автор неизвестен - Информация, язык, интеллект - страница 57

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 

обозначают булевы дизъюнкцию, конъюнкцию и отрицание. В левой части тех же равенств знаки v , л , обозначают операции дизъюнкции, конъюн­кции и отрицания предикатов.

Множество всех n-арных предикатов, задан­ных на Un, на котором определены операции ди­зъюнкции, конъюнкции и отрицания, предикатов называется алгеброй n -арных предикатов на U . Операции дизъюнкции, конъюнкции и отрицания предикатов называются базисными для алгебры предикатов. Алгебра предикатов при любом значе­нии n является разновидностью булевой алгебры. В ней выполняются все основные тождества буле­вой алгебры. В алгебре предикатов роль элементов0 , 1 и операций + , и' выполняют соответствен­но тождественно ложный и тождественно истин­ный предикаты и операции дизъюнкции, конъюн­кции и отрицания предикатов. Предикат вида:

= |1,если xi = a, (86) [0, если xt ф a называются базисными для алгебры предикатов. Здесь iє{1,2,...,n}, a — любой элемент универсума U . Если универсум конечен и состоит из k эле­ментов, то всего имеется kn различных базисных элементов. Алгебра предикатов полна в том смысле, что любой ее предикат можно представить в виде некоторой суперпозиции базисных операций, примененных к базисным элементам. Предикат xa называется узнаванием предмета a по переменной

xi.

Для узнаваний предметов при любом iє{ 1,2,...,n} справедливы следующие тождества: закон истинности —

v xa = 1, (87) закон отрицания — для любого a єU

=v xb (88)

b Фа

закон ложности — для любых a,bєU , если aфb , то

xaixbi = 0 (89)

Запись v обозначает операцию логического

суммирования, выполняемую для всех a, прина­длежащих универсуму U.

Если универсум конечен U = {а1,а2,..,ак}, то только что приведенные тождества можно перепи­сать в виде:

закон истинности — для любого i є{ 1,2,..., n}

xa1 vxa2 v...vxak = 1, (90)

закон отрицания — для любых iє{1,2,...,п} и j є{1,2,...,к}

x] = x]1 v x]2 v... v x]j-1 v x]j+1 v... v xak, (91)

закон ложности — для любых iє{1,2,...,п} , j,lє{1,2,...,к} и j ф l

xajxai = 0. (92)

Пусть P — отношение, заданное на Un. Преди­кат P , значения которого вычисляются по прави­лу

P(x1,x2,. ,x„) =J^(^2,^P (93) [0, если x1,x2,...,xn)gP

называется предикатом, соответствующим отноше­нию P . Каждому отношению P на Un соответс­твует свой предикат P на Un и наоборот. Наличие такого взаимно однозначного соответствия между отношениями и предикатами дает возможность математически записывать любое отношение в виде некоторой формулы алгебры предикатов, по которой могут быть вычислены значения предиката, соответствующего этому отношению. Например, отношению

P = {(п,а,п,а),(м,а, м,а)}

соответствуетпредикат P , значения которого опреде-ляетсяформулой P(x1,x2,x3,x4) = x2Lx4x(xnxn vx1Mx3M). Переменные x1, x2, x3, x4, фигурирующие в формуле, можно содержательно интерпретировать как имена первого, второго, третьего и четвертого мест элемен­тов в наборах, образующих отношение P (считая слева неправо). Запись

означает, что в данном случае речь идет о наборе (п, а, п, а), на первом и третьем местах которого стоит буква п, а на втором и четвертом буква а.

Любой предикат P , заданный на Un, можно выразить следующей формулой алгебры предика­тов

P(x1,x2,...,xn) =     v     x]1 x? ^x]n, (94)

(ab02,...,an P

называемой совершенной дизъюнктивной нор­мальной формой предиката P (сокращенно СДНФ предиката). Запись в правой части равенства (94) означает, что ведется логическое суммирование по всем наборам предметов (a1,a2,^,an), входящим в состав отношения P , соответствующего предика­ту P .

Декартову произведению A1 x A2 x...x An мно­жеств A1,A2,...,An сU соответствует предикат A x A2 x...x An, значения которого определяются формулой

(A X A2 x „. x An    x2,^, xn )= (95)

= A1(x1 )A2(x2). An(xn).

Здесь A — предикат, соответствующий мно­жеству A (i = 1,2,...,n), стоящему на i -м месте в де­картовом произведении A = A x A2 x...x Ai x...x An. Его значения отыскиваются по формуле

A (xi )=vxa (96)

Если множество A конечно (A ={a1,a2,..,ak}) , то значения соответствующего ему предиката оп­ределяются формулой

Ai (xt) = x]1 vx]2 v...vx]k (97)

Выражение множеств A формулами (96) и (97) выявляет следующий важный факт: оказывается, что предикат A (хі ), соответствующий множес-тву A , описывает не только само это множес­тво, но и его место в декартовом произведении A = A x A2 x...x A x...x An. Это место представлено переменной X/. Таким образом, выражение мно­жества A предикатом A (хі) = x]1 vх]2 v...vx]k характеризует множество более полно, чем запись A = {al,a2,..,ak}. Рассмотрим, к примеру, декарто­во произведение A = M x M , где M = {a,b}. Мно­жеству M , стоящему на первом месте в A, соглас­но (97) соответствует предикат M(x1 ) = x] v xb . Множеству же M, стоящему на втором месте в A и имеющему то же число и тот же состав элемен­тов, соответствует иной предикат M(x2 ) = х] v x\ .

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа