Дискретная математика 36 часов лекций 36 часов лабораторных работ зачет/экзамен Специальности: «Прикладная математика и информатика», «Математическое обеспечение. - презентация

1 Дискретная математика 36 часов лекций 36 часов лабораторных работ зачет/экзамен Специальности: «Прикладная математика и информатика», «Математическое обеспечение и администрирование информационных систем» 1 курс

2 Литература: Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика - М.: Наука. Физматлит, Новиков Ф.А. Дискретная математика для программистов.- СПб: Питер, Яблонский С.В. Введение в дискретную математику. - М.: Высшая школа, Хаггарти Р. Дискретная математика для программистов.- М.: Техносфера, Иванов Б.Н. Дискретная математика: Алгоритмы и программы.-М.: Лаборатория базовых знаний, Ерусалимский Я.М. Дискретная математика : теория, задачи, приложения.-М.: Вузовская книга, Романовский И.В. Дискретный анализ.- СПб.: Невский Диалект; БХВ- Петербург, Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретная математики. М.: Наука, Капитонова Ю.В. и др. Лекции по дискретной математике. - СПб.:БХВ- Петербург, Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: МАИ, 1992.

3 Тема 1. О предмете курса «Дискретная математика». Discretus (лат.) – прерывистый, состоящий из отдельных частей. Дискретная величина – это величина между отдельными значениями которой, заключено лишь конечное число других ее значений. Противоположное понятие – непрерывная величина Исследуемый объект непрерывный характердискретный характер классическая математикадискретная математика (ДМ)

4 Специфика дискретной математики 1. Отказ от классических понятий непрерывности и предела 2. Важнейшими задачами ДМ являются задачи типа алгоритмической разрешимости и построения конкретных решающих алгоритмов Разделы дискретной математики 1. Комбинаторный анализ 2. Теория графов 3. Теория кодирования 4. Теория функциональных систем 5. Математическая логика 6. Теория алгоритмов и т.д.

5 Тема 2. Начальные понятия теории множеств Основоположник теории множеств – Георг Кантор ( гг.) Немецкий математик. Родился в Петербурге. В 1867г. окончил Берлинский университет. Ученик К.Вейерштрасса. В гг.- профессор университета в Галле. Разработал теорию бесконечных множеств и теорию трансфинитных чисел. Доказал несчетность множества всех действительных чисел (1874г.). Сформулировал общее понятие мощности множества (1878г.). Систематически изложил принципы своего учения о бесконечности. Ввел понятие предельной точки производного множества, развил одну из теорий иррациональных чисел. Созданная Кантором теория множеств (некоторые ее идеи встречались у его предшественников, в частности у Б. Больцано) не только лежит ныне в основе математического анализа, но и послужила причиной общего пересмотра логических основ математики и оказала влияние на всю современную структуру математики.

6 Множество – это совокупность каких-либо объектов, обладающих общим свойством. Эти объекты называются элементами множества Обозначения: множества: А, В, С и т.д. элементы множества: а, в, с и т.д. Пустое множество – это множество, которое не содержит ни одного элемента - ø. Мощность множества – это количество элементов в множестве. Например, |А|. Множество, состоящее из конечного числа элементов – конечное. Другие множества– бесконечные. отношение принадлежности множеству:

7 Способы задания множеств 1. Перечисление элементов (только для конечных множеств) Пример: 2. Указание характеристического свойства, то есть свойства, которым обладают все элементы множества и не обладают никакие другие элементы, не принадлежащие данному множеству (для любых множеств) Пример:

8 Принцип объемности (Г.Кантор) Множества А и В считаются равными, если они состоят из одних и тех же элементов. Обозначение: Пример1: Действительно: Пусть, тогда Пусть, тогда Пример2: Пример3: {1,2,3} {3,2,1}= {{1,2}} {1,2}

9 Парадокс Б.Рассела Рассел Бертран (18 мая февраля 1970), английский философ, логик, математик, общественный деятель. Основоположник английского неореализма и неопозитивизма. Развил дедуктивно- аксиоматическое построение логики в целях логического обоснования математики. Автор (совместно с А. Уайтхедом) основополагающего труда по математической логике «Основания математики». Нобелевская премия по литературе (1950). Занимаясь теорией множеств, Рассел обнаружил парадокс, который впоследствии получил его имя. Этот парадокс привлек широкое внимание ученых, ибо в начале 20 в. теория множеств считалась образцовой математической дисциплиной, непротиворечивой и полностью формализованной.

10 Парадокс – логическое утверждение, которое истинно и ложно одновременно. Примеры других парадоксов 1. По преданию, Эпименид утверждал, что все критяне лжецы. Верно ли это утверждение, если учесть, что сам Эпименид родом с острова Крит? 2. Если Бог всемогущ, то сможет ли Он создать такой камень, который он сам не сможет поднять? A={x / x A} Если х А, то х А

11 Отношение включения -, если каждый элемент множества А является элементом множества В. А – собственное подмножество множества В. Пример: Утверждение1. 1. Для любого множества Х выполняется 2. Для любых множеств Х, Y, Z выполняется следующее свойство: 3. Для любых множеств X, Y выполняется свойство: Универсальное множество U – это множество всех рассматриваемых в данной задаче элементов. {1,2} {1,2,3,4}

12 Графическое представление множеств Для наглядного представления отношений между подмножествами какого-либо универсального множества используют диаграммы Дж.Венна Английский математик ( ). Родился в семье священника. После получения высшего образования в Кембриджском Университете стал священником (1858г.). В 1862г. Возвращается в Кембриджский Университет как лектор. В область его интересов попадали: логика, философия и метафизика. Венн расширил булеву математическую логику и стал автором способа представления отношений между множествами. В 1883г. Становится доктором наук Кембриджского Университета. Пример:

13 Множество всех подмножеств Множеством всех подмножеств называется булеан или степень-множество Обозначение: А – множество Р(А) – множество всех подмножеств множества А Утверждение2. Если множество А состоит из n элементов, то булеан множества состоит из 2 n элементов. Пример:

14 Доказательство. Возьмем произвольный элемент Поставим в соответствие этому элементу двоичный набор из n элементов. Тогда Утверждение доказано.

15 Алгоритм построения Р(А) 1. Построить двоичный набор из n элементов. 2. Прибавлять к начальному набору 1 по правилам сложения в двоичной системе счисления до тех пор, пока не получим единичный набор. … и т.д.

16 Пример: 1) 2)

17 Операции над множествами 1. Объединение Объединением множеств А и В называется множество, все элементы которого являются элементами множества А или В. Пример:

18 2. Пересечение Пересечением множеств А и В называется множество, элементы которого являются элементами обоих множеств А и В. Пример: Если, то А и В – непересекающиеся множества Утверждение3. Для любых множеств А и В выполняются следующие включения: 1. 2.

19 3. Относительное дополнение (разность) Разностью множеств А и В называется множество, элементы которого являются элементами множества А и не являются элементами множества В. 4. Симметрическая разность Пример: 5. Абсолютное дополнение

20 Основные тождества алгебры множеств Для любых подмножеств А, В и С множества U выполняются тождества: 1. Коммутативность 2. Ассоциативность 3. Дистрибутивность 4. Идемпотентность 5. Действия с ø

21 6. Действия с U 7. Законы де Моргана 8. Закон поглощения 9. Закон двойного дополнения 10. Действия с

22 Доказательство дистрибутивности Принцип взаимного включения: 1 шаг. Докажем, что Пусть произвольный элемент х Следовательно, левая часть содержится в правой части. 2 шаг. Докажем, что Пусть произвольный элемент х В силу произвольности элемента х свойство доказано. Следовательно, правая часть содержится в левой части.

23 Доказательство закона де Моргана 1 шаг. Докажем, что Пусть произвольный элемент х Следовательно, левая часть содержится в правой части. 2 шаг. Докажем, что Пусть произвольный элемент х В силу произвольности элемента х свойство доказано. Следовательно, правая часть содержится в левой части.

24 Проверка доказательства с помощью диаграмм Венна Левая часть: Правая часть:

25 Формула включений и исключений Вопрос: как найти число элементов объединения двух или нескольких множеств, если известно число элементов каждого множества? Утверждение4. Пусть даны два множества Х 1 ={а 1,а 2,…,а n } и Х 2 ={b 1,b 2,…,b n }. Если Х 1 Х 2 = Ø, то | Х 1 Х 2 |=| Х 1 |+| Х 2 | Если Х 1 Х 2 Ø, то | Х 1 Х 2 |=| Х 1 |+| Х 2 |-| Х 1 Х 2 |

26 Утверждение5. Если X 1,X 2,…, X n – некоторые множества и n>2, то |X 1 X 2 … X n | = ( |X 1 | + |X 2 | +…+ |X n | ) – ( |X 1 X 2 | + |X 1 X 3 | +…+ |X n-1 X n | ) +( |X 1 X 2 X 3 | +…+ |X n-2 X n-1 X n |) -…+ (-1) n-1 |X 1 X 2 … X n | Доказательство Перепишем доказываемую формулу в виде: |X 1 X 2 … X n | =S 1 (X 1,X 2,…, X n ) - S 2 (X 1,X 2,…, X n )+…+ (-1) n-1 S n (X 1,X2,…, X n ) где S k (X 1,X 2,…, X n ) – сумма чисел |X i 1 X i 2 … X i k | по всем возможным пересечениям ровно k различных множеств, выбранных среди X 1,X 2,…, X n. Доказательство проведем методом индукции. 1. Для n=2 эта формула верна (см. утв.4) 2. Предположим, что эта формула верна для (n-1) множеств 3. Докажем, что эта формула верна для n множеств. |X 1 X 2 … X n | = |X 1 | + |X 2 … X n | – |X 1 (X 2 … X n )| = = |X 1 | + |X 2 … X n | – | (X 1 X 2 ) … (X n-1 X n ) |= = |X 1 | + [S 1 (X 2,…, X n ) - S 2 (X 2,…, X n )+…+ (-1) n-2 S n-1 (X 2,…, X n )] – - [S 1 (X 1 X 2,…, X 1 X n ) - S 2 (X 1 X 2,…, X 1 X n )+…+ (-1) n-2 S n-1 (X 1 X 2,…, X 1 X n )]

27 Сгруппируем теперь слагаемые так: |X 1 | + S 1 (X 2,…, X n ) = |X 1 | + |X 2 | +…+ |X n | S 2 (X 2,…, X n )+ S 1 (X 1 X 2,…, X 1 X n ) = |X 1 X 2 | +…+|X 1 X n |+ |X 2 X 3 |+..+|X n-1 X n | = S 1 (X 1,X 2,…, X n ), = S 2 (X 1,X 2,…, X n ), точно также S k (X 2,…, X n )+ S k-1 (X 1 X 2,…, X 1 X n )= S k (X 1,X 2,…, X n ) и, наконец, S n-1 (X 1 X 2,…, X 1 X n )=| X 1 X 2 X 1 X 3 … X 1 X n |=|X 1 X 2 … X n | = S n (X 1,X 2,…, X n ) Утверждение доказано. После сложения сгруппированных слагаемых получим доказываемую формулу в преобразованном виде.

28 Тема 3. Бинарные отношения Обозначения: - упорядоченная пара, то есть совокупность двух элементов x и y, расположенных в определенном порядке. - упорядоченная n-ка Опр. Бинарным (двухместным) отношением ρ называется множество упорядоченных пар. Обозначение: ρ или х ρ у Область определения ρ: Область значений ρ:

29 Пример1: ρ ={,, } Пример2: Пример3: Пример4: если пара упорядоченная

30 Декартово произведение множеств Опр. Декартово произведение множеств Х и Y – это множество упорядоченных пар, таких что, первый элемент в паре принадлежит множеству Х, а второй – Y. Бинарное отношение есть подмножество декартова произведения, причем Произведение множеств Степень множества

31 Пример1: Х={1,2,3}, Y={0,1} ={,,,,, } Свойство: Пример2: Х={a,b}, Y={e,d}

32 Операции над бинарными отношениями 1. Теоретико-множественные операции: объединение, пересечение, разность 2. Обратное отношение 3. Композиция Утверждение 1. 2.

33 Доказательство 1. Очевидно из определения 2. Пусть Утверждение доказано Свойства бинарных отношений 1. Опр. Отношение ρ на множестве Х называется рефлексивным, если 2. Опр. Отношение ρ на множестве Х называется симметричным, если 3. Опр. Отношение ρ на множестве Х называется симметричным, если

34 Специальные бинарные отношения 1. Отношение эквивалентности Опр. Отношением эквивалентности называется симметричное, рефлексивное и транзитивное отношение. 2. Отношение порядка Пример1: Пример2: отношение подобия на множестве треугольников Пример3: отношение принадлежности к одной студенческой группе Бинарные отношения – частный случай множества

35 Способы задания бинарных отношений 1. Перечисление 2. Указание характеристического свойства 3. Стрелочные диаграммы 4. График

36 Особенности графического изображения специальных бинарных отношений 1. График рефлексивного отношения содержит в себе диагональ. 2. График симметричного отношения симметричен относительно диагонали. 3. Стрелочные диаграммы рефлексивного отношения имеют петли в каждой точке. 4. Стрелочные диаграммы симметричного отношения имеют между каждой парой точек пару стрелок. 5. Стрелочные диаграммы транзитивного отношения обладают следующим свойством: для любой пары стрелок, таких что конец первой совпадает с началом второй, существует третья стрелка, имеющая общее начало с первой и общий конец со второй.

37 Тема 4. Разбиение множеств Пусть ρ – отношение эквивалентности. Опр. Классом эквивалентности порожденным элементом х, называется подмножество множества Х, состоящее из элементов y, для которых х ρ y. Пример1: [x]={x} Пример2: ρ – отношение принадлежности к одной студенческой группе Класс эквивалентности – множество студентов, принадлежащих одной группе Опр. Разбиением множества А называется семейство его частей В 1 ….В n, обладающих следующими свойствами:

38 Пусть дано множество- n-множестово Опр. Числом Стирлинга называется число разбиений n-множества на k блоков. Проверим на примере множества А: A={a,b,c,d}|A|=4S(4,3)=6 1 вариант. abcd 2 вариант. aсbdbd 3 вариант. bсadad 4 вариант. adbcbc 5 вариант. bdacac 6 вариант. cdab Числа Стирлинга и числа Белла

39 Теорема. При n>1 Доказательство Чтобы получить разбиение А={a 1,…a n } на k блоков надо: 1. разбить множество А без последнего элемента (A \ {a n }={a 1,…a n-1 }) на k блоков (S(n-1,k)) и последний элемент – a n – поместить в один из k блоков. либо 2. разбить множество А без последнего элемента (A \ {a n }={a 1,…a n-1 }) на (k-1) блок (S(n-1,k-1)), а из оставшегося элемента – a n – образовать отдельный k-ый блок. Теорема доказана Таблица Стирлинга

40 Опр. Число Белла - общее число разбиений n-множества. S(n)=S(n,0)+S(n,1)+S(n,2)+…+S(n,n) – сумма чисел Стирлинга для k от 0 до n. Пример: A={a,b,c}В(3)=5 1 вариант. abc 2 вариант. abс 3 вариант. baсaс 4 вариант. abc 5 вариант. abc

41 Утверждение1 Пусть ρ – отношение эквивалентности из множества Х. Тогда: То есть, каждый класс эквивалентности порождается своими элементами. Доказательство ρ – отношение эквивалентности. Значит, выполняется свойство рефлексивности, то есть х ρ х. 1 шаг. Докажем, что Пусть, произвольный элемент. Тогда y ρ z. По условию: х ρ у х ρ z (по свойству транзитивности) 2 шаг. Докажем, что Пусть, произвольный элемент Утверждение доказано. Тогда x ρ z. По условию: х ρ у. (ρ – отношение эквивалентности. Значит, выполняется свойство симметричности, то есть если х ρ y, то и y ρ x.) y ρ x. y ρ z (по свойству транзитивности) а) б)

42 Теорема. Всякое отношение эквивалентности на множестве А задает разбиение множества А, блоками которого являются классы эквивалентности. Верно и обратное: всякому разбиению множества А соответствует отношение эквивалентности, классы эквивалентности которого совпадают с блоками разбиения. Доказательство 1. Необходимость. Дано: ρ - отношение эквивалентности. Надо доказать: оно задает разбиение, блоками которого являются классы эквивалентности, то есть надо доказать: если а ρ b, то [a]=[b], где a,b – элементы мн-ва А Докажем методом от противного. Пусть a ρ b (по свойству транзитивности) a ρ х и x ρ b (по свойству симметричности)a ρ х и b ρ x

43 Получили противоречие, значит наше предположение неверно. В силу утверждения1, любой класс эквивалентности не пуст, а в сумме все классы эквивалентности дают все исходное множество А. 2. Достаточность. Дано: отношение ρ задает разбиение, блоками которого являются классы эквивалентности Надо доказать: ρ - отношение эквивалентности. Рассмотрим отношение ρ такое, что а ρ b тогда и только тогда, когда a и b принадлежат одному блоку разбиения. Для того чтобы доказать, что ρ - отношение эквивалентности, надо доказать наличие у него трех свойств: рефлексивность а ρ а, т.к. из одного блока разбиения (зн. это св-во имеет место)

44 симметричность Пусть а ρ b. По определению отношения ρ это значит, что а и b принадлежат одному блоку разбиения. Но b и а тоже принадлежат одному блоку разбиения. b ρ ab ρ a транзитивность Пусть a ρ b и b ρ c (A i, A j – блоки разбиения А) (т.к. пересекаться они не могут)a ρ ca ρ c Теорема доказана выполняется условие: Опр. Отношение ρ называется антисимметричным, если для любых Опр. Отношением частичного порядка на множестве Х называется рефлексивное, антисимметричное, транзитивное отношение.

45 Специальные отношения Свойства отношений рефлексив- ность транзитив- ность симметрич- ность антисим- метричность эквивалент- ности +++- частичного порядка ++-+ Пример1: - отношение предшествования на множестве вещ-ых чисел - отношение частичного порядка Пример2: - отношение подмножеств - отношение частичного порядка Опр. Отношение частичного порядка называется отношением линейного порядка, если любые два элемента сравнимы. Опр. Множество с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.

46 Тема 4. Комбинаторика. Изучает способы подсчета числа элементов в различных конечных множествах. Правило произведения Пусть требуется выполнить одно за другим k независимых действий. Если 1-ое действие можно выполнить n 1 способами, 2-ое – n 2 способами и т.д., а k-ое – n k способами, то все k действий можно выполнить n 1 * n 2 * … * n k способами. Пример. Самара – Ульяновск – Казань пароход автобус самолет поезд автобус пароход Сколько существует способов добраться из Самары в Казань? Таким образом, всего существует 4*2=8 способов добраться из Самары в Казань.

47 Правило суммы Пусть Х – конечное множество, |X|=k Пусть Х i (i=1..k) – подмножества множества Х Причем: Тогда: Правило суммы для случая k=2. Если объект х может быть выбран m способами, а объект у – n способами, то выбор «либо х, либо у» может быть выполнен (m+n) способами.

48 Основные комбинаторные объекты и комбинаторные числа 1. Система подмножеств множества 2. Размещение элементов множества 3. Перестановки элементов множества 4. Сочетание элементов множества 5. Разбиение множества Опр. Комбинаторное число характеризует число объектов в данном множестве. Пусть Х={х 1,х 2,…,х n } Опр. Набор элементов х i 1,x i 2,…,x i k называется выборкой объема k из n элементов или (n,k)-выборкой. Выборка может быть: - упорядоченной и неупорядоченной - с повторениями и без повторений Опр. Выборка называется упорядоченной, если в ней задан порядок расположения элементов. (Две выборки из одних и тех же элементов, расположенных в разном порядке - различны). Опр. Выборка называется неупорядоченной, если порядок расположения элементов несущественен.

49 Размещение элементов множества Опр. Упорядоченная (n,k)-выборка, в которой элементы могут повторяться называется (n,k)-размещением с повторениями. Опр. Упорядоченная (n,k)-выборка, в которой элементы попарно различны называется (n,k)-размещением без повторений. Пример: Х={1, 2, 3} 1. Выпишем все (3,2)-размещения с повторениями (1,1); (1,2); (1,3); (2,1); (2,2); (2,3); (3,1); (3,2); (3,3) 2. Выпишем все (3,2)-размещения без повторений (1,2); (1,3); (2,1); (2,3); (3,1); (3,2) Комбинаторное число – число возможных размещений Обозначение: - число (n,k)-размещений с повторениями - число (n,k)-размещений без повторений

50 Утверждение1. Доказательство Каждое (n,k)-размещение с повторениями является упорядоченной последовательностью длины k. Причем 1-ый элемент последовательности может быть выбран n способами, 2-ой – также n способами, и т.д., k-ый – n способами. По правилу произведения получим n k. Утверждение доказано. Утверждение2. Доказательство 1. k n Каждое (n,k)-размещение без повторений является упорядоченной последоват- тью длины k. Члены ее теперь различны и выбираются из множества, содержащего n элементов. Тогда 1-ый элемент может быть выбран n способами, 2-ой – (n-1) способом, …, k-ый – (n-k+1) способом. Тогда, по правилу произведения получим: Умножим и разделим полученное выражение на (12 3 … (n-k)). Получим:

51 2. k>n Утверждение очевидно, так как невозможно, например, найти ни одного размещения из трех элементов по пять элементов без повторения. Утверждение доказано. Утверждение Перестановки элементов множества Опр. (n,n)-размещение без повторений называется перестановкой, т.е. это частный случай (n,k) размещений для случая k=n. Пример: Х={1, 2, 3}(1,2,3); (1,3,2); (2,1,3); (2,3,1); (3,1,2); (3,2,1) Утверждение4. Оценки для n!: Комбинаторное число – число возможных перестановок

52 Сочетание элементов множества Опр. Неупорядоченная (n,k)-выборка, в которой элементы могут повторяться называется (n,k)-сочетанием с повторениями. Опр. Неупорядоченная (n,k)-выборка, в которой элементы попарно различны называется (n,k)-сочетанием без повторений. Пример: Х={1, 2, 3} 1. Выпишем все (3,2)-сочетания с повторениями (1,1); (1,2); (1,3); (2,2); (2,3); (3,3) 2. Выпишем все (3,2)-сочетания без повторений (1,2); (1,3); (2,3) Комбинаторное число – число возможных сочетаний Обозначение: - число (n,k)-сочетаний с повторениями - число (n,k)-сочетаний без повторений

53 Утверждение5. Доказательство 1. k n Сочетание получается из размещения, если удалить все ненужное: (2,1);(3,1);(3,2). Если k n, то каждое (n,k)-сочетание можно упорядочить k! способами (то есть, каждому сочетанию соответствует k! размещений). Объединение получаемых таким образом попарно непересекающихся множеств (n,k)-размещений для всех возможных (n,k)-сочетаний дает (n,k)-размещения. Тогда, по правилу суммы: где сумма берется по всем (n,k)-сочетаниям без повторений. Таким образом, получим: Учитывая, что, получим: 2. k>n Утверждение очевидно, так как невозможно, например, найти ни одного сочетания из трех элементов по пять элементов без повторения. Утверждение доказано.

54 Утверждение6. Доказательство Каждому (n,k)-сочетанию с повторением В поставим в соответствие вектор длины n+k-1, состоящий из k нулей и n-1 единицы. Причем, число нулей, находящихся между i-1 и i единицами, где 2 i n-1 будет равно числу элементов x i, входящих в сочетание. Число нулей, стоящих перед 1-ой единицей равно количеству элементов х 1, входящих в сочетание. Число нулей, стоящих после (n-1)-ой единицы равно количеству элементов x n, входящих в сочетание. Например, пусть n=4, k=6, х={1,2,3,4}. Тогда: В={2,2,3,3,3,4},a = ( ) или если В={3,3,4,4,4,4}, то =( ) Такое соответствие является взаимно-однозначным: сколько сочетаний – столько двоичных наборов и наоборот. Сколько таких двоичных наборов? Число векторов с k нулями и n-1 единицами равно числу k-элементных множеств, являющихся подмножествами (n+k-1)-элементного множества – множества всех компонент-векторов. Следовательно, имеет место формула: Теорема доказана.

55 Разбиение множества Пусть дано множество Х={a 1,a 2,…,a n }, |X|=n Опр. Разбиением мн-ва Х называется неупорядоченная система непустых подмножеств (Х 1,Х 2,…,Х k ) множества Х, обладающих двумя свойствами: Комбинаторное число – число возможных разбиений Обозначение: - число возможных разбиений n – размерность исходного множества; n 1,n 2,…,n k – размер блоков, на которые разбивается множество Утверждение7. Доказательство 1 шаг.Докажем, что Исходное множество: {1,2,3,…,n} Каждый из Х i – это сочетание без повторений. Для того чтобы получить все Х i необходимо все исходное множество Х последовательно разбить на блоки. Значит, будет работать правило произведения. 1. Х 1 … Х k =X2. X i X j =, ij Тогда если |X i |=n i, то

56 Для образования сочетания, соответствующего множеству Х 1, могут быть использованы все элементы множества Х. То есть, множество Х 1 может быть выбрано способами. После выбора Х 1, множество Х 2 выбирается из (n-n 1 ) элементов множества Х и т.д. По правилу произведения, выбор последовательности множеств Х 1,Х 2,…,Х k может быть осуществлен способами. 2 шаг. Распишем полученное произведение. Так как, то 1 Теорема доказана.

57 Тема5. Элементы теории графов. Леонард Эйлер ( ) В 1723 году Эйлер получил степень магистра искусств, а в 1727 году защитил диссертацию о распространении звука. В 1727 году Эйлер, принимает приглашение только что созданной Петербургской академии наук и приезжает в Петербург, где он был назначен адъюнктом по математике. В 1730 году Л. Эйлер получил место профессора (академика) кафедры физики, а в 1733 кафедру математики. В 1741 году Л. Эйлер переезжает в Берлин. В 1766 году Л. Эйлер со своей семьей возвращается в Петербург. В этот период он справедливо считался первым математиком в мире и пользовался всеобщим уважением и почетом. Умер Л. Эйлер 18 сентября 1783 года в Петербурге. Необычайно велико научное наследие Л. Эйлера. Полное собрание его сочинений насчитывает более 70 томов, а в списках его трудов более 850 названий. Эйлеру принадлежит первое систематическое изложение математического анализа («Введение в анализ» 2 тома, «Дифференциальное исчисление» 1 том, «Интегральное исчисление» 3 тома), он автор книг по механике, теории движения Луны и планет, по географии, по теории кораблестроения, теории музыки и т. д.

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

59 Слож- ность Размеры наибольшей задачи, разрешимой за 1 час. На современных ЭВМ На ЭВМ в 100 раз более быстрых На ЭВМ в 1000 раз более быстрых NN1N1 100 N N 1 n2n2 N2N2 10 N N 2 n3n3 N3N N 3 10 N 3 n5n5 N4N4 2.5 N N 4 2n2n N5N N N 5 3n3n N6N N N 6 Таблица1. Влияние технического совершенствования ЭВМ на полиномиальные и экспоненциальные алгоритмы

60 СложностьВремя решения задачи 1 с.10 2 с. 1.7 мин с. 2.7 ч с. 12 сут с. 3 года с. 3 века n n log n n n n/ n2n Таблица2. Максимальная размерность задач, разрешимых за данное время

61 Опр. Графом G называется совокупность двух множеств: непустого множества V и множества Х={ / v i,v j V} – множества пар элементов множества V. Условные обозначения: G= ; V ; Х V V; V={v 1,…v n }; Х={ / v i,v j V} Пример1. Задача о кенигсбергских мостах.Пример2. Опр. Элементы множества V называются вершинами. Опр. Элементы множества Х называются ребрами. Во множестве Х могут встречаться пары с одинаковыми элементами вида, а также одинаковые пары. Опр. Ребра вида называются петлями. Опр. Одинаковые пары в множестве Х называются кратными ребрами.

62 Опр. Количество одинаковых пар в Х называется кратностью ребра. петля кратные ребра Опр. Граф с кратными ребрами и петлями называется псевдографом. Опр. Псевдограф без петель называется мультиграфом. Опр. Если пары в наборе Х являются упорядоченными, то граф называется ориентированным.

63 Опр. Ребра ориентированного графа называются дугами. Опр. Если пары в наборе Х являются неупорядоченными, то граф называется неориентированным. Пример2. V={v 1, v 2, v 3, v 4, v 5 }; X={х 1 =, х 2 =, х 3 =, х 4 = } G= - неориентированный граф v 5 V, несмотря на то, что эта вершина не соединена с другими вершинами ребрами. Пример3. V={v 1, v 2, v 3, v 4 }; X={х 1 =, х 2 =, х 3 =, х 4 = }. G= - ориентированный псевдограф Внимание! 1. Дуги всегда изображаются с помощью стрелок (от первого элемента пары ко второму элементу пары) 2. Кратные дуги изображаются каждая отдельно.

64 Опр. Если х= - ребро графа, то вершины v и w называются концами ребра х. Говорят что ребро х соединяет вершины v и w. Опр. Если х= - дуга ориентированного графа, то вершина v называется началом дуги, а вершина w называются концом дуги х. Говорят что дуга х исходит из вершины v и заходит в вершину w. Опр. Если в неориентированном графе вершина v является концом ребра х, то говорят, что v и х инцидентны. Опр. Если в ориентированном графе вершина v является концом или началом дуги х, то говорят, что v и х инцидентны. Опр. Вершины v,w G= называются смежными, если X. Опр. Два ребра называются смежными, если они имеют общую вершину. Опр. Степенью вершины v графа G называется число d(v) ребер графа, инцидентных вершине v. Опр. Полустепень исхода вершины v ориентированного графа G называется число d - (v) дуг, исходящих из вершины v. Опр. Полустепень захода вершины v ориентированного графа G называется число d + (v) дуг, заходящих в вершину v. Опр. Вершина v, имеющая степень 0 называется изолированной, т.е. d(v)=0. Опр. Вершина v, имеющая степень 1 называется висячей, т.е. d(v)=1.

65 Пример4. Концы ребра х 1 – это вершины V 1 и V 2. Вершина V 2 инцидентна ребрам х 1, х 2, х 3, то есть d(V 2 )=3 V 1 и V 2 – смежные вершины. V 5 – изолированная вершина. Пример5. Дуга х 1 исходит из вершины V 1 и заходит в вершину V 2. Вершина V 2 инцидентна дугам х 1, х 2, х 3,х 4

66 Пусть n(G) – количество вершин в графе G m(G) – количество ребер в графе G Теорема Эйлера. 1) Для любого псевдографа G выполняется равенство: 2) Для любого ориентированного псевдографа G выполняется равенство: Опр. Графы G 1 = и G 2 = называются изоморфными, если существует φ – взаимно-однозначное отображение между множествами вершин графов G 1 и G 2 (φ:V 1V 2 ), сохраняющее смежность, то есть X 1 X 2

67 Свойства изоморфизма 1) Если G 1 = и G 2 = изоморфны и φ:V 1 V 2 – взаимно-однозначное отображение, сохраняющее смежность, то: а) v V 1 d(v)=d(φ(v)) б) m(G 1 )=m(G 2 );n(G 1 )=n(G 2 ) 2) Если D 1 = и D 2 = изоморфны и φ:V 1 V 2 – взаимно-однозначное отображение, сохраняющее смежность, то: а) v V 1 d + (v)=d + (φ(v)); d - (v)=d - (φ(v)) б) m(D 1 )=m(D 2 );n(D 1 )=n(D 2 ) Опр. Графы G 1 = и G 2 = называются изоморфными, если существует два взаимно-однозначное отображения: φ:V 1V 2 и :Х 1Х 2 таких, что X 1 (х)= X 2, то есть сохраняется не только смежность, но и кратность соответствующих ребер. Изоморфизм графов (ориентированных графов) является отношением эквивалентности на множестве графов (ориентированных графов).

68 Пример6. G 1 и G 2 - изоморфныG 2 и G 3 - неизоморфны Пример7. G 3,3, G 3 и G 4 - изоморфны

69 Опр. Операция подразбиения ребра в графе состоит в: Опр. Граф D 2 называется подразбиением графа D 1, если граф D 2 можно получить из D 1 путем последовательного применения операции подразбиения ребер. Пример8. D 2 является подразбиением графа D 1. 3) добавлении в X \ { } двух ребер 2) добавлении в V новой вершины V 1 1) удалении из Х ребра

70 Опр. Граф D 1 и D 2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными. Опр. Граф G 1 = называется подграфом графа G= если V 1 V, X 1 X Обозначение: G 1 G – G 1 является подграфом графа G Опр. Граф G 1 является собственным подграфом графа G, если G 1 G, G 1G. Обозначение: G 1 G – G 1 является собственным подграфом графа G Теоретико-множественные операции над графами Опр. Объединением графов G 1 = и G 2 = называется граф G 1 G 2 = Опр. Пересечением графов G 1 = и G 2 = называется граф G 1 G 2 =, где V 1 V 2.

71 Опр. Граф называется планарным, если его можно изобразить на плоскости так, что его ребра пересекаются только в вершинах. Критерий планарности Понтрягина. Граф G планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам G 5 и G 3,3, где Пример9. Данный граф планарен, так как ребро мы можем изобразить не изменяя смежность вершин, следующим образом:

72 Способы задания графов 1. Графический 2. Описание множеств вершин V и множеств ребер X 3. Матричный 3.1 Матрица смежности (задается одинаково для ориентированных и неориентированных графов) Пусть G= - граф, где V={v 1,…,v n }, X={x 1,…,x m } Матрицей смежности графа G называется квадратная матрица (n x n) а ij = 1, если X 0, если X, где Матрица смежности заполняется по строкам

73 Пример10. A(G)= v1v1 v2v2 v3v3 v1v1 v2v2 v3v Пример11. A(G)= v1v1 v2v2 v3v3 v1v1 v2v2 v3v

74 3.2 Матрица инцидентности (или инциденций) а) Для ориентированного графа Пусть G= - граф, где V={v 1,…,v n }, X={x 1,…,x m } Матрицей инцидентности графа G называется матрица (n x m), где b ij = 1, если v i – конец дуги x j -1, если v i – начало дуги x j 0, если v i и x j не инцидентны б) Для неориентированного графа Матрицей инцидентности графа G называется матрица (n x m), где b ij = 1, если v i инцидентна ребру x j 0, если v i и x j не инцидентны Матрица инцидентности заполняется по столбцам

75 Пример12. B(G)= v1v1 v2v2 x3x3 x1x1 x2x2 v3v x4x4 1 0 Пример13. B(G)= v1v1 v2v2 x3x3 x1x1 x2x2 v3v

76 Свойства матриц смежности и инцидентности 1. Для любого неориентированного графа G матрица смежности A(G) является симметричной. 2. Для ориентированного графа G матрица смежности A(G) в общем случае не является симметричной. 3. Для любого неориентированного мультиграфа G (сумма элементов по i столбцу) (сумма элементов по i строке) 4. Для любого ориентированного псевдографа G 5. Для любого ориентированного мультиграфа G=, где Х выполняются свойства: а) сумма строк матрицы B(G) является нулевой строкой б) любая строка матрицы B(G) является линейной комбинацией остальных строк в) ранг матрицы В(G) не превосходит n(G)-1

77 Компоненты связности. Опр. Если есть граф G=, то вершина w этого графа достижима из вершины v, если 1. w=v 2. существует путь (маршрут) из v в w Опр. Неориентированный граф называется связным, если v, w V существует путь, соединяющий эти вершины. Опр. Ориентированный граф называется сильно связным, если v, w V существует путь, соединяющий эти вершины. Опр. Ориентированный граф называется односторонне связным, если для любых двух вершин по крайней мере одна достижима из другой. Опр. Графом, ассоциированным с графом G 1 называется граф G 2 =, в котором множество X 1 * получается из множества Х 1 путем замены упорядоченных пар на неупорядоченные.

78 Опр. Ориентированный граф называется слабо связным, если связным является ассоциированный с ним граф. Опр. Компонентом сильной связности графа G называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа графа G. Пример14. Компоненты сильной связности: G 1 =, V 1 ={v 1,v 3,v 5 } G 2 =, V 2 ={v 2 } G 3 =, V 3 ={v 4 }

79 Утверждение1. Пусть дан граф G=, в котором можно выделить р компонент связности: G 1 =, …, G p =. Тогда V=V 1 V 2 … V p X=X 1 X 2 … X p то есть G=G 1 G 2 … G p V i V j = при ij X i X j = при ij n(G 1 )+n(G 2 ) + … +n( G p )=n(G) m(G 1 )+m(G 2 ) + … +m( G p )=m(G)

80 Утверждение2. Пусть дан ориентированный граф G=, в котором можно выделить р компонент сильной связности: G 1 =, …, G p =. Тогда V=V 1 V 2 … V p X X 1 X 2 … X p V i V j = при ij X i X j = при ij n(G 1 )+n(G 2 ) + … +n( G p )=n(G) m(G 1 )+m(G 2 ) + … +m( G p ) m(G) Утверждение3. Пусть - отношение достижимости на множестве вершин V графа G=, то есть для произвольных вершин v и w выполняется: v w v=w, либо существует путь (маршрут) v x 1 …x k w. Тогда 1. - отношение эквивалентности на множестве вершин V графа G 2. v w тогда и только тогда, когда v и w принадлежат одной компоненте сильной связности

81 Матрица достижимости. Пусть G= - граф, где V={v 1,…,v n }, X={x 1,…,x m } Матрицей достижимости графа G называется квадратная матрица (n x n), где t ij = 1, если v j достижима из v i (т.е. существует маршрут) 0, если v j не достижима из v i Матрица сильной связности. Пусть G= - граф, где V={v 1,…,v n }, X={x 1,…,x m } Матрицей сильной связности графа G называется квадратная матрица (n x n), где s ij = 1, если v j достижима из v i и v i достижима v j 0, иначе

82 Алгоритм выделения компонент сильной связности. Пусть дан граф G=, его матрица сильной связности S(G) и матрица смежности A(G). 1 шаг. Введем р - счетчик компонент сильной связности. Полагаем р=1 и S 1 =S(G), то есть первоначально матрица сильной связности совпадает с исходной матрицей сильной связности. 2шаг. Включаем в множество вершин V p вершины, соответствующие единицам первой строки матрицы S p. При этом V p - множество вершин р-ой компоненты связности. В качестве A(G p ) берем подматрицу матрицы A(G), находящуюся на пересечении строк и столбцов соответствующих вершинам из множества V p. 3шаг. Вычеркиваем из матрицы S p строки и столбцы, соответствующие вершинам из V p. Если в результате не осталось ни одной строчки, то р - это количество компонент сильной связности, а A(G 1 )...A(G p ) - матрицы смежности компонент сильной связности. Иначе, обозначаем за S p+1 матрицу, оставшуюся после вычеркивания строк и столбцов, увеличиваем р на 1: р=р+1 и переходим к шагу 2. (для неориентированных и ориентированных графов)

83 Пример15.A(G) v1v1 v2v2 v3v3 v1v1 v2v2 v3v v4v v5v5 v4v4 v5v S(G) v1v1 v2v2 v3v3 v1v1 v2v2 v3v v4v v5v5 v4v4 v5v шаг.р=1 V 1 ={V 1, V 3, V 5 }2 шаг. A(G 1 ) v1v1 v3v3 v5v5 v1v1 v3v3 v5v S 1 (G)=

84 3 шаг. S 2 (G) v2v2 v4v4 v2v2 v4v p=2 4 шаг. V 2 ={V 2 } A(G 2 ) v2v2 v2v2 0 5 шаг. p=3 S 3 (G) v4v4 v4v4 1 6 шаг. V 4 ={V 4 } A(G 3 ) v4v4 v4v4 0 7 шаг. После вычеркивания строк и столбцов в матрице сильной связности не остается, значит конец алгоритма. Таким образом, в исходном графе 3 компонента сильной связности. S(G) v1v1 v2v2 v3v3 v1v1 v2v2 v3v v4v v5v5 v4v4 v5v

85 Маршруты (пути) на графах. Опр. Последовательность v 1,x 1,v 2,x 2,..., x k v k+1, называется маршрутом для ориентированного графа. Опр. Маршрут называется путем для неориентированного графа. Причем, каждая из дуг х i имеет вид Пример16. А,,B- не путь так как каждое ребро не соединяет предыдущую и последующую вершины А,,E,,B- путь Опр. Длиною маршрута (пути) называется число ребер (дуг) в этом маршруте (пути). Опр. Если V 1 =V k+1, то путь (маршрут) называется замкнутым.

86 Поиск маршрута в графе. Алгоритм Терри. Пусть надо найти маршрут из вершины v в вершину w в графе G=. Для того, чтобы найти маршрут соединяющий вершины v и w, необходимо исходя из вершины v последовательно переходить от каждой достигнутой вершины к смежной по правилам: 1. идя по произвольному ребру каждый раз отмечать направление в котором оно было пройдено 2. исходя из некоторой вершины следовать всегда только к тому ребру, которое не было пройдено или было пройдено в противоположном направлении. 3. Для любых вершин v*v отмечать 1-ое заходящее в вершину ребро если эта вершина встречается 1-ый раз 4. исходя из некоторой вершины v* по 1-ому заходящему в v* ребру идти лишь тогда, когда нет другой возможности. Найти путь из v 1 в v 5 Пример.

87 Поиск минимальных путей (маршрутов). Опр. Маршрут в графе G из v в w называется минимальным (кратчайшим), если он имеет минимальную длину среди всех маршрутов из v в w. Пример17. 1 =v x 1 v 1 x 2 v 2 x 3 wd( 1 )=3 2 =v x 4 v 5 x 5 w d( 2 )=2 3 =v x 6 v 4 x 7 v 3 x 8 w d( 3 )=3 2 - минимальный маршрут Для неориентированного графа аналогично. Опр. Образ вершины v -это множество вершин w, таких что существует дуга (ребро) из v в w. D(V)={w / X} Опр. Прообраз вершины v - это множество вершин w таких, что существует дуга (ребро) из w в v. D -1 (V)={w / X} Пример18. D(v 1 )={v 2 } D -1 (v 1 )={v}

88 Алгоритм поиска минимальных маршрутов в ориентированном графе. Алгоритм фронта волны. Пусть дан граф G=. |V|=n 2 Найти минимальный маршрут из вершины v в вершину w (vw). 1 шаг. Пометим вершину v индексом 0, то есть I v =0, а все вершины v D(v) помечаем индексом 1, то есть I v =1. Формируем множество:FW 1 (v)={v / I v =1} Обозначение: FW i (v) – фронт волны i-го уровня Обозначим индекс через k. Таким образом, k=1. 2 шаг. Если фронт волны вершины – пустое множество или k=n-1, а при этом w FW k (v), то вершина w не достижима из вершины v конец алгоритма. Иначе, переход к шагу 3. 3 шаг. Если w FW k (v), то переход к шагу 4. Иначе, существует минимальный маршрут из v в w и d( )=k. Маршрут содержит следующие вершины: v w 1 w 2 …w k-1 w, при этом w k-1 FW k-1 (v) D -1 (w),w k-2 FW k-2 (v) D -1 (v k-1 ) …w 1 FW 1 (v) D -1 (w 2 ) 4 шаг. I v =k+1 - помечаем индексом (k+1) такие вершины v, которые не были помечены ранее и содержатся в образе множества вершин с индексом k. k=k+1. Переход к шагу 2. Конец алгоритма. Примечание. У графа может быть несколько минимальных маршрутов. В этом случае вершины w 1, w 2, …, w k-1 определяются неоднозначно.

89 Пример18.Пусть дан граф G=. |V|=n=6 A(G) v1v1 v2v2 v3v3 v1v1 v2v2 v3v v4v v5v5 v4v4 v5v v6v6 v6v Найти минимальный маршрут v 1 v Строим фронты волны вершины v 1 v1v1 v2v2 FW 2 FW 0 FW 1 v3v FW 3 v4v4 v5v5 1 1 v6v6 3 Поиск образа вершины – это анализ строки матрицы смежности с номером, совпадающим с номером вершины. 2. Восстановим маршрут. - минимальный маршрут.d( )=3 v1v1 w1w1 w2w2 v6v6 w 1, w 2 – неизвестные вершины По алгоритму: w 2 FW 2 (v 1 ) D -1 (v 6 ) Поиск прообраза вершины – это анализ столбца матрицы смежности с номером, совпадающим с номером вершины. w 2 {v 2,v 3 } {v 3 } w 2 =v 3 w 1 FW 1 (v 1 ) D -1 (w 2 ) w 1 {v 4,v 5 } {v 4,v 5 } w 1 ={v 4,v 5 } Итак: 1 = v1,v1, v4,v4,v3,v3, v6v6 2 = v1,v1, v5,v5,v3,v3, v6v6

90 Деревья Опр. Цепью называется незамкнутый маршрут (путь), в котором все ребра различны. Опр. Цепь, в которой все вершины попарно различны называется простой цепью. Опр. Замкнутый маршрут, в котором все ребра попарно различны называется циклом (для ориентированного графа - контуром). Опр. Цикл, в котором все вершины попарно различны называется простым. Опр. Граф называется деревом, если он является связным и не имеет циклов.

91 Свойства деревьев. Следующие утверждения эквивалентны: 1. G – дерево. 2. G – связный граф. 3. G=, |V|=n, |X|=m. Тогда m=n-1 (количество дуг меньше количества вершин на 1). 4. Любые две вершины можно соединить единственной простой цепью. 5. G не содержит циклов, но добавляя к нему любое новое ребро получаем ровно один и при том простой цикл, проходящий через данное ребро. Опр. Если одну из вершин выделить в качестве корня, то дерево называется корневым. Корневое дерево – это граф со следующими свойствами: 1. Имеется в точности одна вершина (корень), в которую не входит ни одно ребро. 2. В каждую вершину, кроме корня входит ровно 1 ребро. 3. Из корня к каждой вершине идет путь и при том единственный. Самостоятельно: Нагруженные графы Длина маршрута (пути) нагруженных графов.

92 Тема6. Математическая логика. Джордж Буль ( ) Родился в семье рабочего. В 12 лет знал латынь, затем овладел греческим, французским, немецким и итальянским языками. В 16 лет уже преподавал в деревенской школе, а в 20 открыл собственную школу в Линкольне. Начиная с 1839 года Буль стал посылать свои работы в новый Кембриджский математический журнал. В 1844 году молодой ученый был награжден медалью Королевского общества за вклад в математический анализ. Вскоре после того как Буль убедился, что его алгебра вполне применима к логике, в 1847 году он опубликовал памфлет «Математический анализ логики», в котором высказал идею, что логика более близка к математике, чем к философии. Эта работа была чрезвычайно высоко оценена английским математиком О. Де Морганом. Благодаря этой работе Буль в 1849 году получил пост профессора математики, несмотря на то, что он даже не имел университетского образования.

93 В 1854 году опубликовал работу «Исследование законов мышления, базирующихся на математической логике и теории вероятностей». Работы 1847 и 1854 годов положили начало алгебре логики, или булевой алгебре. Буль первым показал, что существует аналогия между алгебраическими и логическими действиями, так как и те, и другие предполагают лишь два варианта ответов – истина или ложь, нуль или единица. Он придумал систему обозначений и правил, пользуясь которыми можно было закодировать любые высказывания, а затем манипулировать ими как обычными числами. Булева алгебра располагала тремя основными операциями – И, ИЛИ, НЕ, которые позволяли производить сложение, вычитание, умножение, деление и сравнение символов и чисел. Таким образом, Булю удалось подробно описать двоичную систему счисления. В своей работе «Законы мышления» (1854 г.) Буль окончательно сформулировал основы математической логики. В 1857 году Буль был избран членом Лондонского Королевского общества. Его работы «Трактат о дифференциальных уравнениях» (1859 г.) и «Трактат о вычислении предельных разностей» (1860 г.) оказали колоссальное влияние на развитие математики. В них нашли свое отражение наиболее важные открытия Буля. Сегодня идеи Буля используются во всех современных цифровых устройствах.

94 Математическая логика – наука, изучающая умозаключения с точки зрения их формального строения. Пример1. Умозаключение1. «Все люди смертны. Сократ – человек. Следовательно, Сократ смертен». Умозаключение2. «Все граждане России имеют право на образование. Сидоров – гражданин России. Следовательно Сидоров имеет право на образование». Эти умозаключения построены по одной и той же схеме. Они одинаковы. Схема: Все М – суть Р. S есть М. Следовательно S есть Р.

95 Высказывания Опр. Под высказыванием понимают языковое предложение, о котором имеет смысл говорить истинно оно или ложно. Пример2. «Который час?» - не высказывание «2*10=20»- высказывание «2*х=20» - не высказывание, так как истинность зависит от чего-то неоднозначность Если языковое предложение содержит параметр или условие, то оно не является высказыванием. О высказывании всегда можно однозначно сказать: истинно оно или ложно. Опр. Истина и ложь называются истинностными значениями. При этом, истина интерпретируется как 1, а ложь – как 0. Пример3. «Москва – столица России». - высказывание

96 Операции над высказываниями. Логические операции (связки) Логические операции служат для связи высказываний. Они не выводят за класс высказываний. 1. Отрицание Отрицанием высказывания Р является высказывание, истинное тогда и только тогда, когда высказывание Р ложно. Обозначение: Р или Аналог в языке: не верно что Р; не Р 2. Конъюнкция (связывает 2 высказывания двухместная связка) Обозначение: Р Q; P Q; PQ Аналог в языке: Р и Q (логическое умножение) Конъюнкцией 2-х высказываний Р и Q называется высказывание, истинное тогда и только тогда, когда истины оба высказывания Р и Q. 3. Дизъюнкция (связывает 2 высказывания двухместная логическая оп-ия) Дизъюнкцией 2-х высказываний Р и Q называется высказывание, ложное тогда и только тогда, когда ложны оба высказывания Р и Q. Обозначение: Р Q Аналог в языке: Р или Q

97 4. Импликация (двухместная логическая операция) Импликацией высказываний P и Q называется высказывание, ложное тогда и только тогда, когда Р истинно, а Q – ложно (из истины не может следовать ложь) Обозначение: P Q, P Q, P Q Аналог в языке: из Р следует Q; если Р, то Q 5. Эквиваленция (двухместная логическая операция) Обозначение:P~Q Аналог в языке: P эквивалентно Q Эквиваленцией высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q совпадают (либо они оба истинны, либо оба ложны) Р – посылка импликации Q – заключение импликации

98 Алфавит математической логики Алфавит математической логики состоит из следующих элементов: 1.высказывательные переменные – буквы латинского алфавита, возможно с индексами 2. логические символы: 3. символы скобок: ( ) Опр. Элементы алфавита называются символами алфавита. Опр. Произвольная конечная последовательность символов называется словом. Опр. Слово в алфавите логики высказываний называется формулой, если: 1. это высказывательная переменная (такая формула называется атомарной) 2. х и у формулы, то ( х), (х у), (х у), (х у), (х у) тоже формулы 3. других формул нет Пример4. (х у) z a – слово, но не формула Qне формула Q – формула ((х у) (z ( a)) – формула

99 Соглашение для сокращения записи формул: 1. внешние скобки можно опускать 2. считается, что отрицание относится к наикратчайшей формуле, следующей за ним Замечание. 1. Связка отрицания сильнее любой другой логической операции. 2. Логическая операция конъюнкция сильнее чем любая другая двухместная логическая операция

100 Булевые (двоичные) наборы Обозначение: =( 1, 2,..., n ), где i E 2 Смысл: координаты в n-мерном пространстве Каждая координата может принимать два значения: 0 или 1 n – длина набора i – компоненты (координаты) набора Опр. Совокупностью двоичных наборов называется множество = { = ( 1, 2,..., n ) / i E 2 } - множество всех двоичных наборов Опр. Расстояние между двумя двоичными наборами определяется следующим образом:

101 Пример5.=(1, 0, 1) =(1, 1, 1)=1 Расстояние между двумя двоичными наборами также можно интерпретировать как количество компонентов, в которых наборы различаются. Опр. Набор и называется соседними, если расстояние между ними равно 1. Опр. Если, то наборы называются противоположными. Пример6. = (0, 0, 0) = (1, 1, 1)=n=n Опр. Набор предшествует набору, если i=1..n i i Обозначение: Пример7. (1, 0, 1) (1, 1, 1) так как 1 1, 0 1, 1 1 (1, 0, 1) (0, 1, 0) – несравнимые наборы Опр. Наборы и сравнимы, если либо, либо, в противном случае наборы несравнимы Замечание. Отношение предшествования – отношение частичного порядка

102 Булевые функции Опр. Булевая функция – это произвольная функция область определения которой – декартово произведение Е 2, а область значений – само Е 2, где Е 2 ={0,1} F: E 2 x E 2 x... xE 2 E 2, где Е 2 ={0,1} Обозначим: Е 2 ={0,1} n раз Для конъюнкции n=2, а для отрицания n=1 Способы задания булевых функций 1. Таблица истинности Т(f) x 1, x 2... x n F(x 1, x 2... x n ) F( ) F( ) F( ) а) Стандартное расположение двоичных наборов – каждый двоичный набор рассматривается как запись номера строки в двоичной системе счисления

103 При n=2 x 1, x 2 F(x 1, x 2 ) 00 F(0 0) 10 1F(0 1) 21 0F(1 0) 31 F(1 1) При n=3 x 1, x 2, x 3 F(x 1, x 2, x 3 ) F(0 0 0) F(0 0 1) F(0 1 0) F(0 1 1) F(1 0 0) F(1 0 1) F(1 1 0) F(1 1 1) б) использование корневых деревьев

104 2. Прямоугольная таблица истинности П k,n-k (f) 3. Вектор значений 4. Аналитическая форма записи x 1, x 2... X k, x k+1, …, x n

105 Элементарные функции алгебры логики 1. F(x)=0 2. F(x)=1 3. F(x)=x 4. F(x)= x 5. F(x 1,x 2 )=x 1 x 2 6. F(x 1,x 2 )=x 1 x 2 7. F(x 1,x 2 )=x 1 x 2 xF1F1 F2F2 F3F3 F4F F(x 1,x 2 )=x 1 ~ x 2 X1X1 X2X2 F5F5 F6F6 F7F7 F8F

106 9. F(x 1,x 2 )=x 1 x 2 - сложение по модулю 2 X1X1 X2X2 F9F mod 2=1 (3-2=1) 2 mod 2=0 (2-2=0) 6 mod 2=0 ( =0) 7 mod 2=1 ( =1) 10. F(x 1,x 2 )=x 1 | x 2 - штрих Шеффера (отрицание конъюнкции) X1X1 X2X2 F F(x 1,x 2 )=x 1 x 2 - стрелка Пирса (отрицание дизъюнкции) X1X1 X2X2 F

107 Равносильность формул Опр. Упорядоченный набор высказывательных переменных называется списком формулы А, если все переменные формулы содержатся в этом наборе. Пример8. A=(x 1 x 2 ) x 5 B=(x 2 ( x 4 )) ~ x 8 Опр. Оценкой списка переменных называется сопоставление каждой переменной истинностного значения. Если список содержит n переменных, то число оценок равно Пример9.,,, - оценки списка переменных Опр. Формулы А и В называются равносильными (эквивалентными), если на любой оценке списка переменных они принимают одинаковые значения. Обозначение: А В Равносильность двух формул – отношение эквивалентности

108 Основные равносильности Для любых формул А, В, С справедливы следующие равносильности: 1. Коммутативность a b b a 2. Идемпотентность a а a 3. Ассоциативность a (b с) (a b) с 4. Дистрибутивность a (b с) (a b) (а с) 5. Законы поглощения a а (a b)

109 6. Снятие двойного отрицания а 7. Законы де Моргана (a b) a b 7. Расщипление a (a b) (a b) 8. Взаимосвязь логических связок а ~b (a b) (b a) (a b)( a b) a b a b (a b) a b (a b) ( a b)

110 Способы доказательства 1. С помощью таблицы истинности Пример10.закон де Моргана аb a b (a b) a b a b (a b) a b

111 2. Путем рассуждений Пример11.закон де Моргана (a b) a b А) Предположим, что на некоторой оценке списка переменных левая часть формулы (a b) принимает значение ложь. Следовательно, конъюнкция (a b) принимает значение истина. Таким образом, значения a и b тоже истинны (по определению конъюнкции). Тогда: a – ложь b - ложь Следовательно: a b - ложь Б) Предположим, что на некоторой оценке списка переменных левая часть формулы (a b) принимает значение истина. Дальнейшие рассуждения аналогичны.

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

113 Двойственность Опр. Символы и называются двойственными друг к другу. Опр. Функция F*(x 1 … x n ) называется двойственными к функции F(x 1 … x n ), если в функции F все символы и заменены на двойственные. Замечание. Построить функцию F*(x 1 … x n ), двойственную к функции F(x 1 … x n ), можно только при условии, если в функции F из логических операций присутствуют только, и. Замечание. Двойственным к 1 является 0, а двойственным к 0 является 1, то есть 1*=0; 0*=1. Пример12. F(x 1, x 2 )=(x 1 x 2 ) x 1 F*(x 1, x 2 )=(x 1 x 2 ) x 1 Пример13. F(x 1, x 2 )=1 (x 1 x 2 ) a b= a b F(x 1, x 2 )=0 (x 1 x 2 ) F*(x 1, x 2 )=1 (x 1 x 2 ) Опр. Если F*=F, то функция F называются самодвойственными. Пример14. F(x,y,z)=xy yz xz F*(x,y,z)=(x y) (y z) (x z)= (x y) (x y yz xz z)= = (по дистрибутивному закону + закон поглощения)= xy (1 z) xz yz= =xy yz xz 1

114 Утверждение1.(F*)*=F Лемма. Пусть есть формула А, зависящая от списка переменных и произвольная оценка. Утверждают что: A( )=1 A*( )=0, где оценка - двойственная к оценке, то есть оценка, в которой 1 и 0 заменены на двойственные (1 0,0 1). Доказательство Доказательство будем проводить методом математической индукции. Параметр математической индукции – количество логических символов в А. Пример15. х y - 1 логический символ. х y - 3 логических символа. 1 шаг.Докажем, что утверждение верно при количестве логических символов в А, равном 0. Обозначим: m=0. Тогда, А=х i p – атомарная формула Очевидно, что А*= х i p Пусть А( )=1 х i p ( )=1 s p =1 t p =0 х i p ( )=0 2 шаг. Пусть утверждение леммы верно для любого m / m

115 3 шаг. Докажем, что утверждение леммы верно для m=n. Рассмотрим различные виды формул. 1 случай. А= В Очевидно, что А*= В*. Пусть А( )=1 В( )=0 в В количество логических операций меньше, чем в А, а значит, выполняется шаг2 леммы, то есть В*( )=1 В*( )=0 Так как А*= В*, то для этого случая лемма доказана. Пусть А( )=0 В( )=1 в В количество логических операций меньше, чем в А, а значит, выполняется шаг2 леммы, то есть В*( )=0 В*( )=1 Так как А*= В*, то для этого случая лемма доказана. Обратное утверждение: Пусть А*( )=1 В*( )=0 в В* количество логических операций меньше, чем в А*, а значит, выполняется шаг2 леммы, то есть (В*)*( )=1 (В*)*( )=0 В( )=0 Для этого случая лемма доказана.

116 Пусть А*( )=0 В*( )=1 в В* количество логических операций меньше, чем в А*, а значит, выполняется шаг2 леммы, то есть (В*)*( )=0 (В*)*( )=1 В( )=1 Для этого случая лемма доказана. 2 случай. А= В С Очевидно, что А*= В* С*. Пусть А( )=1 В( )=1 и С( )=1 в В и С количество логических операций меньше, чем в А, а значит, выполняется шаг2 леммы для В и С, то есть В*( )=0 и С*( )=0 (В* С*)( )=0 Так как А*= В* С*, то для этого случая лемма доказана. Пусть А( )=0 …. аналогично Обратное утверждение: Пусть (В* С*)( )=0 В*( )=0 и С*( )=0 в В* и С* количество логических операций меньше, чем в А*, а значит, выполняется шаг2 леммы для В* и С*, то есть В( )=1 и С( )=1 (B С)( )=1 Так как А*= В* С*, то для этого случая лемма доказана.

117 3 случай. А= В С Очевидно, что А*= В* С*. Аналогично случаю 2. Обратить внимание: при «дизъюнкции» союз «и» заменится на «или». Принцип двойственности Если А В, то А* В* Доказательство Пусть А В. - список переменных и для А и для В. Пусть есть произвольная оценка списка переменных. Пусть А*( )=1 (А*)*( )=0, где - двойственная оценка для так как (А*)*=А, то на основании леммы получим В( )=0 В*( )=1 что и требовалось доказать

118 Обратное утверждение: Пусть В*( )=1 Пусть А*( )=0 …. аналогично В*( )=0 (В*)*( )=0 А( )=0 А*( )=1 так как (В*)*=В=А, то на основании леммы получим что и требовалось доказать Пусть В*( )=0 … А*( )=0 аналогично Так как оценка произвольная, то это равенство будет выполняться для любой оценки списка. что и требовалось доказать

119 Дизъюнктивные и конъюнктивные нормальные формы. Опр. Формулу называют элементарной конъюнкцией, если она является конъюнкцией (может быть одночленной) переменных и отрицания переменных. Пример16.Элементарными конъюнкциями являются: 1) х 1 2) х 2 3) х 1 х 2 4) х 1 х 2 Элементарными конъюнкциями не являются: 1) х 1 ( х 2 х3) 2) х 1 ( х 2 х3) Опр. Формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (может быть одночленной) элементарных конъюнкций. Пример17. Формулами, находящимися в ДНФ являются: 1) х 1 2) х 2 3) х 1 х 2 4) (х 1 х 2 х 2 ) (х 1 х 5 ) элементарная конъюнкция

120 Опр. Формулу называют элементарной дизъюнкцией, если она является дизъюнкцией (может быть одночленной) переменных и отрицания переменных. Пример18. Элементарными дизъюнкциями являются: 1) х 1 2) х 2 3) х 1 х 2 4) х 1 х 2 Элементарными дизъюнкциями не являются: 1) х 1 ( х 2 х3)2) х 1 ( х 2 х3) Опр. Формула находится в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией (может быть одночленной) элементарных дизъюнкций. Пример19.Формулами, находящимися в КНФ являются: 1) х 1 2) х 2 3) х 1 х 2 4) (х 1 х 2 х 2 ) (х 1 х 5 ) элементарная дизъюнкция

121 Замечание. ДНФ и КНФ не являются однозначно определенными формулами. Пример20. х 1 (х 2 х 3 ) - ДНФ х 1 (х 2 х 3 ) (х 1 х 2 ) (х 1 х 3 ) (х 1 х 1 ) (х 1 х 3 ) (х 2 х 1 ) (х 2 х 3 ) - ДНФ Совершенные дизъюнктивные нормальные формы. Опр1. Пусть есть формула А зависит от списка переменных. А находится в совершенной дизъюнктивной нормальной форме (СДНФ), если: 1. А - ДНФ 2. Каждый дизъюнктивный член формулы А является k-членной конъюнкцией, причем на l -ом месте (1 l k) обязательно стоит переменная x i l или ее отрицание. 3. Все дизъюнктивные члены попарно различны. Структура: ( ) ( )

122 а) х 1 (х 1 х 2 ) 1. это ДНФ 2. х 1 – не двухместный дизъюнктивный член Таким образом, это не СДНФ б) (х 1 х 2 ) (х 2 х 1 ) 1. это ДНФ 2. все члены ДНФ – 2-х членные конъюнкции, но в (х 2 х 1 ) на первом месте стоит не х 1, а х 2. Таким образом, это не СДНФ в) (х 1 х 2 ) (х 1 х 2 ) 1. это ДНФ 2. все члены ДНФ – 2-х членные конъюнкции и на первом месте стоит х 1, а на втором х дизъюнктивные члены не попарно различны Таким образом, это не СДНФ Пример21.Рассмотрим ДНФ для F(x 1,x 2 )

123 г) (х 1 х 2 ) ( х 1 х 2 ) 1. это ДНФ 3. дизъюнктивные члены попарно различны Таким образом, это СДНФ 2. все члены ДНФ – 2-х членные конъюнкции и на первом месте стоит х 1 или ее отрицание, а на втором х 2 или ее отрицание. Опр2. Формула А находится в совершенной дизъюнктивной нормальной форме (СДНФ), если она представима в виде: где

124 Опр1. Пусть есть формула А зависит от списка переменных. А находится в совершенной конъюнктивной нормальной форме (СКНФ), если: Совершенные конъюнктивные нормальные формы. 1. А - ДНФ 2. Каждый конъюнктивный член формулы А является k-членной дизъюнкцией, причем на l -ом месте (1 l k) обязательно стоит переменная x i l или ее отрицание. 3. Все конъюнктивные члены попарно различны. Опр2. Формула А находится в совершенной конъюнктивной нормальной форме (СКНФ), если двойственная к А формула А* находится в СДНФ. Структура: ( ) ( )

125 Опр3. Формула А находится в совершенной конъюнктивной нормальной форме (СКНФ), если она представима в виде: где Пример22. а) (х 1 х 2 ) (х 1 х 2 х 3 ) не СКНФ, т.к. первый конъюнктивный член не является 3-х членной дизъюнкцией б) (х 1 х 2 х 3 ) (х 1 х 2 х 3 ) - СКНФ в) (х 3 х 2 х 1 ) (х 1 х 2 х 3 ) не СКНФ, т.к. в первом конъюнктивном члене на 1-ом месте должна стоять х 1, на втором – х 2, а на третьем – х 3. г) (х 1 х 2 х 3 ) - СКНФ

126 Теорема о приведении к ДНФ. Для любой формулы А можно найти (существует) формулу В, находящуюся в ДНФ, такую что, А В. (В называется ДНФ формулы А). Доказательство 1 шаг. Для формулы А надо построить формулу А 1, такую что: АА 1 и не содержит никаких логических операций (~, т.д.) кроме, и. Это можно сделать, используя основные равносильности. 2 шаг. Докажем, что для формулы А 1 можно построить формулу А 2, такую что: А 2А 1 и отрицание в ней содержится только перед переменными (формула с тесными отрицаниями). Доказательство будем проводить методом математической индукции по числу логических символов в А 1. 1 этап. Обозначим через n – количество логических символов в А 1. Возьмем n=0. А 1 =x i А 2 =x i А 1 А 2 – утверждение верно 2 этап. Предполагаем, что утверждение верно для количества логических переменных меньшего n. 3 этап. Докажем, что утверждение верно для формулы А 1 с количеством логических операций равным n.

127 Рассмотрим случаи для разных видов А 1. а) А 1 =В 1 С 1 В В 1 логических операций меньше, чем в А 1, а следовательно меньше n. Поэтому по шагу2 будет существовать формула В 2, такая что В 2 В 1 и в ней будут только тесные отрицания. Аналогично, существует С 2 С 1 и С 2 – формула с тесными отрицаниями. Т.о. А 1 В 2 С 2, следовательно А 1 может быть приведена к формуле с тесными отрицаниями. б) А 1 =В 1 С 1 Доказательство аналогично в) А 1 = В 1 А 1 В 1 В В 1 логических операций меньше, чем в А 1, а следовательно меньше n. Поэтому по шагу2 будет существовать формула В 2,являющаяся ДНФ и такая что В 2 В 1. Т.о. А 1 В 2, следовательно В 2 будет ДНФ и для А 1 г) А 1 = (В 1 С 1 ) А 1 В 1 С 1 В В 1 и С 1 логических операций меньше, чем в А 1, а следовательно меньше n. Поэтому по шагу2 будет существовать формула В 2,являющаяся ДНФ и такая что В 2 В 1 и будет существовать формула С 2,являющаяся ДНФ и такая что С 2 С 1.

128 Т.о. А 1 В 2 С 2, следовательно А 1 может быть приведена к формуле с тесными отрицаниями. д) А 1 = (В 1 С 1 ) Доказательство аналогично Утверждение доказано 3 шаг. Формула А 2 построена из переменных и их отрицаний с помощью многочленной конъюнкции или дизъюнкции. Применив дистрибутивный закон (если это необходимо), преобразуем формулу А 2. Полученная формула будет являться ДНФ. Теорема доказана. Пример23. Построить ДНФ ( (х 1 х 2 ) (х 2 х 1 )) – не ДНФ, т.к. дизъюнкция применяется не к элементарным конъюнкциям. 1 шаг. Формула состоит только из,,. 2 шаг. Получим тесные отрицания. Для этого 2 раза применим закон де Моргана: ( х 1 х 2 ) ( х 2 х 1 ) – не ДНФ, т.к. это не дизъюнкция конъюнкций. Применим дистрибутивный закон: ( х 1 х 2 ) ( х 1 х 1 ) (х 2 х 2 ) (х 2 х 1 ) - ДНФ

129 Теорема о приведении к КНФ. Для любой формулы А можно найти (существует) формулу В, находящуюся в КНФ, такую что, А В. (В называется КНФ формулы А). Доказательство 1 вариант. Аналогично доказательству теоремы о приведении к ДНФ. 2 вариант. На основе принципа двойственности. Для формулы А существует формула А 1, такая что: АА 1 и не содержит никаких логических операций (~, т.д.) кроме, и. Для формулы А* 1 (в силу теоремы о приведении к ДНФ) существует формула В 1, такая что: В 1А* 1 и В 1 – ДНФ. По определению В* 1 – КНФ. В 1 * (А 1 *)* А 1 (на основе принципа двойственности) В силу того, что АА 1 получим, что В 1 * А. Теорема доказана. Следовательно, В 1 * будет являться КНФ для А.

130 Пример24. Построить КНФ (х 1 х 2 ) ( х 1 х 3 ) Применим следующую равносильность: а ~b (a b)( a b) аb Получим: ((х 1 х 2 ) ( х 1 х 3 )) ( (х 1 х 2 ) ( х 1 х 3 )) (х 1 х 2 х 1 х 3 ) ( ( х 1 х 2 ) ( х 1 х 3 )) (х 1 х 1 х 2 ) (х 1 х 1 х 3 ) (х 2 х 1 х 2 ) (х 2 х 1 х 3 ) ( х 1 х 1 х 2 ) ( х 1 х 1 х 3 ) (х 3 х 1 х 2 ) (х 3 х 1 х 3 ) (1 х 2 ) (х 1 х 3 ) (1 х 1 ) (х 2 х 1 х 3 ) ( х 1 х 2 ) (1 х 3 ) (х 3 х 1 х 2 ) (1 х 1 ) (х 1 х 3 ) (х 2 х 1 х 3 ) ( х 1 х 2 (х 3 х 1 х 2 )

131 Теорема о приведении к СДНФ. Пусть формула А зависит от списка переменных и А 0. Тогда существует формула В, которая зависит от списка переменных, А В и В – находится в СДНФ. Доказательство В последовательности доказательства будет лежать определение СДНФ. По определению, существует формула А 1 А и при этом А 1 – ДНФ (по теореме о приведении к ДНФ). Рассмотрим дизъюнктивные члены А 1. 1 случай. Пусть в элементарные конъюнкции входят x i p и x i p. Если это единственная элементарная конъюнкция, то она является тождественной ложью. Следовательно, А 0, что противоречит условию. Следовательно, существуют другие элементарные конъюнкции и при этом: А (x i p x i p ) D D 0 причем, в D нет одновременного вхождения x i p и x i p.

132 2 случай. Пусть в элементарные конъюнкции x i p и x i p включаются несколько раз. Тогда можно воспользоваться свойством: (x i p x i p ) x i p 3 случай. После 1 и 2 случаев, элементарные конъюнкции будут содержать какую-либо переменную не более одного раза. Возможны следующие варианты: а) Конъюнкция С содержит x i p и не содержит x i p б) Конъюнкция С содержит x i p и не содержит x i p в) Конъюнкция С не содержит x i p и не содержит x i p В случаях а) и б) определение СДНФ не нарушается, а в случае в) получается, что в конъюнкции не хватает одной переменной, значит ее надо ввести в нее. Сделать это можно с помощью закона расщепления: С=С x ip С x ip Закон расщепления необходимо применить столько раз, пока не будут выполняться а) и б). где С x ip – исходная конъюнкция, в которую добавлена переменная x i p С x ip – исходная конъюнкция, в которую добавлена переменная x i p

133 4 случай. На основе закона коммутативности, переставляем в каждой элементарной конъюнкции переменные таким образом, чтобы l -ом месте (1 l k) обязательно стояла переменная x i l или ее отрицание. Если в полученной формуле несколько раз повторяется какая-либо из элементарных конъюнкций, то необходимо применить закон идемпотентности. Теорема доказана. Пример25. Построить СДНФ х 1 х 3 х 2 х 1 х 3 х 2 х 1 х 3 х 2 х 2 х 1 х 2 х 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 х 1 х 2 х 3 х 1 х 2 х 3 х 1 х 2 х 3 - СДНФ

134 Теорема о единственности СДНФ. Если В 1 и В 2 – СДНФ для А 1, то В 1 и В 2 могут отличаться только порядком своих дизъюнктивных членов. Доказательство Существует теорема (1-ая теорема о представлении булевой функции): Пусть F(x 1, x 2,…,x k ) – k-местная булева функция (k 1). Если F 0, то существует такая формула G, зависящая от списка переменных и находящаяся в СДНФ относительно этого списка, что G выражает собой функцию F. Формула G определена однозначно с точностью до перестановки дизъюнктивных членов. Докажем вторую часть теоремы о единственности. Пусть F 1 и F 2 – две формулы, выражающие функцию F, находящиеся в СДНФ относительно списка переменных и существенно различные, то есть либо в F 1 есть элементарные конъюнкции, не содержащиеся в F 2, либо наоборот. Рассмотрим, например, первый случай. Если- элементарная конъюнкция, содержащаяся в F1, но не в F2, то она будет ассоциирована с оценкой.

135 Любая элементарная конъюнкция, содержащаяся в F 2 будет ассоциирована с некоторой другой оценкой. Поэтому на оценке любая такая конъюнкция примет значение 0, а следовательно и вся F 2 примет значение 0. С другой стороны, на этой оценке конъюнкция примет значение 1, а следовательно и вся F1 примет значение 1. Тогда F 1 и F 2 будут выражать собой различные булевы функции. Таким образом, если А выражает булеву функцию F(x 1, x 2,…,x k ), то любая СДНФ для А должна (в силу равносильности) выражать собой ту же функцию. Поэтому СДНФ В 1 и В 2 должны совпадать с точностью до порядка элементарных конъюнкций. Теорема доказана.

136 Теорема о приведении к СКНФ. Пусть формула А зависит от списка переменных и А 0. Тогда существует формула В, которая зависит от списка переменных, А В и В – находится в СКНФ. Теорема о единственности СКНФ. Если В 1 и В 2 – СКНФ для А 1, то В 1 и В 2 могут отличаться только порядком своих конъюнктивных членов. Существует теорема (2-ая теорема о представлении булевой функции): Пусть F(x 1, x 2,…,x k ) – k-местная булева функция (k 1). Если F 1, то существует такая формула G, зависящая от списка переменных и находящаяся в СКНФ относительно этого списка, что G выражает собой функцию F. Формула G определена однозначно с точностью до перестановки конъюнктивных членов.

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

138 Полнота и замкнутость. Обозначение: Р 2 – множество всех булевых функций. Пусть есть некоторое конечное множество булевых функций: К 0 ={F(х 1,..., х k1 ), F(х 1,..., х k2 ),..., F(х 1,..., х km )}, где F i (х 1,..., х ki ) Р 2 Опр. Функция F Р 2, называется суперпозицией первого ранга функций F 1, F 2,..., F m, где F i Р 2, если F может быть получена одним из следующих способов: 1. переименованием x j в F i F=F i (x 1,...,x j-1,y,x j+1,...,x ki ) где y может быть любой (может совпадать с любой переменной). 2. подстановкой некоторой функции F l (1 l m) вместо x j в функции F i K 0 F=F i (x 1,...,x j-1,Fl (x 1,...x kl ),x j+1,...,x ki ) Все суперпозиции первого ранга обозначаются К 1. Опр. Класс функций, получающийся из функций класса K r-1 суперпозиций r-1 ранга, называется классом функций К r суперпозиций r ранга. Опр. Суперпозицией функций из класса К 0 называется функция, входящая в один из классов К r.

139 Опр1. Система функций {F 1, F 2,..., F i...},где F i Р 2 называется полной, если любая булева функция может быть представлена в виде формулы через функции этой системы, (то есть с помощью суперпозиции). Пример26. Пусть К 0 ={ x 1 x 2 } – в системе одна функция Построить суперпозицию. 1.х 2 х 1 Получим: х 1 х 1 =1 Т.о. тождественная единица является суперпозицией над К 0 2. х 1 х 2 Получим: х 2 х 2 =1 – аналогично случаю второе правило задействовать невозможно, так как функция одна. Но мы можем получить К 2 х 1 1Получим: 1 х 2 =0 х 2 =х 2 Пример само Р 2 - полная система: 2. { х 1 х 2 х 2 х 1 х 2 } - полная система: 3. {0,1} - не полная система:

140 Теорема. Пусть система функций {F 1, F 2,..., F n },где F i Р 2 является полной и любая функция из F i может быть выражена через g 1...g l (с помощью операции суперпозиции). Тогда система {g 1...g l } тоже является полной. Доказательство. Возьмем произвольную функцию h P 2. Так как {F 1, F 2,..., F n } – полная, то h=C(F 1, F 2,..., F n ), где С – суперпозиция По условию: F 1 =C 1 (g 1...g l ) F 2 =C 2 (g 1...g l ).... F n =C n (g 1...g l ) Подставим в h эти суперпозиции. Получим: h=C(C 1 (g 1...g l ), C 2 (g 1...g l ),..., C n (g 1...g l )). Таким образом, мы получили, что h – произвольная функция и она может быть записана через функции системы {g 1...g l }. Следовательно по определению {g 1...g l } - полная система. теорема доказана.

141 Пример28. 1.{ } - полная система. Докажем полноту системы { } F 1 = F 2 = F 3 = g 1 = g 2 = F 1 =g 1 F 2 =x 1 x 2 = x 1 x 2 (закон де Моргана) F 3 =g 2 Таким образом эта система полная. 2. { } - аналогично полная система 3. { } – полная система, так как х=х 1 4. { } - полная система

142 Полином Жегалкина. Опр. Полиномом Жегалкина называется многочлен, являющийся суммой констант и различных многочленов, в которых каждая из переменных входит не выше чем в первой степени. В первой степени, так как х 2 =х х=х Суммирование происходит по наборам, в которых i j различны. Теорема Жегалкина. Каждая булева функция может быть представлена полиномом Жегалкина, причем единственным образом. Способы построения полинома Жегалкина. 1.элементарные преобразования x y = x y) =(x 1)(y 1) 1=xy x y 1 1=xy x y 2. способ неопределенных коэффициентов x y = axy bx cy d – общий вид полинома Жегалкина a, b, c, d – неопределенные коэффициенты.

143 xy x y F(0, 0)=a*0*0 b*0 c*0 d=0 d=0 F(0, 1)=a*0*1 b*0 c*1 0=1 c=1 F(1, 0)=a*1*0 b*1 1*0 0=1 b=1 F(1, 1)=a*1*1 1*1 c*1 0=0 a=1 Таким образом: x y = xy x y Опр. L – класс линейных функций, то есть функций представимых в виде: F(x n )=a 0 a 1 x 1 a 2 x 2... a n x n, где a i E 2 Пример , 1, x, x, x 1 x 2 линейные функции 2. x 1 x 2, x 1 x 2 – не линейные функции Чтобы выяснить является ли функция линейной нужно построить полином Жегалкина.

144 Опр. Пусть есть А Р 2 (А – подмножество Р 2 ). Замыканием А – [А] – называется множество всех булевых функций, представимых в виде формул через функции множества А (совокупности всех суперпозиций функций из А). Свойства замыканий. 1. [A] A само множество А содержится в [A] 2. [[A]] = A 3. Если A1 A2, то [A1 [A2] 4. [A1 A2] [A1] [A2] Опр. Класс функций называется замкнутым, если он совпадает со своим замыканием: [А]=А Пример [P 2 ]=P 2 2. A={1, x 1 x 2 } [A]=L A – незамкнутый класс Опр2. А – полная система, если [А]=Р 2 P 2 – замкнутый класс

145 Важнейшие замкнутые классы. 1.Т 0 – класс функций, сохраняющих 0 Опр. F P 2, F T 0 F(0... 0)=0 Пример , х, х 1 х 2, х 1 х 2, х 1 х 2 Т , х Т 0 Утверждение. Т 0 – замкнутый класс. Доказательство Надо доказать: замыкание (суперпозиция) класса Т 0 совпадает с самим классом Т 0. G=F(F 1...F m ) F i Т 0 (i=1..m) F Т 0, то G Т 0 G(0...0)=F(F 1 (0...0), F 2 (0...0),..., F m (0...0))=F(0...0)=0 утверждение доказано

146 2. Т 1 – класс функций, сохраняющих 1 Опр. F P 2, F T 1 F(1... 1)=1 Пример , х, х 1 х 2, х 1 х 2, х 1 х 2 Т , х Т 1 Утверждение. Т 1 – замкнутый класс. аналогично доказательству для Т 0 Доказательство 3. S – класс самодвойственных функций Опр. F P 2, F S F=F* Пример х 1 x 2 x 3 S 2. x, х S

147 Способы выявления самодвойственности. 1. построить F* и сравнить совпадает ли она с F 2. по таблице истинности F*= F( x 1,..., x n ) F S F= F( x 1,..., x n ) x1x1 x2x2 x3x3 F=x 1 x 2 x 3 F*

148 Утверждение. S – замкнутый класс. Доказательство Надо доказать: замыкание (суперпозиция) класса S совпадает с самим классом S. Рассмотрим функцию G=F(F 1...F m ) – суперпозицию самодвойственных функций. То есть: F i S (i=1..m) Таким образом, надо показать, что если F S, то и G S. G*=F*(F* 1, F* 2,..., F* m )=F(F 1, F 2,..., F m )=G утверждение доказано Таким образом, в силу произвольности выбора функции F, мы доказали, что замыкание (суперпозиция) класса S совпадает с самим классом S. 4. L – класс линейных функций

149 5. М – класс монотонных функций Опр. F P 2, F М, из того, что F( ) F( ) Пример34. 1). 0, 1, х, х 1 х 2, х 1 х 2 М 2). х1 х2, х М сравнение наборов сравнение функций Способы выявления монотонности. 1.Эквивалентные преобразования. Если функция содержит только и, то она монотонна. 2. с помощью таблицы истинности Есть вектор Делим его пополам. Получаем два вектора: Если первый вектор предшествует второму, то каждый из векторов делим пополам и снова сравниваем. Повторяем эти действия до тех пор, пока размерность векторов не станет равной 1. Если на всех этапах имело место отношение предшествования первого вектора второму, то функция монотонна, иначе – не монотонна.

150 Пример35. xyF ( ) 1. (0 1) (1 0) F M 2. = ( ) ( ) ( ) (0 1) (0 1) (1 1) (0) (1) (1) F M

151 Утверждение. M – замкнутый класс. Доказательство Надо доказать: замыкание (суперпозиция) класса M совпадает с самим классом M. Рассмотрим функцию G=F(F 1...F m ) – суперпозицию монотонных функций. То есть: F i М (i=1..m) Таким образом, надо показать, что если F М, то и G М. Пусть G определена на наборе переменных = Тогда: будет определена на наборе и т.д. будет определена на наборе Возьмем две оценки списка переменных и обозначим их и Причем: Аналогичным образом получим наборы …

152 утверждение доказано Таким образом, в силу произвольности выбора функции F, мы доказали, что замыкание (суперпозиция) класса М совпадает с самим классом М. Кроме того,… Таким образом, в силу того, что функции F монотонные и получим: … Тогда, если составить наборы из соответствующих значений функций, то будет иметь место следующее соотношение: А в силу того, что функция F монотонная, получим, что Таким образом, G М.

153 Таблица Поста Дана система функций А={F 1, F 2, …, F k } Таблица Поста: T0T0 T1T1 SLM F1F1 F2F2 … FkFk На пересечении класса и функции ставится «+», если функция принадлежит классу и «-», если не принадлежит. Критерий Поста Для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти важнейших замкнутых классов. (чтобы в каждом столбце таблицы Поста был хотя бы один «-»)

154 Пример36. A={x y, x y,1} Является ли данная система полной? xyF1F1 F2F2 F3F3 F1*F1*F2*F2*F3*F3* T0T0 T1T1 SLM F1F1 F2F2 F3F Система функций является полной

155 Опр. Система функций из замкнутого класса А называется полной в А, если ее замыкание совпадает с А. Опр. Пусть дан А – замкнутый класс. Возьмем В={F 1, …, F s …} – систему функций из А, то есть B A. В будет базисом А, если она полна в А, а любая ее собственная подсистема не является полной А. [B]=A, а B / B B [B]A Пример37. 1) {x 1 x 2, 0, 1, x 1 x 2 x 3 } – базис в Р 2 2) {0, 1, x 1 x 2, х 1 x 2 } – базис в М Замечание. Система функций называется базисом, если ее полнота теряется при удалении хотя бы одной функции.

156 Алгоритм построения базисов 1. Построить таблицу Поста. 2. По таблице Поста составить КНФ, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве дизъюнктивных членов символы тех функций, которые не входят в класс, соответствующий столбцу. 3. Применяя дистрибутивный закон, законы идемпотентности и поглощения привести КНФ к ДНФ. 4. В качестве базисов принимаются подмножества функций, входящие в элементарные конъюнкции в полученной ДНФ. Теорема1. Каждый замкнутый класс в Р 2 имеет конечный базис. Теорема2. Мощность множества замкнутых классов в Р 2 счетно.

157 Пример38.Построить базисы для системы функций. T0T0 T1T1 SLM F1F F2F F3F F4F (F 3 ) (F 1 F 2 F 3 ) (F 2 F 4 ) (F 1 F 2 ) (F 1 F 2 F 3 ) T0T0 T1T1 LSM = F 3 (F 2 F 4 ) (F 1 F 2 ) = {раскроем скобки} а bа b = F 3 ((F 2 (F1 F2) F 4 (F 1 F 2 ) ) = = F 3 (F 2 F 4 F 1 F 4 F 2 ) = а b F 3 (F 2 (1 F 4 ) F 4 F 1 ) = 1 F 3 (F 2 F 4 F 1 ) =F 3 F 2 F 4 F 1 F 3 ДНФ B 1 ={F 3,F 2 }B 2 ={F 1,F 3,F 4 } = {по закону поглощения}

158 Лемма о несамодвойственной функции. Если функция F(x 1, x 2, …,x n ) S, то из нее путем подстановки х и х можно получить несамодвойственную функцию одного переменного – константу. Доказательство Если F S, то существует двоичный набор ( 1, 2, …, n ) / F( x 1,..., x n ) = F(x 1,...,x n ) Рассмотрим (подобранные) функции, которые конструируются следующим образом:, где Рассмотрим (х)=F( 1 (x), …, n (x)). Рассмотрим значения (х) при х=0 и х=1. (0)=F( 1 (0), …, n (0)) = (1) Если i =0, то 0 0 = 0=1 Если i =1, то 0 1 = 0 по (1) = = F( 1,..., n )=F( 1,..., n ) Если i =0, то 1 0 = 1=0 Если i =1, то 1 1 = 1 по (1) = = = F( 1 (1), …, n (1)) = (1) Т.о. мы доказали, что функция является константой. лемма доказана.

159 Лемма о немонотонной функции. Если функция F(x 1, x 2, …,x n ) М, то из нее путем подстановки 0, 1, х можно получить не монотонную функцию одного переменного – x. Доказательство 1 этап. Покажем, что если F М, то существуют два двоичных набора /, и 1 случай. 2 случай. Доказывать ничего не надо. Это значит, что Покажем, что можно выбрать другие наборы и они будут соседними. Они различаются в t компонентах (которые могут стоять и не подряд) и при этом имеет место отношение предшествования. Значит в наборе будут 0, а в наборе Между мы можем взять (t-1) промежуточных набора, причем таких, что и

160 значит, хотя бы для одной пары промежуточных наборов (обозначим их ) будет выполняться неравенство: Пусть данные наборы имеют соседство по i-й координате. N=i 2 этап. Рассмотрим функцию, которая конструируется следующим образом: (х)= F( 1,..., i-1, x, i+1, …, n ). Рассмотрим значения (х) при х=0 и х=1. (0)= F( 1,..., i-1, 0, i+1, …, n ) = = F( 1,..., i-1, 1, i+1, …, n )= (1) (в силу наших обозначений) Учитывая, что мы работаем с булевыми функциями, это становится возможным, только если: (0)= 1, а (1)=0. Следовательно, (х)= х. лемма доказана.

161 Лемма о нелинейной функции. Если функция F(x 1, x 2, …,x n ) L, то из нее путем подстановки 0, 1, х можно получить не линейную функцию– х 1 х 2. Доказательство Для любой функции можно построить полином Жегалкина, притом единственный. Построим его для функции F. Так как F L, то в полиноме найдется член, содержащий не менее двух множителей. Без ограничения общности можно считать, что среди этих множителей присутствуют х 1 и х 2. Тогда можно преобразовать полином следующим образом: Очевидно, что F 1 (x 3 …x n ) 0, так как F L. Выберем такой двоичный набор ( 3, 4, …, n ), на котором F 1 =1. Пусть функция (х 1,x 2 )= F(x 1,x 2, 3, …, n ) = x 1 x 2 x 1 x 2.,, E2={0,1}

162 Рассмотрим функцию, которая конструируется следующим образом: (х 1,x 2 )= (x 1, x 2 ). Подставим в функцию формулу для функции. (х 1,x 2 )=(x 1 )(x 2 ) (x 1 ) (x 2 ) = = x 1 x 2 x 1 x 2 x 1 x 2 = (a a=0) =x 1 x 2 = x 1 x 2 лемма доказана. Критерий Поста Для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти важнейших замкнутых классов. Докажем критерий Поста.

163 Доказательство критерия Поста. Необходимость. Дано: система полна Надо доказать: система не содержится целиком ни в одном из 5 важнейших замкнутых классов Если система А полна, то по определению ее замыкание совпадает с Р 2 : [A]=P 2. Будем проводить доказательство методом от противного. Пусть А содержится целиком в одном из 5 важнейших замкнутых классов. Следовательно: A R, где R {T 0, T 1, L, S, M} Тогда, [A] [R] по 3 свойству замыканий || P2P2 R P 2 R мы получили противоречие, следовательно наше предположение не верно. необходимость доказана.

164 Достаточность. Дано: система не содержится целиком ни в одном из 5 важнейших замкнутых классов Надо доказать: система полна Доказательство будем проводить используя способ сведения системы к заведомо полной системе. Для этого будем опираться на ранее доказанную соответствующую теорему. Пусть система А целиком не содержится ни в одном из 5 важнейших замкнутых классов. Тогда из нее можно выделить подсистему А А, содержащую не более 5 функций, которая также обладает этим свойством. Для этого возьмем в А функции F i, F j, F k, F m, F l, которые не принадлежат соответственно классам T 0, T 1,S, M, L. Таким образом, положим А={T 0, T 1, L, S, M} и F i T 0, F j T 1, F k S, F m M, F l L. Без ограничения общности можно считать, что все эти функции зависят от одних и тех же переменных: х 1 …х n.

165 Схема доказательства. F i, F j, F k, F m, F l x, х y (полная система) {F i, F j, F k, F m, F l } – полная система Построение x, х y I. F i T 0, F j T 1, F k S константы 0 и 1 II. 0, 1, F m M x III. 0, 1, x, F l L х y

166 I этап. У нас есть F i T 0, F j T 1, F k S. F i (0…0)=1 F i (1…1)=? 1 случай.F i (1…1)=1 Построим функцию (х)=F i (x,…,x) Рассмотрим значения (х) при х=0 и х=1. (0)=F i (0,…,0)=1 (1)=F i (1,…,1)=1 Функция имеет одно и то же значение, значит мы построили константу. Константа 0 получается аналогично из F j. 2 случай.F i (1…1)=0 Построим функцию (х)=F i (x,…,x) Рассмотрим значения (х) при х=0 и х=1. (0)=F i (0,…,0)=1 (1)=F i (1,…,1)=0 Функция (х)= x Используя F k и применяя лемму о несамодвойственной функции мы можем построить константу.

167 II этап. На основе 0, 1 (из шага I) и F m M мы можем построить x в силу леммы о немонотонной функции. III этап. На основе 0, 1, x и F l L мы можем построить х y в силу леммы о нелинейной функции. В силу произвольности выбора функций F i, F j, F k, F m, F l мы показали, что все функции из А могут быть представлены через x и х y. На основании соответствующей теоремы мы доказали полноту системы А. критерий доказан.

168 Тема7. k-значная логика. В 1920 – 1922 гг. вышли публикации Поста и Лукасевича по 3-х и k-значной логике. В середине 20-х гг k-значная логика сформировалась как раздел математики. k-значная логика вводится как обобщение 2-значной логики, но при этом: 1. в k-значной логике сохраняются многие свойства и результаты 2-значной 2. в k-значной логике имеются свойства принципиально отличающиеся от 2- значной логики.

169 Опр. Булевая функция – это произвольная функция область определения которой – декартово произведение Е 2, а область значений – само Е 2, где Е 2 ={0,1} F: E 2 x E 2 x... xE 2 E 2, где Е 2 ={0,1} Обозначим: Е 2 ={0,1} Определения функций: n раз Опр. Функция k-значной логики– это произвольная функция область определения которой – декартово произведение Е k, а область значений – само Е k, где Е k ={0,1, …,k-1} F: E k x E k x... xE k E k, где Е k ={0,1, …,k-1} Обозначим: Е k ={0,1, …,k-1} n раз F P 2 – булевая функция F P k –функция k-значной логики

170 Способы задания функций k-значной логики 1. Таблица истинности Т(f) x 1, x 2... x n F(x 1, x 2... x n ) F( ) F( )..... k n -1(k-1)...(k-1)F((k-1)...(k-1)) а) Стандартное расположение наборов – каждый набор рассматривается как запись номера строки в k системе счисления Другие способы задания функции, понятие равносильности, операция суперпозиции, замыкание, замкнутый класс, базис для функций k-значной логики аналогичны этим понятиям в 2-значной логике.

171 Элементарные функций k-значной логики 1. Константы: 0, 1, … k Отрицание Поста (циклический сдвиг) х=х+1 (сложение осуществляется по модулю k) 3. Отрицание Лукасевича (операция зеркального отражения) ~ х=(k-1)-x Например: ~0=k-1 4. Характеристическая функция 1 рода. 5. Характеристическая функция 2 рода.

172 6. Функция min(x 1,x 2 ) (первое обобщение конъюнкции) Также эта функция может обозначаться: х 1 х 2 ; х 1 &х 2 7. Второе обобщение конъюнкции х 1 ·х 2 (по модулю k) 8. Функция max(x 1,x 2 ) (обобщение дизъюнкции) Также эта функция может обозначаться: х 1 х 2 9. Сложение по модулю k х 1 +х 2 (по модулю k) 10. Импликация

173 11. Усеченная разность x y 12. Разность по модулю 13. Функция Вебба V k (x,y)=max(x,y)+1 (по модулю k)

174 Основные тождества k-значной логики 1. Ассоциативность ((х 1 х 2 ) х 3 )=(х 1 (х 2 х 3 )) Обозначим через - min, max,+, · 2. Коммутативность х 1 х 2 =х 2 х 1 3. Идемпотентность max (x,x) =x min (x,x) =x 4. Дистрибутивность max (min (x, y), z) = min ( max (x, z), max (y, z)) min (max (x, y), z) = max ( min (x,z ), min (y, z)) 5. Аналоги правилам де Моргана min ( x, y)= max (x, y) max ( x, y)= min (x, y)

175 6. Правило спуска J «вглубь» формулы Пример тождеств, не имеющих места в k-значной логике 1. ( x) x 2. min (x 1,x 2 ) max ( x 1, x 2 ) (хотя ~(~x) = x)

176 Первая форма (аналог СДНФ) Вторая форма Отличия k-значной логики от 2-значной логики 1. В k-значной логике представление функции полиномом возможно тогда и только тогда, когда k – простое число. 2. В Р k существуют замкнутые классы, не имеющие конечного базиса. 3. Мощность множества всех замкнутых классов Р k равна континууму.

177 Мы познакомились с двумя функциональными системами и определенными в них операциями: 1. Р 2 – булева алгебра – система функций алгебры логики с операцией суперпозиции F: E 2 x E 2 x... xE 2 E 2, где Е 2 ={0,1} n раз 2. Р k – k-значная логика – система функций k-значной логики с операцией суперпозиции F: E k x E k x... xE k E k, где Е k ={0,1, …,k-1} n раз Усложнив функциональные объекты, можно получить другие системы. 3. Р N – счетнозначная логика – система функций счетнозначной логики с операцией суперпозиции F: E N x E N x... xE N E N, где Е N ={0, 1, 2, 3, …} – расширенный натуральный ряд n раз 4. Р С – континуумзначная логика – система функций континуумзначной логики с операцией суперпозиции F: E С x E С x... x E С E С, где Е С ={ / R, [0,1]} n раз

178 Тема8. Детерминированные (автоматные) функции. Данные функции являются разновидностью континуумзначной логики. Вместо действительных чисел из сегмента [0,1] возьмем - множество всех k-значных последовательностей Введем функции, определенные на наборах ( 1, 2, …, n ), где i и принимающие значения из Таким образом, эти функции преобразуют наборы k-значных последовательностей в k-значные последовательности. где Е k ={0,1, …,k-1}, k 2 Е l ={0,1, …, l -1}, l 2 - обозначение того, что последовательность бесконечна

179 Обозначения: - входная последовательность - выходная последовательность - совокупность всех таких функций - если k = l - если n = m =1 Замечание. Для введенных таким образом функций табличное задание неприемлемо, так как множество (а следовательно, и множество «строк» таблицы) имеет континуальную мощность. Отсюда же следует, что мощность множества всех функций, зависящих от х 1, х 2, …, равна гиперконтинууму. Учитывая это обстоятельство, в дальнейшем мы будем рассматривать более узкий функциональный объект. Для наборов и функций будем дальше использовать векторную запись.

180 Обозначим набор переменных (х 1, х 2, …, х n ) через Тогда вместо F(x 1, x 2,..,x n ) будем писать При этом значение переменной есть вектор (набор) = ( 1, 2, …, n ), компонентами которого являются следующие последовательности i = { i (1), i (2), …, i (m),…}, i=1, 2, …, n Будем истолковывать как последовательность векторов = { (1), (2), …, (m),…), где (m) = ( 1 (m), 2 (m), …, n (m)), m=1, 2, … Таким образом, можно считать справедливым тождество: ({ 1 (1), 1 (2), …, 1 (m),…}, { 2 (1), 2 (2), …, 2 (m),…}, … { n (1), n (2), …, n (m),…}) {( 1 (1), 2 (1), …, n (1)), ( 1 (2), 2 (2), …, n (2)), …, ( 1 (m), 2 (m), …, n (m)), …} Полученную последовательность векторов можно рассматривать как последовательность наборов ( 1 (m), 2 (m), …, n (m)) или чисел в k-ичной системе счисления. Итак, функцию F(x 1,x 2,…x n ) из теперь можно рассматривать как функцию, зависящую от одной переменной.

181 Опр. Последовательность называется квазипериодической, если выполняется условие: n 0, T / n 0,T N, n 01, T 1, где Т – длина периода и x(n+T)=x(n), при n n 0 То есть последовательность может быть записана следующим образом: х(1), х(2), … х(n 0 -1)[x(n 0 ),…,x(n 0 +T-1)] период последовательности (повторяется бесконечно) Пример1. =01[1101] то есть= … Опр1. Функция называется детерминированной, если каково бы ни было число m и каковы бы ни были последовательности и такие, что (1) = (1), (2) = (2), …, (m) = (m) Значения и функции F, где = F( ) и = F( ), представляют собой последовательности, у которых тоже совпадают первые m членов, то есть (1) = (1), (2) = (2), …, (m) = (m)

182 Опр2. Функция называется детерминированной (автоматной), если i>1 и для любой входной последовательности, i-ый член выходной последовательности является однозначной функцией первых i символов входной последовательности. Обозначение: - совокупность всех таких функций Пример2. F Определить, является ли функция детерминированной. 1. y(t) = x(t) x(1), t1 - детерминированная функция 2. y(t) = x(t+1) x(1), t1 - не детерминированная функция 3. y(t) = x(1) x(2) … х(t+3), t1 эта функция неоднозначна, значит она не детерминированная 4.4. F(0 0…0 ) = 0 0…0 F(0 1…1 ) = 1 1…1 - не детерминированная функция

183 Пусть F( ) =. В определении говорится, что у детерминированной функции значение (m) m-го (m=1,2,…) члена последовательности полностью определяется значениями первых m членов (1), (2), …, (m) последовательности, то есть (m)=F m ( (1), (2), …, (m)) Поскольку F m ( (1), (2), …, (m)) = F m ( 1 (1),…, n (1), 1 (2), …, n (2), …., 1 (m),…, n (m), ) То ясно, что F m – функция P k, зависящая от nm переменных. Таким образом, детерминированная функция определяется последовательностью функций k-значной логики F ~ {F 1, F 2, …, F m, …} где F 1 = F 1 (X 1 ) F 2 = F 2 (X 1, X 2 ) ………………… F m = F m (X 1, X 2, …, X m ) ………………… X 1 = (x 1 (1), x 2 (1),…,x n (1)) X 2 = (x 1 (2), x 2 (2),…,x n (2)) ……………….. X m = (x 1 (m), x 2 (m),…,x n (m)) ………………

184 Интерпретация детерминированной функции Пусть имеется некоторый «дискретный преобразователь» в котором существует n входов х 1, х 2, …, х n и один выход F. На входы в моменты времени t=1, 2, …, m, … подаются (входные) последовательности 1 = { 1 (1), 1 (2), …, 1 (m),…} 2 = { 2 (1), 2 (2), …, 2 (m),…} ………………… n = { n (1), n (2), …, n (m),…}

185 И в эти же моменты t на выходе возникает (выходная) последовательность ={ (1), (2), …, (m), ….}, причем = F( 1, 2, …, n ). Очевидно, что в дискретном преобразователе значение (m) зависит только от значений входных последовательностей в моменты времени t=1, 2, …,m и не зависит от значений в будущие моменты времени. Поэтому преобразование F есть детерминированная функция. При этом константы из (n=0) интерпретируются дискретным преобразователем без входов («генератором»). Кроме того, поступающие на входы преобразователя последовательности, то есть ( 1, 2, …, n ), можно рассматривать как последовательность наборов {( 1 (1), 2 (1), …, n (1)), ( 1 (2), 2 (2), …, n (2)), …, ( 1 (m), 2 (m), …, n (m)), …}

186 Способы задания детерминированной функции По сравнению с рассмотренными ранее способами, для детерминированных функций используется более наглядный способ задания. При описании детерминированных функций используют бесконечные информативные деревья. Так как деревья являются информативными, то должен быть задан алфавит из которого берется информация, отображаемая на них. А – алфавит из N (N1) элементов Обозначение: D А – дерево, построенное на базе алфавита А Опр. Бесконечное ориентированное корневое дерево D А – это дерево, удовлетворяющее условиям: 1. из каждой вершины выходит ровно N дуг 2. в каждую вершину, отличную от корня входит только одна дуга. В корень дерева не входит ни одной дуги. 3. каждой дуге дерева приписана некоторая буква алфавита А, причем разным дугам, выходящим из одной вершины приписаны разные буквы.

187 Пусть k, n – целые числа и N=k n. Рассмотрим следующую бесконечную фигуру. Она состоит из вершин и ориентированных дуг. Будем называть эту фигуру деревом. Вершина 0 называется корнем дерева, из нее исходит пучок из N дуг, образующих 1-й ярус. Каждая из дуг 1-го яруса ведет в вершину, из которой в свою очередь исходит пучок из N дуг, образующих 2-й ярус, и т.д. Вершины, являющиеся концами дуг m-го яруса, причисляются к m-му рангу (вершина 0 считается вершиной 0-го ранга). Рис.1. Дерево D А, построенное на базе алфавита А={0, …, N-1}

188 Дуги каждого пучка нумеруются слева направо числами 0, 1, …, N-1 или их записями в k-ичной системе счисления: (0, …, 0, 0); (0, …, 0, 1); …; (k-1, k-1, …, k-1) nnn Таким образом, дугой j-го яруса (j1) называется всякая дуга, выходящая из вершины (j-1) ранга. Пример3. Если в качестве алфавита взять А=Е 2 ={0, 1}, то построенное на его базе дерево будет называться бинарным. Рис.2. Бинарное дерево D А, построенное на базе алфавита А={0, 1}

189 Ветвью дерева будем называть подмножество дуг, содержащее в каждом ярусе ровно по одной дуге. Очевидно, что каждой ветви дерева можно сопоставить последовательность = { (1), (2), …, (m),…}, где m – номер яруса, а (m) – номер дуги, входящего в эту ветвь, если идти по ней, начиная от корня. Например, ветви, помеченной на рисунке штриховой линией соответствует последовательность {0, 1, N-1,…}.

190 Очевидно, что. Справедливо и обратное утверждение: каждой последовательности из соответствует некоторая ветвь дерева. Таким образом, мы имеем взаимно однозначное соответствие между ветвями дерева и элементами множества. В силу этого мы можем пользоваться деревом для геометрического задания множества. Пусть является функцией из и =(х 1, …, х n ). Используя соотношение при помощи каждой дуге дерева припишем число из Е k. Для этого возьмем произвольную дугу из m-го яруса (m=1, 2, …) и рассмотрим путь, ведущий из корня к этой дуге – он может быть также определен как отрезок произвольной ветви, проходящей через данное ребро. Очевидно, что путь определен однозначным образом и может быть охарактеризован некоторой последовательностью (1), (2), …, (m) номеров дуг, отсчитываемых от корня. Исходной дуге припишем m-й член выходной последовательности – число (m), где (m) = F m ( (1), (2), …, (m))

191 Полученное дерево будем называть нагруженным. Обозначение: D A,B - нагруженное дерево, построенное на базе входного алфавита А и выходного алфавита В. Нагруженное дерево получается из бесконечного ориентированного корневого дерева приписыванием каждой дуге некоторого значения из выходного алфавита В. Таким образом, можно считать, что нагруженное дерево задает отображение F: Изображение: Замечание. По детерминированной функции можно получить нагруженное дерево. Обратное утверждение (в общем случае) не верно. Нагруженное дерево может определять несколько детерминированных функций.

192 Возьмем нагруженное дерево для некоторой детерминированной функции Вес детерминированной функции Пусть - произвольная его вершина m-го ранга. В нее из корня 0 ведет путь: (1), (2), …, (m) (при = 0 путь является пустым). Совокупность всех ветвей, исходящих из, порождает некоторое дерево с корнем, которое будем называть поддеревом исходного дерева. поддерево исходного дерева Это поддерево определяется множеством всех последовательностей из с фиксированным началом (1), (2), …, (m).

193 Так как исходное дерево занумеровано, то поддерево является также занумерованным. Если в поддереве ввести нумерацию ярусов, начиная с 1-го, то ему будет соответствовать детерминированная функция Аналитически ее можно определить следующим образом: пусть Тогда i=1, 2, … Опр. Два поддерева с корнями 1 и 2 исходного дерева называются эквивалентными, если Очевидно, что при естественном наложении двух эквивалентных поддеревьев их нумерации совпадают. Соотношение эквивалентности позволяет в исходном дереве множество всех поддеревьев разбить на классы эквивалентности.

194 Опр. Число r классов эквивалентности, на которое разбивается множество всех поддеревьев данного дерева, называется весом дерева и соответственно весом детерминированной функции. Иначе говоря, вес – это максимальное число попарно неэквивалентных поддеревьев. При этом не исключается случай, когда вес r бесконечен. Пример4.Пусть функция F(x(1), x(2), ….)=y(1),y(2)… t=1 t=2 t= (1) (0)(0)(0)(0) t ~ номер яруса Вес функции r(t)=