шпора по дискретной математике за второй курс

1) Аксиоматическая система Гильберта-Аккермана для исчисления высказываний.
Система Гильберта - Аккерамана (СГА) - формальная система, моделью которой является булева алгебра. Иными словами в СГА могут быть получены все утверждения, соответствующие тавтологиям.
СГА состоит из следующих элементов:
1. Алфавит 2. Правила образования формул 3. Правила преобразования формул.
1. Алфавит - список первичных понятий. а) Большие латинские буквы, возможно с индексами. Букве не сопоставляется никакое значение истины или лжи - это просто символ.
б) Знаки - операции над высказываниями. Это абстрактные символы.
2. Правила образования формул. Введём a) Все простые высказывания - формулы. (А, В, С)
б) Если и - формулы, то - формула. в) Если - формула, то - формулы.
Сокращённая запись формул: - просто упрощённая запись. , а также
3. Правила преобразования формул. а) Список первичных тезисов или аксиом:
(А1) ; (А2) ; (А3) ; А(4)
Тезис - общезначимая формула. б) Первичные или основные правила вывода:
Правило подстановки. В тезисе можно заменить простое высказывание всюду, где оно встречается на формулу к :
Правило отрыва, modus ponens: Если - тезис и - тезис, то - тезис.
Символ доказуемости , где формула, А - простое высказывание, - ф-ла.
Можно только одну букву заменить везде на простое высказывание.

2) Интерпретация и модель формальной системы.
Исчисление - формальный оператор, который позволяет по определённым правилам оперировать со знаками определённого вида. В результате применения правил на основе ранее известных фактов могут быть получены (доказаны) новые, производные факты. т.е. исчисление - построение новых функций при помощи доказательств.
Модель формальной системы - интерпретация её элементов (слов L) сопоставляющая каждому символу системы некоторый реальный объект.
Любое исчисление содержит следующие компоненты.
1. Язык L для записи утверждений. (как правило слова L - формулы)
2. Набор базовых утверждений (аксиом) А, записанных на языке L. Этот набор аксиом полагается заведомо верным.
3. Набор правил R по которым из аксиом строятся новые, производные утверждения - теорема.
Таким образом создаётся формальная система
Формальная система - чисто синтаксическое понятие. Смысл символов языка L безразличен, важно что теоремы получены из аксиом по правилам.
Алгебра - вычисление значений функций.
Формальное доказательство - цепочка строк (слов L), в которой каждая строка ─ одно из следующего:
а) аксиома в в формальной системе Т б) Теорема, полученная из предыдущих строк правилами R.

3) Синтаксис и семантика формальных систем. Понятия доказуемости и истинности, непротиворечивости и корректности, формальной и материальной полноты.
1. Синтаксис и семантика. ФС - синтаксическое понятие. Смысл символов языка системы безразличен, важно только соблюдение правил вывода.
Модель ФС - интерпретация элементов ФС, сопоставляющая каждому символу системы некоторый осмысленный объект. Например: модель СГА - булева алгебра. Модель задаёт семантический смысл ФС, т.е. законы булевой алгебры.
2. Понятие доказуемости и истинности. а) Утверждение и формула выводима в ФС Т означает, что есть приводящее к формальное доказательство: , где n ─ число шагов док-ва. Доказуемость - семантическое понятие.
б) Утверждение " истинно в модели ФС Т" означает, что при интерпретации символов Т. В модели ФС Т мы получаем истинное утверждение об элементах модели. Понятие истинности обозначается: Истинность - семантическое понятие.

Важно: Если , то оно необязательно истинно модели.
3. Понятие корректности и противоречивости. а) ФС Т в которой выводятся только истинные высказывания - корректно. Корректность - семантическое понятие.
Пример корректной системы - системы, все аксиомы которой в модели истинны. Т.к. правила вывода сохраняют истинность => все теоремы также истинны.
б) ФС Т, в которой невозможно доказать утверждение и одновременно его отрицание - непротиворечива.
Если ФС корректна => ФС непротиворечива.
Корректная система доказывает истинные утверждения, и истинное утверждение и его отрицание не могут быть истинными одновременно.
4. Понятие материальной и формальной полноты: а) ФС Т материально полна, если в ней выводится любая истинная в модели формула. Материальная полнота - семантическое понятие. б) ФС Т формально полна, если к её системе аксиом невозможно добавить новую, не зависящую от исходных, аксиому так, чтобы система не потеряло свойство непротиворечивости. Это синтаксическое понятие.

4) Непротиворечивость и полнота системы Гильберта-Аккермана.
Возьмём алгебру высказываний как модель СГА, носитель , сигнатура . Каждой букве в формуле СГА сопоставляем значение истинности, каждой операции - операции Булевой Алгебры.
1. СГА корректна и непротиворечива. Док-во: Множество тезисов совпадают с множеством тавтологий:
а) Аксиомы - тавтологии (по таблице истинности) б) тезисы, полученные с помощью тавтологии.
в)Так как в Булевой Алгебре если a=>b и а - тавтология, то b - тавтология, то тезисы, полученные при помощи тавтологии => Если СГА и , то и ─ тавтологии, что невозможно => СГА непротиворечивая и корректна.
2. СГА материально и формально полна. а) тавтология ─ тезис. => тавтология => СГА материально полна. б) Является ли СГА формально полной? Или: можем ли мы добавить к А1-А4 новую независимую аксиому так, чтобы СГА осталось непротиворечивой? Доказательство:
Пусть - формула и , где ─ простые высказывания, входящие в формулу. Так как , то - не тавтология и набор значений такой, что . Сделаем замену: Если , то , , то , где формула. Обозначим новую формулу на , т.е. . - всегда ложно. => - тавтология => тавтология выводима из и одновременно - противоречие.

5) Независимость аксиом системы Гильберта-Аккермана.
СГА имеет независимую систему аксиом. Док-во:
Возьмём нестандартную модель. Пусть -
модель СГА. Но .
Докажем независимость:
, , при формулы выводимы из по
и => эти формулы также . Но при , т.е. она не выводима из
Аналогичным образом показывается независимость других аксиом (для этого требуются другие интерпретации)

6) Формальная арифметика, способы её аксиоматизации и их недостатки.
Цель формальной арифметики - построить аксиоматическую систему для задания множества натуральных чисел и соотношений между ними. Существует 2 классических способа задания аксиоматики натуральных чисел.
1. Через аксиомы Пеано. а) 0 - натуральное число. б) Для любого натурального числа х существет определённое натуральное число S, называемое следующим за х в)
г) д) Принцип индукции. Каждое множество натуральных чисел, содержащее 0 и вместе с каждым числом х содержащее S(x) содержит все натуральные числа.
2. Аксиоматически определяются множества действительных чисел, как полное упорядоченное поле. Затем натуральные числа определяются как действительные числа вида
Недостатки указанных способов:
1. Пятая аксиома Пеано использует понятие множество, а это не даёт возможности записать аксиомы в виде формул первого порядка.
2. Опирается на понятие более широкие чем натуральные числа, что не даёт возможности задать систему через них.

7) Язык 1 порядка для формальной арифметики. Арифметические функции.
Формулы первого порядка - слова языка первого порядка. Дадим его определение в приложении к арифметике:
1. Фиксируем некоторый набор символов который назовём индивидными переменными. Они предназначены для обозначения натуральных чисел.
2. Введём символы операций: где S обозначает x+1
3. Терм - последовательность переменных, запятых, скобок и символов операций, построенных по следующим правилам: а) Индивидуальная переменная - это терм; б) Символ 0 - терм; в) Если t - терм,
то S(t) - терм; г) Если и ─ термы, то термы;
4. Правила задания формул: а) Если и ─ термы, то выражения и атомарные формулы. б) Атомарная формула - формула.; в) Если формула, то формула.; г) Если и формулы, то формулы; д) Если ─ формула, а индивидная переменная, то и - формулы.
Формулы, определённые таким образам называеют формулами 1 порядка. Сигнатура
Аналогично можно определить язык 1 порядка другой сигнатуры, например язык предикатов.
Параметр формулы т.е. переменная, от которой может зависеть её значение истинности:
а) Параметрами терма являются все входящие в него индивидные переменные.
б) Параметрами атомарной формулы - параметры всех входящих в неё термов.
в) Параметры формулы те же, что и у формулы
г) Параметрами формул являются все параметры и все параметры
д) Параметрами формул и являются все параметры формулы , кроме переменной ,
иначе параметры называют свободными переменными. Заметим, что формула может иметь одновременно параметр х и использовать квантор в некоторой части формулы. В этом случае говорят, что переменная имеет свободные и связанные вхождения.
Замкнутые формулы или суждения - формулы, не имеющие параметров. Они имеют значения истина или ложь.
Для того, чтобы задать значения лжи или истины формуле с параметрами, необходимо присвоить её свободным переменным значения натуральных чисел.
Арифметические формулы. местное отношение на множестве часто отождествляется с предикатом . местное отношение выражается формулой , если истинна <=> кортеж для кортежей .
Формула выражает n-местную функцию f с натуральными аргументами и значениями, если она выражает n+1 - местное отношение, состоящее из всех кортежей , где . Выразимые при помощи формул такого вида, записанных во введённой ранее сигнатуре отношения и функции называют арифметическими. Пример: 1)Предикат формулой 2) Предикат
3) Предикат Если какое-то отношение является арифметическим, то в дальнейшем его можно использовать в формулах, как если бы оно входило в сигнатуру.
8) Аксиоматическое задание арифметики Пеано в языке 1 порядка.
Возьмём сигнатуру ( Будем называть арифметические формулы языка 1 порядка этой сигнатуры. Построим систему аксиом для натуральных чисел.
Арифметика Пеано (РА).
(Обозначим и опустим кванторы в аксиомах). Аксиомы РА:
а) (с кванторами было бы ; б) ; в) ; г) ; д) ; е) ; ж) , где A(x) ─ произвольная арифметическая формула. 1-6 ─ аксиомы. 7 - схема аксиомы.
Вывод: арифметика РА строится на базе Ф1-Ф7 и правила подстановки: Натуральные числа в РА задаются через ; …
В РА доказуемы все арифметические формулы. Доказательство ведётся при помощи подстановки в аксиомы значений переменных.

9) Понятие предиката как функции. Кванторы и дескриптор. Запись общих и частных высказываний.
Одноместным предикатом называется всякая функция одного переменного, аргумент которой определён на некотором множестве , называемом «миром речи», и принимающая значения на множестве .
Множество , на котором предикат принимает только истинные значения, называют областью истинности предиката.
Предикат называется тождественно истинным, если и тождественно ложным, если .
Аналогичным образом определяются многоместные предикаты.
Исчисление предикатов имеет 2 подхода:
• Многосортный (в мире речи выделяются подмножества (домены, сорта, типы));
• Односортный (мир речи предполагается однородным, т.е. на любое место любого предиката может быть поставлен любой элемент из мира речи).
Переход от многосортного подхода к односортному: при некорректной подстановке предикат принимает значение «ложь» (0).
Высказывания по степеням общности делятся на:
• Единичные (об одном элементе);
• Частные (о некоторых предметах данного класса);
• Общие (обо всех предметах данного класса).
Частные и общие высказывания образуются из предикатов при помощи кванторов.
Квантор существования: (для записи частных высказываний), т.е. : «существует x такое, что P(x)»
В конечном мире речи:
Квантор всеобщности: (для записи общих высказываний), т.е. : «для любого x P(x)».
В конечном мире речи:
Можно ввести квантор единственности существования:
Дескриптор: . возвращает единственный х, для которого выполняется P(x).

10) Аксиоматическая система Гильберта-Аккермана для исчисления предикатов: алфавит и правила построения формул. Связанные и свободные переменные.
Алфавит – список первичных понятий:
а) Прописные маленькие буквы (возможно с индексами): - простые высказывания (пропозициональные буквы);
б) Знаки: и - дизъюнкция и отрицание;
в) Скобки (,) – знаки пунктуации;
г) Предметные переменные: ;
д) Предикатные переменные: ;
е) Кванторы: ;
С каждой предикатной переменной связано конечное натуральное число, называемое числом мест.
Правила образования формул (формулы обозначаются прописными готическими буквами):
1) Все простые высказывания – суть формулы;
2) Если - формула, то - формула;
3) Если - n-местная предикатная переменная, а - суть предметные переменные, то - формула; при этом переменные называются свободными.
4) Если есть формула, в которой предметная переменная x является либо свободной, либо вовсе не встречается, то и также суть формулы, причём предметная переменная x в этих новых формулах называется связанной, а формула - областью действия квантора.
5) Если и - формулы, такие, что одна и та же предметная переменная не встречается связанной в одной формуле и свободной в другой, то - формула.

11) Аксиоматическая система Г-А для исчисления предикатов: аксиомы и правила вывода.
Аксиомы:
А) аксиомы из Сист. Г-А для исчисления высказываний:

б) Дополнительно вводятся аксиомы

Правило вывода:
1) В тезисе любую пропозициональных вхождениях можно заменить на любую формулу, при условии, что:
А) Результат является формулой ( не возникает конфликт переменных)
Б) Рассматриваемая формула не содержит предметных переменных, которые являются связанными в исходном тезисе.
2) (Замена предметных переменных) всякую предметную переменную можно заменить на любую другую, если она не является связанной. - здесь можно заменить на любую переменную кроме .
3) Пусть в формуле встречается местная предикатная переменная в каждом вхождении предметная переменные могут быть различными (*)
Тогда можно заменить на ф-лу , которая будет иметь по меньшей мере переменных.
В качестве формулы можно брать только такую, в которой среди всех прочих предметных переменных ни одна не встречается в связном виде в исходной формуле (*)
Правило заключения: если ф-лы , и - суть тезиса, то - тоже тезис.
Схемы для кванторов предполагают, что предметная переменная является свободной в ф-ле и не встречается в формуле :
Любую связанную переменную можно заменить на любую другую при условии, что после подстановки не возникнет конфликта.

Билет 12. Выполнимые и общезначимые формулы исчисления предикатов.
Предикат называется выполнимым в данном мире речи, если при подстановке каких-то значений из мира речи вместо переменных он обращается в истину.
Предикат называется выполнимым, если он выполняется в каком либо мире речи.
Предикат называется общезначимым в данном мире речи, если при любой подстановке предметов из данного мира речи на свободные места, всегда получается истинное высказывание.
Предикат называется общезначимым, если он общезначим в любом мире речи.
- невыполнимый предикат ( невыполним ни в одном мире речи)
- общезначимый предикат.
Общезначимая формула называется законом исчисления предикатов.
объединение з-нов де Моргана на исчисление предикатов.

Билет 13. Нормальные и предваренные формы. Функции Сколема.
Нормальной формой называется ф-ла исчисления предикатов, в которой из логических операций используются только буквы операций и знак операции отрицания столько, сколько над простыми предикатами.
Предваренной нормальной формой называется такая формула, которая является нормальной формой и, кроме того, все кванторы стоят в начале формулы и вынесены за общую формулу.
Всякая формула исчисления предикатов может быть приведена в предваренной нормальной форме.
Функции Сколема: ( Пример в каждом мире речи)

за счет подбора функций Сколема все кванторы существования исчезают.
Если мы не привязаны к конкретному миру речи, то надо все кванторы заменить на/выразить через

Билет 14. Метод семантических таблиц Бета.
Суть метода в предложении, что исходная формула не общезначима. Исходная формула последовательно разбивается на элементарные подформулы, которые затем относятся к общезначимо истинным или к действительно ложным. Разбиение на подформулы начинается с внешней операций, и проделывается до тех пор, пока формула не будет разбита на единичные высказывания или предикаты. Если представление будет получено для всех единичных высказываний, то формула общезначима, если же найдется хотя бы 1 случай, для которого исходная посылка верна, то формула не общезначима.
Примеры Элементарных таблиц Бета.

Билет 15 Отношения. Способы представления бинарных отношений.
Декартово произведение:
Обобщенное декартово произведение:
Отношение – любое подмножество Декартового произведения.
Способы задания декартовых отношений:
1) Перечислением, как любое множество.
2) Графически, когда каждый элемент предствляется вершиной, а произведние в виде дуги, между этими элементами
3) Матричным способом, спомощью матрицы смежности.
Матрица смежности - квадратная матрица , где и каждый ее элемент
, если , если иначе
4) Фактор-множество множества по отношению к называется множество окрестностей единичного радиуса для всех элементов при заданном .

Билет 16 Функции, операции. Инъекция, сюръекция, биекция.
функция, если (свойство однозначности)
Функция называется операцией, если она имеет значения из множества ее определения и определена всюду на этом множестве.
Сюръекция:
Инъекция:
Биекция: функция называется Биекцией, если она одновременно является и сюръекцией и инъекцией.
Операция:

Билет 17. Свойства бинарных отношений.
Бинарное отношение называется рефлексивным, если . Для определения этого св-ва мн-во должно содержать хотя бы один элемент .
Иррефексивность
Если бинарное отношение не является ни рефлексивным ни иррефлексивным, то оно называется неиррефлексивным бинарным отношением. Так же нерефлексивно пустое бинарное отношение.

Бинарное отношение называется симметричным, если
Антисимметричность:
Если бинарное отношение не обладает ни свойством симметрии, ни свойством антисимметрии, оно называется несимметричным.
Бинарное отношение на множестве с одним элементом или на пустом множестве явл. несимметричным.

Бинарное отношение называется транзитивным, если . Бинарное отношение называется интранзитивным, если .
Если бинарное отношение не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным.

Билет 18 Операции над отношениями. Связь операций со свойствами отношений.
- заданы 2 отношения.
1) Объединение 2-х отношений:

2) Пересечение:

3) Дополнение:

4) Обратное отношение:

5) Композиция отношений:

Сохранение свойств:
1) Если и - рефлексивны, то - также рефлексивны.
2) Если и - иррефлексивны, то - также иррефлексивны.
3) Для -симметрично.
4) Если и - симметричны, то - также симметричны.
симметрична .
5) Если и - антисимметричны, то - также антисимметричны.
6) Если и - транзитивны, то - также транзитивны.

Билет 19 Отношения толерантности и эквивалентности. Теорема Кантора о классах эквивалентности.
Бинарное отношение, заданное на множестве M называется отношением толерантности, если оно рефлексивно и симметрично.
Отношение толерантности обладает свойством транзитивности – отношение эквивалентности.
Классом эквивалентности элемента называется множество всех элементов , с которыми находится в отношении эквивалентности.
Теорема: Пусть дано множество, разбитое на непересекающиеся подмножества.
( - классы эквивалентности).

Всякое разбиение множества на классы эквивалентности задаёт на нём отношение эквивалентности. Верно и обратное.
Доказательство: Прямое:
Введём отношение . Оно очевидно рефлексивно и симметрично. Докажем интранзитивность: . Предположим, что . Тогда:
Противоречие , но отношение транзитивно.
Обратное: - рефлексивное, симметричное, транзитивное множество.
, , (очевидно). Рассмотрим
2 случая:
1) 2) - предположим .
Тогда по транзитивности

Билет 20 Отношения частичного порядка. Диаграммы Хассе. Экстремальные характеристики.
Бинарное отношение R на множестве M обладающее свойствами:
• Рефлексивность:
• Антисимметричность:
• Транзитивность:
называется отношением упорядоченности и обозначается .
Бинарное отношение, обладающее свойствами иррефлексивности, антисимметричности и транзитивности, называется отношением строгой упорядоченности и обозначается <.
Диаграммой Хассе называют граф , задающий частично упорядоченное множество с удалёнными петлями и транзитивно замыкающими дугами.
Дуги идут сверху вниз.

Множество, на котором задано отношение порядка, называется
частично упорядоченным.
Для подмножества x:
с – минимальный эkемент
d, e – максимальный элемент
с – наименьший элемент
- – наибольшего элемента нет.
c,a – миноранта (может как принадлежать, так и не принадлежать подмножеству),
f – мажоранта (может как принадлежать, так и не принадлежать подмножеству).
Наименьшая из мажорант – точная верхняя грань (f).
Наибольшая из минорант – точная нижняя грань (с).

Билет 21 Решетка как бинарное отношение. Алгебраические свойства решеток.
Отношение порядка называется решёткой, если для любых двух её элементов всегда найдётся точная верхняя и точная нижняя грани.
Точная верхняя грань двух элементов называется их объединением:
Точная нижняя грань двух элементов называется их пересечением:
Свойства операций:
• Идемпотентность:
• Коммутативность: (следует непосредственно из определения)
• Ассоциативность:

- миноранта для
По аналогии: . Требуется показать, что

Аналогично для объединения.
• Законы поглощения:

Докажем первое уравнение: Покажем, что
( - мажоранта) (в силу рефлексивности)
- наибольшая миноранта
Второе равенство доказывается аналогично.
Билет 22 Аксиоматическое (алгебраическое) определение решетки. Доказать, что решетка-алгебра является решеткой-отношением. Решётка – это алгебра L: со свойствами операций:
1) - идемпотентность 2) - коммутативность
3) - ассоциативность 4) -поглощение. Теорема Покажем, что решётка-алгебрая является решёткой-отношением.
Требуется показать, что - миноранта
Предположим, что пересечение не является наибольшей минорантой:
решётка является отношением порядка в смысле аксиоматического определения
Билет 23 Дистрибутивные решетки. Эквивалентность двух законов дистрибутивности. Вывод идемпотентности из дистрибутивности. Запрещенные фигуры.
Решётка называется дистрибутивной, если выполняется свойство дистрибутивности:
если выполняется одно, то второе выполняется автоматически.

Аналогично выводится идемпотентность пересечения.
Диаграмма Хассе: На рис. 1а и б показаны фигуры,
при которых нарушается дистрибутивность
Решётка дистрибутивна в ней отсутствуют
Структуры, гомеоморфные изображениям на рис.1
24.Группа:определение,доказать св.. Примеры групп.
О.Абстрактной алгеброй называют систему состоящую из непустого множества М, называемого носителем алгебры, и конечного количества операций ,определённых носителем.
О. Группоидом -называется всякая алгебра с одной двуместной операцией.
О. Полугруппа—это ассоциативный группоид
O. Моноид- полугруппа где иметься нейтральный элемент.
О. Если в носителе иметься такой элемент e,что то такой элемент называется нейтральным элементом(единицей).
Т. Единица в моноиде единственна Док: Допустим что е’ также является нейтральным. тогда е=ее’=е.
О. Эллемент а ,такой что , называется обратным к a .
О. Группа- Моноид в котором для каждого эл. обратный.
Свойства: Т. а - единств. Док: Рассмотрим b:
Т. Док:
Т. В группе каждое из уравнений ax=b и ya=b имеет един. решение:
Док:
В группе можно производить левостороннее и право стороннее сокращения.
.Аналогично
Т. Если в полугруппе для ax=b и ya=b имеют единственное решение, то такая полугруппа являеться группой. Док: для элемента a единст. решение уравнения ax=a; обозначим его .Возьмем произвольны элемент b,тогда обязательно элемент y такой что ya=b.Умножим b на Установили правого нейтрального эл. обозначим его e’.Аналогично доказывается существование левого нейтрального элемента e”.Но ,т.е обе единицы совпадают: полугруппа является моноидом. Далее, для всякого элемента а найдутся такие a’ и a”,что и .Отсюда .Таким образом и мы доказали что полугруппы, в которой возможно выполнение обратных операций, является группой.
25 Кольца: Дать определения, доказать свойства. Примеры колец.
О.Кольцом называют алгебру с двумя бинарными операциями, обладающими следующими свойствами:

Операции кольца называют, соответственно, сложением и умножением.

О. Если выполняются свойства 1-3 ,то это означает, что сложение образует на носителе кольца абелеву группу , которую называют аддитивной группой кольца. Ее нейтральный элемент
называют нулем (o),обратный элемент называют противоположным ( –a).

О. Подалгебра является полугруппой (свойство 4) и называется мультипликативной полугруппой кольца
О. Если в кольце существуют элементы a и b, оба отличные от o, такие, что ab=o, то a
называют левым делителем нуля, а b – правым делителем нуля.
О. Коммутативное кольцо, в котором нет делителей нуля, называют областью целостности.
О.Если мультипликативная полугруппа кольца является моноидом, то кольцо называют кольцом с единицей.
В кольце с единицей - a = e(-a) = (-e)a ; отсюда - (a + b) = -a - b (Док: ))
Свойства:
1)В кольце . В самом деле, отсюда (по св.3 ).
2) Во всяком кольце : Док:

26.Поле: Дать определения, доказать свойства. Примеры полей.
О. Кольцо называется телом, если для элемента кроме 0 и имеет единицу.
О. Тело с коммутативным умножением называют полем.
Свойства: В теле отсутствуют делители нуля. Пусть , и при этом . Тогда
; то есть

Заметим, что в кольце с делителями нуля пара
вообще не является алгеброй (смотри вопрос 25).

27.Булево кольцо: Дать определение, доказать свойства. Примеры булевых колец.
О.Булевым кольцом называют кольцо с единицей и идемпотентным умножением.(идемпотентное кольцо)
Свойства:
1) В булевом кольце a(a + a = o) . Это следует из идемпотентности умножения, наличия единицы и дистрибутивности умножения:
; ;
2) Если , то : Док: .
3) Булево кольцо коммутативно: ; отсюда
, а с учетом предыдущего свойства имеем .
Элемент a + e называют дополнением к a и обозначают .
Свойства дополнения:1) ; 2) ; 3)

28.Булева решётка: дать определение ,доказать свойства. Примеры булевых решеток.
О. Булевой решеткой называют алгебру с двумя бинарными операциями и одной унарной операцией (называемой дополнением), обладающими следующими свойствами:
1.
2.
3.
4.
5. Как видим, операции объединения и пересечения образуют дистрибутивную решетку.
Аксиомы 5 можно переписать в виде . Подставим вместо b в
первое неравенство , а во второе – : . Но выбор a и b произволен, то .
Очевидно, что , т.е. в булевой решетке наименьший и наибольший элементы.
Свойства:
1)Если и , то :

Отсюда, поскольку то .
2) Из этого же свойства выводятся два закона де Моргана:

Для доказательства первого из них рассмотрим выражения и . Если их
пересечение даст , а объединение равно 1, то одно из этих выражений будет
дополнением для другого.
;

Второй закон доказываем аналогично.
Поскольку .
Из законов де Моргана выводится закон контрапозиции:
.

29.Взаимосвязь булевых колец и булевых решеток.
Между булевыми кольцами и булевыми решетками существует связь. Пусть дано булево
кольцо . Положим Нетрудно
проверить, что алгебра будет булевой решеткой. Обе новые операции,
очевидно, коммутативны, пересечение ассоциативно по определению. Проверим
Остальные свойства:
Ассоциативность объединения:

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

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

Свойства дополнения:

Нуль кольца станет наименьшим элементом решетки:

Единица кольца станет наибольшим элементом решетки:

С другой стороны, имея булеву решетку, можно построить булево кольцо, положив
. При этом, если булева решетка была получена из
булева кольца указанным выше образом, то новое кольцо совпадет с исходным. Для
этого достаточно проверить, что новое сложение совпадает с исходным сложением:

Булевы решетки и булевы кольца, по сути, представляют собой
единую теорию, называемую булевой алгеброй.