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

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) (табл.2.12).

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

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

 

Таблица 2.12

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.

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

 

Пример 2.7

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

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.

 

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

 

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

Пример 2.8. Покажем с помощью таблицы истинности

(табл. 2.13) что константа 0 двойственна к 1.

 

Таблица 2.13

x	f	f *

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

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

Таблица 2.14

x	f	f *	g	g *

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

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

 

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

Таблица 2.15

x 1	x 2	x 3	f	f *

 

 

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

 

 

Таблица 2.16

x 1 x 2	f = х 1Ú х 2	f *	g = x 1| x 2	g *= x 1 x 2
0 0 0 1 1 0 1 1

 

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

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

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

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

 

 

Теорема 2.2. О принципе двойственности

Пусть функция 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 *(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).

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

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

Таблица 2.17

x y	x Å y	(x Å y)*	x y	(x y)*
0 0 0 1 1 0 1 1

Из табл. 2.17 видно, что

(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).

 

Разложение булевой функции по переменным

Обозначим x^s =

Посмотрим, чему равно x^s при разных значениях x и s (табл. 2.18).

 

Таблица 2.18

x\s

 

Из табл. 2.18 следует: x^s =1 тогда и только тогда, когда x = s.