Основы дискретной математики

Министерство образования и науки Украины ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ КОНСПЕКТ ЛЕКЦИЙ по дисциплине ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ для студентов заочной формы обучения специальности 6.0915 Херсонського политехнического колледжа одесса 2006 Конспект лекций по дисциплине «Основы дискретной математики» для студентов заочной формы обучения специальности 6.0915 Херсонсного порлитехнического колледжа / Сост. А.Н. Мартынюк. – Одесса: ОНПУ, 2006. – 76 с. Составитель: А.Н. Мартынюк, ст. преподаватель 1. ТЕОРИЯ МНОЖЕСТВ 1.1. Основы теории множеств 1.1.1. Основные понятия и задание множеств Определение: Под множеством понимается объединение определенных, отличных друг от друга объектов (реальных или воображаемых), называемых элементами множества в их сущности. Пример: А={ 1,2,а,с} - корректно, В={ а,b,c,b} - некорректно. Общее обозначение множеств - фигурные скобки {...}, внутри которых задаются элементы множеств. Конкретные множества обозначаются прописными буквами А, В4,Сі, ..., элементы множеств обозначаются строчными латинскими буквами a, b4, cі ... . Запись mM означает высказывание «m является элементом множества М» или «m принадлежит множеству М». Запись mM - означает отрицание высказывания mM. Запись М1М2 означает высказывание «каждый элемент множества М1 является элементом множества М2», или «M1 является подмножеством множества М2, а М2 - надмножеством множества М1», или «M1 включается в М2». Запись М1М2 - отрицание высказывания М1М2. Запись М1=М2 означает высказывание «M1M2 и М2М1» или «множества М1 и М2 равны (эквивалентны)». Запись М1М2 - отрицание высказывания М1М2. Запись М1М2 эквивалентна высказыванию «M1M2 и М1М2» или «M1 является собственным подмножеством множества М2». Несобственные множества в этом случае - само множество М2 и множество  - единственное множество, не содержащее элементов - пустое М. Можно считать, что все рассматриваемые множества являются подмножествами универсума U (для целых чисел - бесконечность). Определение: Множество, элементами которого являются все подмножества множества М, называются множеством подмножеств, или множеством - степенью, или булеаном множества М и обозначается как Р(М) или В(М). Пример: М={1,2,3}, P(M)={, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. Запись М означает число элементов множества М, Р(М)= 2М. Задание множеств осуществляется тремя основными способами: 1. Перечисление всех элементов, входящих в множество. Пример: А={а1, а2, а3 }, В={1, 2, b, c}, C={aі}1 3 2. Заданием характеристического свойства, выделяющего элементы данного множества среди элементов указанных других. Пример: N={n|n и n}, М={mM|m=n2 и n} 3. Описанием порождающей процедуры с указанием множеств, которые пробегают параметры этой процедуры. Пример: М={n2|n C ={8х1+14х2+32х3|х1, х2, х3. Из определения равенства множеств и способов задания их следует, что порядок элементов в множествах несущественен. Для интерпретации множеств и операций над ними используются геометрические фигуры - круги Эйлера и диаграммы Венна (см. рис. 1.1.). Рис. 1.1. Круги Эйлера 1.1.2. Операции над множествами. Формулы. Тождества Новые множества могут порождаться в результате применения некоторых операций к уже существующим множествам. Объединением множеств М1 и М2 называется множество М12={m|m1 или m2}. Пересечением множеств М1 и М2 называется множество М12={m|m1 и m2}. Множества М1 и М2 называются дизъюнктными, если М1 2=. Разностью множеств М1 и М2 называется множество М1\М2={m|m1 и m2}. Симметрической разностью множеств М1 и М2 называется множество М1–М2= {m|m1\M2 или mМ2\М1}. Если М12, то разность М2\М1 называется дополнением множества М1 во множестве М2. В частности, М = U\M - дополнение множества М в универсуме или просто дополнение множества М. Другое обозначение дополнения множества - М. Пример:   С    \С  \ \ . Теорема: Любые два множества А и В могут находиться в одном из пяти положений: 1)А=В; 2)АВ; 3)АВ; 4)АВ=; 5)А\В и В\А и АВ Задание множеств с помощью идентификаторов множеств, операций и скобок, т.е. с помощью формул, называется аналитическим. Для операций над множествами справедливы законы (тождества): 1.   ; коммутативность 2. СС; СC; ассоциативность 3. CC CC дистрибутивность 4.  UU  U U U= свойства границ 5. =U = дополнение 6.   идемпотентность 7.   поглощение 8.   (AC)(BC)=(AC)(BC)(AB); (AC)(BC)=(AC)(BC)(AB) Блейка-Порецкого 9. ; (=B склеивание 10.  () де-Моргана 11. Если АU и  то  12.   инволютивность 13. \ 14.  коммутативность 15. CC ассоциативность 16.  UUА= свойства границ 17.  если и только если А или  или  18.  если и только если . 1.1.3. Доказательства тождеств. Булева алгебра множеств Для доказательства тождеств используется универсальный метод доказательств, в основу которого положено определение равенства (эквивалентности) двух множеств. Каждое из доказательств состоит из последовательности утверждений вида “если Р, то Q”, записывается как “PQ” и читаемых как “из  следует Q” Т.о., если существует последовательность утверждений Р,Р1, Р2, Р3, ..., Рn, Q такая, что из Р следует Р1, из Р1 следует Р2,… из Рn следует Q, то существует доказательство, что “из Р следует Q” т.е. Q. Пример: С=(С) D  а) Докажем, что D Если d D, то d и dC), или следовательно, (d и d) или (d и dC). Это значит, что d или dC), т.е. d( или С)), что записывается как dC Т.о., D б) Докажем, что D. Если е то е( или С), следовательно (е и е) или (е и еС). Это значит, что е и еС т.е. еСD. Т.о., ЕD. Следовательно, D=Е. Для доказательства тождеств могут быть использованы доказанные ранее тождества. Пример:   ;   U  U  U  . Для каждого множества М, булеан В(М) замкнут относительно операций ,\,-,, т.е. для всяких М1, М2 множества, получаемые в результате выполнения операций М12, 12, 1\2, 2\1, 1-2 ,1,2 являются элементами булеана В(М). Булеан В(М) вместе с (булевыми) операциями на нем образуют так называемую (булеву) алгебру множеств. Каждое подмножество M’ булеана В(М), замкнутое относительно (булевых) операций, содержит как множества, являющиеся подмножествами каждого множества из M’, так и множества, содержащие в качестве подмножеств каждое множество из M’. M’ с (булевыми) операциями также оказывается (булевой) алгеброй. 1.1.4. Обобщение операций. Двойственность Благодаря свойству ассоциативности объединения, пересечения и симметрической разности произвольных семейств множеств могут быть записаны без приоритетных скобок. 1. М12Мn{Mі| і  n}={m| существует і, где 1іn, такое, что mі. 2. М12n=і| і  nm| для каждого і., где іn, выполнено mі. 3. М12nі| і  n m| существует и единственно і, где 1іn, такое, что mі. Эти определения обобщаются на случай, когда множества Мі заданы как элементы некоторого семейства множеств М и требуется выполнение некоторого дополнительного условия В: і|і и Мі удовлетворяет условию В, Пример: і|і и і0 множество всех отрицательных целых чисел. Вместо і|і используется запись і . Аналогично - для  и  Первые восемь тождеств представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов “” на “” и “” на “”, а также  на U и U на  Соответствующие пары символов   и  U называются двойственными (дуальными). Принцип двойственности: При замене в любой теореме (тождестве, формуле) входящих в нее символов дуальными получим новое предложение, которое также является теоремой (тождеством, формулой). Тождества 9, 11 не изменяются при замене символов дуальными и называются самодвойственными. Принцип двойственности распространяется на “\”  а также на выражения, включающие знаки “” и ”” которые при переходе к дуальным выражениям заменяются на знаки соответственно “” и “” Различные выражения алгебры множеств можно упрощать или преобразовывать к удобному виду с помощью тождественных преобразований, т.е. последовательности применений соответствующих свойств (тождеств) операций над множествами. 1.1.5. Уравнения Алгебра множеств наряду с тождествами рассматривает и уравнения, содержащие как фиксированные подмножества универсума, так и подлежащие определению подмножества универсума. Требуется определить, при каких условиях уравнение имеет решение и какое именно. Решение уравнений с одним определяемым подмножеством основывается на следующих тождественных преобразованиях: 1. В соответствии с тождеством 18 равенство преобразуется в дизъюнктивную сумму (симметрическую разность) его левой и правой частей, которая приравнивается . 2. Полученное уравнение преобразуется к виду  где М и  некоторые множества, не содержащие Х. 3. Так как объединение множеств пусто, если каждое из объединяемых множеств пустое, преобразованное в п.2 уравнение можно заменить системой двух уравнений М и = 4. Согласно тождеству 17 пара уравнений п.3 имеет смысл тогда и только тогда, когда  и . Значит условие существования решения - , а решение уравнения - любое множество Х такое, что . Пример: С=D: 1. (СD. 2. СD)CD)=...=(DCD))=. 3. D и (СD)=. 4. Условие (СD)D или СD; решение (СD) D. 1.1.6. Покрытия и разбиения Определение: Покрытием непустого множества М называется множество Р его собственных подмножеств, объединение которых равно М: Р=і| і    і, і   і   Определение: Разбиением непустого множества М называется множество R его собственных попарно не пересекающихся подмножеств, объединение которых равно М: R={Mі|і    і  і  і   Подмножества множества М, входящие в покрытия Р (разбиение R), т.е. М1, М2, М3,..., М, называются классами или блоками покрытия Р (разбиения R) и обозначаются дополнительными фигурными скобками: Р={{a, c}, {b, d, e}}, иногда – надчеркиванием без фигурных скобок. Разбиение множества называется поэлементным, если каждый его класс - одноэлементное множество, разбиение называется целым, если состоит из единственного класса, равного исходному множеству. Поэлементное и целое разбиения множеств называются тривиальными, остальные, если существуют, нетривиальными. Пример: М={a, b, c, d, e, f} P={{a, b, c,}, {b, d, e, f}, {e, f, a}} R1={{a, b}}, {c}, {d, e, f}} R2={{a}, {b}, {c}, {d}, {e}, {f}} R4={a, b, c, d, e, f} 1.1.7. Мощность множеств. Счетные и континуальные множества. Кардинальное число Множества бывают конечными и бесконечными. Изученные операции и свойства справедливы как для конечных, так и бесконечных множеств. Сравнение множеств связано с установлением взаимно-однозначного соответствия. Элементы множеств М1 и М2 находятся во взаимно-однозначном соответствии, если каждому элементу множества М1 по некоторому закону сопоставлен единственный элемент множества М2 и наоборот. Эти множества называются равномощными (эквивалентными). Пример: Множество N равномощно множеству N2. Множества, равномощные множеству натуральных чисел N, называются счетными. Всякое бесконечное подмножество счетного множества также счетное. Множества целых, рациональных чисел, слов конечной длины в конечном в конечном алфавите счетные. Теорема: Объединение конечной или счетной совокупности счетных множеств также является счетным множеством. Среди бесконечных множеств существуют такие, элементы которых не пересчитываются. Теорема Кантора: Множество всех действительных чисел интервала (0,1) числовой оси несчетно. Всякое множество, эквивалентное множеству всех действительных чисел интервала (0,1), называется континуальным или множеством мощности континуума. Множества иррациональных, трансцендентных чисел несчетны. Теорема: Множество В(М) всех подмножеств некоторого счетного множества М является множеством мощности континуума. Пусть F(А) - множество всех слов в конечном алфавите А. Любое подмножество LF(A) называется языком над алфавитом. Множество всех языков над конечным алфавитом является множеством мощности континуума. Кардинальное число  множества М - это некоторый объект, определяющий мощность множества М (из рассматриваемой совокупности множеств). В случае конечного множества М кардинальным числом М= любого из множеств рассматриваемой совокупности является натуральное число, определяющее число элементов в нем и называемое мощностью множества. Для бесконечных множеств кардинальные числа называют трансфинитными. Для кардинальных чисел конечных множеств возможны три соотношения: 1. 12. 2. М12. 3. М12. При сравнении бесконечных множеств логически возможны четыре случая: 1. Множества М1 и М2 равномощны, т.е. М1=М2 2. Множества М1 и М2 не равномощны, но одно из них, например М1, равномощно подмножеству другого - М1=М2’ и М2’2. В этом случае мощность множества М1 меньше мощности множества М, т.о. М12. 3. Множество М1 эквивалентно (равномощно) некоторому подмножеству множества М2 и, наоборот, множество М2 эквивалентно (равномощно) некоторому подмножеству множества М1. Этот случай сводится к первому. Теорема Кантора-Бернштейна: Если множество М1 эквивалентно (равномощно) некоторому подмножеству множества М2 и одновременно множество М2 эквивалентно (равномощно) некоторому подмножеству множества М1, то множества М1 и М2 эквивалентны (равномощны). 4. Множество М1 не эквивалентно (не равномощно) никакому подмножеству множества М2 и множество М2 не эквивалентно (не равномощно) никакому подмножеству множества М1, т.е. М1 и М2 - несравнимы. Этот случай невозможен и множество всех кардинальных чисел вполне упорядочено. Следствие: Если справедливо включение М12, причем М и М2 – эквивалентны (равномощны), то М и М1 эквивалентны (равномощны). Следствие: Если М12, то М1М2. Следствие: Если М - произвольное конечное множество, то М0, где 0- кардинальное число множества натуральных чисел N (любого счетного множества), называемое алеф-нуль. Теорема: Во всяком бесконечном множестве М можно выделить некоторое счетное подмножество. Теорема: Мощность множества В(М) всех подмножеств любого непустого множества М больше мощности данного множества, т.е. В(М)М. Следствие: Не существует множеств наибольшей мощности, множество всех кардинальных чисел не имеет максимального элемента. 1.2. Упорядоченные множества и графики 1.2.1. Упорядоченные множества Всякое множество можно упорядочить, если каждому элементу его поставить в соответствие некоторое натуральное число от 1 до n, где n- мощность множества. Такое число будет являться номером элемента. Определение: Упорядоченным множеством или кортежем называется последовательность элементов множества, в которой каждый элемент занимает определенное место, элементы кортежа называются его компонентами, число компонентов кортежа - n - его длина Пример: А=1, 2, 3; В=2, 1, 2; С=(a, d, d) Общее обозначение кортежа - пара угловых или круглых скобок <...> или (...), внутри которых задаются в упорядоченном виде компоненты кортежа. Конкретные кортежи, как и множества, обозначаются прописными латинскими буквами А0, В4, Сj, ..., компоненты кортежей обозначаются строчными латинскими буквами a, b4, cj, ... . Кортежи считаются равными, если у них совпадают компоненты и порядок их следования - А=В, иначе кортежи не равны - АВ. Компонентами кортежа могут быть элементы множеств, множества, другие кортежи. Еще одно название кортежей - вектора или n-ки (двойки, тройки, ..., пятерки,…). Определение: Прямым или декартовым произведением множеств А и В называется множество АхВ, состоящее из всех упорядоченных пар, первая компонента которых принадлежит множеству А, а вторая компонента принадлежит множеству В. АхВ={AхВ|аА и bB Пример: А=а, b =1, 2 хВ=а, 1, а,2, b, 1,b. Очевидно, что если n, а m, то хВnm. Определение: Прямым декартовым произведением множеств А1, А2, ..., Аn называется множество А1хА2х...хАn, из всех n-ок, первая компонента которых принадлежит множеству А1, вторая компонента принадлежит множеству А2, ..., n-ая компонента принадлежит множеству Аn: ХАі=А1хА2х ... хАn=а1, а2, ... , аnA1хА2хАх...хАn| a1A1, a2, ... , ann Определение: Прямое декартово произведение множеств А1хА2х ... хАn при равных множествах А1=А2= ... =Аn=A называется прямой n-й декартовой степенью множества А и обозначается Аn: Аn=AхАх ... хА = {An|a1, a2,..., anA} При n=0 и n=1 по определению считается А0={ и А1=А. Важным подмножеством декартова произведения АхА является множество А=а, а|аА, называемое диагональю, обозначаемое также как EA. К кортежам или множеству кортежей одинаковой длины применяется унарная операция проецирования. Определение: Проекцией кортежа А на і-ю ось называется і-я компонента кортежа А, обозначаемая как пріА. Проецирование обычно ведется на совокупность упорядоченных по возрастанию осей. Пример: А=1, 2, 3, 3, 4 пр2А=2 пр4А=3 пр1,4А=1, 3. Определение: Проекцией множества М кортежей длины n называется множество проекций всех кртежей из М Пример: М=1, 2, 2, 3, а, b, c, d, a, 2, 4, c, пр1М=1, а пр13М=1, 2, а, с, а, 4 Прямые декартовы произведение и степень обладают рядом свойств: 1. АхВВхА 2. Ах(ВхС)(АхВ)хСАхВхС 3. (АВ)хС=(АхС)(ВхС) 4. (АВ)хС=(АхС)(ВхС) 5. (А\В)хС=(АхС)\(ВхС) 6. АхАх ... хА=Аn. 7. AlхАmАlm. 8. AlхАmАmхАl. 9. Aх=хА=. 1.2.2. Графики Определение: Множество Р называется графиком, если каждый его элемент есть двойка элементов некоторого множества М. Р=р|р=а, b> и а, bМ Пример: Р=а, b, 1, c, 2, 3 Если М - произвольное множество, то М2 - график, любое подмножество множества М2 также является графиком. Определение: Множество проекций графика Р на первую ось называется областью определения графика Р, множество проекций графика Р на вторую ось называется областью значений графика. Если отложить по первой оси - оси Х область определения, а по второй оси - оси У область значений, то сам график разместится некоторым образом на плоскости (см. рис. 1.2.). Если график Р=, то очевидно пр1Р= и пр2Р=. Рис. 1.2. График и его проекции на плоскости Так как график по определению есть множество, то над графиками могут выполняться все операции, что и с обычными множествами, т.е. операции   \,  . Определение: Двойка с, d называется инверсией двойки a, b, если компонента с равна компоненте а, и компонента d равна компоненте b. Инверсия пары р=а, b обозначается как р-1. Двойная инверсия двойки (р-1)-1 равна самой двойке (р-1)-1=р. Определение: Инверсией графика Р, обозначаемой как Р-1, называется множество инверсий всех пар из Р Р-1=qР-1|q=p-1 и р Пример: Р=, а, b, P-1=2, 1, b, a При инверсии графика Р пр1-1=пр2Р и пр2-1=пр1Р. Определение: График Р называется симметричным, если он наряду с каждой парой содержит ее инверсию р  р-1Р Пример: р=a, b, b, a, c, c Для любого множества М множество М2 - симметричный график, для любого графика Р Р-1 и -1 - симметричные графики (кроме случая -1 = ). Определение: График R=PQ называется композицией графиков Р и Q, если двойка х, у принадлежит R тогда и только тогда, когда существует такой элемент z, что двойка х, z принадлежит Р и двойка z, у принадлежит Q: R=PQ=х, уR|существует z такой, что х, z и z, уQ Пример: Р=а, a, a, c, a, b, b, b, c, b Q=a, b, a, c, c, с R=P Q=a, b, a, c Очевидно, что композиция двух графиков Р и Q пуста тогда и только тогда, когда пр2P1пр1P2 = . Определение: Декартовым произведением Р1 и Р2 называется график Р1Р2=a1, a2, b1, b2|aі, bіі , і=1,2 Определение: График Р называется функциональным, если в нем нет пар с одинаковыми первыми и различными вторыми компонентами, инъективным, если в нем нет пар с одинаковыми вторыми и различными первыми компонентами. Пример: 1=a, b, a, с не функционален 2=a, c, b, c не инъективен Очевидно, что график М2 на произвольном множестве М не является функциональным и инъективным, композиция функциональных графиков функциональна, композиция инъективных графиков инъективна, инверсия переводит функциональный график в инъективный, а инъективный - в функциональный. Операции над графиками обладают рядом специальных свойств: 1. Р12 не коммутативность 2. ( ассоциативность 3.  свойства границ 4. (Р-1-1-1 1.3. Соответствия, образы и прообразы Пусть существуют два множества А и В, элементы которых могут сопоставляться друг другу, образуя пары вида a, b>. Если способ такого сопоставления определен, т.е. для (каждого) а указан b, с которым а сопоставляется, то говорят, что между А и В установлено соответствие. При этом не обязательно, чтобы в сопоставлении участвовали все элементы множеств А и В. Определение: Соответствие - это тройка множеств А, В, G, обозначаемая =G, где третья компонента есть подмножество прямого произведения первой и второй компоненты, т.е. GВ. При этом множество А называется областью отправления соответствия, множество В - областью прибытия соответствия, множество G - графиком соответствия. Пример: =a, b, c, 1, 2, 3, , ,  Определение: Два соответствия считаются равными тогда и только тогда, когда равны их графики, области отправления и прибытия. 1.3.1. Операции и свойства соответствий Соответствия не являются множествами, в связи с чем операции над ними отличны от простых множественных операций. Определение: Объединением соответствий 1 и , где 1=, В1, G1, 2=A B, G2, называется соответствие: 12, В12, G1G2. Определение: Пересечением соответствий 1 и 2, где =1, 1, G1, 2=A2, B2, G2, называется соответствие: 12=12, 12, G1G2. Определение: Разностью соответствий 1 и 2, где 1=А1, В1, G1, 2=2, B2, G2, называется соответствие: 1\2= 12, В12, G1\G2. Определение: Дополнением соответствия =(А, В, G) называется соответствие: =(А, В, АхВ\G). Пример: 1= (a, b, c, d, 1, 2, 3, 4, a, 1>, , }) 2=({b, c, d, e}, {2, 3, 4, 5, 6}, {, , , } 12=({a, b, c, d, e}, 1, 2, 3, 4, 5, 6}, {, , , , }) 12=({b, c, d}, {2, 3, 4}, {, }) 1\2=({b, c, d}, {2, 3, 4}, {}) 2\1=({b, c, d}, {2, 3, 4}, {, }) 12=({b, c, d}, {2, 3, 4}, {, , }) 1=({a, b, c, d}, {1, 2, 3, 4}, {, , , , , b, 4>, , , , , , , }) Определение: Инверсией соответствия =(А, В, G) или обратным соответствием, обозначаемым как --1, называется соответствие, у которого, во-первых, область отправления равна области прибытия В исходного соответствия , во-вторых, область прибытия равна области отправления исходного соответствия , в-третьих, график равен инверсии графика G исходного соответствия , т.е. --1=(В, А, G-1). Очевидно, что инверсия соответствия  равна самому соответствию , т.е.(-1)-1=. Из равенства соответствия своей инверсии, т.е. из -1, следует, что график G - симметричен, а множества А и В равны - А=В. Из =(А, В, ) следует -1=(В, А, ). Определение: Декартовым произведением соответствий 1 и 2 называется соответствие: 12=(А1А2, В1В2, G1G2) Пример: 12=({, , , , , ,...,, , , }, {<1, 2>, <1, 3>, <1, 4>, <1, 5>, <1, 6>, <2, 2>, <2, 3>,...,<4, 2>, <4, 3>, <4, 4>, <4, 5>, <4, 6>}, {<, <1, 2>>, <, <1, 3>>, <, <1, 4>>, , <1, 6>>,...,<, <4, 4>>, <, <4, 6>>}) Определение: Композицией соответствий 1 и 2, обозначаемой 1 2, называется соответствие, у которого, во-первых, область отправления равна области отправления соответствия 1; во-вторых, область прибытия равна области прибытия соответствия 2; в-третьих, график соответствия равен композиции графиков соответствий 1 и 2, т.е. 1 2=(А1, В2, G1 G2). Пример: 1=({a,b,c,d,},{0,1,2,3,4,},{(a,1),(b,0),(c,1),(d,2),(d,3)}), 1=({1,2,3,4,5},{I,II,III},{(1,I).(1,II),(2,II),(3,III),(4,III), (5,III)}), 22=({a,b,c,d},{I,II,III},{(a,I),(a,II),(c,I),(c,II),(d,II),(d,III)}) Определение: Сужением или ограничением соответствия =(А, В, G) на множество А, обозначаемым ’, называется соответствие ’ = (А, В, G(АхВ)). Пример: =({a,b,c},{1,2,3}{(a,1),(a,2),(c,3)}), А=a, b}, ’=({a,b},{1,2,3},{(a,1),(a,2)}) В этом случае соответствие  называется расширением или продолжением соответствия ’. Включение 12 выполняется по определению тогда и только тогда, когда А1А2, В, G1G2. Определение: Соответствие  называется: а) функциональным или функцией, если его график G функционален; б) инъективным или инъекцией, если его график G инъективен; в) всюду определенным, если его область определения совпадает с областью отправления, т.е. пр1G=А; г) сюръективным или сюръекцией , если его область значений совпадает с областью прибытия, т.е. пр2G=В; д) биективным или биекцией, если оно функционально, инъективно, всюду определено и сюръективно (другое название биекции - взаимно-однозначное соответствие). Справедливы следующие утверждения и свойства: 1. 1 2  2 1 не коммутативность 2. 1(2 31 2   ассоциативность 3. 1 2   4.  - функция  --1 – инъекция 5.  - сюръекция  --1 - всюду определено 6.  - биекция   -1 - биекция 1.3.2. Образы и прообразы множеств Определение: Образом множества А при соответствии  или сечением соответствия  по множеству А, обозначаемым (А), называется множество всех тех и только тех вторых компонент двоек графика G, для которых первые компоненты принадлежат множеству А: (А)= b|a, b>G и а. Пример 3=({a,b,c},{1,2,3,4}{(a,1),(a,3),(b,1),(b,4),(c,2)}), А=a, c, d} и A, 32, 3} Определение: Множество сечений соответствия  по каждому из элементов области отправления называется фактор-множеством соответствия  и обозначается F . Пример: 1F={{1}, {2}, {4}, } для 1 3F={{1, 3}, {1, 2, 4}, {2}} для 3. Определение: Полным прообразом или прообразом множества В при соответствии , обозначаемым --1(В ), называется множество всех тех и только тех первых компонент пар графика G, для которых вторые компоненты принадлежат множеству В: --1(В )={a--1(B )|G и b Пример: =({a,b,c},{1,2,3}{(a,1),(b,2),(b,3),(c,2)}), , 3, 4 и В, -1(В )=a, b} Образы и прообразы обладают рядом свойств: 1. (А)пр2G --1(B)пр1G 2. A --1(B1 3. пр1G) --1(B--1(Bпр2G) 4. (A)=Aпр1G= --1(B)=пр2G 5. пр1G)=пр2G --1(пр2G)=пр1G 6.  --1 1.3.3. Отображения и диаграммы Определение: Соответствие =(А, В, G) называется отображением из множества А во множество В или просто отображением, если оно всюду определено и функционально, частичным отображением из множества А во множество В, если оно функционально. Отображение  конечного множества М={m1, m2, ..., mn} в себя часто представляют 2-х n-матрицей: m1, m2, ... mn m1) (m2) … (mn) Композиция отображений такого вида может быть определена по этим матрицам. Если множество М - конечно, то инъекция (сюръекция) М в себя является также биекцией и называется подстановкой множества М. Пусть  - соответствие, на основе определения множества  для  соответствию  может быть сопоставлено отображение из Р(А) в Р(В). Аналогично, отображение из Р(В) в Р(А) может быть сопоставлено соответствию -1. Пусть =(А, В, G) - отображение, и пусть А, АА и В, В. Тогда выполняются соотношения: 1.  2.  (равенство - при инъекции для сужения ) 3. --1--1--1 4. --1)--1--1 Кроме того, эквиваленты следующие три высказывания: 1.   инъективно (сюръективно) 2.  Р(А)Р(В) сюръективно (инъюктивно) 3. --1: Р(В)Р(А) сюръективно (инъюктивно). Определение: Если М является подмножеством множества М т.е. ММ, то характеристической функцией М в М называется отображение GM: GM: М = Gm)=1, если m Gm)=0 в противном случае Определение: Пусть М=М1 ... n - декартово произведение, тогда для каждого і из множества {1, ... , n}, как отмечалось ранее, определены отображения ргі,ргі, называемые проекциями: prі: Мі, prі(m1, ... , mі, ... , mn)=mі  prі: М1 ... і-1і+1 ... n  prі(m1... , mі-1, mі, mі+1, ... , mn)=(m1, m2, ... , mі-1, mі+1, ... , mn). Если 1 k n и 1 і1і2....іn, то проекция prі, і2, ..., іk Мі1і2 ... і определены равенством prі1, і2, ..., іk(m1, m2, ..., mn)=(mі1, mі2, ..., mіk). Для облегчения работы с отображениями применяются диаграммы. Пусть даны отображения і=(Аі, Аі+2 Gі) при і=1, 2 и j=(Aj, Aj+1, Gj) при j=1, 3, им соответствует прямоугольная диаграмма (см. рис. 1.3.): Рис. 1.3. Прямоугольная диаграмма для отображений і=(Аі, Аі+2 Gі) при і=1, 2 и j=(Aj, Aj+1, Gj) при j=1, 3 Эта диаграмма называется коммутативной тогда и только тогда, когда 3а)=а) для всех а1. Аналогично можно представить коммутативность треугольных и прямых диаграмм. 1.4. Отношения. Функции 1.4.1. Основные определения и задание Определение: Под n-арным отношением или n-отношением n на множествах А1, А2, ..., Аn понимается закон (характеристическое свойство), выделяющий в декартовом произведении А12...n некоторое подмножество n1,...,An12...n, называемое графиком (n-мерным) отношения n. Если А1=А2=...=Аn=A, то говорят об n-отношении n на множестве А с графиком nn. Отношения, как и соответствия, часто обозначают греческими буквами, с индексами или без них, и специальными символами =, и др. Часто понятие n-отношения отождествляется с его графиком, т.е. под n-отношением n на множествах А1, А2, ..., Аn понимается само подмножество: nnA2n. Если а1, а2,..., аn)nA1,.., An, где аjj, j=1, 2,..., n, то говорят, что элементы а1, а2,..., аn находятся в отношении n n(a1, a2, ..., an), так что обозначения (а1, a2, ..., an) n и n(a1, a2, ... , an) равносильны. Определение: Последовательность =(а1, a2, ... , an)n1,...,An называется элементом или вектором n-отношения n. Отношения, графики которых состоят из конечного множества векторов, называют конечными n-отношениями. Если nA1,...,An=, то n- пустое n-отношение (n), если nA1, ..., An=A12n, то n- универсальное n-отношение (n). Так как n-отношение n можно рассматривать как подмножества декартова произведения А12Аn, существуют различные способы задания n-отношений, аналогичные способам задания множеств. Так график nA1, ...,An удобно задавать матрицей, строками которой являются векторы отношения n. Пример: nA1, ..., An={ j=(a1 j, a2 j, ... , an j|j=1, 2, ... , r} - множество всех векторов, график в матричной форме: nA1, ..., An= a1 j1 a2 j1 ... an j1 a1 ji2 a2 j2 ... an j2 ................................... a1 jr a2 jr ... an jr Отношения 1 на множестве А называют унарными, отношения 2 на множествах А, В - бинарными, отношения 3 на множествах А, В, С - тернарными и т.д. Унарное отношение 1 на множестве А является характеристическим свойством некоторого подмножества 1А - графика данного отношения, т.о., множество всех унарных отношений на А совпадает с множеством всех подмножеств множества А. Если А=n, то число унарных отношений на А равно 2n. Лемма: Любому n-отношению  n на множествах А1, А2, ..., Аn соответствует унарное отношение 1 на множестве А12n такое, что выполняется 1() тогда и только тогда, когда для отношения выполняется n(a1 i, a2 i..., an i), где =(a1 i, a2 i, ..., an i) - произвольный вектор отношения  n. Бинарное отношение  на множествах А и В определяется графиком . Если элементы а и b находятся в отношении , то наряду с обозначениями (а, b) и (a, b) используется и аb. Пример: а)А=2, 3, 5 = 2 2 В=2, 3, 4, 5, 6 2 4 3 3 3 6 5 5 б) Таблица 1.1.  2 3 4 5 6 2 Х х х 3 х х 4 х в) Рис. 1.4. Бинарное отношение  График тернарного отношения 3 имеет вид 3СС. С бинарной операцией F(х, у), в частности с арифметическими операциями “” ””””””, может быть связано тернарное отношение 3 такое, что 3(х, у, z) тогда и только тогда, когда F(х, у)=z. Наиболее часто употребляются бинарные отношения (графики на плоскости). Если для бинарного отношения 2А1,А2А12 множества А1 и А2 равны А, то говорят, что определено отношение на множестве А, т.е. 2А. Определение: Отношение на множестве А называется а) полным, если 2А=А2; б) пустым и обозначается ОА, если 2А=; в) отношением равенства и обозначается ЕА, если и только если 2А содержит только все возможные пары с одинаковыми компонентами; г) отношением неравенства, если 2А не содержит ни одной пары с одинаковыми компонентами. 1.4.2. Операции над отношениями Изучение n-отношений на множествах А1, А2, ..., Аn возможно связать с изучением их графиков, т.е. подмножеств А1n. На множество n-отношений распространяются множественные операции “””””\””””” и множественные отношения включения “”, т.е. из nA1, A2, ..., An nA1, A2, ..., An- включения графиков следует включение отношений nn. Определение: Объединение отношений  n и  n - это отношение  n= n   n c графиком  nA1, A2, ..., An= nA1, A2, ..., An   nA1, A2, ..., An. Определение: Пересечение отношений  n и  n - это отношение  n= n   n с графиком  nA1, A2, ..., An   nA1, A2, ..., An. Определение: Разность отношений  n и  n - то отношение  n= n \  n с графиком  nA1, A2, ..., An= nA1, A2, ..., An \  nA1, A2, ..., An. Определение: Симметрическая разность отношений  n и  n - это отношение  n= n   n с графиком  nA1, A2, ..., An= nA1, A2, ..., An   nA1, A2 ..., An. Определение: Отношение n называется дополнением отношения  n, если    nA1, A2, ..., An тогда и только тогда, когда   nA1, A2, ..., An Пример: Для бинарных отношений   справедливо N =   = = =     =. Пусть n - отношение на множествах А1, А2, ..., Аn, а m - отношение на множествах Аn+1, ..., An+m. Определение: Декартово произведение отношений  n и  m - это отношение  nm= n m, график которого имеет вид  n+mA1, A2, ..., An+m= nA1, A2, ..., An   mAn+1, ..., An+m. Следует иметь в виду, что в этом случае допускается ассоциативность декартова произведения, т.е. справедливость равенства Ax(BxC) = (AxB)xC = AxBxC. Пример: Пусть А1={0, 1, 2}, A2={a, b}, A3={b, c, d} и  3,  3 – отношения:  2A1, A2= 0 a  3A1, A2, A3= 0 a b 1 b 1 b c 1 b d Тогда отношение  5= 2 3 определяется графиком: 5A1, A2, A3 A4, A5= 0 a  0 a b = 0 a 0 a b 1 b 1 b c 0 a 1 d c 1 b d 0 a 1 b d 1 b 0 a b 1 b 1 b c 1 b 1 b d Кроме теоретико-множественных операций в теории n-отношений используются специальные операции перестановки и отождествления координат (столбцов), приписывания фиктивной координаты, а также свертки де-Моргана. Пусть n - отношение на множествах А1, А2, ... , Аn, k=(1, 2, ..., n) - набор координат (номеров) столбцов в матрице графика nA1, ... , An , k=(i1, i2, ... , in) - набор, полученный из k в результате некоторой перестановки элементов. Определение: Операция k’(n) перестановки координат порождает n-отношение n на множествах Аi1, Ai2, ..., Ain, график которого nAi, ... , Ain получается из графика nA1,...,An, перестановкой его столбцов в соответствии с набором k. Определение: Пусть k0=(2, 3, ..., n, 1). Перестановка k(n) называется циклом и обозначается (n). Определение: Пусть k=(2, 1, 3, ... , n). Перестановка k1(n) называется транспозицией и обозначается (n). С помощью цикла n транспозиции можно выразить любую перестановку (n). Пустьk=(n, n-1, ..., 2, 1). Определение: Отношение (n)-1=k(n) над множествами An, An-1,..., A2, A1, полученное из отношения n в результате перестановки, соответствующей наборуk называется обратным. Очевидно, =(an, an-1, ..., a2, a1)n)-1An, ..., A1, тогда и только тогда, когда -1=(a1, a2,,..., an)nA1, An Пример: Для бинарных отношений  справедливо ---1=, --1=, --1=,--1= (Операция перестановки). Операция перестановки для бинарных отношений называется инверсией. Для обращения n-отношений выполняются равенства (при nn) 1. ((n)-1)-1=n 2. (n)-1n)-1 3. (in)-1=(in)-1 4. (in)-1=(in)-1 5. (n)-1=((n)-1) Из равенств следует, что для Ф-11n, 2n, ..., n)=((1n)-1, (2n)-1, ..., (kn)-1), где Ф - выражение, построенное из отношений 1n, ..., n с помощью операций , , . Кроме того, справедливо равенство: 6. (nm)1 = (m)1(n)1 Пусть n - отношение на множествах А1, ..., Аn и j1, j2, ..., jl - некоторое подмножество множества номеров 1, 2, ..., n}. Определение: Операция отождествления координат n) порождает отношение  n-l+l= j1,j2 . , jl(n) на множествах A1,..., Aj2-1, Aj2+1, ..., Aj3-1, Aj3+1, ..., Ajl-1, Ajl+1, ..., An, график которого получается из графика nA1,...An в результате выделения множества векторов =аi(1), ai(2), ..., ai(n))|ai(j1)=ai(j2)=...=ai(jl)}nA1,..., An с последующим вычеркиванием в каждом векторе  элементов ai(j2), ai(j3), ..., ai(jl). Т.е., в отношении n выделяются все векторы, в которых совпадают компоненты, расположенные в столбцах с координатами j1, ..., j, с последующим исключением столбцов-копий, имеющих координаты j2, j3, ..., j. Пример: Для отношения 5А1,А2,А3,А4,А5 из предыдущего примера 24 , где  4 равно:  4А1,А2,А1,А3= 0, a, 0, b 1, b, 1, c 1, b, 1, d Для отношения  4 13 4)=3, где 3 равно 3А1,А2,А3 = 0, a, b 1, b, c 1, b, d Если l=2, j1=1, j2=2, то отождествление 12(n) обозначается n). C помощью (n) и перестановки координат можно произвести любое отождествление координат. Определение: Отношение n на множестве А называется диагональю, если для любого а выполняется (a, ..., a)nA. Пример: Бинарное отношение равенства на множестве  - диагональ. Если 1,2,…nn) - отношение на множестве А, то 1,2,…n(n)n. Кроме того, для любого отношения nn выполняется (n)—1=n Определение: Операция приписывания фиктивной координаты (n) порождает отношение n+1=n) над множествами A, A1, A2, ..., An такое, что при справедливости n(а1 j, a2 j, ..., an j) выполняется  n+1(a, a1 j, a2 j, ..., an j) для любого а. Операция приписывания отношению n фиктивной координаты по множеству А состоит в образовании отношения n+1=(n) с графиком, получаемым следующим образом: для каждого вектора =(ai(1), ai(2), ..., ai(n))nA1,...,An строятся векторы (а, аi(1), ai(2), ..., ai(n)) n+1A,A1,...,An, полученные приписыванием к  слева поочередно всех элементов А. Пример: Для 3 на множестве А= с графиком 3А= 1, 0, 0 0, 1, 0 0, 0, 1 в результате приписывания фиктивной (на множестве А) координаты 4А= 0, 1, 0, 0 0, 0, 1, 0 0, 0, 0, 1 1, 1, 0, 0 1, 0, 1, 0 1, 0, 0, 1 С помощью операции  производится, в частности, выравнивание арностей в отношениях. Одна из наиболее важных операций над отношениями - свертка де Моргана. Пусть n - отношение на множествах А1, А2, ... , Аn-1, A, a m отношение на множествах A, An, An+1, ... , An+m-2. Определение: Тогда операция свертки отношений n и m порождает отношение n+m-2=nm над множествами А1, А2, ..., Аn+m-2, такое, что n+m-2(a1 i, a2 i,..., ain+m-2 j) выполняется тогда и только тогда, когда найдется а, для которого выполняется n(a1 i, a2 i, ..., an-1 i, a) и m(a, an i, an+1 i, ..., an+m-2 i). Пример: nA1,...,An= 1, 2, ... n 2, 3, ... n+1 ............................................................... k-2n+2 k-2n+3 ... k-n+1 nAn, ..., A1= n, n-1, ... 1 n+1, n, ... 2 ................................................................ k-n+1, k-n, ... k-2n+2 2n-2A1,...,An-1,An+1,...A1=1, 2, ... n-1, n-1 ... 2, 1 2, 3, ... n, n ... 3 2 ........................................................................... k-2n+2, k-2n+3, ... k-n, k-n, ... k-2n+3, k-2n+2 Пример: График свертки  бинарных отношений  и  на множествах А=a, b, c} и B={0, 1, 2}=C с графиками АВ= а, 0 BC= 0, 1 b, 1 0, 2 c, 2 1, 2 2, 2 имеет вид ()= a, 1 a, 2 b, 2 c, 2 Операция свертки ассоциативна, но не коммутативна. 1. (nm)= n(m k) 2. nm mn Справедливо равенство 3. (nm)-1=(m)--1(n)-1 Пусть  - бинарное отношение на множествах А, В,  - бинарное отношение на множествах В, С. Свертка бинарных отношений  и  называется их композицией. Операция композиции бинарных отношений допускает и другие обобщения на n-арный случай. Пусть L1, L2, L3 - алгоритмические языки, а  и ’ отношение перевода соответственно с L1 на L2 и с L2 на L3. Тогда композиция  отношений  и ’ также является отношением перевода с языка L1 на L3. Пусть 1m – отношение на множествах А1,…, Аm-1, B1; 2m на множествах А1,…, Аm-1, B2;…; n-1m – на множествах А1,…, Аm-1, Bn-1; n – на множествах В1,…, Вn-1, Am. Определение: Суперпозицией отношений 1m,2m,…, n-1m, n называется m-отношение m=n(1m,2m,…, n-1m) на множествах А1,A2,…, Аm такое, что m(а1 i, a2i,…, am i) тогда и только тогда, когда найдутся элементы b1 jB1, b2 j B2,…, bn-1 j Bn-1, для которых sm(а1 i, a2 i,…, am-1 i, bs j при любом s=1, 2,…, n-1, причем, n(b1 j, b2 j, bn-1 j, am i). Пример: 13 = 0, 1, 1 23 = 0, 0, 0 33 = 0, 0, 1  4= 0, 0, 0, 0 1, 0, 0 0, 1, 0 0, 1, 1 1, 0, 1, 1 1, 1, 1 1, 1, 1 1, 1, 0 1, 1, 0, 0 1, 1, 1 1, 1, 1, 1  3=4(13,23,33)= 0, 1, 1 1, 1, 0 1, 1, 1 Частный случай суперпозиции отношений - свертка де-Моргана. 1.4.3. Основные свойства отношений Пусть n - отношение на множествах А1, А2, ..., Аn с графиком nA1, ..., An= a1i1, a2i1, ... ani1 a1i2 a2i2, ... ani2 ................................. a1ir a2ir, ... anir Определение: Проекцией отношения n на множество Аj (при любом j=1, 2, ..., n), называется множество рrj(n)={aji1, aji2, ajir}Aj всех элементов j-го столбца матрицы nA1, An, т.е. проекция отношения n на множество Аj – это совокупность j-х компонент всех векторов отношения n. Определение: Сечением S(j)a1i…, aj-1i, aj+1i,…, ani отношения n по элементам a1i…, aj-1i, aj+1i,…, ani называется множество всех элементов ajirAj, для которых выполняется n(a1i…, aj-1i, aji, aj+1i,…, ani), т.е., S(j)a1i…, aj-1i, aj+1i,…, ani(n)={ajir|n(a1i,…, aj-1i, aj+1i,…, ani)}, где j=1, 2,…, n. Пусть Aj/n={S(j)а1i…, aj-1i, aj+1i,…, ani(n)} – множество сечений отношения n по всевозможным совокупностям (а1i…, aj-1i, aj+1i,…, ani)А1хА2х…хАj-1xAj+1x…xAn. Множество Aj/n называется фактор-множеством Aj по отношению n. Вместо одной последовательности (а1i…, aj-1i, aj+1i,…, ani) можно рассматривать их совокупность Х={(а1ir…, aj-1ir, aj+1ir,…, anir)r=1, 2,…, k}. Тогда сечение S(j)X(n) отношения по совокупности Х является объединением сечений отношения n по всем последовательностям, входящим в Х: S(j)X(n)= r=1k (S(j)а1ir…, aj-1ir, aj+1ir,…, anir(n)). Пример: Пусть отношение 3 на множествах А={a1, a2}, B={b1, b2, b3} и C={0,1} определено графиком 3= a1, b1, 0 a1, b2, 0 a2, b1, 1 a2, b2, 1 a2, b2, 0 тогда pr1(3)=A, pr2(3)={b1, b2}, pr3(3)=C, S(1)b2,0(3)={a1,a2}, S(2)a1,0(3)={b1,b2}, C/3={S(3)a1,b1, S(3)a2,b1, S(3)a1,b2, S(3)a2,b2, S(3)a1,b3, S(3)a2,b3}, для множества X={(a1, b1),(a2, b1)} S(3)X(3)=S(3)a1,b1 S(3)a2,b1=C. Определение: Отношение n на множествах А1, А2,…, Аn называется функциональным при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn, если для каждой последовательности элементов (аi(1)…, ai(2),…, ai(n-1))А1хА2х…хAn-1 сечение S(n)аi(1), ai(2),…, ai(n-1)(n) содержит не более одного элемента ai(n-)Аn. Определение: Если для любой последовательности (аi(1), ai(2),…, ai(n-1))А1хА2х…хAn-1 сечение S(n)аi(1), ai(2),…, ai(n-1)(n) - не пустое, то n – всюду определенное отношение при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn. Определение: Если сечение S(n)X(n) по совокупности Х=А1хА2х…хАn-1 равно множеству Аn, то n – сюръективное отношение при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn. Определение: Если для любых двух последовательностей элементов (аi(1), ai(2),…, ai(n-1)), (аj(1), aj(2),…, aj(n-1))А1хА2х…хAn-1 пересечение сечений S(n)аi(1), ai(2),…, ai(n-1)(n) S(n)аj(1), aj(2),…, aj(n-1)(n)=, то n – инъективное отношение при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn. Отношение n – биективное при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn, если оно всюду определено, функционально, инъективно и сюръективно при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn. Определение: Пусть n – функциональное отношение на множествах А1,…, Аn при отображении его в бинарное отношение 2 на множествах (А1х А2х…хАn) и Аn. Функция Fn(x1,…, xn-1) называется связанной с отношением n, если каждая ее переменная хі принимает значения из множества Аi, где i=1, 2,…, n-1, причем Fn(аi(1), ai(2),…, ai(n-1))=S(n)аi(1), ai(2),…, ai(n-1)(n) для любого набора (аi(1), ai(2),…, ai(n-1))  А1х х…хAn-1. Если отношения 1m, 2m,…, n-1m, n – функциональны и с ними связаны функции F1m, F2m,…, Fn-1m, Fn соответственно, то суперпозиция n(1m, 2m,…, n-1m) также является функциональным отношением, причем, с ней связана суперпозиция функций Fn(F1m, F2m,…, Fn-1m). Определение: Суперпозиция всюду определенных функциональных отношений также является всюду определенным функциональным отношением. Определение: Отношение  называется отображением множества А в В, если - функционально и всюду определено, т.е. для любого аА сечение Sa() – не пусто и содержит один элемент sa()=bB. Определение: Как и для соответствий, элемент b=(a) называется образом элемента а в B при отображении , а элемент а – прообразом b. Определение: Совокупность всех аА таких, что (а)=b, называется полным прообразом элемента b в А при отображении . Определение: Отображение  множества А в В называется отображением А на В, если оно обладает также и свойством сюръективности. Определение: Отображение  множества А на множество В – взаимно-однозначно (биективно), если оно также и инъективно. В частности, взаимно-однозначным отображением А на А является диагональное отношение А, часто называемое тождественным отображением А в себя. Теорема: Отображение  множества А на множество В взаимно-однозначно (в этом случае множества А и В – эквивалентны) тогда и только тогда, когда ,  -  , где ,  - тождественные отображения множеств А и В. Следствие: Если А=В, то отношение  - взаимно-однозначное отображение множества А на себя тогда и только тогда, когда  -=. Определение: n-отношение An на множестве А называется: • рефлексивным, если для любого а выполняется An(а, а,…, а), т.е. nn; • антирефлексивным, если не существует а, для которого выполняется An(а, а,…, а), т.е. nn=; • иррефлексивным (нерефлексивным), если для некоторых, но не для всех а выполняется An(а, а,…, а), т.е. nn и nn. Определение: Бинарное отношение A на множестве А называется: • рефлексивным, если для любого а выполняется A(а, а), т.е.   ; • антирефлексивным, если не существует а, для которого выполняется A(а, а), т.е.   =; • иррефлексивным, если для некоторых, но не для всех а выполняется A(а, а), т.е.    и . Определение: n-отношение An на множестве А называется: • симметричным, если при справедливости An(аi(1), аi(2),…, аi(n)) график An содержит и любую перестановку вектора (аi(1), аi(2),…, аi(n)); • антисимметричным, если для каждого вектора (аi(1), аi(2),…, аi(n)), для которого справедливо An(аi(1), аi(2),…, аi(n)), график An не содержит хотя бы одну перестановку вектора (аi(1), аi(2),…, аi(n)); • асимметричным, если оно не является ни симметричным, ни антисимметричным, т.е. для некоторых векторов выполняется свойство симметричности, а для некоторых векторов – свойство антисимметричности. Определение: Бинарное отношение A на множестве А называется: • симметричным, если при справедливости A(а1, а2) график A содержит и вектор (а2, а1); • антисимметричным, если для каждого вектора (а1, а2), для которого справедливо A(а1, а2), график A не содержит вектор (а2, а1); • асимметричным, если оно не является ни симметричным, ни антисимметричным, т.е. для некоторых векторов выполняется свойство симметричности, а для некоторых векторов – свойство антисимметричности. Определение: Бинарное отношение A на множестве А называется транзитивным, если из справедливости A(a, b) и A(b, с) следует справедливость A(а, с) для любых a, b, c, иначе не транзитивно. Определение: Бинарное отношение A на множестве А называется cвязным, если для любых a, b справедливо A(a, b) или A(b, а), иначе несвязно. Если отношение An удовлетворяет любому из перечисленных свойств, то обратное отношение (An)-1 удовлетворяет этому же свойству. 1.5. Специальные виды отношения 1.5.1. Эквивалентность Определение: Бинарное отношение А на множестве А, удовлетворяющее свойствам рефлексивности, транзитивности и симметричности, называется отношением эквивалентности (. Если А - отношение эквивалентности на множестве А, то и обратное отношение А-1 - отношение эквивалентности на данном множестве. Отношение эквивалентности на множестве А связано с разбиениями этого множества на попарно непересекающиеся подмножества. Пусть А - некоторое отношение эквивалентности на непустом множестве А. Рассмотрим фактор - множество АА=Sа(А)|а. Определение: Сечение Sa(A) называется смежным классом элемента а по отношению А. Лемма: Фактор-множество АА по отношению эквивалентности А является разбиением множества А на смежные классы Sa(A)=A. А - рефлексивно аSa и для любого с такого, что сSa Sb, выполняется аАс и bc в силу симметричности ас и сАb, в силу транзитивности аb и Sa(A)Sb(A), симметричности bAa и Sb()Sa(A), Sa(Sb(A), различные смежные классы не пересекаются. Каждому разбиению R(A)={A1, A2,..., Ak} множества А соответствует отношение эквивалентности  на А, смежные классы которого совпадают с классами данного разбиения, т.е. аb тогда и только тогда, когда а,bі, где і=1, 2,..., k. Теорема: Каждому отношению эквивалентности на множестве А соответствует единственное разбиение R(A) данного множества и, наоборот, любому разбиению множества А однозначно соответствует некоторое отношение эквивалентности на А. Связь отношений эквивалентности и разбиений множеств можно использовать при определении понятия кардинального числа, если считать, что два множества эквивалентны тогда и только тогда, когда они равномощны. Каждому классу эквивалентности соответствует мощность (кардинальное число), классу разбиения конечных множеств соответствует натуральное число - число элементов. Пусть  - отношение эквивалентности на множестве А, A/=Sa()/a - фактор-множество множества А по данному отношению эквивалентности. Определение: Отображение множества А на фактор-множество А, сопоставляющее каждому элементу а смежный класс Sa(), которому принадлежит элемент а, называется естественным отображением множества А на фактор-множество А. Пусть  - отображение множества А на множество В и ему соответствует вполне определенное отношение эквивалентности  на множестве А. Пусть для элементов а1, а2 а1а2 тогда и только тогда, когда (а1)а2). При сопоставлении каждому элементу b его полного прообраза при отображении  получается взаимно-однозначное отображение  множества В на фактор-множество А, причем композиция  совпадает с естественным отображением множества А на фактор-множество А. Все элементы, принадлежащие некоторому классу Аi разбиения R={A1,..., An} множества А, связаны отношением эквивалентности и взаимозаменяемы в том смысле, что любой из этих элементов определяет данный класс, т.е. может служить его представителем (эталоном). Определение: Подмножество множества А, содержащее по одному и только одному элементу аi из каждого класса Аi некоторого разбиения Р={A1, A2, ... , Ai,..., An} множества А, называется системой представителей отношения эквивалентности. Пример: а) Р1а1, а2, а3 А,1=а1, a1>, , , , , ,,, } A,2={, , } P2={{a1}, {a2}, {a3}} PB={{b1, b2, b3}, {b4}, {b5, b6, b7}} B={b1, b2, b3, b4, b5, b6, b7}; б) Таблица 1.2. B b1 b2 b3 b4 b5 b6 b7 B1 1 1 1 B2 1 1 1 b3 1 1 1 b4 1 b5 1 1 1 b6 1 1 1 b7 1 1 1 в) Рис. 1.5. Отношение эквивалентности B 1.5.2. Порядок Определение: Бинарное отношение А на некотором множестве А, удовлетворяющее свойствам рефлексивности, транзитивности и антисимметричности, называется отношением нестрогого порядка (А). Множество А с определенным на нем отношением нестрогого порядка  называется нестрого упорядоченным. Элементы a, b такие, что ab или ab, называются сравнимыми элементами нестрого упорядоченного множества, в нестрого упорядоченное множество могут входить и несравнимые элементы. Нестрого упорядоченное множество, в котором каждая пара элементов сравнима, называется совершенно или линейно упорядоченным множеством или цепью. В этом случае имеет место совершенный или линейный нестрогий порядок. Т.о., отношение нестрого порядка совершенно тогда и только тогда, когда оно связно, в противном случае отношение нестрого порядка называется частичным. Отношение  на множестве А позволяет определить отношение  такое, что для а, b ab тогда и только тогда, когда аb и аb. Отношение  на множестве А называется отношением строгого порядка и обладает свойствами антирефлексивности, сильной антисимметричности, транзитивности. Отношение  на множестве А позволяет в свою очередь однозначно определить отношение  на данном множестве  и  \ . Аналогично нестрогому порядку для строгого порядка также вводятся понятия строго упорядоченного множества, сравнимых элементов, совершенного или линейного строгого порядка (свойство связности) и частичного строго порядка. Пример: Отношение нестрогого порядка быть делителем на множестве 1, 2, 3, 4, 5, 6, 7 а) Таблица 1.3. 1 2 3 4 5 6 7 1 1 2 1 1 3 1 1 4 1 1 1 5 1 1 6 1 1 1 1 7 1 1 б) Рис. 1.6.Отношение нестрогого порядка Пусть Р(А2) - множество всех бинарных отношений, определенных на некотором множестве А и пусть  - бинарное отношение на множестве Р(А2) такое, что для отношений , Р(А2) справедливо  тогда и только тогда, когда из аb следует аb, где а, b, т.е. для всех графиков А и А выполняется включение . Т.о., множество Р(А2) частично упорядочено относительно отношения  . Пусть Т(А2)2 - совокупность всех отношений эквивалентности на множестве А. Определенная частичная упорядоченность  на множестве Р(А2) индуцирует частичную упорядоченность множества Т(А2), причем если характеризовать отношения эквивалентности соответствующими им разбиениями множества А, то  означает, что разбиение А=Sa(a более дробно, чем разбиение А=Sa(a, т.е. для каждого смежного класса Sa( существует разбиение R(Sa())=Sa(|a Sa(. В этом случае разбиение А является подразбиением разбиения А. Пусть F(А)=А* - множество всех слов (векторов) конечной длины в алфавите (множестве) А и на множестве А задано отношение частичного (строгого) порядка. Лемма: Для двух векторов В, СF(A) вектор В нестрого предшествует вектору С тогда и только тогда, когда длина вектора В равна длине вектора С, т.е. С= и каждая компонента bi вектора В - нестрого предшествует соответствующей компоненте сi вектора С. Вектор В строго предшествует вектору С, если и только если одновременно с выполнением отношения нестрогого предшествования существует по крайней мере одна компонента bi вектора В, строго предшествующая компоненте ci вектора С. Пример: А={1, 2, 3}, А3 - множество векторов длины 3. <1, 2, 3>  <1, 2, 3> <1, 2, 3><1, 3, 3> <1, 2, 3>  <2, 2, 3> <1, 2, 3>>|< <2, 1, 3>. Лемма: Отношение нестрогого (строгого) предшествования на множестве векторов есть отношение нестрого (строгого) порядка на множестве векторов конечной длины. Пусть F(A)=А* - множество всех слов (векторов) конечной длины в алфавите (множестве) А и на множестве А задано отношение совершенного строгого порядка. В этом случае возможно ввести лексиграфический порядок на множестве F(A)(. Для двух векторов В,СF(A) вектор В лексиграфически предшествует вектору С (ВС) тогда и только тогда, когда выполняется одно из двух условий: а) существует такое i, где 1 i min (, C, что для всех 1ji выполняется bj=cj, но bici б) для всех i, где 1iшin (, C), bi=ci, но С. Пример: Слова леслето борборовик, упорядоченные в словаре. 1.5.3. Толерантность Определение: Отношение  на множестве А называется отношением толерантности, если оно рефлексивно и симметрично. Синонимом толерантности является совместимость. Для отношения толерантности в отличие от отношения эквивалентности транзитивность не обязательна, следовательно, отношение эквивалентности - частный случай отношения толерантности. Определение: Классом совместимости называется подмножество А такое, что любые два элемента а1 и а2, ему принадлежащие, толерантны. Класс совместимости называется максимальным, если он не является подмножеством никакого другого класса совместимости. Различные классы могут содержать одинаковые элементы, следовательно, являются пересекающимися множествами. Теорема: Всякое отношение толерантности  на множестве А задает покрытие множества А, блоки покрытия при этом являются и классами совместимости, и, наоборот, всякое покрытие множества А подмножествами из 1, А2,..., Аn определяет между элементами любого из подмножеств покрытия некоторое отношение толерантности. Покрытие множества может быть не единственным, в связи с чем важное значение имеет поиск покрытий с минимальным, с учетом повторений, числом элементов в нем, называемый задачей определения минимального покрытия. Очевидно, что в случае отношения эквивалентности абсолютно минимальным покрытием является разбиение - минимальное суммарное число элементов в нем равно мощности множества . Пример: А=пол(1), лицо(2), кит(3), море(4), мина(5). Пара слов принадлежит отношению , если они имеют общую букву. 1, 2, 4, 2, 3, 5, 2, 4, 5 - максимальные классы совместимости 1, 2, 2, 4, 2, 5, 3, 5, 4, 5 - не максимальные классы совместимости Покрытие 1, 2, 4, 2, 3, 5, 2, 4, 5 взаимно однозначно соответствует отношению толерантности =(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (2, 5), (5, 2), (3, 5), (5, 3), (4, 5), (5, 4). а) Таблица 1.4. 1 2 3 4 5 1 1 1 1 2 1 1 1 1 1 3 1 1 1 4 1 1 1 1 5 1 1 1 1 б) Рис. 1.7. Отношение толернтности 1.5.4. Квазипорядок Определение: Отношение  на множестве А называется отношением квазипорядка, если оно рефлексивно и транзитивно. Синонимом квазипорядка являются предпорядок и предупорядочение. Для отношения квазипорядка в отличие от отношений эквивалентности и частичного порядка свойства соответственно симметричности и антисимметричности не обязательны, следовательно, отношения эквивалентности и частичного порядка - частные случаи отношения квазипорядка. Пример: Отношение делимости на множестве целых чисел (положительных, отрицательных и нуля) является отношением квазипорядка а) Таблица 1.5. -2 -1 1 2 3 4 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 3 1 4 1 б) Рис. 1.8. Отношение квазипорядка 1.5.5. Замыкания отношений Определение: Транзитивным замыканием R+ отношения R называется пересечение всех транзитивных отношений, содержащих R в качестве подмножества. Определение: Рефлексивным (и транзитивным) замыканием R* отношения R называется пересечение всех рефлексивных и одновременно транзитивных отношений, содержащих R в качестве подмножества. Справедливы равенства: 1. R*=ER 2. R=(х, у)2|в графе отношения R существует путь из х в у. Следует отметить, что пересечение R является транзитивным отношением, а R* - рефлексивным и транзитивным. Если множество А конечно, то рефлексивное и транзитивное замыкание отношения R может быть получено с помощью метода Варшалла: Рефлексивное замыкание: R*=RR(RR)RRR), транзитивное замыкание: R=R(RR)(RRR) где R=E, =n, в последней композиции – n членов. Определение: Пусть А - множество, n и n, A, G) - соответствие. Подмножество А множества А называется замкнутым относительно соответствия , если ((А)n). Лемма: Для каждого подмножества А множества А существует единственное наименьшее объемлющее А подмножество А множества А, замкнутое относительно соответствия , называемое -замыканием А или замыканием А относительно . Лемма: Справедливо равенство А=^|А^ и А^ - замкнуто относительно , т.к., если А^ и А^ - замкнуто относительно , то А^. Однозначность -замыканий используется при так называемых индуктивных определениях, чтобы задать некоторое множество А, элементы которого удовлетворяют данным условиям, полностью описывают некоторое подмножество А этого множества и определяют все множество А как замыкание А относительно некоторых операций. Пример: М=Р(А) и =(М2, М, G) - такое соответствие, которое каждым двум подмножествам А и  множества А сопоставляет три множества А А и А\А. Семейство (множество), содержащее  и все конечные подмножества множества А, замкнуто относительно . Пример: А=В2 и =(А2, А, ((х, у), (у, z)), (х , z)) | х, у, z  Для любого отношения  на В в этом случае  - замыкание  относительно . 1.6. Специальные функции и операции 1.6.1. Специальные функции Определение: Подстановкой множества А называется биекция на А (биективное соответствие на А). Число подстановок для конечных множеств легко вычислить. Пусть =n и пусть nPn - число таких подстановок. nPn=n! Т.к. Аn, то можно свести подстановку множества А к подстановке множества n, любая подстановка n должна определять образ каждого элемента в n, который должен быть единственным и отличным от других (всюду определенность, функциональность и инъективность). Пусть  - подстановка n, тогда  можно определить как множество n пар =(1, x1), (2, x2),..., (n, xn)}, где (x1, x2,..., xn}=Nn. Пример: 1 1 2 3 4 5 6   5 6 3 1 4 2  1  5 6 3 1 4 2   4 5 6 3 1 2  Пусть А=а1, а2,..., аn}. Определение: Подстановка  называется циклом (циклической подстановкой), если ={(a1, a2), (a2, a3),..., (an-1, an), (an, a1)}. Говорят о цикле длины n, если область (множество) А известно. Пусть А и В - конечно. Расширение  на все множество В позволяет определить новую подстановку : : x= x), если x; x, если x, в этом случае  - ведет себя подобно  во всех случаях, когда В не «остаются на месте». Не все подстановки являются циклами. Пример: 1 - сама по себе не является циклом, но содержит такие - (1, 5, 4), (2, 6), (3) Теорема: Каждая подстановка  на конечном множестве А выражается в виде множества циклов, циклы при этом могут располагаться в любом порядке и не пересекаются. Элемент а множества А, для которого (а) а называется нестационарным (в 1 -  - стационарный элемент). Если =m, а =nm, то число сюръективных и инъективных функций из А в В или число фукциональных отображений из В в А равно nm (число перестановок без повторений), где nmn!(n-m)! Если при этом ВА, то число таких множеств В (число сочетаний без повторений из n по m) равно Сnm=nPmmm= n!/m!(n-m)! и Сnm=Cnn-m. Определение: Последовательностью на множестве А называется отображение  в А. Если :  - заданная последовательность и n)=an, то обычно обозначают последовательность не , а (аn) или (а1, а2,..., аn,...). В этом случае аn называют n-м членом последовательности. Пусть даны множества А, В, С и ВС - множество всех функций из В в С. Определение: Функция f: AC называется функционалом, т.е. для любого а f(a) - функция - f(a) BC, для любого b f(a)(b)C. Множества функций С могут рассматриваться как и любые другие множества, т.е. функционалы следует рассматривать как функции, имеющие нетривиальные области значений. Существуют функции, сохраняющие алгебраические свойства и структуры (простейший пример - для эквивалентности). Определение: Пусть X и  - множества, а x и у - отношения эквивалентности на них и пусть f  X - отображение. Пусть далее f: ху такое, что f={(xyy=f(x), x y, где x и y - классы эквивалентности соответственно с x и y. Если f - функция, то из x1x2 следует, что f(x1=f(x2, и f является отображением, сохраняющим эквивалентность. В этом случае говорят, что f  индуцирует отображение f . 1.6.2. Операции Часто некоторые функции используют при введении более простых обозначений. Определение: Операцией над множеством S называется функция f: SnS, n, два важных момента операции: а) однозначность f(1)1 б) замкнутость на S. Операция SnS имеет порядок n. Если n=1, то операция одноместна (унарная, монадическая), если n=2, то операция двуместная (бинарная, диадическая). Компоненты s1, s2,…, si,…, sn из набора (вектора) (s1, s2,…, si,…, sn)Sn называют операндами, сами символы операций называют операторами. Другой подход понимает под операторами операнды, связанные символами операций в формулы. В случае одноместных операций символ оператора ставят обычно перед операндом, в случае двуместных операций возможны три способа: а) infix (инфикс) - оператор между операндами б) prefix (префикс) - оператор перед операндами в) postfix (постфикс) - оператор после операндов. Пример: a+b - infix ; +ab - prefix ; ab+ - postfix Формы prefix и postfix не требуют скобок при определении порядка вычислений сложных выражений, что делает их удобными для автоматической обработки. Пример: a+bc+(d+e(f+g)) - infix; ++abc+de+fg - prefix; abc+defg+++ - postfix а) (((a+(bc))+(d+(e(f+g)))) - infix б) ++abc+de+fg - prefix в) abc+defg+++ - postfix Рис. 1.9. Инфиксная, префиксная и постфиксная формы Пусть как  обозначается аддитивная операция (типа сложения), а как  - мультипликативная операция (типа умножения). Свойства операций 1. ab=ba; ab=ba коммутативность. 2. a(bc)=(ab)c; a(bc)=(ab)c ассоциативность. 3. а(bc)=(ab)(ac); a(bc)=(ab)(ac) дистрибутивность. 4. аа=а; аа=а идемпотентность. 5. Если для всех а существует b такой, что а) ba=a (ba=a), то b – левая единица (левый нуль); б) ab=a (ab=a), то b – правая единица (правый нуль); в) одновременно ab=a (ab=a) и ba=a (ba=a), то b – двухсторонняя единица (нуль) по  (). 6. Если е – единица (нуль) и ху=е (ху=е), то х – левый обратный элемент к у, у – правый обратный элемент к х, если ху=е (ху=е) и ух=е (ух=е), то х и у – обратные элементы по отношению друг к другу. Лемма: Пусть  () – мультипликативная (аддитивная) операция на множестве А и существует единица (нуль) по отношению к  (). Единичный (нулевой) элемент единственен. Лемма: Пусть  () – ассоциативная операция на множестве А и е – единица (нуль) по отношению к  (). Тогда, если а и имеет обратный элемент, то обратный элемент единственен по отношению к  (). Пример:   , С   и  - коммутативность; СС={1, 2, 3 ,4, 5} и СС={3} – ассоциативность; CC={1, 2 ,3, 4} и CC={1, 3, 4} - дистрибутивность; ={1, 2, 3, 4} и ={1, 2, 3, 4} – идемпотентность; ={1, 2, 3, 4} і ={1, 2, 3, 4} - двусторонний нуль; U={1, 2, 3, 4} і U={1, 2, 3, 4} - двусторонняя единица; =U и =, следовательно  и  - обратные элементы по отношению друг к другу. 2. БУЛЕВА АЛГЕБРА 2.1. Функции 2.1.1. Логические функции Отличительная особенность логических функций состоит в том, что они принимают значения в конечных множествах, т.е. область значений логической функции - всегда конечное множество. Если область значений логической функции содержит k различных элементов, то функция называется k-значной. Логические функции могут зависеть от одной, двух и более числа переменных (аргументов) x1, x2,..., xn, которые в отличие от самой функции могут принимать значения элементов как конечных, так и бесконечных множеств. В теоретико-множественном смысле логическая функция от n переменных y=f(x1, x2,..., xn) представляет собой отображение множества наборов слов (n-мерных кортежей, векторов) вида x1, x2,..., xn, являющегося областью ее определения, на множество ее значений =y1, y2,..., yk. Если аргументы принимают значения из того же множества, что и сама функция, то ее называют однородной. 2.1.2. Булевы функции Наиболее простым и наиболее важным классом однородных логических функций является класс двузначных-булевых функций. Определение: Буквой функцией называется однородная логическая функция, принимающая значения из двухэлементного булева множества В=0, 1 или В=ложь, истина. Так как булева функция - однородна, то любой ее аргумент принимает значения из В=0, 1 или В=ложь, истина, область определения булевой функции от n переменных (аргументов) множество слов длины n. Общее число всевозможных двоичных наборов длины n равно 2n . Число всевозможных булевых функций от n аргументов равно 22^n . Любая булева функция может быть задана таблицей истинности (соответствия), в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах. Пример: а) n=2, число наборов - 22=4, число функций - 22^n= 24=16; б) n=3, число наборов - 23=8, число функций - 22^n= 28=256 в) n=5, число наборов - 25= 32, число функций - 232- 4109. Булевы функции от одной и двух переменных существенно меньше и подробно исследованы. Булевы функции одной переменной n=1, число наборов - 21=2, число функций - 22=4 (см. табл. 2.1.) Таблица 2.1. X Y0 Y1 Y2 Y3 1 1 1 1 1 Y0 и Y3 - функции - константы (Y0 - константа , Y - константа 1), принимающие постоянные значения на всех наборах аргументов. Функция 1 повторяет значения аргумента. Функции 0, 1, 3 - тривиальные функции. Единственная нетривиальная функция - 2, называется отрицанием или инверсией., т.е. y=x и читается как у2 равно не x. Булевы функции двух переменных n=2, число наборов 22=4, число функций - 24=16 (см. табл. 2.2.) Таблица 2.2. х1х2 у0 у1  у2  у3 х1 у4  у5 х2 y6  у7  y8  у9  у10 х2 у11  у12 х1 у13  у14  У15  00 1 1 1 1 1 1 1 1 01 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 Из приведенных функций шесть функций не зависят от х1, или х2, или обоих вместе. Это у0=0 - константа нуля, у15=1 - константа единицы, функции повторения у3=х1 и у5=х2, а также функции отрицания у10=х2 и у12=х1. Остальные булевы функции зависят от двух переменных. Часть из них имеет свои специфические названия и широко используются в булевой алгебре. 1. Булева функция конъюнкции (логического умножения) у1=х1х2 или у1=х1&х2 или у1=х1х2 или у1=х1х2 или у1=х1 и х2. Данную функцию называют логическим умножением, т.к. ее таблица истинности совпадает с таблицей умножения для чисел  и , т.е. равна единице только при единичных аргументах. 2. Булева функция дизъюнкции (логического сложения) у7=х1х2 или у7=х1х2 или у7=х1 или х2 Данная функция равна единице, если хотя бы один из аргументов равен единице. 3. Сложение по модулю (неравнозначности) у6 =х1 х2 или Данная функция равна единице на несовпадающих наборах х1 и х2 4. Булева функция эквивалентности (равнозначности) у9 =х1х2 или у9=х1х2 или у9=(х1 и х2) или (х2 и х1) Данная функция равна единице на совпадающих наборах х1 и х2. 5. Булева функция импликации (логического следования) у13=х1х2, читается, «если х1, то х2 », или у13= х1 или х2 Данная функция равна единице при х1 равном нулю и повторяет значение х2 при х1 равном единице. Аналогично, у11=х2х1, читается «если х2, то х1» 6.Булева функция отрицания импликации (запрета) у2=(х1х2) или у2=х1 их2 В другой интерпретации этой функции у2=(х1х2), при этом левая и правая стрелки понимаются одинаково, т.е. х1х2 = x2x1. Данная функция равна единице только при х1 равном 1 и х2 равном 0. Аналогично, у4=х2х1 в первой интерпретации равна единице только при х2 равном 1 и x1 равном 0. 7. Булева функция «стрела Пирса» (отрицание дизъюнкции) у8=х1х2 или у8= х1 и х2 Данная функция принимает единичное значение только при нулевых значениях х1 и х2. В этой связи у8 является отрицанием дизъюнкции, т.е. у8 =у7 . 8. Булева функция «штрих Шеффера» (отрицание конъюнкции) у14=х1х2 или у14= х1 или х2 Данная функция принимает единичное значение, если хотя бы х1 или х2 равен нулю. В этой связи у14 является отрицанием конъюнкции, т.е. у14=у1. 2.1.3. Логические формулы Наиболее часто используемыми являются булевы функции отрицания у=х (унарная), конъюнкции у=х1х2 (бинарная), дизъюнкции у=х1х2 (бинарная). Выражения, с помощью которых задаются булевы функции, называются логическими формулами, т.е. логические формулы - это булевы переменные, связанные знаками логических операций. Более сложные, чем приведенные выше, логические формулы получаются суперпозицией (замещением, подстановкой) входящих в них переменных другими логическими формулами. Пример: пусть у=х1х2, где х1=а, х2=bc, тогда в результате суперпозиции у =аbc Каждая формула определяет некоторую булеву функцию. Ее значения при различных значениях переменных можно определить на основании таблицы истинности для функций двух переменных. Пример: а=0, b=0, c=1 х1=а=0=1; х2=bc=01=0; у=х1х2=10=1 Две булевы функции, как и определяющие их формулы, называются равносильными, если при любых значениях аргументов обе функции принимают одинаковые значения. Равносильные функции соединяют знаком равенства. 2.2. Способы задания булевых функций Существуют три способа задания булевых функций: табличный, аналитический, геометрический. 2.2.1. Табличный способ Способ предполагает наличие таблицы истинности (соответствия). Пример: Таблица истинности булевой функции от трех переменных y=f(x1, x2, x3) (см. табл.2.3.). Таблица 2.3. x1 x2 x3 Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Другими примерами табличного задания функций являются приведенные раннее таблицы истинности для функций от двух переменных. 2.2.2. Аналитический способ Нормальные формы Определение: Дизъюнктивная нормальная форма (ДНФ) - это дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза. Определение: Конъюнктивная нормальная форма (КНФ) - это конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза. Пример: у=х1х2х2х3х4 ДНФ, у=(х1х2)(х2х3х4) КНФ, у=х1х2х2 (х3х4) не ДНФ и не КНФ. Определение: Члены ДНФ, представляющие собой элементарные конъюнкции из  букв, называются минтермами к-го ранга. Члены КНФ, представляющие собой элементарные дизъюнкции из  букв, называются макстермами к-го ранга. Пример: х1х2 - минтерм 2-го порядка, х2х3х4 - минтерм 3-го порядка, (х1х2) - макстерм 2-го порядка, (х2х3х4) - макстерм 3-го порядка. Совершенные нормальные формы Определение: Если в каждом члене нормальной дизъюнктивной или конъюнктивной формы представлены все n переменных (в прямом или инверсном виде) от которых зависит булева функция, то такая форма называется совершенной дизъюнктивной или конъюнктивной нормальной формой (СДНФ или СКНФ). Лемма: Любая булева функция, не являющаяся тождественно равной нулю, имеет одну и только одну СДНФ. Любая булева функция, не являющаяся тождественно равной единице, имеет одну и только одну СКНФ. Минтермы СДНФ называют конституентами единицы. Макстермы СКНФ называют конституентами нуля. Конституента 1 обращается в единицу только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конститунты принять равными единице, а для всех инверсий конституенты переменные принять равными нулю. Конституента  обращается в нуль только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конституенты принять равными нулю, а для всех инверсий конституенты переменные принять равными единице. Пример: х1х2х3х4=110=1 х1х2х3х4=11=0 Так как СДНФ является дизъюнкцией конституент , то можно утверждать, что представляющая ее булева функция f(x1, x2,..., xn) обращается в единицу только при наборах значений переменных, соответствующих хотя бы одной единице этих конституент. На остальных наборах эта функция обращается в нуль. Аналогично, так как СКНФ является конъюнкцией конституент , можно утверждать, что ее булева функция f(x1, x2,..., xn) обращается в нуль только при наборах значений переменных, соответствующих хотя бы одному нулю этих конституент. На остальных наборах эта функция обращается в единицу. Правила задания булевой функции в виде СДНФ, СКНФ Для задания любой булевой функции в виде СДНФ необходимо записать дизъюнкцию конституент  для всех наборов переменных, на которых функция принимает единичное значение. Для задания любой булевой функции в виде СКНФ необходимо записать конъюнкцию конституент  для всех наборов переменных, на которых функция принимает нулевое значение. Такое представление булевой функции называют аналитическим представлением в виде СДНФ или СКНФ. Пример: Таблица истинности (см. табл. 2.4.), СДНФ и СКНФ булевой функции от трех переменных Таблица 2.4. X1 X2 X3 Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 у=х1х2х3х1х2х3х1х2х3х1х2х3 СДНФ у=(х1х2х3)(х1х2х3)(х1х2х3)(х1х2х3) СКНФ Очевидно, что для всюду определенной булевой функции СДНФ и СКНФ равносильны, т.е. БФ(СДНФ)=БФ(СКНФ). Аналитическое задание булевой функции возможно и в ДНФ и КНФ, в тупиковых, минимальных и др. формах. 2.2.3. Геометрический способ Областью определения булевых функций от n переменных является множество мощностью 2n n-мерных векторов. Если поставить в соответствие каждому вектору вершину n-мерного куба, то область определения булевой функции представляется в виде некоторой n-мерной геометрической фигуры. Булева функция задается на n-мерном кубе выделением вершин, соответствующих векторам х1, х2,..., хn, на которых функция равна единице или нулю. Каждой из n переменных выделяется своя ось координат, на которой откладывается единичный вектор. Начало вектора соответствует нулевому значению переменной, конец вектора - единичному значению. Пример Рис. 2.1. Одномерный а), двумерный б) и трехмерный с) кубы для функций соответственно от одной, двух и трех переменных • n = 1, мощность множества вершин равна 2, пример функции - у =х (см. рис.2.1.а)); • n = 2, мощность множества вершин равна 4, геометрическая фигура выглядит в виде квадрата с отмеченными для конституент вершинами, пример функции – y = x1 x2  x1 x2 (см. рис.2.1.б)); • n = 3, мощность множества вершин равна 8, геометрическая фигура выглядит в виде куба с отмеченными для конституент вершинами, пример функции – y = x3  x1x2 x1 x2.(см. рис.2.1.с)). При n  4 графический способ теряет наглядность. 2.2.4. Численный способ В численном виде булева функция задается в виде СКНФ и СДНФ перечислением номеров наборов, на которых функция принимает нулевые или единичные значения соответственно. Пример: Таблица истинности (см. табл. 2.5.) и численное задание СДНФ и СКНФ функции от трех переменных Таблица 2.5. № X1 X2 X3 Y 1 1 1 2 1 3 1 1 1 4 1 1 5 1 1 6 1 1 7 1 1 1 1 у=1 (0, 3, 4, 7) СДНФ у=0 (1, 2, 5, 6) СКНФ 2.2.5. Приведение формул булевой алгебры к совершенной форме Если какой-либо член j ДНФ не содержит переменной хi, то она вводится тождественным преобразованием: j=j(xixi)=(jxi)(jxi) Если какой-либо член j КНФ не содержит переменной хi, то эта переменная вводится в него следующим тождественным преобразованием: j=jxixi=(jxi)(jxi). Пример у=х1х2х3=х1х2х3х1х2х3х1х3х1х3=х1х2х3х1х2х3х1х2х3х1х2х3х1х2х3х1х2х3 у=(х1х2)х3=((х1х2)х3х3)((х3х1х1)х2х2)=(х1х2)х3)((х1х2)х3)(((х3х1)(х3х1))х2)(((х3х1)(х3х1))х2)=(х1х2х3)(х1х2х3)(х3х1)х2)((х3х1)х2х3х1)х2)((х3х1)х2)=(х1х2х3)(х1х2х3)(х1х2х3)(х1х2х3)(х1х2х3)х1х2х3). 2.3. Булева алгебра Пусть задано некоторое множество М и набор операций Ф, выполняемых на этом множестве: Ф={1, 2,..., n}, тогда двойка множества А=(М, Ф) называется алгеброй. Множество М называется основным или несущим множеством. Множество Ф называется сигнатурой операций или просто сигнатурой. Определение: Булевой алгеброй В=(М,  ,  0, 1) называется множество М с двумя бинарными операциями  и , одной унарной операцией инверсии  в сигнатуре и двумя отмеченными элементами (универсальными границами) 0 и 1, причем для любых x1, x2, x3M набор операций удовлетворяет следующим тождествам: 2.3.1. Основные тождества булевой алгебры 1. x1x2=x2x1; x1x2=x2x1; коммутативность 2. x1(x2x3)=(x1x2)x3; x1(x2x3)=(x1x2)x3; ассоциативность 3. x1(x2x3)=(x1x2)(x1x3); x1(x2x3)=(x1x2)(x1x3); дистрибутивность; 4. x10=0; x10=x1; x11=x1; x11=1; универсальные границы; 5. x1x1=x1; x1x1=x1; идемпотентность; 6. x1x1=0; x1x1=1; (x)=x; дополнение и инволютивность 7. x1(x1x2=x1; x1(x1x2)=x1; поглощение; 8. (x1x2)(x1x2)=x1; (x1x2)(x1x2)=x1; склеивание; 9. x1(x1x2)=x1x2; x1(x1x2)=x1x2; (x1x3)(x2x3)=(x1x3)(x2x3)(x1x2); (x1x3)(x2x3)=(x1x3)(x2x3)(x1x2); Блейка-Порецкого 10. (x1x2)=x1x2; (x1x2)=x1x2; де Моргана Кроме десяти основных тождеств определены теоремы разложения (11, 12) и теоремы подстановки(13-16): 11. f(x1, x2,..., xi,..., xn)=xif(x1, x2,...,1,..., xn)xi f(x1, x2,..., 0,..., xn); 12. f(x1, x2,..., xi,..., xn)=(xif(x1, x2,..., 0,..., xn))(xif(x1, x2,..., 1,..., xn)) 13. xif(x1, x2,..., xi,xi,..., xn)=xif(x1, x2,..., 1, 0,..., xn); 14. xif(x1, x2,..., xi,xi,..., xn)=xif(x1, x2,..., 0, 1,..., xn); 15. xif(x1, x2,..., xi,xi,..., xn)=xif(x1, x2,..., 0, 1,..., xn); 16. xif(x1, x2,..., xi,xi,..., xn)=xif(x1, x2,..., 1, 0,..., xn) Для доказательства тождеств можно использовать метод сопоставления таблиц истинности левой и правой части тождеств - достаточно убедиться в одинаковых значениях на соответствующих наборах аргументов. Другой метод основан на эквивалентных преобразованиях с использованием доказанных ранее тождеств булевой алгебры. Пример: а) Идемпотентность (сохранение степени): хх=(хх)1=(хх)(хх)=х(хх)=х0=х; б) Поглощение: хху=(х1)(ху)=х(1y)=x 1=х 2.3.2. Некоторые упрощения записи формул Из таблицы булевых функций от двух переменных видно, что между функциями имеется зависимость уi=y15-i ,где 0  i  15. На основании этого можно записать соотношения: для констант: 0=1 и 1=0 для БФ от одной переменной: х= (х) для БФ от двух переменных: х1х2=(х1х2) х1х2=(х1+х2) х1х2=(х1х2) х1х2=(х1х2) х1х2=(х1+х2) х1х2=х1+х2) х1+х2=(х1х2) х1х2=(х1х2) х1х2=(х1х2) х1+х2=(х1х2) Из приведенных зависимостей следует, что любая функция двух переменных, включая и константы, выражается в аналитическом виде через совокупность из шести функций, содержащую отрицание и любые функции из указанных пар {у0, у15, {y1, y14}, {y2, y13}, {y4, y11}, {y6, y9, y7, y8} и являющуюся избыточной. Легко доказать, что (х1х2)=х1х2 (х1х2)=(х1х2)(х1х2) Таким образом, совокупность возможно сократить до четырех функций: “константы 0”, отрицания х, дизъюнкции “x1x2” и конъюнкции х1х2. Эти четыре функции также могут быть сокращены - из законов де-Моргана и инволютивности (двойного отрицания). Таким образом, выполняются тождества: х1х2=(х1х2); х1х1=0; (х1х1)=0; х1х2=(х1х2). Отсюда следует, что булевы функции выполняются через отрицание и конъюнкцию или отрицание и дизъюнкцию. Если в булевой формуле переменные связаны только одним типом операции (дизъюнкции или конъюнкции), то в силу ассоциативности скобки не проставляются. Пример: (х1х2)(х3х4)=х1х2х3х4 Скобки, в которых заключена общая операция инверсии (отрицания), также опускаются, т.к. для операций отрицания, конъюнкции и дизъюнкции приоритет убывает слева направо перечисления: Пример: (ху)z=xyz=(x y) z=x y z. 2.3.3. Двойственность формул булевой алгебры В булевой алгебре имеет место принцип двойственности взаимно двойственными операциями являются дизъюнкция и конъюнкция. Заменяя в некоторой формуле каждую операцию на двойственную ей, получаем двойственную формулу. Пример: Формула - (х1х2)(х3х4) Двойственная формула - (х1х2)(х3х4). Определение: Таблица истинности двойственной функции f получается заменой значений переменных и значений самой функции f в таблице истинности исходной функции f на противоположные, т.е. 01, 10. Пример: х1 х2 f=x1x2 x1 x2 f =x1x2 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 Остается только перевернуть полученную таблицу для возрастания значений аргументов сверху вниз. x1 x2 f =x1x2 0 0 0 0 1 0 1 0 0 1 1 1 Формула или функция, равносильная своей двойственной функции, называется самодвойственной. Пример: у1=х1х2х1х3х2х3 и у2=(х1х2)(х1х3)(х2х3) – двойственные и равносильные функции, т.е. у=у1=у2 - самодвойственная функция. Теорема: Если формулы f1 или f2 равносильны, то и двойственные им формулы f1 и f2 также равносильны, и наоборот. f1=f2f1=f2 Пример: хху=х  х(ху)=х Теорема: (принцип двойственности): Если в булевой формуле f заменить конъюнкции на дизъюнкции, «0» на «1», «1» на «0», то получим формулу f, двойственную исходной. Приведение булевых формул к совершенной нормальной форме также основано на использовании тождеств булевой алгебры, в частности использовании двойственных формул. 2.4. Булева алгебра множеств Понятие булевой алгебры носит более общий характер, чем только булева алгебра на множестве функций. Алгебра с сигнатурой типа (2, 2, 1), где тип задает арность операций над булевыми функциями, называется булевой алгеброй, если ее операции удовлетворяют тождествам 1-10. Пусть задано некоторое множество М. Определение: Алгебра А=(В(М),    называется булевой алгеброй множеств над множеством М, тип булевой алгебры множеств - (2, 2, 1). Определение: Алгебры А и А называются изоморфными, если и только если существует взаимно-однозначное соответствие между их основными множествами и сигнатурами (т.е. операциями). Пусть определено взаимно-однозначное соответствие между множеством В(М), где М=m1, m2,..., mn и множеством двоичных векторов Вn размерности n: G: В(М)Вn Каждому подмножеству ММ соответствует двоичный вектор b=, где bi=1, если miM, и bi = 0, если mi. Пусть на множестве двоичных векторов Вn определена булева алгебра вида: А=(Вn,{, , , при этом операции для любых векторов =1, 2,..., n и =<1, 2,..., n определяются следующим образом: 1. =11, 22,..., nn 2. =11, 22,..., n n 3. =1,..., n. Операции над векторами  и  называются поразрядными логическими операциями над двоичными векторами. Пример: =10110; =00101; =10111; =01001; =00100; =11010. Поразрядные операции входят в состав системы команд любой ЭВМ, что упрощает реализацию данной алгебры на ЭВМ. Очевидно, что данная алгебра изоморфна булевой алгебре множеств, это позволяет заменить теоретико-множественные операции объединения, пересечения, дополнения над системами множеств поразрядными логическими операциями над двоичными векторами, легко реализуемыми на ЭВМ: G: А, G-1: А Пример: М=m1, m2, m3, m4, M1=m1, m2, m3, M2=m2, m3, m4,  b=1, 1, 1, 0, b=0, 1, 1, 1 12b1b2=0, 1, 1, 0 2.5. Алгебра Жегалкина Алгебра Жегалкина задана на всем множестве булевых функций на основе операции неравнозначности  (или сложения по модулю «2») и конъюнкции. Определение: Алгебра Жегалкина задается системой А=(В,  , 1). Тип алгебры Жегалкина - (2, 2), т.е. она является булевой алгеброй. В алгебре Жегалкина выполняются следующие тождества: 1. ху=ух; ху=ух коммутативность 2. х(уz)=(xy)z; x(yz)=(xy)z ассоциативность 3. x(yz)=(xy)(xz) дистрибутивность конъюнкции 4. x1=x; x0=0; x1=x; x0=x свойства границ 5. хх=0; хх=х приведение и идемпотентность 6. xx=1; xx=0 дополнение 7. xy=(xy)(xy) перевод в булев базис 8. xy=xy(xy) перевод в базис Жегалкина Тождества 4, 6, 8 позволяют перейти от любой формулы булевой алгебры к соответствующей ей формуле алгебры Жегалкина, а с помощью тождеств 4, 6, 7 - осуществить обратный переход. Пример: x(xy) = x((1x)y) = x((1x)y(1x)y)) = x(1xyy(xy)) = x(xx)(xyx) = xx(xy) = xy; 1xy =xy = (xy)(xy). Система операций алгебры Жегалкина   вместе с константой «1» образует ослабленно функционально полную систему. 2.6. Типы булевых функций Определение: В булевой алгебре из множества булевых функций от n переменных f(x1, x2,..., xn) мощности 22^n выделяются пять типов булевых функций: 1. Функции, сохраняющие константу «0», т.е. функции, на нулевых наборах аргументов принимающие нулевые значения: f(x1, x2,..., xn)f(0, 0,..., 0)=0; Пример: f(x1, x2)=x1x2f(0, 0)=0. 2. Функции, сохраняющие константу «1» ,т.е. функции, на единичных наборах аргументов принимающие единичные значения: f(x1, x2,..., xn)f(1, 1,..., 1)=1; Пример: f(x1, x2)=x1x2 f(1, 1)=1. 3. Самодвойственные функции, принимающие противоположные значения на любых двух противоположных наборах: Пример: f(x)=xf(0)=1, f(1)=0. 4. Линейные функции, представляемые в алгебре Жегалкина каноническим многочленом, не содержащих произведений переменных: f(x1, x2,..., xn)=a0 a1x1a2x2...anxn, где а0, а1, а2,..., аn – константы, принимающие значения 0 или 1 Пример: f(x)=1 x1 x2 5. Монотонные функции, принимающие для любых двух упорядоченных наборов аргументов x11, x12,..., x1n и x21, x22,..., x2n, где x11, x12,..., x1nx21, x22,.., x2n также упорядоченные значения, т.е. f(x11, x12,..., x1n)f(x21, x22,..., x2n). Пример: f1(x1, x2)=x1x2 или f2(x1, x2)=x1x2 <0, 0> 0 <0, 0> 0 <0, 1> 1 <0, 1> 0 <1, 0> 1 <1, 0> 0 <1, 1> 1 <1, 1> 1 2.7. Функциональная полнота Определение: Система булевых функций называется функционально полнотой, если суперпозиция этих функций позволяет получить любую функцию из множества булевых функций. Если в функционально полной системе присутствуют функции константа «0» или константа «1», то ее называют ослаблено функционально полной. Говорят, что функционально полная система функций образует базис в логическом пространстве. Определение: Система булевых функций называется минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную. Определение: Всякая совокупность функций алгебры логики, замкнутая относительно суперпозиции, т.е. такая, что любая суперпозиция функций из совокупности вновь порождает функию, принадлежащую этой же совокупности, называется функционально замкнутым классом. Функционально замкнутые классы, отличные от пустого класса и совокупности всех возможных булевых функций, называются собственными функционально замкнутыми классами. Собственный функционально замкнутый класс называется предполным, если он не содержится ни в каком функционально замкнутом классе отличном от данного класса и класса всех возможных булевых функций. Теорема о функциональной полноте(критерий Поста): Для того, чтобы система булевых функций была полной необходимо и достаточно, чтобы она включала хотя бы одну функцию, не сохраняющую константу «0», не сохраняющую константу «1», несамодвойственную, нелинейную и немонотонную функцию. Теорему следует понимать так, что одна и та же функция может представлять в функционально полной системе одно или несколько требуемых свойств, если она обладает этими свойствами. Пример: Свойства основных элементарных булевых функций от двух переменных с позиций функционально полнотых систем (см. табл. 2.6.) Из таблицы видно, что системы функций {конъюнкция, отрицание}, {дизъюнкция, отрицание}, {штрих Шеффера}, {стрелка Пирса} удовлетворяют теореме о функциональной полноте. Система функций    образует так называемый булев базис. Система   вместе с константой 1 образует ослаблено функционально полную систему. Таблица 2.6. Булева функция Форму-ла Несохр.”0” Несохр.”1” Несамо-двойств. Нели-нейна Немо-нотон Константа “0” + + Константа “1” 1 + + Отрицание  x + + + Конъюнкция x1x2 + + Дизъюнкция x1x2 + + Сумма по модулю “2” x1x2 + + + Штрих Шеффера x1x2 + + + + + Стрелка Пирса x1x2 + + + + + 2.8. Логические (переключательные) схемы 2.8.1. Основные понятия В качестве первой элементной базы для реализации построения булевых функций использовались реле (контактные схемы), выполнявшие роль ключа, который может быть включен, либо выключен. Т.о., реле имеет столько же состояний, сколько и булева функция (переменная) - отсутствие тока и прохождение тока. Нормально замкнутые контакты реле реализуют функцию инверсии, нормально разомкнутые - повторения. Логические функции конъюнкции и дизъюнкции образуются соответственно последовательным и параллельным соединением реле между собой. Реле образуют функционально полную систему, с их помощью можно реализовать любую булеву функцию. Релейные системы еще находят применение в сильноточных устройствах, например в энергетике. Однако, для реализации булевых функций уже продолжительное время разрабатываются и используются логические элементы, которые являются обычно полупроводниковыми приборами, выполненными по микронной или субмикронной технологии. Их входы соответствуют булевым переменным, выходы - реализуемой функции. Для обозначения логических элементов используют прямоугольники. В поле прямоугольника (элемента) указывается та операция, которую он реализует. Подобно суперпозиции булевых функций логические схемы получаются соединением логических элементов. Пример Рис. 2.2. Релейные переключательные схемы для трех функций а) y1 =x; б) y2 = x; с) у3 =x1(x2x3) Пример Рис. 2.3.Логическая схема для функции y = x1x2 x1 x2 2.8.2. Каноническая задача синтеза логических схем Устройства, реализующие элементарные булевы функции, называются логическими элементами. Логической схемой называется соединение (суперпозиция) логических элементов. Задача построения логической схемы, соответствующей заданной булевой функции, называется задачей синтеза. Задача определения булевой функции для заданной логической схемы называется задачей анализа. Между формулой, соответствующей булевой функции, и логической схемой ее реализующей, существует функциональное соответствие. Однако, одна и та же булева функция может быть представлена с помощью нескольких формул, следовательно, можно построить несколько схем, реализующих одну и ту же булеву функцию. Такие логические схемы называются эквивалентными. Очевидно, что более простой формуле соответствует и более простая логическая схема. Принято считать более простой ту формулу, которая содержит меньшее число переменных и логических операций. Т.о., для получения более простой логической схемы необходимо провести упрощение формулы логической функции с помощью логических преобразований. Определение: Каноническая задача синтеза логических схем в булевом базисе (, ,  ) сводится к следующему: 1. Исходная булева функция представляется в СДНФ (СКНФ). 2. С помощью операций дополнения, поглощения булева функция приводится к виду ДНФ (КНФ), содержащей не поддающееся сокращению количество (букв) переменных и знаков операций, т.е. тупиковой ДНФ (тупиковой КНФ) или ТДНФ (ТКНФ). 3. Для полученной ТДНФ (ТКНФ) строится логическая схема. Операции дополнения: (x1x2)(x1x2)=x1; (x1x2) (x1x2)=x1. Операции поглощения: x1(x1x2)=x1; x1(x1x2)=x1. В результате применения операций дополнения и поглощения получаются формулы, для которых дальнейшие операции дополнения и поглощения применить невозможно, т.е. тупиковые формы - ТДНФ и ТКНФ. Среди тупиковых форм находится и минимальная (МДНФ и МКНФ), причем минимальных форм может быть несколько. Еще один шаг в минимизации – получение скобочной формы. Пример: y=x1x2x3x1x2x3x1x2x3 СДНФ y=x1x2x3x1x2x3x1x2x3x1x2x3 y=x1x2x2x3 МДНФ y=x2(x1x) СкНФ 2.9. Минимизация булевых функций 2.9.1. Графический метод Каждой вершине n-мерного куба можно поставить в соответствие константу единицы. Следовательно, подмножество отмеченных вершин является отображением булевой функции от n переменных в СДНФ. Для отображения функции от n переменных, представленной в СДНФ, необходимо установить соответствие между ее минтермами и элементами n-мерного куба. Минтерм n-го ранга для функции n-переменных соответствует вершине n-мерного куба. Минтерм (n-1)-го ранга можно рассматривать как результат дополнения двух минтермов n-го ранга, отличающихся одной переменной: n-1=n-1xin-1xi На n-мерном кубе это соответствует замене двух вершин, отличающихся значением одной переменной, ребром, соединяющим эти вершины. Говорят, что ребро покрывает инцидентные ему вершины. Т.о., минтермам (n-1)-го порядка соответствуют ребра n-мерного куба. Аналогично устанавливается соответствие минтермов (n-2)-го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (квадратом). Элементы n-мерного куба, характеризующиеся S измерениями, называются s-кубами. Так вершины называются 0-кубами, ребра - 1-кубами, грани - 2-кубами и т.д. Т.о., любая ДНФ отображается на n-мерном кубе совокупностью S-кубов, которые покрывают все отмеченные вершины, соответствующие конституентам «1» (0-кубам). Говорят, что такая совокупность S-кубов или минтермов образует покрытие функции. Пример: Для функции от трех переменных y= x1x2x3  x1x2 x3 x1x2 x3 x1 x2 x3 x1 x2x3  x1 x2 x3, заданной в виде СДНФ, графический метод даст формулу вида ymin = x3 x1 x2  x1x2 = x3  (x1  x2). Рис. 2.4.Грань и ребра для функции ymin = x3 x1 x2  x1x2 в графическом методе минимизации Минимизация на n-мерном кубе сводится к поиску такого покрытия, число S-кубов которого будет минимально, а их размерность S максимальна. Такое покрытие называют минимальным покрытием, а соответствующая ему ДНФ - минимальной ДНФ(МДНФ). Аналогично возможно выполнить минимизацию графическим способом для КНФ, для этого необходимо вместо СДНФ и минтермов рассматривать СКНФ и макстермы Данный метод нагляден и прост при n=3. При n=4 метод уже затруднителен. 2.9.2. Табличный метод минимизации (карты Карно) Карты Карно - это специальным образом организованные таблицы соответствия: столбцы и строки таблицы соответствуют всевозможным наборам не более двух переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому соседние по вертикали и горизонтали клетки отличаются только одной переменной. Клетки, расположенные симметрично по краям таблицы также считаются соседними и отличаются одной переменной. Для ДНФ клетки наборов, на которых функция принимает значение «1» заполняются «1». Нулевые клетки не заполняются. Для КНФ клетки наборов, на которых функция принимает значение «0» заполняются «0». Единичные клетки не заполняются. Аналогично n-мерному кубу, совокупности двух соседних клеток соответствует 1-куб, 4-х соседних клеток - 2-куб т.д. Считывание минтермов осуществляется по следующему правилу: клетки, образующие S-куб дают минтерм (n-s)-го ранга, в который входят те (n-s) переменных, которые сохраняют одинаковые значения на этом s-кубе. Для ДНФ значению «1» соответствуют прямые значения переменных, значению «0» - их отрицания. Для КНФ значению «0» соответствуют прямые значения переменных, значению «1» - их отрицания. Переменные, не сохраняющие свои значения на s-кубе, в минтерм (макстерм для КНФ) не входят. Задача минимизации с помощью карт Карно формулируется аналогично задаче минимизации на n-мерном кубе. Данный алгоритм минимизации дает МДНФ для значений функции «1» или МКНФ для значений функции «0». Пример: Карта Кано для функций от одной переменной f1= x (см. табл. 2.7.); двух переменных f2=x1x2 (см. табл. 2.8.); трех переменных f3(x1, x2, x3)=(x2x3)(x1x2) (см. табл. 2.9.); четырех переменных f4(x1, x2, x3, x4)=x2x3 x1x3x4 (см. табл. 2.10.). Таблица 2.7. x= 0 1 1 Таблица 2.8. x1,x2 00 01 11 10 1 1 1 Таблица 2.9. x3 x1,x2 00 01 11 10 1 1 1 1 Таблица 2.10. x3x4 x1,x2 00 01 11 10 1 1 1 1 1 1 1 1 Использование карт Карно требует более простых построений (наглядных), особенно в случае функций от 4-х переменных, в сравнении с отображением на n-мерном кубе. Для отображения функций 5-ти переменных используются две карты Карно от 4-х переменных, для функций 6-ти переменных используются четыре карты Карно: Пример: Две карты Карно для функции от пяти переменных, отличающиеся значением x5 (см. табл.2.11., 2.12.). Таблица 2.11. x3x4 x1,x2 00 01 11 10 x5=0 Таблица 2.12. x3x4 x1,x2 00 01 11 10 x5=1 При n5 наглядность карт Карно теряется. Карты Закревского позволяют сохранить наглядность табличного метода при n8. Подобны картам Карно карты Вейча, отличающиеся только другим порядком следования наборов. Пример: Карта Вейча (см. табл. 2.13.). Таблица 2.13. x1,x2 10 11 01 00 2.9.3. Аналитические методы минимизации Комплекс кубов Аналитические методы минимизации используют специальные методы представления булевых функций, одним из которых является комплекс кубов. Определение: Комплекс кубов К(у) функции y=f(x1, x2,..., xn) - это объединение множеств Кs(y) всех s-кубов, где 0sn-1, причем некоторые из Кs(y) могут быть пустыми: К(у)= Кs(y) Каждый s-куб отображает определенный минтерм. Для записи s-кубов и соответствующих им минтермов функции от «n» переменных используют слова длины «n». Входящие в минтерм переменные называются связанными и представляются 1 для xi и 0 для хi. Не входящие в минтерм переменные называются свободными и обозначаются через «» (крест). Пример: n=5 x1x3x4 101 - 2-куб x1x2x5 010 - 2-куб x3x5 10 - 3-куб 0-кубы соответствуют конституентам 1. Совокупность всех s-кубов записывается как множество слов, соответствующих кубам определенной размерности. Пример: y = x1x2x3  x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 K(y) = КК1K2, где K = 1 0 0 K1 = {1 0  K2 =    1 0 1  0 1 0 0 1 0  1 0 1 1  1 1 0 1 0 1  1 1 1 1} 0 1 } Комплекс кубов образует максимальное покрытие функции. Исключая из него все те S-кубы, которые покрываются кубами высшей размерности, получаем тупиковое покрытие. На множестве тупиковых покрытий определяется минимальное. Используя кубы для обозначения макстернмов, точно таким же образом можно получать тупиковые и минимальные покрытия для КНФ. Постановка задачи Минимизация схем в булевом базисе сводится к поиску минимальной ДНФ, которой соответствует минимальное покрытие. Для оценки сложности булевой функции используется критерий Квайна, формулируемый следующим образом: Утверждение: Минимальной функции соответствует минимальная цена по Квайну, определяемая как С=qs(n-s), где qs - число S-кубов, образующих покрытие данной функции от n-переменных, s - размерность кубов. Минимальное покрытие характеризуется минимальной ценой. Пример: y=x1x3x4x1x2x1x3 n=4 C=1(4-1)+2(4-2)=3+4=7 Задача минимизации решается в два шага: На первом шаге находится сокращенное покрытие, включающее все S-кубы максимальной размерности и не содержащее ни одного куба, который покрывается каким-либо кубом этого покрытия. Соответствующую сокращенному покрытию ДНФ называют сокращенной ДНФ а ее минтермы - простыми импликантами. Для любой булевой функции сокращенное покрытие является единственным, но оно может быть избыточным вследствие того, что некоторые из кубов покрываются совокупностями других кубов. На втором шаге осуществляется переход от сокращенной ДНФ к тупиковой ДНФ, образуемой из сокращенной ДНФ исключением всех избыточных кубов, без которых оставшаяся совокупность кубов еще образует покрытие данной функции, но при дальнейшем исключении любого из кубов получаемая совокупность кубов не покрывает заданную функцию, т.е. перестает быть покрытием. Куб сокращенного покрытия, который покрывает вершины данной функции, не покрываемые никакими другими кубами сокращенного покрытия не может оказаться избыточным и всегда войдет в минимальное покрытие. Такой куб, как и соответствующая ему импликанта, называется экстремалью или существенной импликантой, а покрываемые ими вершины - отмеченными вершинами. Множество экстремалей образуют ядро покрытия. При переходе от сокращенного покрытия к минимальному сначала выделяется ядро покрытия. Если множество экстремалей не образует покрытия, то оно дополняется тем или иным способом до покрытия кубами из сокращенного покрытия. На множестве полученных таким образом тупиковых покрытий выбирается минимальное. СДНФ  СкДНФ  ТДНФ  МДНФ Пример: y =x1 x2x3 x1 x2 x3  x1x2x3  x1x2 x3  x1 x2 x3 K0 = 0 1 0 K1 = 0 1  K2 =  0 1 1  1 1 1 0 0 1 0  1 0 1 1  1 1 1 1 CкДНФ = К1 ТДНФ1 = 0 1  ТДНФ2 = 0 1  1 0   1 1 1  1 ` 1 0  МДНФ1 = 0 1  МДНФ2 = 0 1  1 0   1 1 1  1 1 0  Метод Квайна В качестве исходной формы булевой функции для минимизации методом Квайна используется СДНФ или таблица истинности. Приведение к сокращенной ДНФ осуществляется применением свойств дополнения (операции склеивания). аxiaxi=a Множеству конституент «1» соответствует совокупность 0-кубов К0, операции склеивания соответствует объединение двух 0-кубов, отличающихся только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом . Пример: 0-кубы: 1010  1-куб: 100 1000 Сравнивая попарно все 0-кубы, получаем множество 1-кубов К1. Применяя таким же образом к множеству К1 операцию склеивания, находим множество 2-кубов К2 и т.д. Этот процесс продолжается до тех пор, пока полученное из множества КS очередное множество КS+1 не окажется пустым (или не будет получен n-куб, представляющий функцию – константу «1»). В результате получается комплекс кубов, состоящий из множеств КS: К=К0, К1,..., КS, где sn-1. Для выделения из К множества простых импликант ZK при каждой операции склеивания тем или инім способом отмечаются те кубы, которые объединяются в кубы высшей размерности. Очевидно, что неотмеченные кубы и образуют множество простых импликант Z, именуемое сокращенной ДНФ. На следующем шаге при извлечении экстремалей используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы - конституентам «1» (0-кубам) данной функции. В клетке таблицы ставится метка, если простая импликанта, соответствующая данной строке, покрывает вершину, соответствующую данному столбцу клетки. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых данные строки имеют метки, получаем сокращенную таблицу покрытий. Из сокращенной таблицы покрытий тем или иным способом выбираются простые импликанты, дополняющие выделенное множество экстремалей до тупиковых покрытий. Метод Квайна не формализует этот шаг в виде какой-либо процедуры. На множестве всех тупиковых покрытий определяется минимальные покрытия, которых может быть несколько. Пример: Задана функция y=(0, 1, 2, 5, 6, 7). Комплекс кубов включает три множества, из которых К1 равно сокращенной ДНФ, таблица 2.14. иллюстрирует покрытие простыми импликантами из СкДНФ конституент 1. KО = 000 К1 = 00 К2 =  001 00 СкДНФ = К1 010 01 101 10 110 11 111 11 Таблица 2.14. 000 001 010 101 110 111 00    00   В 01   С 10   D 11   E 11   F AB AC BD CE DF EF В примере экстремали отсутствуют. Тупиковые ДНФ имеют вид: ТДНФ1= 00 ТДНФ2= 00 ТДНФ3= 00 00 10 01 11 11 11 11 Минимальные ДНФ и их цены по Квайну имеют вид: МДНФ1=ТДНФ2, Смднф1=3(n-1)=6, ymin1=x2x3x1 x2 x1 x3 МДНФ2=ТДНФ3, Смднф2=3(n-1)=6, ymin2=x1x3 x1x2x2 x3. Алгебраический метод получения минимального покрытия (алгоритм Петрика) Выбор минимального покрытия на заключительном этапе формализуется с помощью алгебраического метода, предложенного Петриком. Исходная форма для алгоритма – таблица покрытий. Простые импликанты обозначаются символами, например, буквами латинского алфавита. В каждом столбце таблицы записывается дизъюнкция простых импликант, покрывающих соответствующий 0-куб. Покрытию функции соответствует конъюнкция всех записанных дизъюнкций векторов. Упрощая полученное выражение с помощью тождеств булевой алгебры, получаем некоторую ДНФ, каждый член которой соответствует некоторому тупиковому покрытию. Выбирая те из них, которые содержат минимальное количество букв, находим минимальные покрытия. Пример: Из предыдущей таблицы и ряда упрощений при раскрытии скобок следует : Множество ТДНФ: (АВ)(АС)(ВD)(CE)(DF)(EF)=…= =ADEABEFBCDEBCEFACDFABCFBCDFBCF. Подчеркнуты конъюнкции, обладающие наименьшей ценой и соответствующие дополнениям ядра до МДНФ. Так как ядро (множество экстремалей) пустое, сами подчеркнутые конъюнкции и образуют множество МДНФ. Алгебраические преобразования упрощаются, если исходить из сокращенной таблицы покрытий, получаемой после выделения экстремалей. Тогда результатом таких преобразований являются множества простых импликант, дополняющих совокупность экстремалей до тупиковых покрытий. Минимальное из этих дополнений совместно с ядром образует минимальное покрытие булевой функции. Метод Квайна -Мак-Класки Недостатком метода Квайна является большое число сравнений, проводимое между импликантами каждого из кубов КS. Метод Квайна-Мак-Класки является модификацией метода Квайна, позволяющей уменьшить число сравнений. Для этого каждое множество КS разбивается на классы, в каждом из которых содержатся S-кубы с одинаковым числом единиц. Классы упорядочиваются, например, по возрастанию числа единиц. Так как, склеиваться могут только такие два S-куба, число единиц в которых отличается на одну единицу, то достаточно ограничиться попарным сравнением S-кубов некоторого класса с S-кубами соседнего класса. В остальном модификация работает как и метод Квайна. Пример: Задана функция у=(3, 4, 5, 6, 7, 9, 11, 12, 13), ее комплекс, таблица покрытий (см. табл. 2.15.), ТДНФ и МДНФ имеют вид: К0= 0011 К0= 0100 К1= 010 К2={10} К3= 0100 - - - - 100 0101 0011 - - - - 0111 0101 011 1001 1001 011 1011 1100 011 1100 - - - - 101 1101 0111 101 1101 110 Таблица 2.15. 0011 0100 0101 0111 1001 1011 1100 1101 011   А 011   В 011   С 101   D 101   E 10     H AC AB DE CD Существует единственная экстремаль - 10. Из сокращенной таблицы покрытий, включающей первый, четвертый, пятый и шестой столбцы и первую – пятую строки, следует: (AC)(AB)(DE)(CD)=ADACEBCDBCE Т.о., существует четыре тупиковых покрытия: ТДНФ1 = 10 ТДНФ2 = 10 ТДНФ3 = 10 ТДНФ4 = 10 011 011 011 011 101 011 011 011 101 101 101 МДНФ = ТДНФ1 10 Смднф=12+23=8 011 101 Метод Блейка-Порецкого При минимизации функции методом Квайна-МакКласки требуется предварительно представить ее в СДНФ, что часто связано с дополнительными преобразованиями. Если исходить из произвольной ДНФ, то для получения промежуточной сокращенной ДНФ возможно применить прямой метод Блейка-Порецкого, основанный на тождестве acbc = acbcab называемом операцией обобщенного склеивания. Действительно, acbc = ac  abc  bc  abc = ac  bc  ab(c c) = ac  bc  ab. Входящие в тождество буквы могут представлять любые булевы формулы, в частности, конъюнкции переменных. Возможно показать, что произвольная ДНФ приводится к сокращенной ДНФ применением всех возможных обобщенных склеиваний с последующим устранением минтермов на основе операции поглощения a  ab = a. При этом возможны следующие случаи: 1. Конъюнкция а содержит переменную xj, конъюнкция b – отрицание той же переменной xj (или наоборот). Тогда ab=0 и в результате операции обобщенного склеивания не получаются новые минтермы. Таким образом, следует подвергать этой операции только те пары минтермов, в которых единственная переменная представлена как xj и xj. 2. Конъюнкция а содержит только те переменные, которые входят в конъюнкцию b (или наоборот), т.е. b = ас. Тогда axi  bxi = axi  acxi = axi  acxi  ac = axi  ac = axi  b, т.е. минтерм исходной ДНФ поглощается минтермом, образованным в результате обобщенного склеивания. Пример: Пусть функция задана некоторым покрытием, которое соответствует ДНФ y = x2x3x4  x1x2x3  x1x2x4  x1x2x4  x1x2x3x4. Применяя операцию обобщенного склеивания к парам (x2x3x4, x1x2x4), (x1x2x3, x1x2x4), (x1x2,x3 x1x2x4), (x1x2x4, x1x2x3x4) и учитывая, что в двух последних парах происходит поглощение минтермов, получаем y = (x2x3x4  x1x2x4  x1x2x3)  (x1x2x3  x1x2x4  x1x3x4)  (x1x2x3  x1x2x4  x2x3x4)  (x1x2x4  x2x3x4)  (x1x2x4  x1x3x4). Удаляя одинаковые члены a  a = a и группируя старые и новые минтермы, получаем y = (x2x3x4  x1x2x4  x1x2x3  x1x2x4)  (x1x2x3  x1x3x4 x2x3x4  x2x3x4  x1x3x4). При дальнейшем обобщенном склеивании имеет смысл рассматривать только те пары, образованные новыми минтермами со всеми минтермами полученной ДНФ. Такими парами являются (x2x3x4, x1x3x4), (x2x3x4, x2x3x4), (x1x2x4, x1x3x4), (x1x2x4, x2x3x4), (x1x2x3, x1x2x3), (x1x2x4, x2x3x4), (x1x2x4, x1x3x4), (x1x2x3, x1x3x4), (x1x2x3, x1x3x4), (x1x3x4, x2x3x4), (x2x3x4, x1x3x4). Применяя к каждой паре операции обобщенного склеивания и поглощения в соответствии с приведенными ранее правилами, определяем y = x1x2x4  x1x2x4  x1x3x4  x2x3x4  x1x3x4  x2x3. Единственный новый минтерм x2x3 в паре с любым из остальных минтермов не приводит к появлению новых минтермов, поэтому полученная форма является сокращенной ДНФ. Минимизация частично определенных функций Частично определенной функцией называется функция, определенная не на всех наборах значений переменных. Частично определенные функции встречаются, когда по условиям функционирования некоторые из наборов не используются и безразлично, какие значения принимает функция на этих наборах. Это можно использовать при минимизации функции, доопределив ее на безразличных наборах так, чтобы обеспечить наиболее экономическую реализацию. Пусть дана частично определенная функция y = f(x1, x2,..., xn). Тогда y1=f1(x1, x2,..., xn) - функция , доопределенная на всех безразличных наборах единицами, y0=f0(x1, x2,..., xn)- функция, доопределенная на всех безразличных наборах нулями. Задача доопределения функции для ДНФ сводится к выбору из сокращенного покрытия функции у1 (для КНФ - к выбору из сокращенного покрытия функции у0) минимального количества кубов максимальной размерности, совокупность которых покрывала бы все вершины функции у. Такая совокупность кубов и образует минимальное покрытие частично определенной функции. Пример: Задана функция у=(5, 6, 7, 13) и ее неопределенные наборы=(0,4, 8, 15). Карта Карно (см. табл. 2.16.) дает первое представление о минимизации: Таблица 2.16. x3x4 х1х2 00 01 11 10 x0 x1 x0 1 1 1 X1 1 Карта Карно с учетом безразличных кубов дает y=x1x2x2x4. Комплекс кубов и таблица (см. табл. 2.17.) имеют вид: К0= 0000 К1= 000 К2= 01 0100 000 11 1000 010 0101 010 К3= 0110 011 0111 101 1101 011 1111 011 111 111 Таблица 2.17. 0101 0110 0111 1101 01xx    A x1x1    B AB A AB B Из таблицы покрытий следует существование двух экстремалей, образующих ядро и покрывающих все конституенты1 функции, следовательно ymin =x1 x2  x2 x4 2.10. Логика предикатов 2.10.1. Высказывания и логика предикатов Пусть А и В - некоторые высказывания, могущие быть истинными («1») или ложными («0»). Обозначив буквами простые высказывания, можно представить сложное высказывание с помощью соответствующих логических операций. Пример: А - «Я пойду в театр» В - «Я встречу друга» А&В - «Я пойду в театр и встречу друга» Если высказывание истинно, то его отрицание ложно. Обычно высказывания выражают свойства одного или нескольких объектов. Пример: А - «Давление масла на шарик клапана больше давления пружины», В - «Масло открывает клапан» С - «Масло перетекает из нагнетательной полости во впускную» АВС Содержательная часть высказывания играет роль определяющего свойства совокупности объектов, для которых это высказывание истинно, и называется предикатом. Предикат представляет собой логическую функцию Р(х), принимающую как и булевы функции значение «0» или «1», но в отличие от них значения аргумента выбираются из некоторого множества М объектов (хМ). В общем случае такая функция может зависить от многих переменных х1, х2,..., хn, принимающих значения из одного или различных множеств, и записываться как Р(х1, х2,..., хn). Аргументы неоднородных функций, в отличие от однородных, могут принимать значения из любых конечных или бесконечных множеств, но область значений самих функций ограничена конечными множествами. Определение: N-местным предикатом называется неоднородная двузначная логическая функция вида Р(х1, х2,.., хn), с областью значений {0, 1}. Аргументы N-местного предиката представляют собой объекты из некоторой области определения Х(хХ) и называются предметными переменными. Конкретные значения переменных называются предметными постоянными. Пример: Р(х1, х2) - «х1, х2 -четные числа», где х1, х2Х, Х - множество натуральных чисел. В том случае Р(2, 3)=0, т.е. ложно, а Р(2, 4)=1, т.е. истинно При замещении аргумента «хi» некоторым его значением «а» N-местный предикат Р(х1, х2,..., хn) превращается в (N-1)-местный предикат Р(х1, х2,..., а,..., хn) и от переменной хi уже не зависит. N-местный предикат, в котором все х1, х2,…, хn переменных заменены постоянными значениями, превращаются в высказывание, которое можно рассматривать как 0-местный предикат. Пример: Р(х1, х2, х3) - «х1 есть сумма х2 и х3», 3-местный Р(5, х2, х3) - «5 есть сумма х2 и х3», 2-местный Р(5, 3, х3) - «5 есть сумма 3 и х3», 1-местный Р(5, 3, 2) = 1 - «5 есть сумма 3 и 2», - 0-местный Р(5, 3, 1) = 0 - «5 есть сумма 3 и 1» - 0-местный ложный. В логике предикатов часто используются две операции, называемые кванторами. Пусть Р(х) - предикат, определяемый на множестве Х. Определение: Утверждение, что все хХ обладают свойством Р(х), записывается с помощью квантора общности  в виде х Р(х) или Р(х), что читается как «для всех хХ Р(х) - предикат от х - истинен». Определение: Утверждение, что существует хотя бы один объект х, обладающий свойством Р(х), записывается с помощью квантора существования  в виде  хХ Р(х) или  х Р(х), что читается как «существует х, что Р(х) - предикат от х -истинен». Кванторы  и  связывают переменную х, превращая одноместный предикат в высказывание. Очевидно, «хР(х)», рассматриваемое как высказывание, истинно только при условии, что Р(х) - тождественно истинный предикат, во всех остальных случаях это высказывание ложно. «хР(х)», рассматриваемое как высказывание, всегда истинно, кроме единственного случая, когда Р(х) - тождественно ложный предикат. Пример: Р(х) - «х - простое число», где х и Х - множество натуральных чисел. хР(х)=0 - «все натуральные числа простые» - ложно. хР(х)= - «существует простое натуральное число» - истинно. Применение квантора к N-местному предикату превращает его в (N-1)-местный предикат. В общем случае возможно применение к одному N-местному предикату нескольких кванторов. Если к N-местному предикату применить k-кванторов, где kn, то предикат превращается в (N-k)-местный предикат, если k=n, то предикат превращается в высказывание. Переменные, к которым применяются кванторы, называются связанными, остальные переменные называются свободными. Пример : х Р(х, у) - 1-местный предикат, х, у Р(х, у) - высказывание 2.10.2. Правила применения кванторов 1. Одноименные кванторы можно переставлять местами х у Р(х, у = у х Р(х, у) х у Р(х, у) = у х Р(х, у) 2. Разноименные кванторы в общем случае переставлять нельзя х у Р(х, у)у х Р(х, у) 3. Между кванторами общности  и существования  имеют место соотношения, обобщающие законы де-Моргана. (х Р(х)) =х(Р(х)) (х Р(х))=х (Р(х)) Выражения, которые можно образовывать применением к предикатам связок и кванторов, представляют собой формулы логики предикатов. Под логическими связками понимаются слова «не», «и», «или», «если..., то...», «если и только если...». Т.к. предикаты - это двузначные функции, то каждой из этих связок соответствует своя логическая операция - отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности соответственно. Формулы предикатов используют для записи свойств, отношений и т.д. Пример: Пусть Р(х1, х2) - бинарное отношение , определенное на множестве Х. При рассмотрении его как двуместного предиката, можно записать свойства отношений: а) рефлексивность: х Р(х, х) или х (хх) б) симметричность: х1 х2(Р(х1, х2)Р(х2, х1)) или х1 х2((х1х2)(х2х1)) в) транзитивность: х1 х2 х3((Р(х1, х2)Р(х2, х3))Р(х1, х3)) или х1 х2 х3(((х1 х2)(х2 х3))(х1 х3)). Формулы логики предикатов, в которых отрицания относятся только к элементарным предикатам, или высказываниям, причем, из логических операций содержатся только операции булевого базиса называются приведенными или почти нормальными формами. Пример: х1 х2(Р(х1, х2)Р(х2, х1)) - не приведенная формула (х Р(х)) - не приведенная формула х (Р(х, х)) - приведенная формула. С помощью предикатов возможно осуществить запись функций. Пример: Для n-входового конъюнктора (схемы, реализующей конъюнкцию от n переменных) y = &(x1, x2,…, xi,…,xn) запись с помощью предикатов выглядит следующим образом: хi P(xi)  P(y). Для n-входового дизюнктора (схемы, реализующей дизюнкцию от n переменных) y = (x1, x2,…, xi,…,xn) запись с помощью предикатов выглядит следующим образом: хi P(xi)  P(y). Для функции y = x1 x2  x2 x4 запись с помощью предикатов хоть и несколько громоздко, но выглядит следующим образом: ((P(x1) и P(x2)) или (P(x2) и P(x4)))  P(y). ЛИТЕРАТУРА 1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 2. Кук Д., Бейз Г. Компьютерная математика. -М.:Наука, 1990. 3. Горбатов В.А. Основы дискретной математики. -М.:Высшая школа, 1986. 4. Сигорский В.П. Математический аппарат инженера. -К.:Техника, 1975. 5. Коршунов Ю.М. Математические основы кибернетики. -М.:Энергия, 1980. 6. Яблонский С.В. Введение в дискретную математику. -М.:Наука, 1979. 7. Лапа В.Г. Математические основы кибернетики. -К.:Вища школа, 1974.