Алгебраическое представление решеток.

Введем обозначения: sup(a,b)=a b, inf(a,b)=a b. Для решетки справедливы следующие свойства:

1. Коммутативный:

a b=b a a b=b a

2. Ассоциативный:

а (в с)=(а в) с а (в с)=(а в) с

3. Идемпотентности:

а а=а а а=а

4. Поглощения:

а (а в)=а а (а в)=а

Решетки, для которой выполняется дистрибутивный закон:

а (в с)=(а в) (а с) а (в с)=(а в) (а с)

называется дистрибутивной решеткой.

Решетка называется ограниченной, если он имеет максимальный и минимальный элемент.

 

ПРИМЕР

Пусть дана решетка (рис. 13). Определить является ли решетка дистрибутивной.

 

 

РИС 13 Диаграмма Хассе решетки

 

Решетка не является дистрибутивной, т.к. для элементов {2;3;4} не выполняется дистрибутивный закон:

 

 

Дана решетка j=<F,M>,

где М={x½0<x<1}, Ф={<x,y>½x<y}. Эта решетка не является, так как не определен максимальный элемент (0.9999999999....) и минимальный элемент (0.0000000...1).

 

Обозначим в ограниченной решетке максимальный элемент 1, а минимальный элемент 0. Элемент называется дополнением элемента а в данной решетке, если и . Решетка называется с дополнением, если каждый элемент имеет хотя бы одно дополнение.

 

ПРИМЕР

Рассмотрим решетку, представленную на рис. 13. Найдем дополнения для каждого элемента решетки

Данная решетка является решеткой с дополнением.

 

Ограниченная дистрибутивная решетка с дополнением называется булевой решеткой.

 

На рис. 14 представлены дистрибутивные решетки

 

 

РИС. 14. Примеры булевых решеток

 

Математическая логика

Высказывания и операции над высказываниями.

 

Высказыванием называется повествовательное предложение, о котором можно сказать истинно оно или ложно.

1. Москва - столица России.

2. Если студент учится на отлично, то он получит красный диплом.

3. Осадки - это снег или дождь.

4. Курица – не птица.

5. Пейте томатный сок.

6. Я лгу.

7. 23<5

Высказываниями являются 1, 2, 3,4 и 7 предложения. Предложение 5 не является высказыванием, так как про него нельзя сказать истинно оно или ложно. Предложение 6 является логическим парадоксом.

Элементарным высказыванием называется высказывание, которое содержит одно утверждение (предложения 1,7).

Сложное (составное) высказывание состоит из элементарных высказываний связанных с помощью следующих предлогов и частиц: И, НЕ, ИЛИ, ЕСЛИ - ТО, ТОГДА И ТОЛЬКО ТОГДА и другие. Предложения 2,3,4 являются сложными высказываниями.

 

Операции над высказываниями.

Отрицанием высказывани я х называется новое высказывание, которое истинно, если высказывание ложное и наоборот. Таблица истинности операции отрицания имеет вид:

Дизъюнкцией двух высказываний x и y(логическое «или») называется новое высказывание, которое будет истинным тогда когда, когда хотя бы одно из высказываний будет истинным.

 

Конъюнкцией двух высказываний x и y(логическое «и») называется новое высказывание, которое будет истинным тогда когда, когда оба высказывания истины. Обозначение операции конъюнкция - & (

 

 

Импликацией двух высказываний x и y(«если – то») называется новое высказывание, которое ложно тогда, когда х(предпосылка) - истинно, а у(следствие) - ложно.

 

 

Эквивалентностью двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно, если высказывания х и у будут одновременно истинны или ложны.

 

 

Неодназночностью (суммой по модулю два) двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно тогда когда одно из высказываний х или у истинно, а другое ложно.

 

 

Штрих Шеффера (логическое «и - не») высказываний x и y - это новое высказывание, которое будет ложно тогда и только тогда когда оба высказывания истинны.

 

 

Стрелка Пирса (логическое «или - не») высказываний x и y - это новое высказывание, которое будет истинно тогда и только тогда когда оба высказывания ложны.

 

 

Для операций справедливы следующие приоритеты: ù, &, Ú, ®, «.