Головна

булеві решітки

  1.  булеві функції
  2.  булеві функції
  3.  Булеві функції двох змінних.
  4.  Булеві функції та їх властивості.
  5.  Злом решітки
  6.  Класи булевих функцій

Введемо позначення Sup (a, b) = a E b, Inf (a, b) = a C b,

Будемо вважати традиційно використовуються тут значки E, C не мають ніякого відношення до теоретико-множинним операціям об'єднання і перетину.

Якщо виконуються закони:

1. a E b = b E a 1 '. a C b = b C a

2. (a E b) E c = (b E c) Ea = a E b E c 2 '. (A C b) C c = (b C c) C a = a C b C c

3. a E (a C b) = a 3 '. а C (b E a) = a

4. a E a = a 4 '. а C a = a

то має місце решітка.

Тобто решітка можна визначити як алгебру Z = , для операцій якій виконуються перераховані вище закони.

решітка називається дистрибутивної, Якщо додатково до вищеперелічених виконується дистрибутивний закон:

5. a E b C c = (a E b) C (a E c) 5 '. а C (b E c) = a C b E a C c

приклад :Недістрібутівная решітка:

 a E b C e = (a E b) C (a E e)

а E e = a C a

a = a

b E c C d = b C c E b C d

b E e = a E a

b ? a недістрібутівность

Ці грати недістрібутівная.

решітка називається обмеженою, Якщо вона має максимальний і мінімальний елементи.

Наприклад, якщо взяти відрізок дійсної осі від 0 до 1 (разом з кінцевими точками) і відношення "менше", то це буде обмежена решітка. Прибравши крайні точки, отримуємо необмежену грати.

 1 + 1

 - Необмежена решітка - обмежена

(Без 1 і 0)

0 0

Зазвичай мінімальний елемент решітки позначають як 0, а максимальний як 1.

a - доповнення а, якщо а E a = 1 і а C a = 0

решітка є гратами з доповненням, Якщо кожен елемент має хоча б одне доповнення.

Обмежена дистрибутивная решітка з доповненням є булевої.

Приклади булевих решіток:

                   
     
       
         
2n
 
 
 
 




 поняття множини |  Операції над множинами |  Діаграми Ейлера - Венна |  алгебра множин |  Кортеж. Графік |  властивості графіків |  І П С Т |  ставлення еквівалентності |  морфізм |  грати |

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