Что такое творческие кладовые по дискретной математике
портала "Русский след"?

                                                                   Поэзия всей сути чисел
                                                     Сравнима с россыпью светил,
                                                     Прекрасна как алмазный бисер
                                                    Родоначальница мерил. (Ю.Н. Пиллигримов)

---

                     29. Классы функций. Базисная система функций.
                      Теорема Поста .

        Одним из разделов алгебры логики является направление "исчисление классов",
доведённой до современного уровня русским математиком и логиком Жегалкиным И.И
Подразделом этого направления является класс функций. Высказывания-функции, которые
могут принимать значения "ложь", "истина" в зависимости от того, какое значение будет
придано переменной, входящей в высказывание функцию. Например, высказывание-функция "х - столица  одного из государств" будет "ложь", если заменить х  словом  "Ялта", и будет "истина", если поставить слово "Киев".

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

        Совокупность объектов,  имеющих один или несколько характеристических признаков называют классом. При этом не обязательно, чтобы каждый объект обладал всей совокупностью характеристик. Например, говорят "строевой лес", но в этом лесу есть  и деревья, которые нельзя строго отнести к строевому лесу. Общим же признаком у строевого леса, является расположение участка на котором находится строевой лес. Другими словами, признаки, в которых рассматриваемые предметы сходны называются общими  признаками класса. Предметы (объекты), входящие в класс, называются элементами класса.

        Классы могут быть конечными (например класс планет солнечной системы), бесконечными, например класс  вещественных чисел, неопределёнными, пустыми и состоящими из одного элемента.

        Так как класс определяется как совокупность предметов, то операции над этими предметами, очевидно включают операции над множествами. С классами можно проводить такие операции как пересечение классов, то есть тоже самое, что и пересечение множеств с вытекающими формулами (конъюнкцией) логического умножения, объединение классов, то есть объединение множеств , то есть дизъюнкции или иначе логического сложения, дополнения классов, нечто аналогичное с дополнением множеств или отрицанием. Поэтому часто логика классов рассматривается как соответствующее  усиление и расширение логики высказываний. 

            К алфавиту логики высказываний добавляются переменные а,b,c...для классов, знаки для операций с классами,, постоянные термины 1 и 0, знаки для отношений между классами. Дополнительно уточняется понятие формула и вводится понятие терма.

            Терм - это выражение, обозначающее индивидуумы и классы, и записываемое в виде букв или сочетаний букв, соединённых с помощью логических связок. и заключённых в скобки. Понятие терм   вводится индуктивно, от есть от частных примеров к общему целостному понятию, как например: 0 - есть терм;  каждая переменная есть терм, если  s и t термы, то и  (s + t), s×t, и (s)' -  тоже термы. Никаких других больше термов нет. 

            Соединение термов союзами связками образует предложение. Например, s = t; это предложение. Если А и В - предложения, то знак  Ù  - означает конъюнкцию,  Ú   - дизъюнкцию, черта сверху - отрицание, знаки квантора общности "х  и знака существования   $х - также являются предложениями.

              Термы могут быть постоянными (например 0 для пустого класса, 1 - для универсального класса) и могут быть переменными (например,  а, b, c...)_

                Для любых термов t, r, s  следующие целый ряд формулы являются теоремами,

например,  теорема t × (r + s) = (t × r) + (t × s) (дистрибутивность)_

                    (r + s)× t = (r × t) + (s ×  t)   (дистрибутивность)_

              (t × r) × s = t × (r × s)   (ассоциативность умножения)

               t + s = r + s É  = r  (правило сокращения для  знака +),  где знак   É -  знак импликации, сходный с союзом "если..., то"

               Теоремами также будет еще целый ряд формул, написанных по аналогии с формулами на множествах. Терм в системе классов является объектом и уподобляется существительному в исчислении  предикатов. Предикат - это сказуемое суждение, то есть то, что высказывается (утверждается или отрицается), иными словами, предикат - это логическая функция , определённая на предметной области и принимающая значение либо истинности, либо ложности. Предикаты могут быть одноместные, то есть с одной переменной - объектом, либо многоместными, то есть иметь несколько переменных. Функции-предикаты могут быть однородными и неоднородными.

                Если объекты-аргументы принимают значения из того же множества, что и  сама функция, то такую функцию называют однородной. Множество, на   котором объекты-аргументы, которые иногда, называются   элементами,   называется    областью   определения  однородной   функции         у = f (x₁, x₂, x₃…, x_n). служит множество наборов (x₁, x₂, x₃…, x_n ), называемых словами, где каждый из аргументов   x₁, x₂, x₃…, x_n замещается буквами k-ичного алфавита {0, 1,...k-1)}. Количество букв в данном слове определяет его длину, очевидно, что число слов такого множества составляют его мощность и равно k ⁿ  .      Отличительной особенностью логических функций является то, что они принимают значения в конечных множествах. Аргументы неоднородной функции в отличие от однородных, могут принимать значения из любых конечных или бесконечных множеств, но область определения значений самих функций ограничена конечными множествами.

               Следует отметить, что стремление оптимизировать всё и вся на свете, не обошло   и направление уменьшения числа основных операций в различных исчислениях алгебры логики.   Так для булевой алгебры достаточно иметь три функции, а Шефферу достаточно было одной операции  штриха, чтоб все остальные операции можно было им заменить. Естественно, возникает вопрос, а сколько надо основных функций для решения возникающих проблем в приложения логики? Так возникло понятия базисной системы функций.Забота  о минимизации базисной системе функций не случайна, так введение этих функций идёт на уровне аксиом, остальные функции устанавливаются как закон, как теорема, как формула. как свойство, вытекающие из базисной системы функций. Чем меньше аксиом и больше доказательств, то есть теорем, тем меньше спорных моментов в справедливости утверждений.

                  Под базисной системой функций понимается минимальная полная система функций, то есть такая полная система, удаление из которой одной функции делает систему неполной. Понятия функциональная полнота и базис в логическом пространстве стали практически синонимами. Система функций, суперпозицией которой может быть представлена любая функция из некоторого множества булевых функций называется функциональной полнотой. При анализе с точки зрения полноты выяснено, что полнотой обладают: дизъюнкция и отрицание, конъюнкция и отрицание, штрих Шеффера, стрелка Пирса, импликация и константа 0.

                Все выводимые законы на основе базисной системы могут быть не только вспомогательным средством для решения возникающих задач, но и фундаментальными законами для решения  новых перспективных направлений. Знаменательным примером этого явился закон Поста о вычислительной машине. Этот же закон, независимо от Поста, был высказан и Тьюрингом. В настоящее время этот закон явился основой для создания и построения вычислительной техники, в обоснованиях Алфёровым понятия алгоритм. Суть  этого закона в упрощённом варианте состоит в следующем: имеется бесконечная лента. имеется считывающая (распознающая)_головка и четыре варианта команд. Процесс работы машины Тьюринга-Поста можно схематически быть описан так: в каждый данный дискретный момент управляющая головка считывает символ, записанный на квадрате ленты, и посылает входной сигнал в ту часть машины, в которой содержится конечное число состояний. Отвечая на входной сигнал, машина может изменить символ, записанный на ленту и сдвинуть ленту на шаг вперёд или назад. В следующий такт работы читающая головка прочтёт символ, записанный на другом квадрате ленты и и пошлёт новый входной сигнал Устройство ответит на него определённым действием Суть закона Поста состоит в  следующем: алгоритмические процессы  -- это процессы, которые могут осуществляться на соответствующем образом сконструированных машинах.

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