На головну

принцип подвійності

  1. I. 2.4. Принципи та методи дослідження сучасної психології
  2. II. Національний інтерес як головний принцип зовнішньої політики в Новий час
  3. III. Принципи лікування ДСЗ
  4. III. Принципи, які стверджують реалізацію в процесі навчання закономірностей пізнавальної діяльності учнів
  5. III.3.1) Мета покарання і загальні принципи відповідальності.
  6. XI.8 Принцип розподілу тем курсових робіт серед студентів.
  7. А) Принцип централізації управління персоналом

теорема:нехай функція h(x1, ..., xn) Реалізована формулою h(x1, ..., xn) = =g(G1, ..., Gm) = g(f1(x1, ..., xn), ..., fm(x1, ..., xn)), Де якісь змінні можуть бути фіктивними. тоді h* ( x1, ..., xn) = g* (f1* ( x1, ..., xn), ..., fm* (x1, ..., xn)), Це означає, що якщо функція задана деякою формулою, то щоб отримати подвійну функцію, треба в цій формулі всі знаки функцій замінити на подвійні, 0 на 1, 1 на 0.

Доведення. h* (x1, ..., xn) = ( 1, ..., n) = (f1( 1, ..., n), ..., fm( 1, ..., n)) = ( 1( 1, ..., n), ..., ( 1, ..., n)) =  ((  ), ..., ((  ) = g* (f1* ( x1, ..., xn), ..., fm* ( x1, ..., xn)), що й потрібно було довести.

якщо функція h(x1, ..., xn) Реалізується формулою N[f1, ..., fn], То формулу, отриману з N заміною fi, Що входять в неї, на fi* І реалізує функцію h* (x1, ..., xn), Будемо називати двоїстої і позначати N* (x1, ..., xn).

приклад 4. Побудувати формулу, що реалізує f*, Якщо f = ((x y) U z) (y (xAyz)). Покажемо, що вона еквівалентна формулі N = z(xAy).

знайдемо (xAy) * І (x y) *.

x y xAy (xAy) * x y (x y) *
 0 00 11 01 1

З таблиць видно, що

(x y) * = x ~ y = = x y  1, x y = y x ,

(x y) * = y, x y = y.

За принципом подвійності:

f* = yz ( (x (y z)  1)) = yz z(x (y z)  1) = z( yU ( xA zA  )) = z( yU (xAzA1)) = z( yU (xA  )) = z yU (z xAz  ) = z( yUx  ) = z(xAy).

тоді f = (f*) * = [z(xAy)] * = zU (x~y).

приклад 5. Знайти формулу для f * і показати, що вона еквівалентна формулі N = (xU (zAt))  , якщо f = (xyz~ (tUx  )) U t.

f* = ((xUyUz) At( Uy)) ( Ut) = ( t( Uy) U (xUyUz)  ) ( Ut) =

= ( tU (xUyUz) ( Ux  )) ( Ut) = tU (xUyUz) ( Ux Utx  ) =

= tU (xUyUz) ( Ux  ) = ( xU tU zUxUxz) = ( tUxU zUxz)

= (xU (zAt)).



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   Наступна

Елементи математичної логіки. | Приклад 2. | Приклад 4. | Теорема про розкладання функції по змінним | повні системи | теорема Жегалкина | Теорема Поста про повноту | Приклади використання теореми Поста. | Теорема про достатність чотирьох функцій. | можливість розв'язання |

© um.co.ua - учбові матеріали та реферати