Дискретная математика. Сергиевская И.М. - 5 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

5
0 0 0 1 1
0 0 1 1 1
0 1 0 0 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1
Построим таблицу истинности для функции
)()(),( zxyxyxg →→→
=
.
x
y
z
y
x
→
z
x
→
)()( zxyx →→→
0 0 0 1 1 1
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 0 0 1
1 0 1 0 1 1
1 1 0 1 0 0
1 1 1 1 1 1
Результирующие столбцы в таблицах истинности
совпадают, следовательно, формулы эквивалентны.
Существенные и фиктивные переменные.
Переменная
i
x ( ni
≤
≤
1 ) булевой функции
),...,,,,...,(
111 niii
xxxxxf
+−
называется фиктивной, если имеет
место равенство
=
+−
),...,,0,,...,(
111 nii
xxxxf ),...,,1,,...,(
111 nii
xxxxf
+−
для любых значений переменных
nii
xxxx ,...,,,...,
111 +−
. В против-
ном случае переменная
i
x называется существенной. Наборы
значений переменных в последнем равенстве называются
соседними по переменной
i
x . 
     0       0    0           1          1
     0       0    1           1          1
     0       1    0           0          1
     0       1    1           1          1
     1       0    0           1          1
     1       0    1           1          1
     1       1    0           0          0
     1       1    1           1          1
          Построим таблицу истинности для функции
g ( x, y ) = ( x → y ) → ( x → z ) .
     x       y     z      x→ y       x→z   ( x → y) → ( x → z )
     0       0    0          1        1             1
     0       0    1          1        1             1
     0       1    0          1        1             1
     0       1    1          1        1             1
     1       0    0          0        0             1
     1       0    1          0        1             1
     1       1    0          1        0             0
     1       1    1          1        1             1
          Результирующие столбцы в таблицах истинности
совпадают, следовательно, формулы эквивалентны.

Существенные и фиктивные переменные.
     Переменная    xi  (1 ≤ i ≤ n ) булевой                                          функции
 f ( x1 ,..., xi −1 , xi , xi +1 ,..., x n ) называется фиктивной, если имеет
место равенство
 f ( x1 ,..., xi −1 ,0, xi +1 ,..., x n ) = f ( x1 ,..., xi −1 ,1, xi +1 ,..., x n )
для любых значений переменных x1 ,..., xi −1 , xi +1 ,..., x n . В против-
ном случае переменная xi называется существенной. Наборы
значений переменных в последнем равенстве называются
соседними по переменной xi .

                                             5

Страницы