Линейные функции. Монотонные функции. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Рассмотрим Систему Функций:
...
Рассмотрим систему функций:
, , , . (***)
Суперпозицию функций системы (***) можно преобразовать, пользуясь правилами элементарной алгебры и специальными правилами:
, , .
В частности, если раскрыть скобки и привести подобные члены, то полученная сумма «одночленов» называется многочленом Жегалкина.
Теорема 1: Для любой функции алгебры логики существует многочлен Жегалкина, задающий эту функцию.
Доказательство: Действительно, в предыдущем параграфе было доказано, что система функций является полной в . Полную систему образует и система функции , так как . Теорема доказана.
Можно доказать, что каждая функция представляется в виде многочлена Жегалкина единственным образом. Это следует из доказанной теоремы и того факта, что число многочленов Жегалкина от переменных равно , т. е. совпадает с числом всех функций алгебры логики от этих переменных.
Определение 1: Функция называется линейной, если имеет место соотношение: .
Теорема 2: Функция, представленная многочленом Жегалкина, существенно зависит от всех входящих в него переменных.
Доказательство: Пусть, например, – переменная, о которой идёт речь в условии теоремы. Сгруппируем члены, и вынесем за скобки. Получим:
,
где функция – не равна тождественно нулю. В противном случае (в силу единственности представления функции многочленом Жегалкина) не входила бы в многочлен для . Возьмем значения переменных , на которых равна . Тогда значение будет зависеть от значения .
Замечание: Множество всех линейных функций составляет замкнутый класс.
Для того чтобы произвольную функцию представить многочленом Жегалкина, нужно выразить все операции через конъюнкцию и отрицание, учитывая, что . Затем следует привести подобные слагаемые, используя при этом правила, указанные выше: , , .
Далее будет рассмотрен класс функций, обладающих несколько иными свойствами.
Упорядочим множество , полагая . Поскольку мы будем иметь дело с функциями от нескольких переменных, то введем частичное упорядочение двоичных наборов одинаковой длины.
Определение 2: Пусть — двоичные наборы. Будем говорить, что предшествует (обозначение ), если для всех , причем, по крайней мере, для одного , имеет место строгое неравенство. Будем писать: , если или наборы и совпадают.
Это упорядочение является только частичным, так как не всякие наборы можно сравнивать.
Определение 3: Функция алгебры логики называется монотонной, если для всяких наборов таких, что имеем неравенство: .
Например, нетрудно заметить, что константы, конъюнкция, дизъюнкция являются монотонными функциями.
Теорема 3: Множество всех монотонных функций образует замкнутый класс.
Доказательство: Т.к. функция — монотонна, то достаточно показать, что если функции , , ,..., являются монотонными, то функция монотонной будет также функция:
.
Рассмотрим два произвольных набора таких, что . В этом случае , где . Следовательно,
и, значит, в силу монотонности функции имеет место неравенство: . Теорема доказана.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ... ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Линейные функции. Монотонные функции.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Упражнения для самостоятельной работы.
1. Даны следующие высказывания:
P = «Данное число – целое»,
Q = «Данное число – положительное»,
R = «Данное число – простое»,
S = «Данное число
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются формулы из некоторых
Алгоритм преобразования произвольной формулы в СНДФ.
1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание.
2) Используя дистрибутивные законы, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнк
Определения.
В математике принято одной и той же буквой обозначать различные объекты, т. е. под буквой фактически понимается переменная, принимающая значения из некоторого множества. Такие перем
Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов.
1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и
Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции.
2. Записать на языке логики предикатов следующую те
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле
Новости и инфо для студентов