Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 4
Текст из файла (страница 4)
Покажите, что верно и обратное: любая монотонная булева функция либо постоянна (всюду истинна или всюду ложна),либо может быть выражена формулой, содержащей только ∧ и ∨.10. Пусть ϕ → ψ — тавтология. Покажите, что найдётся формула τ ,которая включает в себя только общие для ϕ и ψ переменные, для которой формулы (ϕ → τ ) и (τ → ψ) являются тавтологиями. (Более общийвариант этого утверждения, в котором рассматриваются формулы с кванторами, называется леммой Крейга.)В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Любая булева функция может играть роль связки. Например, можно рассмотреть связку (p notand q), задаваемуюэквивалентностью(p notand q) ↔ ¬(p ∧ q)(словами: (p notand q) ложно, лишь если p и q истинны).
Через неёвыражается отрицание (p notand p), после чего можно выразитьконъюнкцию, а затем, как мы знаем, и вообще любую функцию.(Знакомые с цифровыми логическими схемами малого уровня интеграции хорошо знакомы с этим утверждением: достаточно большойзапас схем И-НЕ позволяет реализовать любую требуемую зависимость выхода от входов.)Другая интересная полная система связок — сложение по модулю 2, конъюнкция и константа 1 (которую можно считать 0-арнойсвязкой, задающей функцию от нуля аргументов).
Представленныев этой системе булевы функции становятся полиномами с коэффициентами в кольце вычетов по модулю 2. Идея рассматривать булевыфункции как полиномы (оказавшаяся неожиданно плодотворной впоследние годы) была высказана в 1927 г. российским математикомИваном Ивановичем Жегалкиным.Назовём мономом конъюнкцию любого набора переменных иликонстанту 1 (которую естественно рассматривать как конъюнкциюнуля переменных). Название это естественно, так как при нашихсоглашениях (1 обозначает истину, 0 — ложь) конъюнкция соответствует умножению.Назовём полиномом сумму таких мономов по модулю 2 (это значит, что 0 ⊕ 0 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1 и 1 ⊕ 1 = 0). Ясно, что два повторяющихся монома можно сократить (ведь сложение по модулю 2),так что будем рассматривать только полиномы без повторяющихсямономов.
При этом, естественно, порядок членов в мономе (как и порядок мономов в полиноме) роли не играет, их можно переставлять.[п. 2]Полные системы связок19Теорема 5 (о полиномах Жегалкина). Всякая булева функция однозначно представляется таким полиномом. Существование искомого полинома следует из теоремы 4, таккак конъюнкция есть умножение, отрицание — прибавление единицы, а дизъюнкцию можно через них выразить (получится p + q + pq).Надо только заметить, что степени не нужны: переменные принимают значения 0 и 1, так что xn можно заменить на x.Можно также сослаться на известное из алгебры утверждение отом, что всякая функция с аргументами из конечного поля (в данном случае это двухэлементное поле вычетов по модулю 2) задаётсяполиномом.
(Так получается новое доказательство теоремы 3.)Далее можно заметить, что полиномов столько же, сколько буnлевых функций, а именно 22 . В самом деле, булева функция можетпринимать любое из двух значений в каждой из 2n точек булевакуба Bn , а многочлен может включать или не включать любой из2n мономов. (Мономов ровно 2n , потому что каждый моном включает или не включает любую из n переменных.) Поэтому избыткаполиномов нет, и если любая функция представима полиномом, тоединственным образом.Можно и не ссылаться на сведения из алгебры и теорему 4, а датьявную конструкцию.
Это удобно сделать индукцией по n. Пусть мыуже умеем представлять любую булеву функцию от n−1 аргументовс помощью полинома. Тогда ϕ(p1 , . . . , pn ) можно представить какϕ(p1 , . . . , pn ) = ϕ(0, p2 , . . . , pn ) + [ϕ(0, p2 , . . . , pn ) + ϕ(1, p2 , . . . , pn )]p1(проверьте). Остаётся заметить, что правую часть можно представить полиномом по предположению индукции.Для единственности также есть другое доказательство: пусть двамногочлена (имеющие степень 1 по каждой переменной) равны привсех значениях переменных. Тогда их сумма (или разность — вычисления происходят по модулю 2) является ненулевым многочленом(содержит какие-то мономы), но тождественно равна нулю. Так небывает, и это легко доказать по индукции.
В самом деле, любой многочлен A(p1 , . . . , pn ) можно представить в видеA(p1 , . . . , pn ) = B(p2 , . . . , pn ) + p1 C(p2 , . . . , pn ),где B и C — многочлены от меньшего числа переменных. Подставляясначала p1 = 0, а затем p1 = 1, убеждаемся, что многочлены B и20Логика высказываний[гл. 1]C равны нулю во всех точках, и потому (согласно предположениюиндукции) равны нулю как многочлены (не содержат мономов). 11. Пусть F — произвольное поле.
Назовём мультилинейной функцией полином от n переменных с коэффициентами из F , в котором все показатели степеней равны либо 0, либо 1. (Таким образом, каждый мономв ней есть произведение коэффициента и некоторого набора переменныхбез повторений.) Будем рассматривать B = {0, 1} как подмножество F .Докажите, что всякая булева функция Bn → B однозначно продолжаетсядо мультилинейной функции F n → F , и коэффициенты мультилинейнойфункции можно считать целыми числами.Если рассматривать произвольные булевы функции в качествесвязок, возникает вопрос: в каком случае набор булевых функцийобразует полный базис? (Это значит, что любая булева функцияпредставляется в виде композиции функций из набора, т. е.
записывается в виде формулы, где связками служат функции набора.)Подобные вопросы вызывали в своё время большой интерес и былихорошо изучены. Начальным этапом явилось такое утверждение:Теорема 6 (критерий Поста). Набор булевых функций являетсяполным тогда и только тогда, когда он не содержится целиком ни водном из пяти следующих «предполных классов»:• монотонные функции;• функции, сохраняющие нуль;• функции, сохраняющие единицу;• линейные функции;• самодвойственные функции.(Функция f монотонна, если она монотонно неубывает по каждому из своих аргументов. Функция f сохраняет нуль/единицу, еслиf (0, .
. . , 0) = 0 (соответственно f (1, . . . , 1) = 1). Функция f линейна,если она представима многочленом, в котором все мономы содержат не более одной переменной. Наконец, функция f называетсясамодвойственной, если f (1 − p1 , . . . , 1 − pn ) = 1 − f (p1 , . . . , pn ).) Если набор содержится в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверитьдля каждого из классов в отдельности) и поэтому набор не являетсяполным. Докажем обратное утверждение.
Пусть для каждого класса выбрана какая-то функция, в нём не лежащая. Убедимся, что с[п. 2]Полные системы связок21помощью комбинаций выбранных функций можно получить все булевы функции.У нас есть функция, не сохраняющая нуль. Подставим вместовсех аргументов одну и ту же переменную.
Получится функция отодного аргумента, отображающая нуль в единицу, то есть либо константа 1, либо отрицание. Сделав то же самое с функцией, не сохраняющей единицу, получим либо константу нуль, либо отрицание.Таким образом, у нас либо есть отрицание, либо обе константы 0 и 1.Если есть обе константы, то всё равно можно получить отрицание. Возьмём немонотонную функцию. Легко понять, что она должна менять значение с единицы на нуль при изменении какого-то одного аргумента с нуля на единицу (в самом деле, будем увеличивать аргументы по одному, в какой-то момент значение функцииуменьшится.) Зафиксировав значения остальных аргументов (ведьмы считаем, что константы есть), получаем отрицание.Имея отрицание и несамодвойственную функцию, легко получить константы (если их не было). В самом деле, несамодвойственность означает, что f (x1 , .
. . , xn ) = f (1 − x1 , . . . , 1 − xn ) для каких-тозначений x1 , . . . , xn ∈ {0, 1}. Вместо нулевых значений переменныхx1 , . . . , xn подставим p, вместо единиц подставим ¬p, получится однаиз констант. Вторая получится отрицанием.Теперь у нас есть константы, отрицание и нелинейная функцияf (p1 , . . . , pn ). Нелинейность означает, что в её представлении в видемногочлена есть моном, состоящий более чем из одной переменной.Пусть, например, этот моном содержит переменные p1 и p2 . Сгруппируем члены по четырём группам и получим выражениеp1 p2 A(p3 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
