Функции алгебры логики. Стасюк В.В. - 7 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

переменных. Таким образом, все булевы функции можно рассматривать с точностью до фик-
тивных переменных и, следовательно, считать, что все функции данной системы зависят от
одних и тех же переменных.
Пример 3. Исключим из функции ( , , ) ( 1101 1101 )fxyz
=
примера 2 фиктивную пе-
ременную
x
.
Другими словами, мы должны построить таблицу функции, зависящей от всех пере-
менных существенно и принимающей значения, совпадающие со значениями
f
.
Так как половина стандартной таблицы функции, на которой значение фиктивной пе-
ременной равно 0 совпадает с другой половиной таблицы, на которой это значение равно 1,
мы не потеряем информацию, если вычеркнем все строки, где значение фиктивной перемен-
ной равно 1, а затем вычеркнем из таблицы столбец самой фиктивной переменной.
После исключения переменной
x
таблица функции примет вид:
( , ) ( 1101 )fyz
=
,
что соответствует таблице импликации
(см. таблицу 2).
y→ z
Формулы
Определение. Пусть
{
}
1
,...,
k
Ff f=
— некоторая система булевых функций. Форму-
лой над
называется выражение вида F
[
]
(
)
1
,...,
n
Ff
ϕ
ϕ
Φ=
,
где
F∈ и
ϕ
i
либо переменная, либо формула над . При этом
F
ϕ
i
называются подформу-
лами.
Согласно данному определению всякой формуле
Φ
соответствует некоторая булева
функция
f
. В этом смысле говорят, что формула
Φ
реализует функцию
f
:
f
unc f
Φ
= .
Зная таблицы для функций системы, можно построить таблицу той функции, которую реали-
зует данная формула.
Пример 4. Построим таблицу для функции, реализуемой формулой :
xy x y⊕⊕Φ=
х у xy
xy
⊕
x xy
⊕
x
⊕
y
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
0
0
1
1
1
Таким образом, формула
реализует дизъюнкцию:
xy x y⊕⊕Φ=
(
)
f
unc xy x y x y⊕⊕
=
∨
.
Равносильные формулы 
переменных. Таким образом, все булевы функции можно рассматривать с точностью до фик-
тивных переменных и, следовательно, считать, что все функции данной системы зависят от
одних и тех же переменных.
      Пример 3. Исключим из функции f ( x, y, z ) = ( 1101 1101 ) примера 2 фиктивную пе-
ременную x .
      Другими словами, мы должны построить таблицу функции, зависящей от всех пере-
менных существенно и принимающей значения, совпадающие со значениями f .
      Так как половина стандартной таблицы функции, на которой значение фиктивной пе-
ременной равно 0 совпадает с другой половиной таблицы, на которой это значение равно 1,
мы не потеряем информацию, если вычеркнем все строки, где значение фиктивной перемен-
ной равно 1, а затем вычеркнем из таблицы столбец самой фиктивной переменной.
      После исключения переменной x таблица функции примет вид:

                                        f ( y, z ) = ( 1101 ) ,

что соответствует таблице импликации y → z (см. таблицу 2).


                                          Формулы

       Определение. Пусть F = { f1 ,..., f k } — некоторая система булевых функций. Форму-
лой над F называется выражение вида

                                    Φ [ F ] = f (ϕ1 ,..., ϕ n ) ,

где f ∈ F и ϕi либо переменная, либо формула над F . При этом ϕi называются подформу-
лами.
      Согласно данному определению всякой формуле Φ соответствует некоторая булева
функция f . В этом смысле говорят, что формула Φ реализует функцию f :

                                            funcΦ = f .

Зная таблицы для функций системы, можно построить таблицу той функции, которую реали-
зует данная формула.
       Пример 4. Построим таблицу для функции, реализуемой формулой Φ = xy ⊕ x ⊕ y :

                               х    у     xy xy ⊕ x xy ⊕ x ⊕ y
                               0    0     0    0        0
                               0    1     0    0        1
                               1    0     0    1        1
                               1    1     1    0        1

Таким образом, формула Φ = xy ⊕ x ⊕ y реализует дизъюнкцию:

                                   func ( xy ⊕ x ⊕ y ) = x ∨ y .




                                Равносильные формулы

Страницы