Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



 

Пусть NÎ < M> и имеет вид: N(x1, ..., xn) = g(G1, ...Gi, ..., Gm). Пусть подформула Gi~Gi¢, тогда формула N(x1, ..., xn) = g(G1, ..., Gi,..., Gm) эквивалентна формуле N¢ (x1, ..., xn) = g(G1¢, ..., Gi¢, ..., G¢ m).

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

N(x1, ..., xn) = g(f1(x1, ..., xn ), ..., fi(x1, ..., xn), ..., fm(x1, ..., xn)),

N¢ (x1, ..., xn)= g(f1¢ (x1, ..., xn ), ..., fi¢ (x1, ..., xn), ..., fm¢ (x1, ..., xn)).

По условию Gi~Gi¢, следовательно на наборе (a1, ..., an) имеем fi (a1, ..., an) = = fi¢ (a1, ..., an) следовательно, на любом наборе (a1, ..., an)значения функции g(f1, ..., fi, ..., fm) и g(f1¢, ..., fi¢, ..., fm¢ ) совпадают. Получим 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. x2x3Ú x1 2x3 = x3(x2Ú x1 2) = x3((x2Ú x1)& (x2Ú 2)) = (x1Ú x2)x3.

2. x1Ú 1x2Ú 1 2x3Ú 1 2x3x4 = x1Ú 1(x2Ú 2 3x4) = x1Ú 1(x2Ú x3Ú 2 3x4) = (x1Ú 1)(x1Ú x2Ú x3Ú 2 3х4) = x1Ú (x2Ú x3)Ú ( )x4 = x1Ú (x2Ú х3Ú ( ))(x2Ú x3Ú x4) = x1Ú x2Ú x3Ú x4.

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

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

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

x f f*

 

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

x f f* g g*

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

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

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

x1 x2 x3 f f*

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

Пример 3. Покажем, что функция х1Ú х2 двойственна к x1& x2, функция х1 х2 двойственна к функции x1|x2.

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*(x1, ..., xn) = ( 1, ..., n). Найдем двойственную функцию к f*, т.е. (f*( x1, ..., xn))* = ( ( 1, ..., n))* = ( 1, ..., n) = f(x1, .., xn).

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

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

Теорема: Пусть функция 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(( ), ..., (( ) = 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) Ú 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Ú zt( Ú 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)).

 


Поделиться:



Популярное:

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


Последнее изменение этой страницы: 2016-04-09; Просмотров: 945; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.033 с.)
Главная | Случайная страница | Обратная связь