Значительное внимание в настоящей главе уделяется логике высказываний и логике предикатов. Символический язык этих разделов математической логики широко используется не только в самой математике, но и в технической литературе. Кроме того можно полагать, что формальные методы логического обоснования станут со временем необходимым элементом при решении практических задач, а значит, и составной частью математического аппарата инженера. Этому в значительной мере способствует развитие автоматизации проектирования с применением вычислительной техники.
В заключительном параграфе приводятся некоторые сведения из теории алгоритмов, которые могут представлять интерес для инженеров в связи с задачами алгоритмизации процессов производства и проектирования.
1. Логические функции
1. Логические функции как отображения. Отличительная особенность логических функций состоит в том, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов. Если область значений функции содержит k различных элементов, то она называется k-значной функцией.
Чтобы различать элементы области значений функции, их необходимо как-то отметить. Удобнее всего элементы перенумеровать числами от 1 до k или обозначить какими-нибудь символами (например, буквами). Перечень всех символов, соответствующих области значений, называют алфавитом, а сами символы — буквами этого алфавита (буквами могут служить как собственно буквы латинского, русского или другого алфавита, так и порядковые числа или любые другие символы).
- 504 -
Логические функции могут зависеть от одной, двух и, вообще, любого числа переменных (аргументов) x1, x2, ..., xn. В отличие от самой функции, аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств.
В теоретико-множественном смысле логическая функция n переменных y = f(x1, x2, ..., xn) представляет собой отображение множества наборов (n-мерных векторов, кортежей, последовательностей) вида (x1, x2, ..., xn), являющегося областью ее определения, на множестве ее значений N = {α1, α2, ..., αn}. Логическую функцию можно также рассматривать как операцию, заданную законом композиции X1, X2, ..., Xn где - множества, на которых определены аргументы x1 ∈ X1, x2 ∈ X2, ..., xn ∈ Xn.
2. Однородные функции. Если аргументы принимают значения из того же множества, что и сама функция, то ее называют однородной функцией. В этом случае X1 = Х2 = ... = Хn = N и однородная функция, рассматриваемая как закон композиции Nn → N определяет некоторую п-местную операцию на конечном множестве N.
Областью определения однородной функции у = f(х1, х2, ..., xn) служит множество наборов (х1, х2, ..., xn), называемых словами, где каждый из аргументов х1, х2, ..., xn замещается буквами k-ичного алфавита {0, 1, ..., k -1}. Количество n букв в данном слове определяет его длину.
Очевидно, число всевозможных слов длины n в k-ичном алфавите равно kn. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от n переменных выражается числом k(kn).
Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х1, х2, ..., xn) символически представляется упорядоченной последовательностью n таких чисел и рассматривается как запись n-разрядного числа в позиционной системе счисления с основанием k, т. е. x1kn -1 + x2kn –2 + … + xn -1k1 + xnk0 = q. Числа q = 0, 1, ..., kn - 1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kn -разрядные числа в той же системе счисления.