Седов Н.Н. Введение в компьютерную математику - файл n1.doc

Седов Н.Н. Введение в компьютерную математику
скачать (3909 kb.)
Доступные файлы (1):
n1.doc3909kb.21.10.2012 09:52скачать

n1.doc

  1   2   3   4   5   6   7   8
МПС РОССИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ ______________________________________________


Н. Н. СЕДОВ


ВВЕДЕНИЕ В КОМПЬЮТЕРНУЮ МАТЕМАТИКУ


Учебное пособие


Москва  2002

УДК 519.6
Введение в компьютерную математику: Учебное пособие. / СЕДОВ Н. Н. Российск. госуд. откр. техн. ун-т путей сообщ. М.: 2002, 89 c.

Дается представление о разделах дискретного анализа, использующихся в современных компьютерных технологиях. Особое внимание уделено понятиям нечеткой математики и сфере их применения. Пособие предназначается для студентов-заочников и вечерников 2-3 курсов специальностей ЭВМ, ИСЖ.


Рецензенты: кафедра высшей математики РГОТУПСа, д-р. физ.-мат. наук,

проф. О. В. ДРУЖИНИНА,
д-р. техн. наук, проф. И. Н. ДОРОХОВ

(РХТУ им. Д. И. Менделеева).
ОГЛАВЛЕНИЕ



1. Введение…………………………………………….....................................4

2. Булевы алгебры.............................................................….............................8

3. Алгебра высказываний................................................….............................12

4. Алгебра предикатов.....................................................….............................18

5. Правила логического вывода.....................................…..............................23

6. Нечеткие множества и нечеткая логика...................…...............................25

7. Четкие и нечеткие отношения............................................…......................38

8. Четкие и нечеткие графы....................................................…......................50

9. Алгоритмы………………………………………………..............................57

9.1 Рекурсивные функции………………………………................................. 61

9.2 Машины Поста и Тьюринга………………….......................................65

9.3 Эквивалентность формализаций алгоритма. Проблема остановки…71

9.4. Разработка алгоритмов и анализ их сложности…...............................75

10. Автоматы………………………………………………................................81

Литература……..……………………………………………..............................89

1. ВВЕДЕНИЕ
Теоретико-множественное обоснование современной математики; статистические представления, лежащие в основе научной картины мира; прикладные и теоретические аспекты развития искусственного интеллекта  этот перечень внешне, казалось бы, совсем разных проблем базируется на одной и той же математической структуре  алгебре Буля. Ниже приведены две задачи, иллюстрирующие связь между математической логикой и теорией множеств  примерами булевых структур.

Рассмотрим следующую задачу. Два школьника задержаны у разбитого окна.

Три свидетеля, убоявшись солгать, но желая запутать директора, дают разные показания. Первый: стекло разбил Петров, или Курносов; второй: не Курносов, или Петров; третий: не Петров, или не Курносов. Как выявить нарушителя? Задачу можно решить с помощью логических рассуждений, а можно «механически»: закодировать условия с помощью логических переменных и упростить полученные выражения по формулам математической логики.

Назовем высказыванием р утверждение, о котором можно говорить, что оно истинно, или ложно. Истинным высказываниям можно сопоставить число 1, а ложным  0, например:

р = «дважды два четыре» = 1, q = «5 делится на 2» = 0.

Из исходных высказываний строятся сложные с помощью логических операций.

Высказывание, составленное из данных высказываний р и q с помощью союза «или», называют дизъюнкцией и обозначают pq (читается «p или q»). Дизъюнкция считается истинной (pq=1) тогда и только тогда, когда истинно хотя бы одно из составляющих высказываний.

Высказывание, составленное из данных высказываний р и q с помощью союза «и», называют конъюнкцией и обозначают pq (читается «p и q»). Конъюнкция считается истинной (pq=1) тогда и только тогда, когда р=q=1.

Операция отрицания высказывания p соответствует частице «не». Обозначается как ¬p, или (читается «не р»). , когда р истинно; , когда р = 0.

Приоритет перечисленных операций (последовательность преобразований в сложных формулах) дается в обратном порядке. Конъюнкцию еще называют логическим умножением, дизъюнкцию - сложением, и по аналогии с числовой алгеброй знак  можно опускать, например:

(pq)(rs) = (pq)(rs), pqr = pqr.

По аналогии с переменными х,у числовой алгебры, «пробегающими» множество числовых значений, будем рассматривать переменные p,q,r... сорта «высказывание», принимающие только два значения : 0, или 1. Для них выполняется ряд законов , общих с числовой алгеброй, например:

p0 = p, p1 = p, р(qr) = pqpr (cравни: 2(3+4) = 23 + 24 ),

но есть и отличия - второй дистрибутивный закон:

pqr = (pq)(pr) (тогда как 2 + 34  (2+3)(2+4) !).

Имеет место закон противоречия - для всех р: (одно и то же нельзя одновременно и утверждать и отрицать).

Решим теперь задачу о дознании. Пусть р = «Петров разбил стекло»;

q = «Курносов разбил стекло». Директор располагает тремя показаниями:

  1. pq = «стекло разбил Петров, или Курносов»,

  2. = «стекло разбил или Петров, или не Курносов»,

  3. = «Петров не разбивал стекла, или Курносов не разбивал»

Поскольку все показания истинны, то истинна будет и их конъюнкция, которую будем упрощать, последовательно перемножая показания:



Здесь использованы второй дистрибутивный закон и закон противоречия. Умножая результат на третье показание, раскрываем скобки:



Итак, по условию задачи и в силу логических законов:



Из последнего равенства следует , то есть, Петров разбил окно, а Курносов не разбивал.

Теперь рассмотрим следующую задачу. У директора лицея три дочери на выданье. Решив устроить бал, он выслушивает наказы каждой дочки о составе приглашаемых: первая  «хочу футболистов c гитаристами»; вторая - «только не футболистов, или не гитаристов»; третья согласна обойтись без гитаристов, согласна и на футболистов.

Это задача алгебры множеств, решением ее будет множество лицеистов, обладающих таким свойством, чтобы ни одна из дочерей не могла придраться к его составу.

Напомним основные понятия теории множеств. Принадлежность элемента х множеству М запишем как хМ, соответственно уМ означает, что у не входит в М. Cуществуют два способа задания множества - перечислением его элементов, или указанием их общего свойства. Например, множество М корней уравнения

х2 1 = 0 можно описать двояко: M= {-1, 1} = {x: х2  1 = 0}. Вводится пустое множество , не содержащее ни одного элемента, например:

{X: х2 + 1 = 0} =  (если ограничиваться только вещественными числами). Множество В является подмножеством А: B A, если все его элементы входят

в А. является подмножеством любого множества.

Перечислим основные операции над множествами А и В

  1. AB = {x: xA и хВ} - пересечение, или произведение множеств;

  2. AB = {x: xA , или хВ} - объединение, или сумма множеств;

  3. A \ B = {x: xA , но хВ} - разность множеств.

Cерые области на диаграммах Эйлера-Венна (рис. 1.1) являются графическими интерпретациями этих операций.


Все рассматриваемые в конкретной задаче множества вместе с входящими в них элементами образуют универсальное множество I (для социологов I - множество людей; в задачах планиметрии I - множество точек на плоскости). Посредством универсального множества I определяется операция дополнения к множеству А:

  1. = {x: xI и хА} = I \ A.

На рис. 1.2 - серая область прямоугольника, обозначающего I. Для всех А:



Для операций над множествами выполняется ряд законов-тождеств, аналогичных законам алгебры логики, например, оба дистрибутивных закона:



Опуская операцию , как более приоритетную, можем сократить формулы:

(1)

Продемонстрируем доказательство тождеств алгебры множеств на последней формуле (1). Она будет справедлива, если будут доказаны два включения:

  1. , 2) .

Пусть ххА, или х ВС. В силу первой возможности х входит в объединения А с любыми множествами, в том числе: х и х

В силу второй возможности хВ и хС и

Обращением хода рассуждений проверяется включение правой части доказываемого тождества в левую.

Вернемся к задаче о составе приглашенных на бал. Пусть I - множество лицеистов, cодержащее множество футболистов F и множество гитаристов G. Первую дочь устраивают все футболисты и гитаристы - , вторую  кавалеры, лишенные хотя бы одного из этих качеств: , третью - . Решением задачи будет пересечение желаемых множеств:



(здесь использованы законы (1) и равенства типа ) Итак, пригласив на бал множество футболистов, не играющих на гитаре, директор угодит сразу всем дочерям.

Анализ рассмотренных задач показывает, что оба директора должны выполнить одни и те же преобразования над разными по форме объектами - высказываниями и множествами, действия над которыми подчиняются сходным законам. Причину сходства законов алгебры множеств и алгебры логики проясняет схема доказательства тождеств (1), основанная на анализе логического смысла операций над множествами , определенных с помощью союзов «или», «и», «не», соответствующих операциям над высказываниями. Следующие сравнения:



иллюстрируют тот факт, что алгебра множеств и алгебра логики являются примерами общих алгебраических структур, начало изучения которых было положено английским математиком Дж. Булем в работе «Законы мышления» (1854 г.).

  1. БУЛЕВЫ АЛГЕБРЫ


Булевой алгеброй назовем множество В вместе с тремя операциями Бинарные операции: +,  и унарная операция вместе с двумя элементами В, которые обозначаются символами 0 и 1, удовлетворяют нижеследующим законам (в которых операция  опущена). Для всех x,y,z В :

  1. a) x + 0 = x, б) x1 = x;

  2. a) x + y = y + x, б) xy = yx - коммутативность;

  3. a) x + (y+z) = (x+y) + z, б) х (yz) = (xy) z - accoциативность;

  4. a) x (y+z) = xy + xz, б) x + yz = (x+y) (x+z) - дистрибутивность;

  5. a) б) - комплементарность.

В начале списка следуют тождества, обычные для числовой алгебры (заметим, что эти очевидные законы выполняются не во всех алгебрах, например, для матриц А и B АВ ВА !). Специфичными являются дистрибутивный закон (4.б) и законы (5), характеризующие элемент-дополнение . Следующие, получаемые из аксиом соотношения особенно часто используются в булевых вычислениях:

  1. a) x + 1 = 1, б) x0 = 0;

  2. a) x + x = x, б) хх = х - идемпотентность;

  3. a) x + xy = x, б) х (x+y) = x - поглощение;

  4. a) б) - законы де Моргана;

  1. - двойное дополнение.

В отличие от числовых операций сложения и умножения булевы операции + и  симметрично входят в тождества 1-9. Если в выписанных тождествах взаимно заменить символы + и, а также 0 и 1, то получится то же самое множество тождеств. На этом основан принцип двойственности для булевых алгебр: если доказана истинность некоторого утверждения, то истинным будет и двойственное утверждение, то есть, то, которое получается из данного взаимной заменой символов + и, а также 0 и 1. Например, доказав тождество мы можем быть уверены в тождестве . Рассмотрим примеры булевых алгебр.
1. Алгебра высказываний дает пример с множеством В из двух элементов:

В = {0,1} (1 - истина, 0 - ложь). Поскольку логические переменные принимают только два значения, операции над ними однозначно определяются в виде таблиц истинности для сложения , умножения  и отрицания:


p

q

pq




p

q

pq




p



0

0

1

1

0

1

0

1

0

1

1

1

0

0

1

1

0

1

0

1

0

0

0

1

0

1

1

0








последний столбец таблицы  результат операции над каждым из возможных наборов операндов (представляющим двоичное представление номера соответствующей строки). При построении таблицы истинности сложных формул промежуточные результаты выстраиваются слева направо в виде промежуточных столбцов. Например, для левой и правой частей тождества (4.б):

p qr = (pq)(pr)

таблицы истинности (в которых число строк теперь будет равно числу трехразрядных двоичных наборов - 23 = 8) примут вид:


p

g

r

gr

pgr




p

g

R

pg

pr

(pg) (pr)

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

0

1

0

0

0

1

0

0

0

1

1

1

1

1




0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

1

1

1

1

1

1

0

1

0

1

1

1

1

1

0

0

0

1

1

1

1

1


Cовпадение двух последних столбцов в таблицах доказывает справедливость (4.б). Аналогичным образом можно проверить все тождества (1-10) для всех значений логических переменных.

2.Множество P всех подмножеств универсального множества I, включая само I и пустое множество , образует булеву алгебру с нулем и единицей I, операциями сложения , пересечения  и дополнения . Подсчитаем число элементов P в случае конечного множества I, содержащего n элементов. При n=1, I= {a} имеем два подмножества: P = {, {a}} ; при n=2, I = {a,b} число подмножеств удвоится: P = {, {a}, {b}, {a,b}}. При n=3 и I = {a,b,c} P будет содержать перечисленные ранее подмножества и еще столько же, полученных добавлением к каждому из них нового элемента с. Таким образом, при увеличении n на единицу число подмножеств I будет удваиваться, следовательно, P будет содержать 2n элементов.

В алгебре множеств закон (1.a): означает, что при объединении с пустым множеством ничего не изменится; закон (7.б): означает, что пересечение А с самим собой совпадает с А. Помимо тождеств (1-10) в теории множеств имеет место ряд законов, связанных с включением одного множества в другое. Например, если А В и В С, то А С; если А С, то соотношение эквивалентно

Булевы операции над множествами приводят к построению объектов того же сорта - подмножеств универсального множества I. Сейчас будет изложен способ конструирования более сложных множеств, «вылезающих» за пределы I. Рассмотрим множество размеченных клеток шахматной доски, множество С столбцов, которые обозначим буквами a, b,...,h и множество S строк от 1 до 8. Каждая клетка может быть однозначно задана двумя символами: один из множества С={a, b,...,h}, другой из множества S = {1,2,...,8}, например, e2,e4, h8. Таким образом, из множеств С и S мы образовали множество СS всех клеток доски.

Декартовым произведением АВ множеств А и В называется множество упорядоченных пар элементов из А и В:

AB={(a,b): aA, bB}.

Приведем примеры. Пусть X = {0,1}, Y = {x,y}, тогда XY = {(0,x), (0,y), (1,x), (1,y)}; YX = {(x,0), (x,1), (y,0), (Y,1)}, таким образом, XYYX, то есть, коммутативный закон не выполняется. Декартовым произведением числовой оси R (геометрического образа множества вещественных чисел) на самое себя будет плоскость R2 = RR.

Пусть даны n множеств A1, A2, ..., An. Множество всех упорядоченных

наборов (а1, а2, ..., аn) таких, что а1А1, а2А2, ..., аnАn, называют декартовым произведением A1A2  ... An . Например, множество разнообразных обедов из трех блюд в ресторане будет декартовым произведением трех меню для каждого из блюд. Декартово произведение RRR = {(x,y,z), x,y,zR} описывает бесконечное множество всех точек пространства R3.

3. Случайные события, связанные с некоторым экспериментом, образуют булеву алгебру относительно операции сложения А+В (наступление хотя бы одного из событий А, В), умножения АВ (одновременное появление А и В), перехода от А к противоположному событию (наступающему в точности при не появлении данного события). Кроме того, фиксируется невозможное (никогда не наступающее) событие , соответствующее булевому нулю, и достоверное (всегда наступающее при проведении данного эксперимента) событие , соответствующее булевой единице. Тождество (5.а) означает, что в результате опыта обязательно произойдет либо событие А, либо : A+=; (5.б) означает, что А и одновременно произойти не могут: А = . Булева алгебра событий является исходным материалом для теории вероятности. Пусть эксперимент  содержит n() исходов, cреди которых событию А благоприятствуют n(A) исходов, тогда вероятность наступления А равна р(А) = n(A) / n(). Например, если  - бросание шестигранной игральной кости (n()=6), A - выпадание четной грани (n(A)=3), то р(А) = 3/6. Интерпретация события А как подмножества {2, 4, 6} универсального множества {1,2,3,4,5,6} всех исходов , позволяет привлечь к вычислению вероятности сложных событий идеи булевой алгебры множеств. Выведем формулу вычисления р(А+В) по известным вероятностям р(А), p(B), p(AB). Имеем:

n(A+B) = n(A) + n(B)  n(AB),

так как элементы, содержащиеся одновременно в А и в В, то есть, элементы АВ, считаются дважды при суммировании элементов А с элементами В. Деля обе части равенства на n(), получим:

p(A+B) = p(A) + p(B)  p(AB).

Для трех слагаемых имеем: p[(A+B)+C] = p(A+B) + p(С)  р[(А+В)C]; закон (4.а)

дает: (A+B)C = AC + BC, отсюда

р[(А+В)C] = p(AC+BC) = p(AC) + p(BC)  p(АСВС).

C учетом равенств АСВС = АВСС = АВС (законы (2.б), (7.б)) окончательно получим:

p(A+B+C) = p(A) + p(B) + p(С)  p(AB)  p(AC)  p(BC) + p(ABC).


  1. АЛГЕБРА ВЫСКАЗЫВАНИЙ


Подобно функциям математического анализа, например f(x,y,z) = x + yz, принимающим вещественные значения для x,y,z R, введем в рассмотрение функции нескольких булевых переменных, например, f(p,q,r) = pqr, принимающие вместе с аргументами только одно из двух значений: 0, или 1.

Рассмотрим набор n переменных (x1, x2,...,xn), где xi  {0,1}, который назовем двоичным набором длины n. Число таких наборов равно 2n, поскольку при увеличении n на единицу будет происходить их удвоение (комбинирование каждого старого набора с новым нулем, или единицей). Назовем булевой функцией n переменных функцию, определенную на двоичных наборах длины n и принимающую на этих наборах значения 0, или 1. Так как область определения такой функции ограничивается 2n наборами значений аргументов, то ее можно однозначно описать Таблицей 1 из 2n строк. Правый столбец значений функции в таблице в свою очередь является двоичным набором длины 2n, следовательно, число булевых функций n аргументов равно числу всех таких наборов, т. е. . Например, существуют = 4 булевых функции  к одного аргумента (табл. 2) и = 24 = 16 булевых функций к двух переменных х,у, представленных в табл. 3, которая содержит (как частный случай) четыре функции одного переменного:

o(x)  0  o(x,y);

1(x)  x  5(x,y);

2(x)   10(x,y);

3(x)  1  15(x,y).
Каждую из 16-ти функций можно отождествить с бинарной логической операцией. Отметим среди них 11-ю и 9-ю, имеющие особое смысловое значение. Импликация xy, или логическое следование высказываний x и y, принимает ложное значение только в том случае, когда из истинной предпосылки х следует ложное заключение у; эквиваленция ху принимает истинные значения только при совпадающих значениях операндов (см. табл. 4).


Таблица 1.




Таблица 3.




x1

x2



xn-1

xn

f(x1 ,..., xn)

1 0 1 0

x

0

1

2

3



2n-1

0

0

0

0



1

0

0

0

0



1













0

0

1

1



1

0

1

0

1



1

f(0,...,0,0)

f(0,...,0,1)

f(0,...,1,0)

f(0,...,1,1)

...............

f(1,...,1,1)

1 1 0 0

y

0 0 0 0

0(x,y)  0

1 0 0 0

1(x,y) = xy

0 1 0 0

2(x,y) =

1 1 0 0

3(x,y) = y

0 0 1 0

4(x,y) =

Таблица 2.

1 0 1 0

5(x,y) = x

x

0

1

2

3




0 1 1 0

6(x,y) =

0

1

0 0 1 1

0 1 0 1

1 1 1 0

7(x,y) = x + y

0 0 0 1

8(x,y) =


Таблица 4.

1 0 0 1

9(x,y) =

0 1 0 1

10(x,y) =

x y

xy

xy




1 1 0 1

11(x,y) = xy

0 0

1

1

0 0 1 1

12(x,y) =

0 1

1

0

1 0 1 1

13(x,y) =

1 0

0

0

0 1 1 1

14(x,y) =

1 1

1

1

1 1 1 1

15(x,y)  1


C помощью таблицы истинности проверяется справедливость следующей замены: (1)

Покажем, как сложные высказывания, образованные с помощью произвольных логических операций, сводятся к формулам, включающим три основные операции – конъюнкцию, дизъюнкцию и отрицание.

Для произвольной бинарной функции f(x,y) справедливо тождество, проверяемое непосредственной подстановкой конкретных значений х и у:

.

C его помощью получается разложение:



Применим это разложение для эквиваленции:

таким образом,

Для булевой функции n переменных справедливо тождество:

Применяя это выражение многократно для всех хi (i = 1,2,..., n), получим:

(2)

В выражении (2) слагаемые, для которых f(...) = 0, можно опустить. Дизъюнкция оставшихся конъюнкций называется совершенной дизъюнктивной нормальной формой - СДНФ. Ее совершенство заключается в однородности состава всех конъюнкций, в каждую из которых входит полный набор n аргументов. Формула (1) является примером несовершенной ДНФ, так как в каждое слагаемое входит только по одному аргументу. СДНФ (2) генерируется по таблице истинности следующим образом. Суммируются конъюнкции на наборах-строчках с ненулевым значением f(...) = 1, при этом единичному значению i-го аргумента в данной строке соответствует сомножитель хi , нулевому значению - его отрицание В качестве примера приведем к СДНФ импликацию, заданную таблицей, справа от которой выписаны слагаемые на единичных наборах (табл. 5). Ее СДНФравна
.
Упрощение СДНФ приводит к более простой ДНФ:

Дальнейшие упрощения дают правую часть (1):


Таблица 5

Таблица 6

x y

xy




x1 x2 x3

f(x1, x2, x3)




0 0

1



0 0 0

0

x1 + x2 + x3

0 1

1



0 0 1

1




1 0

0




0 1 0

0



1 1

1

x y

0 1 1

0












1 0 0

1













1 0 1

1













1 1 0

0












1 1 1

1






Применение законов двойственности к СДНФ позволяет получить представление произвольной булевой функции в виде конъюнкции дизъюнкций - совершенной конъюнктивной нормальной формы (СКНФ). Теперь по таблице истинности выбираются строчки, соответствующие наборам с нулевым значением f(...)=0. Для каждой из них составляется дизъюнкция аргументов, либо их отрицаний (в случае xi = 1).

Построим СКНФ для функции, представленной таблицей 6. Cправа от строк, где f(...)=0, выписаны соответствующие дизъюнкции. СКНФ имеет вид:
.
Алгебра высказываний является эффективным аппаратом проектирования цифровых схем, состоящих из двоичных логических элементов. Рассмотрим электрические схемы из проводников и переключателей (рис. 3.1,а).

Единственные фрагменты, которыми схемы отличаются друг от друга - это их нижние части, содержащие переключатели. Следовательно, остальные части схем можно не изображать (см. релейно-контактные схемы на рис. 3.1,b).


Элементы современных микросхем (рис. 3.1,c) принято называть вентилями И (реализация конъюнкции), ИЛИ (реализация дизъюнкции), НЕ (реализация отрицания – инвертор).

Анализ вентильной схемы заключается в нахождении булевой функции f(x1,...,xn), которую она реализует, и ее таблицы истинности:




x

y

z

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

xy

xy + z



0 0 0 0 0 0 1 1

0 1 0 1 0 1 1 1

1 0 1 0 1 0 0 0


Приведем пример обратной задачи синтеза - реализации булевой функции вентильными схемами, соответствующими СДНФ (рис. 3.2,а) и СКНФ (рис. 3.2,b). Очевидно, СКНФ дает более экономичный вариант реализации функции f.

Исчисление высказываний помогает решить задачу оптимального синтеза  упрощения схемы посредством минимизации логических выражений на основе законов булевой алгебры, например:



X Y z

F






Рис. 3.2

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0

1

0

1

0

1

1

1

x+y+z












СДНФ:


СКНФ:





Упростим СДНФ предыдущей функции:

Оптимальная цифровая схема для данной функции реализуется двумя вентилями:





Логические схемы, имеющие множество выходов, описываются системой булевых функций:

Y1 = f(X1, X2,..., Xn),

Y2 = f(X1, X2,..., Xn),

-----------------------

Ym = f(X1, X2,..., Xn).

В качестве примера рассмотрим схему полусумматора, реализующего суммирование одного разряда двоичных чисел в соответствии с таблицей:





вход

выход

A B

S P

0 0

0 1

1 0

1 1

0 0

1 0

1 0

0 1



Результат суммирования S становится 1 только при комбинациях (0,1) и (1,0), то есть, Перенос P в следующий разряд имеет место только при (1,1), поэтому P = AB.
4. АЛГЕБРА ПРЕДИКАТОВ
Рассмотрим истинное высказывание « 5 - целое число » и ложное высказывание « целое число ». Общую часть их можно выделить как предложение-шаблон « - целое число », при подстановке в который конкретного числа получается конкретное высказывание. Введя обозначение :

Р(х) = « х - целое число »,

получим P(5) = 1; P( ) = 0 . Теперь пусть Р(х) = « x - овощ ». Замещая х на конкретные плоды, получаем истинное высказывание Р(ЛУК)=1, или ложное: P(СЛИВА) = 0 .

Назовем предикатом Р(х) предложение, зависящее от переменной х, принадлежащей некоторой предметной области - множеству U: xU. В первом примере хR, во втором U - это множество плодов. При подстановке фиксированного элемента аU предикат Р(х) превращается в высказывание Р(а){0,1}. Таким образом, предикат можно считать логической функцией, определенной на элементах множества U произвольной природы.

U разбивается предикатом Р(х) на два непересекающихся подмножества: на первом из них , которое назовем множеством истинности , предикат принимает истинные значения, на втором - ложные. Обозначив их через Р и Р, соответственно, получим: U = P P.

На рис. 4.1 прямоугольная область U представлена в виде объединения двух непересекающихся частей.




  1   2   3   4   5   6   7   8


Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации