Учебник по дискретной математике

Оглавление
n1.doc (26 стр.)
Скачать
1   ...   5   6   7   8   9   10   11   12   ...   26

Пример 3:


Упростим формулы:

1. x2x3x12x3 = x3(x2x12) = x3((x2x1)&(x22)) = (x1x2)x3.

2. x11x212x312x3x4 = x11(x223x4) = x11(x2x323x4) = (x11)(x1x2x323х4) = x1(x2x3)()x4 = x1(x2х3())(x2x3x4) = x1x2x3x4.


2.3 Принцип двойственности
Определение 1. Функции f*(x1, ..., xn) называется двойственной к функции f(x1, ..., xn), если f*(x1, ..., xn) = (1, ..., n).

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:


x

f

f*

0

1

0

0

1

1


Функции f(x) = x и g(x) = двойственны сами себе:

x

f

f*

g

g*

0

1

0

1

0

1

1

0

1

0

так как f*(0)=(1).

Определение 2. Если f*(x1, ..., xn) = f(x1, ..., xn), то f(x1, ..., xn) называется самодвойственной.

Пример 2. Покажем, что f(x1,x2,x3)=x1x2x3 – самодвойственна:

x1

x2

x3

f

f*

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

1

0

1

0

0

1

0

1

1

0

1

0

0

1

Если f*– самодвойственна, то (1, ..., n) = f(x1, ..., xn), т.е. на противоположных наборах функция принимает противоположные значения.
Портфель ученика
© lib.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации