РЕШЕНИЕ ЭЛЕМЕНТАРНЫХ ЗАДАЧ БУЛЕВОЙ АЛГЕБРЫ

SOLUTION OF ELEMENTARY PROBLEMS OF BOOLEAN ALGEBRA

Aleksandrina Vagapova

4th year student of the Faculty of Physics and Mathematics, Tashkent State Pedagogical University,

Uzbekistan, Tashkent

Ключевые слова: Математическая логика; Булева алгебры; аксиомы Булевых алгебр; множество; элементы.

Keywords: Mathematical logic; Boolean algebra; axioms of Boolean algebras; a bunch of; elements.

Порой количество условий (вводных) настолько велико, а взаимосвязи между ними столь запутанны и сложны, что человеческий мозг не в состоянии «переварить» все сразу. Может понадобиться не один месяц (неделя, год) для понимания происходящего. Но современная жизнь не дает нам таких временных интервалов на принятие решений. И мы прибегаем к помощи компьютеров. И вот тут-то и появляется алгебра логики, со своими законами и свойствами.

Булевой алгеброй называется такая алгебра  с носителем В, в котором выделены два элемента 1 и 0, и на котором определены двуместные операции + и *, и одноместная операция ⎺, причем выполняются следующие аксиомы:

1. A) 

B) 

2. A) 

B)

3. A) 

B)

4. A) 

B)

5. A) , тогда и только тогда, когда

6. A) 

B)

7. A) 

B)

8. A) 

B)

Нас интересуют только свойства этих операций. Таким образом, символы  можно рассматривать, как переменные, и предавать им те или иные значения. В статье хотелось бы рассмотреть примеры для полного раскрытия данной темы.

Задача на теоремы булевой алгебры

Докажите, что если в алгебре высказываний  и , то .

Доказательство. Пусть  и . Тогда используя аксиомы булевой алгебры, имеем:

Что и требовалось доказать.

Задача на составление таблицы истинности

Записать формулу и построить таблицу для функций. Здесь:

,  ,  , 

,  ,  , 

Таблица 1.

Таблица истинности

Преобразование логических выражений

В задачах на преобразование логических выражений требуется привести выражение либо к дизъюнктивной нормальной форме, либо к конъюнктивной нормальной форме.

Найти двумя способами СДНФ и СКНФ для формулы .

Решение:

1. С помощью таблицы истинности

Таблица 2.

Таблица истинности

СДНФ . СКНФ .

2. С помощью равносильных преобразований.

СДНФ :

СКНФ  :

.

Применение булевых функций для решения логических задач

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

Определить, участвовал ли в соревновании Икрамов, если известно, что:

1. Если Икрамов не участвовал или Юсупов участвовал, то Камалов участвовал;

2. Если Икрамов не участвовал, то Камалов не участвовал.

Решение. Выделим в условии задачи простые высказывания: А ={Икрамов участвовал}, В ={Юсупов участвовал},  С ={Камалов участвовал}. Тогда первое условие задачи записывается в виде истинной формулы:  второе условие – в виде истинной формулы . Соединим их знаком конъюнкции. Истинная формула является символической записью условия задачи. Упростим полученную формулу с помощью равносильностей алгебры высказываний.

Так как упрощённая формула  принимает значение «истина», то высказывания и принимают значение «истина». Значит, Икрамов участвовал в соревновании.

Построение функции по таблице истинности

Самый простой способ нахождения функции - построение дизъюнктивной нормальной формы (ДНФ) этой функции.

Найти функцию заданную таблицей истинности

Таблица 3.

Таблица истинности

Список литературы:

1. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1979
2. Владимиров Д. А. «Булевы алгебры». М.: «Наука», 1969. — 320 с.
3. Гашков, С. Б. Дискретная математика: учебник и практикум для вузов — Москва: Издательство Юрайт, 2020. — 483 с.
4. Гуров С.И. «Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры». — М.: Либроком, 2013. — 352 с.