Алгебра логики Скачать
презентацию
<<  История алгебры логики Алгебра высказываний  >>
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Необходимо условиться об алфавите
Две задачи
Две задачи
47
47
48
48
49
49
50
50
Фото из презентации «Функции алгебры логики» к уроку алгебры на тему «Алгебра логики»

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

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

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

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

Алгебра

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