Алгебра логики Скачать
презентацию
<<  История алгебры логики Алгебра высказываний  >>
Методы дискретного анализа в организационных системах
Методы дискретного анализа в организационных системах
Функции алгебры логики
Функции алгебры логики
Рекомендуемая литература
Рекомендуемая литература
Джордж Буль
Джордж Буль
Английский математик
Английский математик
Огастес (Август) де Морган
Огастес (Август) де Морган
Табличное задание функций
Табличное задание функций
Область определения
Область определения
Операции над двумя переменными
Операции над двумя переменными
Индуктивное определение формулы
Индуктивное определение формулы
Определение
Определение
«Табличное» задание функции
«Табличное» задание функции
Алгебраические свойства элементарных операций
Алгебраические свойства элементарных операций
Ассоциативность операции
Ассоциативность операции
Дистрибутивность
Дистрибутивность
Дистрибутивность импликации
Дистрибутивность импликации
Соотношение для двойного отрицания
Соотношение для двойного отрицания
Соотношения между отрицанием, конъюнкцией и дизъюнкцией
Соотношения между отрицанием, конъюнкцией и дизъюнкцией
Соотношения, связанные с “навешиванием отрицания”
Соотношения, связанные с “навешиванием отрицания”
Константы
Константы
Правила поглощения
Правила поглощения
Свойства конъюнкции и дизъюнкции
Свойства конъюнкции и дизъюнкции
Тождества
Тождества
Определение
Определение
Переменная
Переменная
Правила поглощения
Правила поглощения
Разложение функций алгебры логики по переменным
Разложение функций алгебры логики по переменным
Значение “основания”
Значение “основания”
Лемма
Лемма
Доказательство
Доказательство
Конъюнкция
Конъюнкция
Обозначения
Обозначения
Произвольная функция
Произвольная функция
Произвольный набор значений переменных
Произвольный набор значений переменных
Представление
Представление
Разложение
Разложение
Если k = n , то получаем разложение
Если k = n , то получаем разложение
Разложение
Разложение
Функцию алгебры логики можно выразить формулой
Функцию алгебры логики можно выразить формулой
Доказательство
Доказательство
Булеву функцию можно выразить формулой над множеством операций
Булеву функцию можно выразить формулой над множеством операций
Пример
Пример
Задача выполнимости булевых формул
Задача выполнимости булевых формул
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Вычислительная сложность
Вычислительная сложность
Две задачи
Две задачи
47
47
48
48
49
49
50
50
Функциональная полнота
Функциональная полнота
Замена переменных
Замена переменных
Пусть имеется функция
Пусть имеется функция
Суперпозиция функций алгебры логики
Суперпозиция функций алгебры логики
Множество функций
Множество функций
Система функций
Система функций
Набор полных систем
Набор полных систем
Замкнутые классы
Замкнутые классы
Множество функции одной переменной
Множество функции одной переменной
Класс функций, сохраняющих 0
Класс функций, сохраняющих 0
Таблица для функции f
Таблица для функции f
62
62
Класс функций, сохраняющих 1
Класс функций, сохраняющих 1
Замкнутый класс
Замкнутый класс
Класс линейных функций
Класс линейных функций
Докажем
Докажем
Линейная функция
Линейная функция
Класс самодвойственных функций
Класс самодвойственных функций
Функция f является двойственной
Функция f является двойственной
Теорема
Теорема
Доказательство
Доказательство
Класс всех самодвойственных функций
Класс всех самодвойственных функций
Самодвойственная функция
Самодвойственная функция
Докажем теперь, что класс S замкнут
Докажем теперь, что класс S замкнут
Пусть
Пусть
Класс монотонных функций
Класс монотонных функций
77
77
Функция алгебры логики
Функция алгебры логики
Класс монотонных функций М - замкнутый класс
Класс монотонных функций М - замкнутый класс
Наборы переменных
Наборы переменных
Слайды из презентации «Функции алгебры логики» к уроку алгебры на тему «Алгебра логики»

Автор: user. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Функции алгебры логики.ppt» бесплатно в zip-архиве размером 304 КБ.

Скачать презентацию

Функции алгебры логики

содержание презентации «Функции алгебры логики.ppt»
СлайдТекст
1 Методы дискретного анализа в организационных системах

Методы дискретного анализа в организационных системах

Алгоритмический подход.

Институт проблем управления РАН, Физический факультет МГУ http://www.ipu.ru/ http://www.phys.msu.ru/rus/about/structure/div/div-experimental/chair-upravleniya/ http://www.orsot.ru/ Лазарев Александр Алексеевич 2009-2010 учебный год

1

2 Функции алгебры логики

Функции алгебры логики

План.

Функции алгебры логики Элементы комбинаторики Элементы теории графов Три контрольные работы (в редакторе ТеХ, http://miktex.org/2.8/setup)

2

3 Рекомендуемая литература

Рекомендуемая литература

3

1. Журавлёв Ю.И., Флёров Ю.А. Дискретный анализ. Часть I: Учебное пособие. – М.: МФТИ, 1999. 2. Стэнли Р. Перечислительная комбинаторика. -М.: Мир, 1990. 3. Липский В. Комбинаторика для программистов. - М.: Мир, 1988. 4. Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ,1985. 5. Гаврилов Г.И., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. -М.: Наука, 1992. 6. Риордан Дж. Введение в комбинаторный анализ. - М.: ИЛ, 1963. 7. Холл М. Комбинаторика. - М.: Мир, 1970. 8. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1976. 9. Дискретная математика и математические вопросы кибернетики/ Под ред. С.В.Яблонского, О.В.Лупанова, Т.1, -М.; Наука, 1974. 10. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 1986. 11. Оре О. Теория графов. - М.: Наука, 1968. 12. Кристофидис Н. Теория графов. Алгоритмический подход. -М.: Мир, 1987. 13. Емеличев В.А., Мельников О.И. и др. Лекции по теории графов. М.: Наука, 1990. 14. Уилсон Р.Дж. Введение в теорию графов. - М.: Мир, 1977. 15. Харари Ф. Теория графов. - М.: Мир,1973. 16. Журавлёв Ю.И., Флёров А.А., Федько О.С., Дадашев Т.М. Сборник задач по дискретному анализу. – М.: МФТИ, 2000. 17. Гжегорчик А. Популярная логика.- М.: Наука, 1979. 18. Леонтьев В.К. Избранные задачи комбинаторного анализа. – М. Изд-во МГТУ им. Н.Э. Баумана, 2001. 19. Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач теории расписаний: Учебное пособие. – М.: МФТИ, 2008. 20. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. – 1982. 21. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М. – 2005. 1293 с.

4 Джордж Буль

Джордж Буль

Функции алгебры логики.

Джордж Буль (1815-1864) “Математический анализ логики, являющийся очерком, касающимся исчисления дедуктивных рассуждений”, (1847 г.), “Исследования законов мысли. на которых основываются математические теории логики и вероятностей”, (1854 г.). Аугустус (Огастес, Август) де Морган (1806-1871) “Формальная логика или исчисление выводов, необходимых и возможных” (1847 г.).

4

5 Английский математик

Английский математик

БУЛЬ, ДЖОРДЖ (Boole, George) (1815-1864), английский математик. Родился 2 ноября 1815 в Линкольне. В возрасте 16 лет стал помощником учителя частной школы в Донкастере, в 1835 открыл собственную школу в Линкольне. В свободное время читал математические журналы, работы И.Ньютона, П.Лапласа и Ж.-Л.Лагранжа, начал вести самостоятельные алгебраические исследования. В 1839 написал первую научную работу Исследования по теории аналитических преобразований (Researches on the Theory of Analytical Transformations), которая была опубликована "Кембриджским математическим журналом" ("Cambridge Mathematical Journal"). В 1844 появилась его первая работа, где высказывалась идея объединения алгебры и логики, а в 1847 вышла в свет статья Математический анализ логики (The Mathematical Analysis of Logic), которая положила начало созданию "алгебры высказываний", получившей впоследствии название булевой алгебры. Благодаря этой публикации Буль в 1849 был назначен профессором математики Куинз-колледжа (Корк, Ирландия), где преподавал до конца жизни. В 1857 был избран членом Лондонского королевского общества. Основные идеи Буля суммированы в его работе Исследование законов мышления, на которых основаны математические теории логики и вероятностей (An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, 1854). Здесь впервые определено в явном виде исчисление классов (или множеств), введено обозначение для их пересечения, объединения и т.д., показано, что исчисление классов можно интерпретировать как исчисление высказываний. Булевы алгебры — особые алгебраические системы, для которых определены две операции, — нашли широкое применение в различных разделах математики: в теории вероятностей, топологии, функциональном анализе, а также в создании вычислительных машин. Умер Буль в Баллинтемпле (графство Корк, Ирландия) 8 декабря 1864.

5

6 Огастес (Август) де Морган

Огастес (Август) де Морган

(англ. Augustus de Morgan, 27 июня 1806), Мадура, Индия — 8 марта 1871, Лондон) — шотландский математик и логик; профессор математики университетского колледжа в Лондоне (1828—1831, 1836—1866); первый президент (1866) Лондонского математического общества. Основные труды: по математической логике и теории рядов; к своим идеям в алгебре логики пришёл независимо от Дж. Буля; изложил (1847) элементы логики высказываний и логики классов, дал первую развитую систему алгебры отношений; с его именем связаны известные теоретико-множественные соотношения (законы де Моргана).

6

7 Табличное задание функций

Табличное задание функций

Функции алгебры логики. Табличное задание функций. Элементарные функции, их свойства, таблица операций, коммутативность, ассоциативность, дистрибутивность элементарных функций. Формулы и функции алгебры логики. Теоремы о разложении функций по одной и нескольким переменным. Совершенная дизъюнктивная нормальная форма. Задача о ВЫПОЛНИМОСТИ. Определение понятия NP-трудности задач. Функциональная полнота систем функций алгебры логики. Замкнутые классы. Пять предполных замкнутых классов T0, T1, L, S, M. Пересечение данных классов. Теорема о функции двойственной к суперпозиции. Критерий функциональной полноты систем функций алгебры логики (теорема Поста). Примеры полных систем функций алгебры логики. Основная лемма. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Лемма о нелинейной функции. Следствия из критерия полноты.

7

8 Область определения

Область определения

Функции алгебры логики.

Область определения логических или булевых переменных 0 и 1 Область значений функций также 0 и 1 Функция от одной переменной f(x) x f(x) 0 0 0 1 1 1 0 1 0 1 0 x ? x 1

8

9 Операции над двумя переменными

Операции над двумя переменными

(двухместные, бинарные операции).

x y x ?y x ? y x?y x?y x+y x|y x?y 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 2n конъюнкция ? & и min(x,y) дизъюнкция ? max (x,y) импликация ? ? эквивалентность ? ? ? сумма по модулю 2 + ? штрих (Шеффера) | “не x или не y” стрелка (Пирса) ? “не x и не y”.

9

10 Индуктивное определение формулы

Индуктивное определение формулы

Пусть U - множество переменных. Тогда множество формул алгебры логики над U определяется следующим образом: 1. Всякая переменная - формула. 2. Константы 0 и 1 - формулы. 3. Если А - формула, то ? А (или в другой записи ) - формула. 4. Если А и В - формулы, то (А?В), (А?В), (А?В), (А+В), (А?В), (А?В), (А?В) - формулы. 5. Формулами являются те и только те выражения, которые могут быть получены из констант, переменных и логических связок за конечное число шагов 1- 4.

10

11 Определение

Определение

F(x1 ,x2 ,x3,…, xn),

Определение. Функция от n переменных определенная на множестве и принимающая значения из множества {0, 1}, называется функцией алгебры логики или булевой функцией.

11

12 «Табличное» задание функции

«Табличное» задание функции

x1 x2 ... xn-1 xn f(x1, x2, ... xn-1, xn) 0 0 ... 0 0 f(0, 0, ... , 0, 0) 0 0 ... 0 1 f(0, 0, ... , 0, 1) 0 0 ... 1 0 f(0, 0, ... , 1, 0) ...................... 1 1 ... 1 1 f(1, 1, ... , 1, 1) 2n.

12

13 Алгебраические свойства элементарных операций

Алгебраические свойства элементарных операций

1. Коммутативность (или перестановочность) операции ? означает, что . Логическая операция ? коммутативна, если связка ? принадлежит следующему множеству связок (существенно только, чтобы символ ? в равенстве всюду имел один и тот же смысл):

13

14 Ассоциативность операции

Ассоциативность операции

2. Ассоциативность операции ? означает, что .Свойство ассоциативности позволяет записывать формулы, содержащие одинаковые ассоциативные связки, без скобок, например, . Логическая операция ? ассоциативна, если связка ? принадлежит следующему множеству связок (существенно только, чтобы символ ? в равенстве всюду имел один и тот же смысл): .

14

15 Дистрибутивность

Дистрибутивность

3. Дистрибутивность (распределительный закон) операции ? относительно операции ? означает, что . Дистрибутивность конъюнкции: - дистрибутивность конъюнкции относительно дизъюнкции; - дистрибутивность конъюнкции относительно суммы по модулю 2. Дистрибутивность дизъюнкции: - дистрибутивность дизъюнкции относительно конъюнкции; - дистрибутивность дизъюнкции относительно импликации; - дистрибутивность дизъюнкции относительно эквивалентности.

15

16 Дистрибутивность импликации

Дистрибутивность импликации

- дистрибутивность импликации относительно конъюнкции; - дистрибутивность импликации относительно дизъюнкции; - дистрибутивность импликации относительно импликации.

16

17 Соотношение для двойного отрицания

Соотношение для двойного отрицания

4. Имеет место следующее соотношение для двойного отрицания:

17

18 Соотношения между отрицанием, конъюнкцией и дизъюнкцией

Соотношения между отрицанием, конъюнкцией и дизъюнкцией

5. Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией: закон (правила) де Моргана. Указанные соотношения отражают отношение двойственности между дизъюнкцией и конъюнкцией.

18

19 Соотношения, связанные с “навешиванием отрицания”

Соотношения, связанные с “навешиванием отрицания”

6. Имеют место следующие соотношения, связанные с “навешиванием отрицания” на элементарные логические функции:

19

20 Константы

Константы

7. Константы могут быть выражены следующим образом:

20

21 Правила поглощения

Правила поглощения

8. Правила поглощения:

21

22 Свойства конъюнкции и дизъюнкции

Свойства конъюнкции и дизъюнкции

9. Выполняются следующие свойства конъюнкции и дизъюнкции:

22

23 Тождества

Тождества

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

23

24 Определение

Определение

Через P2(n) будем обозначать множество всех разных булевых функций размерности n.

Теорема. Число p2(n) всех функций из P2(n), зависящих от переменных x1, x2, ... , xn , равно .

24

25 Переменная

Переменная

xi (1? i ? n) функции f(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) из P2(n)называется существенной, если можно указать такие наборы и значений переменных, что В противном случае переменную xi называют несущественной или фиктивной переменной функции f. Две функции f(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) и g(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) называются равными, если множества их существенных переменных совпадают и на любых двух наборах (x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) и (y1, y2, ... ,yi-1, yi , yi+1, ... , yn ), различающихся быть может только значениями несущественных переменных, значения функций одинаковы: f(x)=g(y). Если f(x) и g(y) - равные функции, то одну из них можно получить из другой путем добавления и/или изъятия несущественных переменных.

25

26 Правила поглощения

Правила поглощения

8. Правила поглощения:

26

27 Разложение функций алгебры логики по переменным

Разложение функций алгебры логики по переменным

Чтобы иметь возможность единообразно записывать переменные с отрицанием и без отрицания введем следующее обозначение:

27

28 Значение “основания”

Значение “основания”

Легко видеть, что x? = 1 тогда и только тогда, когда x = ?, то есть значение “основания” равно значению “показателя”.

28

29 Лемма

Лемма

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

(2.1)

29

30 Доказательство

Доказательство

Отметим прежде всего, что представление (2.1), естественно, справедливо для произвольной переменной xi из множества переменных функции f. Для доказательства рассмотрим произвольный набор значений переменных (?1, ... , ?n) и покажем, что левая и правая части соотношения (2.1) принимают на нем одно и то же значение. Рассмотрим набор значений переменных (1, ?2, ... , ?n). Левая часть (2.1) принимает на этом наборе значение f(1, ?2 ,..., ?n ), а правая часть - значение 1?f(1, ?2, ... , ?n ) ? 0?f(0, ?2, ... , ?n ) = f (1, ?2, ... , ?n ). Таким образом, на наборах (1, ?2, ... , ?n) левая и правая части (2.1) принимают одинаковые значения. Рассмотрим набор значений переменных (0, ?2, ... , ?n). Левая часть (2.1) принимает на этом наборе значение f(0, ?2 ,..., ?n ), а правая часть - значение 0?f(1, ?2, ... , ?n ) ? 1?f (0, ?2, ... , ?n ) = f (0, ?2, ... , ?n ). Таким образом, на наборах (0, ?2, ... , ?n) левая и правая части (2.1) принимают одинаковые значения. Тем самым мы доказали, что левая и правая части соотношения (2.1) принимают одинаковые значения на всех наборах (?1, ... , ?n). ?

30

31 Конъюнкция

Конъюнкция

Лемма 2.3. Конъюнкция (произведение) тогда и только тогда, когда . Доказательство. Произведение (конъюнкция) равно 1 тогда и только тогда, когда каждый сомножитель равен 1, но x? = 1 тогда и только тогда, когда x = ?. ?

31

32 Обозначения

Обозначения

В дальнейшем будем употреблять следующие обозначения:

32

33 Произвольная функция

Произвольная функция

Теорема 2.4. (О разложении функции по нескольким переменным). Пусть f(x1 , ... , xn) - произвольная функция алгебры логики. Тогда ее можно представить в следующей форме:

(2.2)

33

34 Произвольный набор значений переменных

Произвольный набор значений переменных

Доказательство. Рассмотрим произвольный набор значений переменных (?1, ... , ?n) и покажем, что левая и правая части соотношения (2.2) принимают на нем одно и то же значение. Левая часть дает f(?1 ,..., ?k ,? k+1 ,..., ?n). Правая часть дает.

34

35 Представление

Представление

(2.2) называется дизъюнктивным разложением функции по k переменным. Пример. Для k = 2 разложение в дизъюнктивную форму имеет вид:

35

36 Разложение

Разложение

Выпишем такое разложение для конкретной функции трех переменных по переменным x2 и x3:

36

37 Если k = n , то получаем разложение

Если k = n , то получаем разложение

Оно может быть преобразовано при f(x1, ... , xn) ? 0 следующим образом:

37

38 Разложение

Разложение

Итак, в этом случае разложение имеет вид: Это разложение называется совершенной дизъюнктивной нормальной формой (совершенная ДНФ.). Оно определено для любой функции f, не равной константе 0.

38

39 Функцию алгебры логики можно выразить формулой

Функцию алгебры логики можно выразить формулой

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

39

40 Доказательство

Доказательство

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

40

41 Булеву функцию можно выразить формулой над множеством операций

Булеву функцию можно выразить формулой над множеством операций

Любую булеву функцию можно выразить формулой над множеством операций {?, ?, ? }, состоящим из трех функций: отрицания, конъюнкции и дизъюнкции. Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу (совершенную ДНФ). А именно, берем таблицу для функции f(x1, ... , xn) (f? 0) и отмечаем в ней все строки (?1, ... , ?n), в которых f(?1, ... , ?n) =1, для каждой такой строки образуем логическое произведение а затем соединяем все полученные конъюнкции знаком дизъюнкции.

41

42 Пример

Пример

Построить совершенную ДНФ для функции, заданной таблицей:

x1 x2 x3

f(x1, x2, x3)

x1 x2 x3

f(x1, x2, x3)

0 0 0

1

1 0 0

0

0 0 1

1

1 0 1

1

0 1 0

0

1 1 0

0

0 1 1

0

1 1 1

1

42

Имеем:

43 Задача выполнимости булевых формул

Задача выполнимости булевых формул

(SAT или ВЫП) — задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной. Согласно теореме Кука, доказанной Стивеном Куком в 1971-м году, задача SAT NP-полна.

43

44 Необходимо условиться об алфавите

Необходимо условиться об алфавите

Чтобы четко сформулировать задачу распознавания, необходимо условиться об алфавите, с помощью которого задаются экземпляры языка. Этот алфавит должен быть фиксирован и конечен. Обычно используют следующий алфавит: { ?, ?, ? , (, ), x, 0, 1}. При использовании такого алфавита скобки и операторы записываются естественным образом, а переменные получают следующие имена: x1, x10, x11, x100 и т. д., согласно их номерам, записанным в двоичной системе счисления. Пусть некоторая булева формула, записанная в обычной математической нотации, имела длину N символов. В ней каждое вхождение каждой переменной было описано хотя бы одним символом, следовательно, всего в данной формуле не более N переменных. Значит, в предложенной выше нотации каждая переменная будет записана с помощью символов. В таком случае, вся формула в новой нотации будет иметь длину символов, то есть длина строки возрастет в полиномиальное число раз. Например, формула примет вид.

44

45 Вычислительная сложность

Вычислительная сложность

В 1971-м году в статье Стивена Кука был впервые введен термин «NP-полная задача», и задача SAT была первой задачей, для которой доказывалось это свойство. В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.

45

46 Две задачи

Две задачи

46

47 47

47

48 48

48

49 49

49

50 50

50

51 Функциональная полнота

Функциональная полнота

систем функций алгебры логики.

Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , x?y, x?y. В связи с этим возникает вопрос, какими свойствами должна обладать система функций, чтобы через функции этой системы можно было выразить произвольную функцию алгебры логики? Новые функции получаются из имеющихся в заданной системе функций с помощью операций замены переменных и суперпозиции. Опишем эти две операции.

51

52 Замена переменных

Замена переменных

1. Замена переменных.

Пусть f(x1, x2, ... , xn) - заданная функция алгебры логики. Будем говорить, что функция ?(y1, y2, ... , yn) получена операцией замены переменных из функции f(x1, x2, ... , xn), если осуществлена подстановка переменных

52

53 Пусть имеется функция

Пусть имеется функция

Пример. Пусть имеется функция.

Тогда при замене переменных

Из функции

Можно получить функцию

.

53

54 Суперпозиция функций алгебры логики

Суперпозиция функций алгебры логики

2. Суперпозиция функций алгебры логики.

Пусть имеется функция f(x1, x2, ... , xn) и функции , тогда функцию будем называть суперпозицией функции f(x1, x2, ... , xn) и функций . Другими словами: пусть F = { fj } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции путем замены одной или нескольких ее переменных функциями из множества F.

54

55 Множество функций

Множество функций

Пример. Пусть задано множество функций F = {f1(x1), f2 (x1 ,x2 ,x3 ), f3(x1 ,x2 )}. Тогда суперпозициями функций из F будут, например, функции: ?1(x2, x3) = f3( f1(x2), f1(x3)); ?2(x1, x2) = f2 (x1 , f1(x1 ), f3(x1 ,x2 )). Cовершенная ДНФ - суперпозиция функций из множества . ?

55

56 Система функций

Система функций

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

56

57 Набор полных систем

Набор полных систем

Мы уже имеем некоторый набор полных систем:

{x+y, xy, 1}.

Как определить условия, при которых система полна?

57

58 Замкнутые классы

Замкнутые классы

Множество (класс) K функций алгебры логики называется замкнутым классом, если оно содержит все функции, получающиеся из K операциями суперпозиции и замены переменных, и не содержит никаких других функций. Пусть K - некоторое подмножество функций из P2(n). Замыканием K называется множество всех булевых функций, представимых с помощью операций суперпозиции и замены переменных функций из множества K. Замыкание множества K обозначается через [K]. В терминах замыкания можно дать другие определения замкнутости и полноты (эквивалентные исходным): K- замкнутый класс, если K = [K]; K - полная система, если [K] = P2(n).

58

59 Множество функции одной переменной

Множество функции одной переменной

Примеры. {0}, {1} - замкнутые классы. Множество функции одной переменной - замкнутый класс. - замкнутый класс. Класс {1, x+y} не является замкнутым классом.

59

60 Класс функций, сохраняющих 0

Класс функций, сохраняющих 0

Замкнутые классы.

1. Т0 - класс функций, сохраняющих 0. Обозначим через Т0 класс всех функций алгебры логики f(x1, x2, ... , xn), сохраняющих константу 0, то есть функций, для которых f(0, ... , 0) = 0. 0, x, xy, x?y, x+y ? T0; 1, ? T0. Из того, что ? T0 следует, например, что нельзя выразить через дизъюнкцию и конъюнкцию.

60

61 Таблица для функции f

Таблица для функции f

Поскольку таблица для функции f из класса Т0 в первой строке содержит фиксированное значение 0, то для функций из Т0 можно задавать произвольные значения только на 2n - 1 наборе значений переменных, то есть , где - множество функций, сохраняющих 0 и зависящих от n переменных. Покажем, что Т0 - замкнутый класс. Так как x?T0 , то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

61

62 62

62

63 Класс функций, сохраняющих 1

Класс функций, сохраняющих 1

2. T1 - класс функций, сохраняющих 1.

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

1, x, xy, x?y, x?y ? T1;

Из того, что x + y ? T1 следует, например, что x + y нельзя выразить через дизъюнкцию и конъюнкцию.

0,

, x+y ? T1

63

64 Замкнутый класс

Замкнутый класс

Т1 - замкнутый класс.

64

65 Класс линейных функций

Класс линейных функций

3. L - класс линейных функций.

xy, x?y ? L .

= x+1 ? L;

0, 1, x, x+y, x1 ? x2 = 1+ x1 + x2,

65

66 Докажем

Докажем

что x?y ? L . Предположим противное. Будем искать выражение для x?y в виде линейной функции с неопределенными коэффициентами:

При x = y = 0 имеем ?=0, при x = 1, y = 0 имеем ? = 1, при x = 0, y = 1 имеем ? = 1, но тогда при x = 1, y = 1 имеем 1? 1 ? 1 + 1, что доказывает нелинейность функции дизъюнкция x?y. Доказательство замкнутости класса линейных функций очевидно.

66

67 Линейная функция

Линейная функция

Поскольку линейная функция однозначно определяется заданием значений n+1 коэффициента ?0, ... , ?n , число линейных функций в классе L(n) функций, зависящих от n переменных равно 2n+1.

67

68 Класс самодвойственных функций

Класс самодвойственных функций

4. S - класс самодвойственных функций.

Функция , определяемая равенством называется двойственной к функции

Таблица для двойственной функции (при стандартной упорядоченности наборов значений переменных) получается из таблицы для исходной функции инвертированием (то есть заменой 0 на 1 и 1 на 0) столбца значений функции и его переворачиванием.

68

69 Функция f является двойственной

Функция f является двойственной

0* = 1, 1* = 0, x* = x,

(f*)* = f

Функция f является двойственной к f*.

(x1 ? x2)* = x1 ? x2, (x1 ? x2)* = x1 ? x2.

69

70 Теорема

Теорема

Если функция ? получена как суперпозиция функций f, f1, f2, ... , fm, то функция, двойственная к суперпозиции, есть суперпозиция двойственных функций.

70

71 Доказательство

Доказательство

?*(x1 ,..., xn) = ? f(?x1 ,...,? xn) =.

71

72 Класс всех самодвойственных функций

Класс всех самодвойственных функций

Обозначим через S класс всех самодвойственных функций из P2: S = {f | f* = f }.

Для самодвойственной функции имеет место тождество

? S; 0, 1, xy, x?y ? S .

x,

72

73 Самодвойственная функция

Самодвойственная функция

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

73

74 Докажем теперь, что класс S замкнут

Докажем теперь, что класс S замкнут

Так как x?S , то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

74

75 Пусть

Пусть

. Тогда достаточно показать, что Последнее устанавливается непосредственно:

75

76 Класс монотонных функций

Класс монотонных функций

5. М - класс монотонных функций.

Набор предшествует набору, если ?i ? ?i для всех i = 1, ... , n. Наборы ? и ? называются сравнимыми, если либо ??? либо ???.В случае, когда ни одно из этих оотношений не выполняется, то наборы называются несравнимыми.

76

77 77

77

78 Функция алгебры логики

Функция алгебры логики

называется монотонной, если для любых двух наборов и , таких, что , имеет место неравенство . Множество всех монотонных функций алгебры логики обозначаетcя через М, а множество всех монотонных функций, зависящих от n переменных - через М(n).

78

79 Класс монотонных функций М - замкнутый класс

Класс монотонных функций М - замкнутый класс

0, 1, x, xy, x?y ? M; x+y, x?y, x?y ? M . Покажем, что класс монотонных функций М - замкнутый класс. Так как x?М, то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

79

80 Наборы переменных

Наборы переменных

соответственно, функций ?, f1, ... , fm , причем множество переменных функции ? состоит из тех и только тех переменных, которые встречаются у функций f1, ... , fm .

80

«Функции алгебры логики»
http://900igr.net/prezentatsii/algebra/Funktsii-algebry-logiki/Funktsii-algebry-logiki.html
cсылка на страницу
Урок

Алгебра

34 темы
Слайды
Презентация: Функции алгебры логики.ppt | Тема: Алгебра логики | Урок: Алгебра | Вид: Слайды
900igr.net > Презентации по алгебре > Алгебра логики > Функции алгебры логики.ppt