Теорема о замене подформул на эквивалентные

 

Пусть NÎ < M> и имеет вид: N(x₁, ..., x_n) = g(G₁, ...G_i, ..., G_m). Пусть подформула G_i~G_i¢, тогда формула N(x₁, ..., x_n) = g(G₁, ..., G_i,..., G_m) эквивалентна формуле N¢ (x₁, ..., x_n) = g(G₁¢, ..., G_i¢, ..., G¢ _m).

Доказательство. Формулы N и N¢ эквивалентны, если реализуют одну и ту же функцию. Согласно построению функции, реализующей формулу имеем:

N(x₁, ..., x_n) = g(f₁(x₁, ..., x_n ), ..., f_i(x₁, ..., x_n), ..., f_m(x₁, ..., x_n)),

N¢ (x₁, ..., x_n)= g(f₁¢ (x₁, ..., x_n ), ..., f_i¢ (x₁, ..., x_n), ..., f_m¢ (x₁, ..., x_n)).

По условию G_i~G_i¢, следовательно на наборе (a₁, ..., a_n) имеем f_i (a₁, ..., a_n) = = f_i¢ (a₁, ..., a_n) следовательно, на любом наборе (a₁, ..., a_n)значения функции g(f₁, ..., f_i, ..., f_m) и g(f₁¢, ..., f_i¢, ..., f_m¢ ) совпадают. Получим N~N¢.

 

Некоторые свойства элементарных функций

 

1. Идемпотентность & и Ú: х& x=x, xÚ x=x.

2. Коммутативность &, Ú, Å, |, ~, .

3. Ассоциативность &, Ú, Å, ~, поэтому в формулах вида xyz можно не ставить никаких скобок.

4. Дистрибутивность:

а) & по отношению к Ú: x& (yÚ z)=xyÚ xz,

б) Ú по отношению к &: xÚ (y& z)=(xÚ y)& (xÚ z),

в) & по отношению к Å: x(yÅ z)=xyÅ xz.

5. Инволюция: =х.

6. Правило де Моргана: = & и = Ú .

7. Законы действия с 0 и 1:

xÚ 0=x, xÚ 1=1, xÚ =1, x& 0=0, x& 1=x, x& =0, xÅ 1= , xÅ 0=x.

8. Самодистрибутивность импликации: x (y z)=(x y) (x z).

Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.

Проверим для примера самодистрибутивность импликации: x (y z)=(x y) (x z).

x	y	z	y z	x (y z)	x y	x z

 

Следствия из свойств элементарных функций

 

1. Законы склеивания:

xyÚ x =x(yÚ )=x 1=x (дистрибутивность & относительно Ú );

(xÚ y)& (x )=x y =xÚ 0=x (дистрибутивность Ú относительно & ).

2. Законы поглощения:

xÚ xy=x(1Ú y)=x 1=x; x& (xÚ y)=xÚ xy=x.

Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы.

Пример 3:

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

1. x₂x₃Ú x_{1 2}x₃ = x₃(x₂Ú x_{1 2}) = x₃((x₂Ú x₁)& (x₂Ú ₂)) = (x₁Ú x₂)x_3.

2. x₁Ú ₁x₂Ú _{1 2}x₃Ú _{1 2}x₃x₄ = x₁Ú ₁(x₂Ú _{2 3}x₄) = x₁Ú ₁(x₂Ú x₃Ú _{2 3}x₄) = (x₁Ú ₁)(x₁Ú x₂Ú x₃Ú _{2 3}х₄) = x₁Ú (x₂Ú x₃)Ú ( )x₄ = x₁Ú (x₂Ú х₃Ú ( ))(x₂Ú x₃Ú x₄) = x₁Ú x₂Ú x₃Ú x_4.

Принцип двойственности

Определение 1 . Функции f*(x₁, ..., x_n) называется двойственной к функции f(x₁, ..., x_n), если f*(x₁, ..., x_n) = ( ₁, ..., _n).

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

x	f	f*

 

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

x	f	f*	g	g*

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

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

Пример 2. Покажем, что f(x₁, x₂, x₃)=x₁Å x₂Å x₃ – самодвойственна:

x1	x2	x3	f	f*

Если f*– самодвойственна, то ( ₁, ..., _n) = f(x₁, ..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 3. Покажем, что функция х₁Ú х₂ двойственна к x₁& x₂, функция х₁ х₂ двойственна к функции x₁|x₂.

x1 x2	f=х1Ú х2	f*	g=x1|x2	g*=x1 x2
0 0 0 1 1 0 1 1

 

Теорема о двойственных функциях

 

Если f* двойственна к f, то f двойственна к f*.

Доказательство. f*(x₁, ..., x_n) = ( ₁, ..., _n). Найдем двойственную функцию к f*, т.е. (f*( x₁, ..., x_n))* = ( ( ₁, ..., _n))* = ( ₁, ..., _n) = f(x₁, .., x_n).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

Принцип двойственности

Теорема: Пусть функция h(x₁, ..., x_n) реализована формулой h(x₁, ..., x_n) = =g(G₁, ..., G_m) = g(f₁(x₁, ..., x_n), ..., f_m(x₁, ..., x_n)), где какие-то переменные могут быть фиктивными. Тогда h*( x₁, ..., x_n) = g*(f₁*( x₁, ..., x_n), ..., f_m*(x₁, …, x_n)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство . h*(x₁, ..., x_n) = ( ₁, ..., _n) = (f₁( ₁, ..., _n), ..., f_m( ₁, ..., _n)) = ( ₁( ₁, ..., _n), ..., ( ₁, ..., _n)) = g(( ), ..., (( ) = g*(f₁*( x₁, ..., x_n), ..., f_m*( x₁, ..., x_n)), что и требовалось доказать.

Если функция h(x₁, ..., x_n) реализуется формулой N[f₁, ..., f_n], то формулу, полученную из N заменой f_i, входящих в нее, на f_i* и реализующую функцию h*(x₁, ..., x_n), будем называть двойственной и обозначать N*(x₁, ..., x_n).

Пример 4. Построить формулу, реализующую f*, если f = ((x y) Ú z) (y (xÅ yz)). Покажем, что она эквивалентна формуле N = z(xÅ y).

Найдем (xÅ y)* и (x y)*.

x y	xÅ y	(xÅ y)*	x y	(x y)*
0 0 0 1 1 0 1 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( yÚ ( xÅ zÅ )) = z( yÚ (xÅ zÅ 1)) = z( yÚ (xÅ )) = z yÚ (z xÅ z ) = z( yÚ x ) = z(xÅ y).

Тогда f = (f*)* = [z(xÅ y)]* = zÚ (x~y).

Пример 5. Найти формулу для f* и показать, что она эквивалентна формуле N = (xÚ (zÅ t)) , если f = (xyz~(tÚ x ))Ú t.

f* = ((xÚ yÚ z)Å t( Ú y))( Ú t) = ( t( Ú y)Ú (xÚ yÚ z) )( Ú t) =

= ( tÚ (xÚ yÚ z)( Ú x ))( Ú t) = tÚ (xÚ yÚ z)( Ú x Ú tx ) =

= tÚ (xÚ yÚ z)( Ú x ) = ( xÚ tÚ zÚ xÚ xz) = ( tÚ xÚ zÚ xz)

= (xÚ (zÅ t)).

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. В каком случае элемент заземлителя должен быть заменен?
2. Внешние эффекты, их виды и последствия. Теорема Коуза
3. Внешние эффекты. Теорема Коуза
4. Интернализация внешних эффектов. Теорема Коуза
5. Критерии оценки знаний на экзамене
6. Момент инерции твердого тела. Теорема Штейнера
7. Парето-эффективность и статическое экономическое равновесие в экономике обмена. Первая теорема экономики благосостояния (общий случай).
8. ПО ДОКЛАДУ О ЗАМЕНЕ РАЗВЕРСТКИ
9. Раздел 1. Перечень элементов содержания, проверяемых на едином государственном экзамене по химии в 2016 году
10. Статья 175. Порядок обращения с ходатайством об освобождении от отбывания наказания и представления о замене неотбытой части наказания более мягким видом наказания
11. Теорема «избыточной мощности» в условиях монополистической конкуренции.
12. Теорема Гаусса при наличии диэлектрика.