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

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

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

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

содержание презентации «Функции алгебры логики.ppt»
Сл Текст Сл Текст
1Методы дискретного анализа в организационных системах. 3030.
Алгоритмический подход. Институт проблем управления РАН, 31Лемма 2.3. Конъюнкция (произведение) тогда и только тогда,
Физический факультет МГУ http://www.ipu.ru/ когда . Доказательство. Произведение (конъюнкция) равно 1 тогда
http://www.phys.msu.ru/rus/about/structure/div/div-experimental/ и только тогда, когда каждый сомножитель равен 1, но x? = 1
hair-upravleniya/ http://www.orsot.ru/ Лазарев Александр тогда и только тогда, когда x = ?. ? 31.
Алексеевич 2009-2010 учебный год. 1. 32В дальнейшем будем употреблять следующие обозначения: 32.
2План. Функции алгебры логики Элементы комбинаторики Элементы 33Теорема 2.4. (О разложении функции по нескольким
теории графов Три контрольные работы (в редакторе ТеХ, переменным). Пусть f(x1 , ... , xn) - произвольная функция
http://miktex.org/2.8/setup). 2. алгебры логики. Тогда ее можно представить в следующей форме:
3Рекомендуемая литература. 3. 1. Журавлёв Ю.И., Флёров Ю.А. (2.2). 33.
Дискретный анализ. Часть I: Учебное пособие. – М.: МФТИ, 1999. 34Доказательство. Рассмотрим произвольный набор значений
2. Стэнли Р. Перечислительная комбинаторика. -М.: Мир, 1990. 3. переменных (?1, ... , ?n) и покажем, что левая и правая части
Липский В. Комбинаторика для программистов. - М.: Мир, 1988. 4. соотношения (2.2) принимают на нем одно и то же значение. Левая
Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ,1985. часть дает f(?1 ,..., ?k ,? k+1 ,..., ?n). Правая часть дает.
5. Гаврилов Г.И., Сапоженко А.А. Задачи и упражнения по курсу 34.
дискретной математики. -М.: Наука, 1992. 6. Риордан Дж. Введение 35Представление (2.2) называется дизъюнктивным разложением
в комбинаторный анализ. - М.: ИЛ, 1963. 7. Холл М. функции по k переменным. Пример. Для k = 2 разложение в
Комбинаторика. - М.: Мир, 1970. 8. Мендельсон Э. Введение в дизъюнктивную форму имеет вид: 35.
математическую логику.- М.: Наука, 1976. 9. Дискретная 36Выпишем такое разложение для конкретной функции трех
математика и математические вопросы кибернетики/ Под ред. переменных по переменным x2 и x3: 36.
С.В.Яблонского, О.В.Лупанова, Т.1, -М.; Наука, 1974. 10. 37Если k = n , то получаем разложение. Оно может быть
Яблонский С.В. Введение в дискретную математику. -М.: Наука, преобразовано при f(x1, ... , xn) ? 0 следующим образом: 37.
1986. 11. Оре О. Теория графов. - М.: Наука, 1968. 12. 38Итак, в этом случае разложение имеет вид: Это разложение
Кристофидис Н. Теория графов. Алгоритмический подход. -М.: Мир, называется совершенной дизъюнктивной нормальной формой
1987. 13. Емеличев В.А., Мельников О.И. и др. Лекции по теории (совершенная ДНФ.). Оно определено для любой функции f, не
графов. М.: Наука, 1990. 14. Уилсон Р.Дж. Введение в теорию равной константе 0. 38.
графов. - М.: Мир, 1977. 15. Харари Ф. Теория графов. - М.: 39Теорема 2.5. Произвольную функцию алгебры логики можно
Мир,1973. 16. Журавлёв Ю.И., Флёров А.А., Федько О.С., Дадашев выразить формулой при помощи операций ?, ?, ?, причем операция ?
Т.М. Сборник задач по дискретному анализу. – М.: МФТИ, 2000. 17. применяется только к переменным. 39.
Гжегорчик А. Популярная логика.- М.: Наука, 1979. 18. Леонтьев 40Доказательство. 1. Пусть f(x1, ... , xn) = 0. Тогда,
В.К. Избранные задачи комбинаторного анализа. – М. Изд-во МГТУ очевидно, f(x1, ... , xn) = x1 ? ? x1 . 2. Пусть f(x1, ... , xn)
им. Н.Э. Баумана, 2001. 19. Лазарев А.А. Теория расписаний. ? 0. Представим ее в форме совершенной ДНФ: Таким образом, в
Оценки абсолютной погрешности и схема приближённого решения обоих случаях функция f выражается в виде формулы через
задач теории расписаний: Учебное пособие. – М.: МФТИ, 2008. 20. конъюнкцию, дизъюнкцию и отрицание, причем отрицание применяется
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые только к символам переменных. ? 40.
задачи. – М.: Мир. – 1982. 21. Кормен Т., Лейзерсон Ч., Ривест 41Любую булеву функцию можно выразить формулой над множеством
Р., Штайн К. Алгоритмы: построение и анализ. – М. – 2005. 1293 операций {?, ?, ? }, состоящим из трех функций: отрицания,
с. конъюнкции и дизъюнкции. Данная теорема носит конструктивный
4Функции алгебры логики. Джордж Буль (1815-1864) характер, так как она позволяет для каждой функции построить
“Математический анализ логики, являющийся очерком, касающимся реализующую ее формулу (совершенную ДНФ). А именно, берем
исчисления дедуктивных рассуждений”, (1847 г.), “Исследования таблицу для функции f(x1, ... , xn) (f? 0) и отмечаем в ней все
законов мысли. на которых основываются математические теории строки (?1, ... , ?n), в которых f(?1, ... , ?n) =1, для каждой
логики и вероятностей”, (1854 г.). Аугустус (Огастес, Август) де такой строки образуем логическое произведение а затем соединяем
Морган (1806-1871) “Формальная логика или исчисление выводов, все полученные конъюнкции знаком дизъюнкции. 41.
необходимых и возможных” (1847 г.). 4. 42Пример. Построить совершенную ДНФ для функции, заданной
5БУЛЬ, ДЖОРДЖ (Boole, George) (1815-1864), английский таблицей: x1 x2 x3. f(x1, x2, x3). x1 x2 x3. f(x1, x2, x3). 0 0
математик. Родился 2 ноября 1815 в Линкольне. В возрасте 16 лет 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.
стал помощником учителя частной школы в Донкастере, в 1835 0. 1 1 1. 1. 42. Имеем:
открыл собственную школу в Линкольне. В свободное время читал 43Задача выполнимости булевых формул (SAT или ВЫП) — задача
математические журналы, работы И.Ньютона, П.Лапласа и распознавания, важная для теории вычислительной сложности.
Ж.-Л.Лагранжа, начал вести самостоятельные алгебраические Экземпляром задачи SAT является булева формула, состоящая только
исследования. В 1839 написал первую научную работу Исследования из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача
по теории аналитических преобразований (Researches on the Theory заключается в следующем: можно ли назначить всем переменным,
of Analytical Transformations), которая была опубликована встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы
"Кембриджским математическим журналом" формула стала истинной. Согласно теореме Кука, доказанной
("Cambridge Mathematical Journal"). В 1844 появилась Стивеном Куком в 1971-м году, задача SAT NP-полна. 43.
его первая работа, где высказывалась идея объединения алгебры и 44Чтобы четко сформулировать задачу распознавания, необходимо
логики, а в 1847 вышла в свет статья Математический анализ условиться об алфавите, с помощью которого задаются экземпляры
логики (The Mathematical Analysis of Logic), которая положила языка. Этот алфавит должен быть фиксирован и конечен. Обычно
начало созданию "алгебры высказываний", получившей используют следующий алфавит: { ?, ?, ? , (, ), x, 0, 1}. При
впоследствии название булевой алгебры. Благодаря этой публикации использовании такого алфавита скобки и операторы записываются
Буль в 1849 был назначен профессором математики Куинз-колледжа естественным образом, а переменные получают следующие имена: x1,
(Корк, Ирландия), где преподавал до конца жизни. В 1857 был x10, x11, x100 и т. д., согласно их номерам, записанным в
избран членом Лондонского королевского общества. Основные идеи двоичной системе счисления. Пусть некоторая булева формула,
Буля суммированы в его работе Исследование законов мышления, на записанная в обычной математической нотации, имела длину N
которых основаны математические теории логики и вероятностей (An символов. В ней каждое вхождение каждой переменной было описано
Investigation of the Laws of Thought, on Which Are Founded the хотя бы одним символом, следовательно, всего в данной формуле не
Mathematical Theories of Logic and Probabilities, 1854). Здесь более N переменных. Значит, в предложенной выше нотации каждая
впервые определено в явном виде исчисление классов (или переменная будет записана с помощью символов. В таком случае,
множеств), введено обозначение для их пересечения, объединения и вся формула в новой нотации будет иметь длину символов, то есть
т.д., показано, что исчисление классов можно интерпретировать длина строки возрастет в полиномиальное число раз. Например,
как исчисление высказываний. Булевы алгебры — особые формула примет вид. 44.
алгебраические системы, для которых определены две операции, — 45Вычислительная сложность В 1971-м году в статье Стивена Кука
нашли широкое применение в различных разделах математики: в был впервые введен термин «NP-полная задача», и задача SAT была
теории вероятностей, топологии, функциональном анализе, а также первой задачей, для которой доказывалось это свойство. В
в создании вычислительных машин. Умер Буль в Баллинтемпле доказательстве теоремы Кука каждая задача из класса NP в явном
(графство Корк, Ирландия) 8 декабря 1864. 5. виде сводится к SAT. После появления результатов Кука была
6Огастес (Август) де Морган (англ. Augustus de Morgan, 27 доказана NP-полнота для множества других задач. При этом чаще
июня 1806), Мадура, Индия — 8 марта 1871, Лондон) — шотландский всего для доказательства NP-полноты некоторой задачи приводится
математик и логик; профессор математики университетского полиномиальное сведение задачи SAT к данной задаче, возможно в
колледжа в Лондоне (1828—1831, 1836—1866); первый президент несколько шагов, то есть с использованием нескольких
(1866) Лондонского математического общества. Основные труды: по промежуточных задач. 45.
математической логике и теории рядов; к своим идеям в алгебре 46Две задачи. 46.
логики пришёл независимо от Дж. Буля; изложил (1847) элементы 4747.
логики высказываний и логики классов, дал первую развитую 4848.
систему алгебры отношений; с его именем связаны известные 4949.
теоретико-множественные соотношения (законы де Моргана). 6. 5050.
7Функции алгебры логики. Табличное задание функций. 51Функциональная полнота систем функций алгебры логики. Выше
Элементарные функции, их свойства, таблица операций, мы видели, что всякая функция алгебры логики может быть выражена
коммутативность, ассоциативность, дистрибутивность элементарных в виде формулы через элементарные функции , x?y, x?y. В связи с
функций. Формулы и функции алгебры логики. Теоремы о разложении этим возникает вопрос, какими свойствами должна обладать система
функций по одной и нескольким переменным. Совершенная функций, чтобы через функции этой системы можно было выразить
дизъюнктивная нормальная форма. Задача о ВЫПОЛНИМОСТИ. произвольную функцию алгебры логики? Новые функции получаются из
Определение понятия NP-трудности задач. Функциональная полнота имеющихся в заданной системе функций с помощью операций замены
систем функций алгебры логики. Замкнутые классы. Пять предполных переменных и суперпозиции. Опишем эти две операции. 51.
замкнутых классов T0, T1, L, S, M. Пересечение данных классов. 521. Замена переменных. Пусть f(x1, x2, ... , xn) - заданная
Теорема о функции двойственной к суперпозиции. Критерий функция алгебры логики. Будем говорить, что функция ?(y1, y2,
функциональной полноты систем функций алгебры логики (теорема ... , yn) получена операцией замены переменных из функции f(x1,
Поста). Примеры полных систем функций алгебры логики. Основная x2, ... , xn), если осуществлена подстановка переменных. 52.
лемма. Лемма о несамодвойственной функции. Лемма о немонотонной 53Пример. Пусть имеется функция. Тогда при замене переменных.
функции. Лемма о нелинейной функции. Следствия из критерия Из функции. Можно получить функцию. . 53.
полноты. 7. 542. Суперпозиция функций алгебры логики. Пусть имеется
8Функции алгебры логики. Область определения логических или функция f(x1, x2, ... , xn) и функции , тогда функцию будем
булевых переменных 0 и 1 Область значений функций также 0 и 1 называть суперпозицией функции f(x1, x2, ... , xn) и функций .
Функция от одной переменной f(x) x f(x) 0 0 0 1 1 1 0 1 0 1 0 x Другими словами: пусть F = { fj } - набор функций алгебры
? x 1. 8. логики, не обязательно конечный. Функция f называется
9Операции над двумя переменными (двухместные, бинарные суперпозицией функций из множества F или функцией над F, если
операции). 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 переменных функциями из множества F. 54.
конъюнкция ? & и min(x,y) дизъюнкция ? max (x,y) импликация 55Пример. Пусть задано множество функций F = {f1(x1), f2 (x1
? ? эквивалентность ? ? ? сумма по модулю 2 + ? штрих (Шеффера) ,x2 ,x3 ), f3(x1 ,x2 )}. Тогда суперпозициями функций из F
| “не x или не y” стрелка (Пирса) ? “не x и не y”. 9. будут, например, функции: ?1(x2, x3) = f3( f1(x2), f1(x3));
10Индуктивное определение формулы: Пусть U - множество ?2(x1, x2) = f2 (x1 , f1(x1 ), f3(x1 ,x2 )). Cовершенная ДНФ -
переменных. Тогда множество формул алгебры логики над U суперпозиция функций из множества . ? 55.
определяется следующим образом: 1. Всякая переменная - формула. 56Система функций называется полной, если при помощи операций
2. Константы 0 и 1 - формулы. 3. Если А - формула, то ? А (или в суперпозиции и замены переменных из функций этой системы может
другой записи ) - формула. 4. Если А и В - формулы, то (А?В), быть получена любая функция алгебры логики. ? 56.
(А?В), (А?В), (А+В), (А?В), (А?В), (А?В) - формулы. 5. Формулами 57Мы уже имеем некоторый набор полных систем: {x+y, xy, 1}.
являются те и только те выражения, которые могут быть получены Как определить условия, при которых система полна? 57.
из констант, переменных и логических связок за конечное число 58Замкнутые классы. Множество (класс) K функций алгебры логики
шагов 1- 4. 10. называется замкнутым классом, если оно содержит все функции,
11F(x1 ,x2 ,x3,…, xn), Определение. Функция от n переменных получающиеся из K операциями суперпозиции и замены переменных, и
определенная на множестве и принимающая значения из множества не содержит никаких других функций. Пусть K - некоторое
{0, 1}, называется функцией алгебры логики или булевой функцией. подмножество функций из P2(n). Замыканием K называется множество
11. всех булевых функций, представимых с помощью операций
12«Табличное» задание функции x1 x2 ... xn-1 xn f(x1, x2, ... суперпозиции и замены переменных функций из множества K.
xn-1, xn) 0 0 ... 0 0 f(0, 0, ... , 0, 0) 0 0 ... 0 1 f(0, 0, Замыкание множества K обозначается через [K]. В терминах
... , 0, 1) 0 0 ... 1 0 f(0, 0, ... , 1, 0) замыкания можно дать другие определения замкнутости и полноты
...................... 1 1 ... 1 1 f(1, 1, ... , 1, 1) 2n. 12. (эквивалентные исходным): K- замкнутый класс, если K = [K]; K -
13Алгебраические свойства элементарных операций. 1. полная система, если [K] = P2(n). 58.
Коммутативность (или перестановочность) операции ? означает, что 59Примеры. {0}, {1} - замкнутые классы. Множество функции
. Логическая операция ? коммутативна, если связка ? принадлежит одной переменной - замкнутый класс. - замкнутый класс. Класс {1,
следующему множеству связок (существенно только, чтобы символ ? x+y} не является замкнутым классом. 59.
в равенстве всюду имел один и тот же смысл): 13. 60Замкнутые классы. 1. Т0 - класс функций, сохраняющих 0.
142. Ассоциативность операции ? означает, что .Свойство Обозначим через Т0 класс всех функций алгебры логики f(x1, x2,
ассоциативности позволяет записывать формулы, содержащие ... , xn), сохраняющих константу 0, то есть функций, для которых
одинаковые ассоциативные связки, без скобок, например, . f(0, ... , 0) = 0. 0, x, xy, x?y, x+y ? T0; 1, ? T0. Из того,
Логическая операция ? ассоциативна, если связка ? принадлежит что ? T0 следует, например, что нельзя выразить через дизъюнкцию
следующему множеству связок (существенно только, чтобы символ ? и конъюнкцию. 60.
в равенстве всюду имел один и тот же смысл): . 14. 61Поскольку таблица для функции f из класса Т0 в первой строке
153. Дистрибутивность (распределительный закон) операции ? содержит фиксированное значение 0, то для функций из Т0 можно
относительно операции ? означает, что . Дистрибутивность задавать произвольные значения только на 2n - 1 наборе значений
конъюнкции: - дистрибутивность конъюнкции относительно переменных, то есть , где - множество функций, сохраняющих 0 и
дизъюнкции; - дистрибутивность конъюнкции относительно суммы по зависящих от n переменных. Покажем, что Т0 - замкнутый класс.
модулю 2. Дистрибутивность дизъюнкции: - дистрибутивность Так как x?T0 , то для обоснования замкнутости достаточно
дизъюнкции относительно конъюнкции; - дистрибутивность показать замкнутость относительно операции суперпозиции,
дизъюнкции относительно импликации; - дистрибутивность поскольку операция замены переменных есть частный случай
дизъюнкции относительно эквивалентности. 15. суперпозиции с функцией x. 61.
16Дистрибутивность импликации: - дистрибутивность импликации 6262.
относительно конъюнкции; - дистрибутивность импликации 632. T1 - класс функций, сохраняющих 1. f(1, ... , 1) = 1. 1,
относительно дизъюнкции; - дистрибутивность импликации x, xy, x?y, x?y ? T1; Из того, что x + y ? T1 следует, например,
относительно импликации. 16. что x + y нельзя выразить через дизъюнкцию и конъюнкцию. 0, ,
174. Имеет место следующее соотношение для двойного отрицания: x+y ? T1. 63.
17. 64Т1 - замкнутый класс. 64.
185. Имеют место следующие соотношения между отрицанием, 653. L - класс линейных функций. xy, x?y ? L . = x+1 ? L; 0,
конъюнкцией и дизъюнкцией: закон (правила) де Моргана. Указанные 1, x, x+y, x1 ? x2 = 1+ x1 + x2, 65.
соотношения отражают отношение двойственности между дизъюнкцией 66Докажем, что x?y ? L . Предположим противное. Будем искать
и конъюнкцией. 18. выражение для x?y в виде линейной функции с неопределенными
196. Имеют место следующие соотношения, связанные с коэффициентами: При x = y = 0 имеем ?=0, при x = 1, y = 0 имеем
“навешиванием отрицания” на элементарные логические функции: 19. ? = 1, при x = 0, y = 1 имеем ? = 1, но тогда при x = 1, y = 1
207. Константы могут быть выражены следующим образом: 20. имеем 1? 1 ? 1 + 1, что доказывает нелинейность функции
218. Правила поглощения: 21. дизъюнкция x?y. Доказательство замкнутости класса линейных
229. Выполняются следующие свойства конъюнкции и дизъюнкции: функций очевидно. 66.
22. 67Поскольку линейная функция однозначно определяется заданием
23Все указанные тождества могут быть проверены путем значений n+1 коэффициента ?0, ... , ?n , число линейных функций
сопоставления функций, реализуемых правой и левой частями в классе L(n) функций, зависящих от n переменных равно 2n+1. 67.
формул, сопоставление таблиц значений функций. Все элементарные 684. S - класс самодвойственных функций. Функция ,
функции могут быть выражены через одну-единственную: штрих определяемая равенством называется двойственной к функции.
Шеффера или стрелку Пирса. 23. Таблица для двойственной функции (при стандартной
24Определение. Через P2(n) будем обозначать множество всех упорядоченности наборов значений переменных) получается из
разных булевых функций размерности n. Теорема. Число p2(n) всех таблицы для исходной функции инвертированием (то есть заменой 0
функций из P2(n), зависящих от переменных x1, x2, ... , xn , на 1 и 1 на 0) столбца значений функции и его переворачиванием.
равно . 24. 68.
25Переменная xi (1? i ? n) функции f(x1, x2, ... ,xi-1, xi , 690* = 1, 1* = 0, x* = x, (f*)* = f. Функция f является
xi+1, ... , xn ) из P2(n)называется существенной, если можно двойственной к f*. (x1 ? x2)* = x1 ? x2, (x1 ? x2)* = x1 ? x2.
указать такие наборы и значений переменных, что В противном 69.
случае переменную xi называют несущественной или фиктивной 70Теорема. Если функция ? получена как суперпозиция функций f,
переменной функции f. Две функции f(x1, x2, ... ,xi-1, xi , f1, f2, ... , fm, то функция, двойственная к суперпозиции, есть
xi+1, ... , xn ) и g(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) суперпозиция двойственных функций. 70.
называются равными, если множества их существенных переменных 71Доказательство. ?*(x1 ,..., xn) = ? f(?x1 ,...,? xn) =. 71.
совпадают и на любых двух наборах (x1, x2, ... ,xi-1, xi , xi+1, 72Обозначим через S класс всех самодвойственных функций из P2:
... , xn ) и (y1, y2, ... ,yi-1, yi , yi+1, ... , yn ), S = {f | f* = f }. Для самодвойственной функции имеет место
различающихся быть может только значениями несущественных тождество. ? S; 0, 1, xy, x?y ? S . x, 72.
переменных, значения функций одинаковы: f(x)=g(y). Если f(x) и 73На наборах и , которые мы будем называть противоположными,
g(y) - равные функции, то одну из них можно получить из другой самодвойственная функция принимает противоположные значения.
путем добавления и/или изъятия несущественных переменных. 25. Отсюда следует, что самодвойственная функция полностью
268. Правила поглощения: 26. определяется своими значениями на первой половине строк
27Разложение функций алгебры логики по переменным. Чтобы иметь стандартной таблицы. Поэтому число самодвойственных функций в
возможность единообразно записывать переменные с отрицанием и классе S(n) функций, зависящих от n переменных, равно: 73.
без отрицания введем следующее обозначение: 27. 74Докажем теперь, что класс S замкнут. Так как x?S , то для
28Легко видеть, что x? = 1 тогда и только тогда, когда x = ?, обоснования замкнутости достаточно показать замкнутость
то есть значение “основания” равно значению “показателя”. 28. относительно операции суперпозиции, поскольку операция замены
29Лемма. (О разложении функции по одной переменной). Пусть переменных есть частный случай суперпозиции с функцией x. 74.
f(x1 , ... , xn) - произвольная функция алгебры логики, тогда 75Пусть . Тогда достаточно показать, что Последнее
справедливо следующее представление f в форме разложения по устанавливается непосредственно: 75.
переменной x1 : (2.1). 29. 765. М - класс монотонных функций. Набор предшествует набору,
30Доказательство. Отметим прежде всего, что представление если ?i ? ?i для всех i = 1, ... , n. Наборы ? и ? называются
(2.1), естественно, справедливо для произвольной переменной xi сравнимыми, если либо ??? либо ???.В случае, когда ни одно из
из множества переменных функции f. Для доказательства рассмотрим этих оотношений не выполняется, то наборы называются
произвольный набор значений переменных (?1, ... , ?n) и покажем, несравнимыми. 76.
что левая и правая части соотношения (2.1) принимают на нем одно 7777.
и то же значение. Рассмотрим набор значений переменных (1, ?2, 78Функция алгебры логики называется монотонной, если для любых
... , ?n). Левая часть (2.1) принимает на этом наборе значение двух наборов и , таких, что , имеет место неравенство .
f(1, ?2 ,..., ?n ), а правая часть - значение 1?f(1, ?2, ... , Множество всех монотонных функций алгебры логики обозначаетcя
?n ) ? 0?f(0, ?2, ... , ?n ) = f (1, ?2, ... , ?n ). Таким через М, а множество всех монотонных функций, зависящих от n
образом, на наборах (1, ?2, ... , ?n) левая и правая части (2.1) переменных - через М(n). 78.
принимают одинаковые значения. Рассмотрим набор значений 790, 1, x, xy, x?y ? M; x+y, x?y, x?y ? M . Покажем, что класс
переменных (0, ?2, ... , ?n). Левая часть (2.1) принимает на монотонных функций М - замкнутый класс. Так как x?М, то для
этом наборе значение f(0, ?2 ,..., ?n ), а правая часть - обоснования замкнутости достаточно показать замкнутость
значение 0?f(1, ?2, ... , ?n ) ? 1?f (0, ?2, ... , ?n ) = f (0, относительно операции суперпозиции, поскольку операция замены
?2, ... , ?n ). Таким образом, на наборах (0, ?2, ... , ?n) переменных есть частный случай суперпозиции с функцией x. 79.
левая и правая части (2.1) принимают одинаковые значения. Тем 80Наборы переменных, соответственно, функций ?, f1, ... , fm ,
самым мы доказали, что левая и правая части соотношения (2.1) причем множество переменных функции ? состоит из тех и только
принимают одинаковые значения на всех наборах (?1, ... , ?n). ? тех переменных, которые встречаются у функций f1, ... , fm . 80.
«Функции алгебры логики» | Функции алгебры логики.ppt
http://900igr.net/kartinki/algebra/Funktsii-algebry-logiki/Funktsii-algebry-logiki.html
cсылка на страницу

Алгебра логики

другие презентации об алгебре логики

«Булевы функции» - Тождества с константами. Основные определения. Правило получения двойственных формул. Булевы функции и алгебра логики. Булевы функции одной переменной. Принцип двойственности. Прочтение. Функции равны. Формула содержит функции. Законы и тождества алгебры логики. Задание булевых функций. Название. Самодвойственные булевы функции.

«Функции алгебры логики» - Произвольный набор значений переменных. Самодвойственная функция. Система функций. Замкнутые классы. Огастес (Август) де Морган. Определение. Дистрибутивность импликации. Лемма. Правила поглощения. Класс функций, сохраняющих 0. Дистрибутивность. Функция f является двойственной. Набор полных систем. Значение “основания”.

«История алгебры логики» - Содержание. Определение формы. Логика– это наука о формах и способах мышления. Умозаключение. История науки алгебры логики. Булева алгебра. Джордж Буль. Основной Закон Буля. Высказывание – это форма мышления. Вильгельм Лейбниц (1646-1716). Формы мышления. Понятие. Вопросы. Аристотель.

«Логическое умножение, сложение и отрицание» - Логическое умножение (конъюнкция). Логическое умножение, сложение и отрицание. Результатом операции логического отрицания является «истина». Высказывание. Логическое отрицание (инверсия). Логическое сложение (дизъюнкция). Результатом операции логического сложения является «ложь». Истина. Компьютерный практикум.

«Примеры логических функций» - Определение. Логические функции двух переменных. Заполните таблицу истинности. Определите значение формулы, упростив и построив таблицу истинности. Логические функции. В нарушении правил обмена валюты подозреваются четыре банка. Банк B нарушил правила обмена валюты. Определите, кто из подозреваемых участвовал в преступлении.

«Алгебра логики» - Постройте отрицания. Понятие. Высказывание. Значение логической переменной. Алгебра логики. Конъюнкция. Логическое следование. Логические операции. Дизъюнкция. Умозаключение. Логические переменные. Формы мышления. Алгебра высказываний. Металлы. Появление математической, или символической, логики. Эквивалентность.

Урок

Алгебра

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