Основные математические понятия
Определение математических понятий: множество, история теории множеств, их сравнение и операции над ними; функция и способы ее задания, группа как непустое множество, конъюнктивная нормальная форма, формальная логика и нормальный алгоритм Маркова.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 19.06.2011 |
| Размер файла | 540,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Свойства
§ Все циклические группы абелевы.
§ Каждая конечная циклическая группа изоморфна группе -- со сложением по модулю n (её также обозначают ), а каждая бесконечная -- изоморфна , группе целых чисел по сложению.
§ В частности, для каждого натурального числа n существует единственная (с точностью до изоморфизма) циклическая группа порядка n.
§ Каждая подгруппа циклической группы циклична.
§ У циклической группы порядка n существует ровно ц(n) порождающих элементов, где ц -- функция Эйлера
§ Если p -- простое число, то любая группа порядка p циклическая и единственна с точностью до изоморфизма (это следует изтеоремы Лагранжа).
§ Прямое произведение двух циклических групп порядков n и m циклично тогда и только тогда, когда n и m взаимно просты.
§ Например, изоморфна , но не изоморфна .
§ Основная теорема о конечнопорождённых абелевых группах утверждает, что любая конечнопорождённая абелева группа единственным образом разлагается в прямое произведение примарных циклических групп. Примарной группой может быть циклическая группа , где p -- простое число, или .
§ Мультипликативная группа любого конечного поля является циклической (она порождается элементом поля наибольшего порядка).Кольцо эндоморфизмов группы изоморфно кольцу . При этом изоморфизме числу r соответствует эндоморфизм , который сопоставляет элементу сумму r его экземпляров. Такое отображение будет биекцией, если и только если r взаимно просто с n, так что группа автоморфизмов изоморфна .
Доказательства Утверждение. Каждая подгруппа циклической группы циклична. Доказательство. Пусть G -- циклическая группа и H -- подгруппа группы G. Если группа G тривиальна (состоит из одного элемента), то H = G и H циклична. Если H -- тривиальная подгруппа (состоит из единичного элемента или совпадает со всей группой G), то H циклична. Далее в ходе доказательства будем считать, что G и H не являются тривиальными.
Пусть g -- образующий элемент группы G, а n -- наименьшее положительное целое число, такое что . Утверждение:
Следовательно, .
Пусть .
.
Согласно алгоритму деления с остатком
.
.
Исходя из того, каким образом мы выбрали n и того, что , делаем вывод, что r = 0.
.
Следовательно, .
Нормамльная подгрумппа (также инвариамнтная подгрумппа) -- подгруппа особого типа, у которой левый и правый смежные классы совпадают. Она особенно важна потому, что позволяет строить факторгруппу по заданной группе. Определения
Подгруппа N группы G называется нормальной, если она инвариантна относительно сопряжений, то есть для любого элемента n изN и любого g из G, элемент gng ? 1 лежит в N:
Следующие условия нормальности подгруппы эквивалентны:
1. Для любого g из G, .
2. Для любого g из G, gNg ? 1 = N.
3. Множества левых и правых смежных классов N в G совпадают.
4. Для любого g из G, gN = Ng.
Условие (1) логически слабее, чем (2), а условие (3) логически слабее, чем (4). Поэтому условия (1) и (3) часто используются при доказательстве нормальности подгруппы, а условия (2) и (4) используются для доказательства следствий нормальности.
Примеры
§ {e} и G -- всегда нормальные подгруппы G. Они называются тривиальными. Если других нормальных подгрупп нет, то группа Gназывается простой.
§ Центр группы -- нормальная подгруппа.
§ Коммутант группы -- нормальная подгруппа.
§ Любая характеристическая подгруппа нормальна, так как сопряжение -- это всегда автоморфизм.
§ Все подгруппы N абелевой группы G нормальны, так как gN = Ng. Неабелева группа, у которой любая подгруппа нормальна, называется гамильтоновой.
§ Группа параллельных переносов в пространстве любой размерности -- нормальная подгруппа евклидовой группы; например, в трёхмерном пространстве поворот, сдвиг и поворот в обратную сторону приводит к простому сдвигу.
§ В группе кубика Рубика, подгруппа, состоящая из операций, действующих только на угловые элементы, нормальна, так как никакое сопряжённое преобразование не заставит такую операцию действовать на краевой, а не угловой элемент. Напротив, подгруппа, состоящая лишь из поворотов верхней грани, не нормальна, так как сопряжения позволяют переместить части верхней грани вниз.
Свойства
§ Нормальность сохраняется при сюрьективных гомоморфизмах и взятии обратных образов.
§ Нормальность сохраняется при построении прямого произведения.
§ Нормальная подгруппа нормальной подгруппы не обязана быть нормальной в группе, то есть нормальность не транзитивна. Однако характеристическая подгруппа нормальной подгруппы нормальна.
§ Каждая подгруппа индекса 2 нормальна. Если p -- наименьший простой делитель порядка G, то любая подгруппа индекса pнормальна.
§ Если N -- нормальная подгруппа в G, то на множестве левых (правых) смежных классов G / N можно ввести групповую структуру по правилу
(g1N)(g2N) = (g1g2)N
Полученное множество называется факторгруппой G по N.
§ N нормальна тогда и только тогда, когда она тривиально действует на левых смежных классах G / N.
Исторические факты Эварист Галуа первым понял важность нормальных подгрупп.
Гомоморфизм (от др.-греч. ?мьт -- равный, одинаковый и мпсцЮ -- вид, форма) -- это морфизм в категории алгебраических систем. Это отображение алгебраической системы А, сохраняющее основные операции и основные соотношения.
Например, рассмотрим группы , . Отображение называется гомоморфизмом групп и , если оно одну групповую операцию переводит в другую: .
Некоторая общая теория, уточняющая понятия гомоморфизма, изоморфизма и морфизма предложена известной группой французских математиков N. Bourbaki в их книге «Теория множеств» (Глава 5). Связанные определения
§ Гомоморфный образ -- образ математического объекта, имеющего структуру полугруппы, группы, кольца, алгебры при гомоморфном отображении. Иногда говорят и о гомоморфных образах других математических объектов, например, графов.
§ Ядро гомоморфизма
§ для гомоморфизма абелевых групп (в частности для колец, векторных пространств и т. д.) -- прообраз нуля,
§ для общих групп -- прообраз единицы.
Свойства Ядро гомоморфизма является нормальной подгруппой. Гомоморфный образ группы изоморфен факторгруппе по ядру гомоморфизма (теорема о гомоморфизме).
Типы гомоморфизмов
§ Мономорфизм -- однозначный (инъективный) гомоморфизм
§ Эпиморфизм -- сюръективный гомоморфизм
§ Изоморфизм -- взаимно однозначный (биективный) гомоморфизм
§ Эндоморфизм -- гомоморфизм в само множество
§ Автоморфизм -- взаимно однозначный гомоморфизм в само множество
Математимческая ломгика (теоретическая логика, символическая логика) -- раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.» Согласно определениюП.С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика -- вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков).» Это определение соответствует определению С.К. Клини: математическая логика -- это «логика, развиваемая с помощью математических методов». Также А.А. Марков определяет современную логику «точной наукой, применяющей математические методы». Все эти определения не противоречат, а дополняют друг друга. Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие -- нет. Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и , то выводима и формула B.Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление И называется семантически пригодным для языка Я, если любая выводимая в И формула языка Я является верной. Аналогично, исчисление И называется семантически полным в языке Я, если любая верная формула языка Я выводима в И.
Математическая логика изучает логические связи и отношения лежащие в основе логического (дедуктивного) вывода с использованием языка математики Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат К. Гёделя о том, что так называемое классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка. С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является теорема Гёделя о неполноте, утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики. Стоит отметить, что на практике множество элементарных логических операций является обязательной частью набора инструкций всех современных микропроцессоров и соответственно входит в языки программирования. Это является одним из важнейших практических приложений методов математической логики, изучаемых в современных учебниках информатики.
Бумлева фумнкция (или логимческая функция, или функция амлгебры ломгики) от n переменных -- в дискретной математике отображение Bn > B, где B = {0,1} -- булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения Bn называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается P2, а от n переменных -- P2(n). Булевы функции названы так по фамилии математика Джорджа Буля.
Основные сведения Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 22n. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
|
x1 |
x2 |
… |
xn |
f(x1,x2,…,xn) |
|
|
0 |
0 |
… |
0 |
f(0,0,…,0) |
|
|
1 |
0 |
… |
0 |
f(1,0,…,0) |
|
|
0 |
1 |
… |
0 |
f(0,1,…,0) |
|
|
1 |
1 |
… |
0 |
f(1,1,…,0) |
|
|
0 |
1 |
… |
1 |
f(0,1,…,1) |
|
|
1 |
1 |
… |
1 |
f(1,1,…,1) |
Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной.
Нульарные функции При n = 0 количество булевых функций сводится к двум 220 = 21 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами -- тождественный нуль и тождественная единица.
Унарные функции При n = 1 число булевых функций равно 221 = 22 = 4. Определение этих функций содержится в следующей таблице.
Таблица значений булевых функций от одной переменной:
|
x |
0 |
x? |
x |
1 |
|
|
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
Названия булевых функций от одной переменной:
|
Обозначение |
Название |
|
|
0 |
тождественный ноль, тождественная ложь, тождественное "НЕТ" |
|
|
x?, ¬x, x' |
отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.) |
|
|
x |
тождественная функция, логическое "ДА", "YES"(англ.) |
|
|
1 |
тождественная единица, тождественная истина, тождественное "ДА", тавтология |
Бинарные функции При n = 2 число булевых функций равно 22? = 24 = 16.
Таблица значений булевых функций от двух переменных:
|
x |
y |
0 |
xvy |
x<y |
x |
x>y |
y |
x?y |
x|y |
x & y |
x ? y |
y |
x>y |
x |
x<y |
x ? y |
1 |
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Названия булевых функций от двух переменных:
|
Обозначение |
Название |
|
|
0 |
тождественный ноль, тождественная ложь, тождественное "НЕТ" |
|
|
x v y, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y) |
НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Дамггера, функция Вембба,стрелка Пимрса |
|
|
x < y, x < y, x LT y, LT(x,y) |
меньше, инверсия обратной импликации |
|
|
x, НЕ1(x,y), NOT1(x,y), x', ¬x |
отрицание (негация, инверсия) первого операнда |
|
|
x > y, x > y, x GT y, GT(x,y) |
больше, инверсия прямой импликации |
|
|
y, НЕ2(x,y), NOT2(x,y), y', ¬y |
отрицание (негация, инверсия) второго операнда |
|
|
x ? y, x +2 y, x ? y, x >< y, x <> y, x XOR y, XOR(x,y) |
сложение по модулю 2, не равно, измена, исключающее «или» |
|
|
x | y, x NAND y, NAND(x,y), x И-НЕ y, И-НЕ(x,y) |
НЕ-2И, 2И-НЕ, антиконъюнкция, штрих Шемффера |
|
|
x & y, x · y, xy, x ? y, x AND y, AND(x,y), x И y, И(x,y), min(x,y) |
2И, конъюнкция |
|
|
x ? y, x = y, x EQV y, EQV(x,y), x ~ y, x - y |
равенство, эквивалентность |
|
|
y, ДА2(x,y), YES2(x,y) |
второй операнд |
|
|
x > y, x ? y, x ? y, x LE y, LE(x,y) |
меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) |
|
|
x, ДА1(x,y), YES1(x,y) |
первый операнд |
|
|
x < y, x ? y, x ? y, x GE y, GE(x,y) |
больше или равно, обратная импликация (от второго аргумента к первому) |
|
|
x ? y, x + y, x ИЛИ y, ИЛИ(x,y), x OR y, OR(x,y), max(x,y) |
2ИЛИ, дизъюнкция |
|
|
1 |
тождественная единица, тождественная истина, тождественное "ДА",тавтология |
Тернарные функции При n = 3 число булевых функций равно 22? = 28 = 256. Некоторые из них определены в следующей таблице:
|
x |
y |
z |
xvyvz |
?2(x,y,z) |
x?y?z |
x|y|z |
min(x,y,z) |
x=y=z |
x?y?z |
?2(x,y,z) |
f1 |
f2 |
max(x,y,z) |
|
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Названия булевых функций трех переменных:
|
Обозначения |
Названия |
|
|
xyz = (x,y,z) = Webb2(x,y,z) |
3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса |
|
|
Переключатель по большинству с инверсией, 3-ППБ-НЕ,мажоритарный клапан с инверсией |
||
|
x?y?z = [?(x,y,z)] = NE(x,y,z,v) |
Неравенство |
|
|
xyz = (x,y,z) |
3-И-НЕ, штрих Шеффера |
|
|
x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z) |
3-И, минимум |
|
|
(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v) |
Равенство |
|
|
x?2y?2z = x+2y+2z = ?2(x,y,z) = +2(x,y,z) |
Тернарное сложение по модулю 2 |
|
|
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x) |
переключатель по большинству, 3-ППБ, мажоритарный клапан |
|
|
f1 |
Разряд займа при тернарном вычитании |
|
|
f2 |
Разряд переноса при тернарном сложении |
|
|
(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z) |
3-ИЛИ, максимум |
множество функция группа конъюнктивная марков
Полные системы булевых функций
Основная статья: Замкнутые классы булевых функций
Конъюнктивная нормальная форма (КНФ).. Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции (суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:
|
x |
y |
z |
f(x,y,z) |
||
|
0 |
0 |
0 |
1 |
||
|
1 |
0 |
0 |
0 |
||
|
0 |
1 |
0 |
1 |
||
|
1 |
1 |
0 |
1 |
||
|
0 |
0 |
1 |
0 |
||
|
1 |
0 |
1 |
0 |
||
|
0 |
1 |
1 |
1 |
||
|
1 |
1 |
1 |
0 |
Говорят, что множество функций замкнуто относительно операции суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это же множество. Замкнутые множества функций называют также замкнутыми классами. В качестве простейших примеров замкнутых классов булевых функций можно назвать множество {x}, состоящее из одной тождественной функции, или множество {0}, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы {0} и , мы с помощью суперпозиции сможем получить константу 1, которая в исходных классах отсутствовала.
Разумеется, множество P2 всех возможных булевых функций тоже является замкнутым. Тождественность и двойственность Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
|
(законы де Моргана) |
(дистрибутивность конъюнкции и дизъюнкции)
Функция называется двойственной функции , если . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.Полнота системы, критерий Поста Основная статья: Критерий Поста Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством P2.
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
§ Функции, сохраняющие константу T0 и T1;
§ Самодвойственные функции S;
§ Монотонные функции M;
§ Линейные функции L.
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с P2, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию. Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
Представление булевых функций. Основная статья: Представление булевых функций Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре У, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
§ Как построить по данной функции представляющую её формулу?
§ Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
§ В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
§ Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций. Дизъюнктивная нормальная форма (ДНФ) Основная статья: Дизъюнктивная нормальная форма Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция
§ правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);
§ полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
§ монотонная, если она не содержит отрицаний переменных.
Например -- является ДНФ.
Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .
Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля -- даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию , где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является , что можно упростить до .
Конъюнктивная нормальная форма (КНФ). Основная статья: Конъюнктивная нормальная форма
Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ -- это конъюнкция простых дизъюнкций. Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот». КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:
которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило
выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот. Полиномы Жегалкина Основная статья: Полином Жегалкина Полином Жегалкина это форма представления логической функции с помощью Функции Жегалкина (Исключающее ИЛИ). Для получения полинома Жегалкина следует выполнить следующие действия:
1. Получить ДНФ функции
2. Все ИЛИ заменить на Исключающее ИЛИ
3. Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)
4. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы
В логике логическими операциями называют действия, вследствие которых порождаются новые понятия, возможно с использованием уже существующих. В более узком, формализованном смысле, понятие логической операции используется в математической логике и программировании.
Формальная логика
Логические операции с понятиями -- такие мыслительные действия, результатом которых является изменение содержания или объёма понятий, а также образование новых понятий.
К операциям, которые связаны преимущественно с изменением содержания понятий, относятся:
§ отрицание;
§ ограничение ;
§ обобщение ;
§ деление.
К операциям, которые связаны преимущественно с объёмами понятий, относятся:
§ сложение;
§ умножение;
§ вычитание.
Данные операции могут быть записаны математически с помощью теории множеств.
Переход же к математической логике связан с понятием суждений и установлением операций над ними с целью получения сложных суждений.
Математическая логика. Логическая операция (логический оператор, логическая связка, пропозициональная связка) -- операция над высказываниями, позволяющая составлять новые высказывания путем соединения более простых. В качестве основных обычно называют конъюнкцию ( или &), дизъюнкцию (), импликацию (), отрицание (). В смысле классической логики логические связки могут быть определены через алгебру логики. В асинхронной секвенциальной логике определена логико-динамическая связка в виде операции венъюнкции (). Математическая формула (от лат. formula -- уменьшительное от forma -- образ, вид) -- принятая в математике (а также физике и прикладных науках) символическая запись законченного логического суждения (определения величины, уравнения, неравенства или тождества).В более широком смысле формула -- всякая чисто символьная запись (см. ниже), противопоставляемая в математике различным выразительным способам, имеющим геометрическую коннотацию: чертежам, графикам, диаграммам, графам и т.п. Основные виды (численных) формул Как правило, в формулу входят переменные (одна или более), причём сама формула представляет собой не просто выражение, а некое суждение. Такое суждение может утверждать что-то о переменных, а может -- о применяемых операциях. Точный смысл формулы зачастую подразумевается из контекста и его невозможно понять непосредственно из её вида. Можно выделить три распространённых случая:
§ Формула должна сообщить, как искать значения переменной (уравнения и т.п.);
§ Формула (записываемая как «искомое = выражение») определяет величину через свои параметры (аналогично присваиванию в программировании и иногда записывается через диграф «:=» как в языке Pascal, но в принципе может считаться вырожденным частным случаем уравнения);
§ Формула является собственно логическим утверждением: тождеством (например, аксиомой), утверждением теоремы и т.п.
Уравнения. Уравнение -- формула, внешняя (верхняя) связка которого представляет собой бинарное отношение равенства. Однако, важная особенность уравнения заключается также в том, что входящие в него символы делятся на переменные и параметры (присутствие последних, впрочем, необязательно). Например, x2 = 1 является уравнением, где x -- переменная. Значения переменной, при которых равенство истинно, называются корнями уравнения: в данном случае таковыми являются два числа 1 и ?1. Как правило, если уравнение на одну переменную не является тождеством (см. ниже), то корни уравнения представляют собой дискретное, чаще всего конечное (возможно и пустое) множество.Если в уравнение входят параметры, то его смысл -- для заданных параметров найти корни (т.е. значения переменной, при котором равенство верно). Иногда это можно сформулировать как нахождение неявной зависимости переменной от параметра (параметров). Например x2 = a понимается как уравнение на x (это обычная буква для обозначения переменной, наряду с y, z и t). Корнями уравнения является квадратный корень из a (считается, что их имеется два, разных знаков). Следует отметить, что подобная формула, сама по себе, задаёт лишь бинарное отношение между x и a и её можно понимать в обратную сторону, как уравнение на aотносительно x. В данном элементарном случае, речь может идти скорее об определении a через x: a = x2. Тождества Тождество -- суждение, верное при любых значениях переменных. Обычно, под тождеством подразумевают тождественно верное равенство, хотя снаружи тождества может стоять и неравенство или какое-либо другое отношение. Во многих случаях тождество можно понимать как некое свойство используемых в нём операций, например тождество a + b = b + a утверждает коммутативность сложения. С помощью математической формулы довольно сложные предложения могут быть записаны в компактной и удобной форме. Формулы, становящиеся истинными при любом замещении переменных конкретными объектами из некоторой области, называются тождественно-истинными в данной области. Например: «для любых a и b имеет место равенство ». Данное тождество можно вывести из аксиом сложения и умножения в коммутативном кольце, которые сами по себе также имеют вид тождеств. Тождество может и не включать в себя переменные и являться арифметическим (или каким-то ещё) равенством, как например . Неравенства. Формула-неравенство может пониматься в обоих описанных в начале раздела смыслах: как тождество (например, неравенство Коши -- Буняковского) или же, подобно уравнению, как задача на отыскание множества (а точнее, подмножества области определения), которому может принадлежать переменная, или переменные.
Сложение и вычитание. Используются знаки «+» и «?» (последний на письме довольно слабо отличим от дефиса). Унарный минус может быть использован лишь при первом (левом) слагаемом, поскольку в противном случае возникали бы неопрятные и избыточные конструкции «a + (?b)» и «a ? (?b)», ничем не отличающиеся по смыслу от более простых «a ? b)» и «a + b» соответственно. По причине ассоциативности сложения, расстановка скобок для задания порядка выполнения сложения не имеет математического смысла. В алгебре слагаемыми называют аргументы как сложения, так и вычитания. Порядок выполнения вычитания, при отсутствии скобок, таков, что вычитаемым оказывается лишь член, выписанный непосредственно справа от знака вычитания, а не результат выполнения операций каких-либо сложения и вычитания, записанных правее. Таким образом со знаком минус входят в сумму лишь те «слагаемые», непосредственно слева от которых знак «?» имеется. Умножение. Знак умножения чаще всего опускается. Это не вызывает двусмысленности, поскольку переменные обозначаются обычно одиночными буквами, а выписывать умножение записанных цифрами констант друг на друга бессмысленно. В редких случаях, когда двусмысленности не избежать, умножение обозначается центрированным по вертикали символом точки «·». Символ «?» применяется лишь в школьной арифметике, в технических текстах (в особом контексте), а также некоторые системы вставляют его на месте знака умножения при переносе формулы на другую строку (обычно однако, перенос по знаку умножения избегается).
Деление. Деление в формулах записывается при помощи дробной черты. В школьной арифметике применяется также «?» (обелюс).
Нормамльный алгоримтм Мамркова (НАМ) -- один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово "алгоритм". Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и следовательно современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.
Описание Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам в котором алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н.формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D -- два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L иD -- два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Подобные документы
Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.
реферат [70,9 K], добавлен 11.03.2009Понятия множеств и их элементов, подмножеств и принадлежности. Способы задания множеств, парадокс Рассела. Количество элементов или мощность. Сравнение множеств, их объединение, пересечение, разность и дополнение. Аксиоматическая теория множеств.
курсовая работа [1,5 M], добавлен 07.02.2011Краткое историческое описание становления теории множеств. Теоремы теории множеств и их применение к выявлению структуры различных числовых множеств. Определение основных понятий, таких как мощность, счетные, замкнутые множества, континуальное множество.
дипломная работа [440,3 K], добавлен 30.03.2011Понятие множества и его элементов. Обозначение принадлежности элемента множеству. Конечные и бесконечные множества. Строгое и нестрогое включение. Способы задания множеств. Равенство множеств и двухсторонее включение. Диаграммы Венна для трех множеств.
презентация [564,8 K], добавлен 23.12.2013Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция [253,7 K], добавлен 01.12.2009Математическая теория нечетких множеств и нечеткая логика как обобщения классической теории множеств и классической формальной логики. Сферы и особенности применения нечетких экспертных систем. Анализ математического аппарата, способы задания функций.
презентация [1,0 M], добавлен 17.04.2013Понятие множества, его обозначения. Операции объединения, пересечения и дополнения множеств. Свойства счетных множеств. История развития представлений о числе, появление множества натуральных, рациональных и действительных чисел, операции с ними.
курсовая работа [358,3 K], добавлен 07.12.2012Множество как ключевой объект математики, теории множеств и логики. Операции над множествами, числовые последовательности. Множества действительных чисел. Бесконечно малые и большие функции. Непрерывность функции в точке. Свойства непрерывных функций.
лекция [540,0 K], добавлен 25.03.2012Понятие функции как одно из важнейших понятий математики. Сюръекции, инъекции и биекции. Композиция или сложная функция и ее иллюстрация. Зависимость множеств Х и У, их области, элементы и простейших операций над ними. История математической функции.
реферат [58,8 K], добавлен 11.03.2009Сущность теории множеств и особенности ее практического применения. Операции над множествами и их главные закономерности. Порядок нахождения области определения функции, участков ее возрастания и убывания. Определение вероятности исследуемого действия.
контрольная работа [46,5 K], добавлен 02.12.2011
