Лекции по математической логике и теории алгоритмов (стр. 2 из 10)
Запись x∞y может читаться так: «ни икс и ни игрек», «икс стрелка Пирсаигрек».
Замечание. Символы Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ участвующие в обозначениях элементарных функций будем называть связками или операциями.
§1.3. Задание булевых функций посредством элементарных.
Если в логическую функцию вместо переменных подставить некоторые булевые функции, то в результате получается новая булевая функция, которая называется суперпозицией подставляемых функций (сложная функция). С помощью суперпозиции можно получать более сложные функции, которые могут зависить от любого числа переменных. Запись булевых функций через элементарные булевые функции будем называть формулой реализующей данную функцию.
Пример 1.3.1. Пусть задана элементарная булева функция x¤y. Подставим вместо x функцию x1∞x2. Получаем функцию трех переменных (x1∞x2)¤y. Если вместо переменной y подставить, например, x3∆x4, то получаем новую функцию от четырех переменных: (x1∞x2)¤(x3∆x4). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.
Забегая вперед, отметим, что любая булева функция может быть представлена как суперпозиция элементарных функций.
Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке:Ÿ, ⁄, ¤, Ø, ~. Для равносильных связок и оставшихся связок {∆,|,∞}, следует пока расставлять скобки.
Примеры 1.3.2. В формуле x⁄y¤z скобки расставляются следующим образом: ((x⁄y)¤z), т.к. операция ⁄ сильнее операции ¤ согласно нашему соглашению.
1. В формуле x¤y~zØx скобки расставляются следующим образом: ((x¤y)~(zØx))
2. В формуле (x∆y)~zØxy¤Ÿz скобки расставляются следующим образом: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Формула xØyØz, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((xØy)Øz) и (xØ(yØz)).
§1.4. Существенные и несущественные переменные.
Булева функция y=f(x 1 ,x 2 ,…,x n ) существенно зависитот переменной x k , если существует такой набор значений a 1 ,a 2 ,…,a k - 1 , a k + 1 ,a k + 2 ,…,an, что f(a1,a2,…,ak-1,0,ak+1,ak+2,…,an) πf(a1,a2,…,ak-1,1,ak+1,ak+2,…,an).
В этом случае xk называют существенной переменной, в противном случае x kназывают несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции.
Пример 1.4.1. Пусть булевы функции f1(x1,x2) и f2(x1,x2) заданы следующей таблицей истинности:
| x 1 | x 2 | f 1 (x 1 ,x 2 ) | f 2 (x 1 ,x 2 ) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Для этих функций переменная x1 — существенная, а переменная x2—несущественная.
Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать: f 1 (x 1 ,x 2 )=x 1 , f 2 (x 1 ,x 2 )=Ÿx 1 ).
§1.5. Таблицы истинности. Эквивалентные функции.
Зная таблицы истинности для элементарных функций, можно вычислить таблицу истинности той функции, которую реализует данная формула.
Пример 1.5.1. F1=x1⁄x2¤(x1⁄Ÿx2¤Ÿx1⁄x2)
| x1 | x2 | x1⁄Ÿx2 | Ÿx1⁄x2 | x1⁄Ÿx2¤Ÿx1⁄x2 | x1⁄x2 | .F1 |
| 0 0 | 0 1 | 0 0 | 0 1 | 0 1 | 0 0 | 0 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Таким образом, формула F1реализует дизъюнкцию. Пример 1.5.2. F2=x1⁄x2Øx1
| x1 | x2 | x1⁄x2 | F2=(x1⁄x2)Ø |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Таким образом, формула F2реализует константу 1. Пример 1.5.3. F3=((x1⁄x2)∆x1)∆x2.
| x1 | x2 | x1⁄x2 | (x1⁄x2)∆x1 | (x1⁄x2)∆x1)∆x2 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
Таким образом, формула F3реализует дизъюнкцию.
Булевы функции f1 и f2 называются эквивалентными, если на всяком наборе (a1, a2,…, an) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: f1=f2.
Согласно приведенным примерам 1-3, можно написать
• x1⁄x2¤(x1⁄Ÿx2¤Ÿx1⁄x2)=x1¤x2;
• x1⁄x2Øx1=1;
• ((x1⁄x2)∆x1)∆x2=x1¤x2.
§1.6. Основные эквивалентности.
Приводимые эквивалентности часто оказываются полезными при оперировании с булевыми функциями.
Ниже H, H1, H2,… означают некоторые булевы функции.
1.
Закон двойного отрицания : H = H .2. Идемпотентность
H&H=H, H¤H=H.
3. Коммутативность:
H1*H2=H2*H1, где символ * означает одну из связок &, ¤, ∆,
~, |, ∞.
4. Ассоциативность:
H1*(H2*H3)=(H1*H2)*H3, где символ * означает одну из связок &, ¤, ∆, ~.
5. Дистрибутивность:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Законы де Моргана:
H1& H2 = H1 ∨ H2 , H1∨ H2 = H1 & H2 .7. Правила поглощения:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Законы склеивания:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.9.
Законы инверсий: H ∨ H = 1, H & H = 0.10. Правила операций с константами:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Для проверки истинности приведенных эквивалентностей достаточно построить соответствующие таблицы истинности.
Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись x¤у¤z¤w корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Функциональная полнота.
В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции.
Введем в рассмотрение ряд классов функций.
1. Класс функций, сохраняющих константу 0, т.е. таких функций
y=f(x 1 ,x 2 ,…,x n ),что f(0,0,…,0)=0. Например, x¤y(Ÿx).
2. Класс функций, сохраняющих константу 1, т.е. таких функций
y=f(x 1 ,x 2 ,…,x n ),что f(1,1,…,1)=1. Например, x¤Ÿ(yx).
3.
Класс самодвойственных функций, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), что f(x 1 , x 2 ,… , x n ) = f( x 1 , x 2 ,… , x n ) .4. Класс линейных функций, т.е. таких функций y=f(x 1 ,x 2 ,…,x n ), которые могут быть представлены в виде f(x 1 ,x 2 ,…,x n )=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n , где с0, c1, c2…коэффициенты, которые могут принимать значение 0 или 1.
5. Класс монотонных функций. На множестве наборов из нулей и единиц Вn={(x 1 ,x 2 ,…,x n ):x i œ{0,1},i=1,2,…,n} введем частичный порядок следующим образом:
(a1,,a2,...,an)§(b1,b2,...,bn) тогда и только тогда когда a1§b1, a2§b2,…,an§bn. Функция f(x1, х2,...,хn) называется монотонной, если для любых двух элементов из Вn таких, что