Архив рубрики «Математика»

Линейное пространство подграфов данного графа

Пусть G=(V,E) есть (p,q) – граф с множеством V=(v1, v2,…, vp) вершин и E=(e1,e2, …,eq) – ребер. Пусть H⊆G – есть остовный подграф графа G с тем же множеством V вершин.

Подграфу H поставим в соответствие характеристический вектор.
aН ={a1, a2, …, an}, где i=1,2,…q и ai равен:
— 1, если ребро ei ∈ H
— 0, если ребро ei ∈ H
Прочитать остальную часть записи »

Циклы в графах

Определение: Поле (F,+,*) есть множество F элементов произвольной природы с определенными на нем двумя операциями сложением λ + μ: FxF → F и умножением λ * μ: FxF → F, Прочитать остальную часть записи »

Деревья, их характеристика, каркасы (остовы)

Определение: Дерево – есть связный граф, не имеющий циклов. Лес – Множество деревьев.

Определение: Ребро е в графе G называется циклическим, если оно принадлежит какому-либо циклу графа G, и ациклическим в противном случае. Граф G ацикличен, если каждое его ребро ациклично. (G – не имеет циклов.)
Прочитать остальную часть записи »

Обходы графа. Циклы Эйлера, Гамильтона, де Брейна

Определение: Степень вершины графа есть число инцидентных (принадлежащих) ей ребер. Граф G – четен, если каждая его вершина имеет четную степень.
Прочитать остальную часть записи »

Программа для решение уравнений онлайн

Хочу представить Вашему вниманию одну очень полезную программу, которая позволит Вам за короткое время получать решение и ответы любых математических выражений. Сразу скажу, что программа абсолютно бесплатная.
Прочитать остальную часть записи »

Способы задания графов и операции над графами

Граф G=(V,E) можно задать списком вершин и ребер. Можно задать и геометрически, нарисовав его на плоскости или любой другой поверхности и отождествив его вершины с точками на плоскости, а ребра с отрезками, соединяющими смежные (соседние) вершины.
Прочитать остальную часть записи »

Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов

Определение: (p,q) – граф, есть система объектов. G=(V,E), где V={v1, v2,…,vp} – множество вершин, E={ e1=(vi1,vj1), e2=(vi2,vj2),…, eq=(viq,vjq)}ik ≠ jk k=1,2,3,..,q – множество неориентированных ребер ik≠j1, k=1..q.
Прочитать остальную часть записи »

Теорема Поста о функциональной полноте

Теорема Поста: система функций из P2 функционально полна ⇔ система содержит:
1) Функцию, не сохраняющую константу 0.
2) Функцию, не сохраняющую константу 1.
3) НЕсамодвойственную функцию
4) НЕмонотонную функцию
5) НЕлинейную функцию
Прочитать остальную часть записи »

Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ

Лемма: (о немонотонной функции).
Суперпозицией констант 0 и 1 и немонотонной функции можно получить отрицание.
Прочитать остальную часть записи »

Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ

Лемма: (о немонотонной функции) суперпозицией констант 0 и 1 и немонотонной функции можно получить отрицание.
Прочитать остальную часть записи »

Класс монотонных функций и его замкнутость относительно суперпозиции

Пусть наборы a=(a1, a2,…,an) и b = (b1, b2,…,bn) — два набора длины n из 0 и 1, тогда а≤b, если поразрядно a1≤b1≤,…, ≤an≤bn.
Прочитать остальную часть записи »

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

Определение: Функция f(x1, x2,…,xn) сохраняет константу a ⇔ f(a, a,…,a) = a, a∈{0,1}

Теорема: Класс функций, сохраняющих константу, замкнут относительно суперпозиции.

Доказательство: пусть функции f(x1, x2,…,xn), gi(x1, x2,…,xn), i=1..n сохраняют константу а, тогда их суперпозиция h = f(g1, g2,…,gn) тоже сохраняет константу а, ибо h(a, a,…,a) = f(g1(a, a,…,a), g2(a, a,…,a),…,gn(a, a,…,a)) = f(a, a,…,a) = a

Лемма о нелинейной функции

Лемма о нелинейной функции.

Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство:
Пусть f(x1,…, xn ) — нелинейная функция, тогда полином Жигалкина для нее содержит слагаемое, в котором присутствует произведение каких-то переменных xi*xj. Пусть для простоты это будет произведение х1х2. Произведя группировку слагаемых в полиноме Жегалкина для f относительно x1х2, х1, х2, функцию f представим в виде f(x1,…, xn)=x1*x2*h0(x3,..,xn)+ {собрали все слагаемые с x1*x2 и вынесли x1*x2 за скобки. В скобках осталась сумма h0(x3,…,xn), в которой переменных x1, x2 нет} + x1*h1(x3,…, xn) + x2*h2(x3,…, xn) + h3(x3,…, xn)
Прочитать остальную часть записи »

Многочлен Жигалкина

Определение: Многочлен Жигалкина в поле F есть выражение ∑(i1,..in)∈Ex1i1x2i2..xnin.

Где xi = {x при i=1, 1 при i=0}.

Теорема Жигалкина: Всякую функцию алгебры логики можно представить единственным полиномом Жигалкина.
Прочитать остальную часть записи »

Класс линейных функций и его замкнутость относительно суперпозиции

Определение: Арифметические функции в алгебре логики есть сложение и умножение по модулю 2.

Следующие свойства математических операций проверяются непосредственно.
1) x+(y+z) = (x+y)+z
2) x+y=y+x
3) x+0=x
4) x+(-x) = 0
5) x(yz) = (xy)z
6) xy = yx
7) x*1 =x
8) x*x-1 =1, x≠0
9) x(y+z) = xy+xz
10) x+x=0
11) x*x =x (идемпотентность)
Прочитать остальную часть записи »

Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.

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

Замечание: Если функция f(x1, x2,…,xn) самодвойственна, то функция ¬f также самодвойственна, то есть
(⌈f(x1, x2,…,xn))*=⌈(⌈f(⌈x1,…, ⌈xn))= [функция самодвойственна f=f*] = ⌈f(x1, …, xn).
Прочитать остальную часть записи »

Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности

Определение: Двойственной функцией для f(x1, x1,…,xn) называется функция f* = ¬f(¬x1, ¬x2,…,¬xn)

Замечание: (f¬(x1, x2,…,xn))* = (¬f(¬x1, ¬x2,…,¬xn))* = ¬f(¬¬x1, ¬¬x2,…,¬¬xn) = f(x1, x2,…,xn) ⇒ (f*) = f.
Прочитать остальную часть записи »

СДНФ и СКНФ

Теорема (о СДНФ):

Всякая тождественно не равная 0 функция f(x1, x2,…,xn) допускает представление f(x1, x2,…,xn) = ∀f(C1,…,Cn)xC11…xCnn (1) , где дизъюнкция берется по всем наборам C=(C1,…,Cn) из 0 и 1, для которых f(c) = 1
Прочитать остальную часть записи »

Дизъюнктивная и Конъюнктивная нормальные формы. Разложение функции по компонентам

Определение: Элементарная конъюнкция, есть конъюнкция, составленная из попарно различных переменных или отрицаний переменных. (x,y,¬x&y&¬z)

Дизъюнктивная нормальная форма (ДНФ) – есть дизъюнкция, составленная из попарно различных элементарных конъюнкций. (xy∨¬xy¬z∨¬x¬y¬z)
Прочитать остальную часть записи »

Булевы свойства логических операций. Эквивалентные преобразования формул

Пусть A1, A2 – есть две формулы, x1, x2,…,xn – есть полный список или множество их переменных. Формулы A1, A2 – называются равносильными или эквивалентными ⇔, если для любого набора значений аргументов x1, x2,…,xn, они принимают одинаковые значения.
Прочитать остальную часть записи »

Суперпозиция функций. Функционально замкнутые классы

Пусть F – есть некоторое подмножество функций из P2.

Определение: Суперпозиция функций (булева формула) над F определяется индуктивно следующим образом:

1. Всякая функция f(x1, x2,…,xn) из F есть суперпозиция (формула) над F.
Прочитать остальную часть записи »

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

Пусть E2 = {0,1} есть двухэлементное множество. Набор длины n из 0 и 1 есть последовательность длины n, состоящая из 0 и 1.

Пример: (0), (1) – набор длины 1.
(0,0), (0,1), (1,0), (1,1) – длины 2.
(0,0,…,0), (0,0,…,1), …, (1,1,…,1) – набор длины n.

Теорема: Число h(n) всех наборов длины n из 0 и 1 равно 2n.
Доказательство: Индукцией по n.
Базис: n=1, h(1) = 2 =21.
Предположение индукции: Допустим h(n) = 2n.
Шаг индукции: покажем, h(n+1) = 2n+1. Разобьем все наборы длины n+1 на 2 класса: класс наборов, начиная с 0, и класс наборов, начинающихся с 1.
0, 0,0,…,0,0 1, 1,0,…,0,0
0, 0,0,…,0,1 1, 1,0,…,0,1

0, 0,1,…,1,1 1, 1,1,…,1,1
Прочитать остальную часть записи »

Булевы решетки и булевы алгебры

Определение: Дистрибутивная решетка с дополнениями называется Булевой решеткой.

Определение: Булева Алгебра А=(А, ∨, ∧, ⌐, 0, 1) есть множество А на котором определены три операции:
1) x∨y: AxA → A
2) x∧y: AxA → A
3) ⌐x: A → A
и два отмеченных элемента (0, 1) (универсальные границы) удовлетворяющие следующим аксиомам ∀ x,y,z ∈A:
Прочитать остальную часть записи »

Решетки в дискретной математике

Определение: Решетка L=(A, ∧, ∨) есть множество А с двумя определенными на нем бинарными операциями x ∨ y: A x A → A; x∧y: A*A→A удовлетворяющее следующим аксиомам:
∀a,b,c ∈ A:

L1) x ∨ x = x, x ∧ x=y – идемпотентность.
L2) x ∨ y = y ∨ x, x ∧ y = y ∧ x — коммутативность.
L3) x ∨ (y ∨ z)= (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z – ассоциативность.
L4) x ∨ (x ∧ y)= x, x ∧ (x ∨ y) = x – поглощение.
Прочитать остальную часть записи »

Отношение частичного порядка

Определение: Бинарное отношение δ⊆A*A определенное на множестве А есть отношение частичного порядка (обозначается a ≤ b), если оно удовлетворяет следующим аксиомам:

1) a ≤ a – рефлексивность
2) a ≤ b & b ≤ a → a = b — антисимметричность.
3) a ≤ b & b ≤ c → a ≤ c – транзитивность.
Прочитать остальную часть записи »

Бинарные отношения. Отношение эквивалентности, фактор-множество

Пусть G={p0=e, p1, …, pr} есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p0 тождественной подстановкой. Определим отношение x~y, положив x~y равносильно, что существует p принадлежащее G(p(x)=y). Введенное отношение есть отношение эквивалентности, то есть оно удовлетворяет трем аксиомам:
Прочитать остальную часть записи »

Основы реляционной алгебры

Фактически речь идет о том, что вместе с реляционной моделью была предложена реляционная алгебра. Под реляционной алгеброй понимают процедурный язык обработки реляционных таблиц. То есть операции реляционной алгебры манипулируют реляционными таблицами. Такая алгебра состоит из 9 операций:
Прочитать остальную часть записи »

Типовые математические модели

Поскольку основой систем моделирования являются математические модели, рассмотрим конкретные формы математического описания компонент системы различными математическими формализмами.

Для адекватного представления современных систем приходится включать в их описание формализмы, описывающие, различные по своей природе физические процессы. А также их взаимное влияние друг на друга, введение деталей в описание модели можно осуществить не только за счет увеличения размерности модели, но и за счет перехода к другой математической форме ее описания.
Прочитать остальную часть записи »

Функции и отношения, их свойства

Пусть E произвольное множество и пусть декартова степень равняется: En=ExEx…E {n раз}, объект f(x1,…,xn): En→E есть n местная функция fn или функция n переменных определённая на множестве E. Нульместная функция есть константа из E.
Прочитать остальную часть записи »

Шкала мощностей

Пусть А есть некоторое множество и P(A) есть множество всех подмножеств множества А. Очевидно, что A⊆P(A) и потому мощность |A|≤|P(A)|.

Теорема: (Кантора). |A|< |P(A)|. Прочитать остальную часть записи »




Статистика