Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

Инверсия, логическое отрицание (НЕ);

Конъюнкция, логическое умножение (И);

Дизъюнкция, нестрогая дизъюнкция, логическое сложение (ИЛИ);

Разделительная (строгая) дизъюнкция, исключающее ИЛИ, сложение по модулю 2, неравнозначность (ЛИБО);

Импликация, следование (ЕСЛИ … , ТО);

Эквиваленция, эквивалентность,, разнозначность (ТОГДА И ТОЛЬКО ТОГДА, КОГДА).

ТАБЛИЦЫ ИСТИННОСТИ

Логические операции задаются таблицами истинности, в которых отображаются их значения.
Таблица истинности — это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ

(КОНЪЮНКЦИЯ)

А	В	А/\В
0	0	0
0	1	0
1	0	0
1	1	1

Связка «И»

ПРИМЕРЫ КОНЪЮНКЦИИ
«истина» и «истина» = «истина»
«истина» и «ложь» = «ложь»
«ложь» и «истина» = «ложь»
«ложь» и «ложь» = «ложь»
ПРИМЕРЫ ДИЗЪЮНКЦИИ
«истина» или «истина» = «истина»
«истина» или «ложь» = «истина»
«ложь» или «истина» = «истина»
«ложь» или «ложь» = «ложь»
ЛОГИЧЕСКОЕ ОТРИЦАНИЕ
(ИНВЕРСИЯ)

А	Ā
0	0
0	1

Связка «НЕ»

ПРИМЕРЫ ИНВЕРСИИ
не «истина» = «ложь»
не «ложь» = «истина»
ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ
Составное высказывание, выраженное в виде формулы, называется логическим выражением.
В логическом выражении простые высказывания обозначают именами логических величин.
Величины, которые отражают истинность высказываний, называют логическими величинами.
ПРИМЕРЫ ФОРМИРОВАНИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Сложные высказывание	Использование связок	Логические выражения
Дождя не ожидается	не (ожидается дождь)	не Д
Ожидается дождь со снегом	(ожидается дождь) и (ожидается снег)	Д и С
Ожидаются осадки	(ожидается дождь) или (ожидается снег)	Д или С
Ожидается сильный мороз и снегопад	(не ожидается дождь) и (ожидается снег)	(не Д) и С

Простые высказывания:
Д – ожидается дождь; С – ожидается снег
ПРАВИЛА ОПРЕДЕЛЕНИЯ ЗНАЧЕНИЙ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

1. 
   Выражение, составленное из одной логической величины и связки «не», имеет значение, противоположное значению величины.
   
2. 
   Выражение, составленное из двух величин и связки «и», имеет значение «истина», только если значение «истина» имеют обе величины.
   
3. 
   Выражение, составленное из двух величин и связки «или», имеет значение «истина», если значение «истина» имеет хотя бы одна величина. Такое выражение имеет значение «ложь», только если значения обеих величин – «ложь».
   

Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности 0, g₁, g₂, ..., g_n> — дискретному объекту, степенной ряд g₀ + g₁z + g₂z² +… + g_nzⁿ +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
История возникновения производящих функций
Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.
В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2⁰, 2¹, 2²,..., 2ⁿ грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.
Метод производящих функций
Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный — ●, T_n — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T₂ = 2.
Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T₃ = 2T₂. Аналогично T₄ = 2T₃, то есть, обобщая для всех n, получаем рекуррентное уравнение T_n = 2T_n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — T_n = 2ⁿ (так как 2⋅2^n-1 = 2ⁿ).
А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:
G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…
Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.
Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары
G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G

получим уравнение G = Ø + ○G +●G.
Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,



Учитывая формулу суммы геометрической прогрессии  , имеем
.

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона:  , где  — число сочетаний из n по k. Тогда с учетом этого имеем:


Коэффициент при ○^k ●^n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно  .

Эту формулу можно было получить непосредственно из  заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим  то есть коэффициент при zⁿ равен 2ⁿ.

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?
Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g₀ + g₁z + g₂z² +… + g_nzⁿ +… причем коэффициенты g_k (не заданные в явном виде) — являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z — является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.
G(z) = g₀ + g₁z + g₂z² +… + g_nzⁿ +… — называется производящей функцией для последовательности 0, g₁, g₂, ..., g_n>. Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z₀, за исключением z = 0, так как G(0) = g₀.
Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g_k

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x² + x³ + ..., а в замкнутом  .