logic_algebra (Лекции ЮКР)

ЗАНЯТИЕ №1.

Основные понятия алгебры логики.

Учебные вопросы:

1. Булевые функции.

2. Базис и изображающие числа булевых функций.

3. Операции над изображающими числами.

4. Нахождение явного вида булевой функции по изображающему числу.

ЗАНЯТИЕ №2.

Применение алгебры логики для решения задач обработки информации.

Учебные вопросы:

1. Логическая зависимость и независимость высказываний.

2. Решение системы булевых уравнений.

3. Применение перестановочной матрицы.

СОДЕРЖАНИЕ ЗАНЯТИЯ №1.

Учебный вопрос №1. БУЛЕВЫЕ ФУНКЦИИ.

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

Элементами алгебры логики являются высказывания. Высказывание—законченное предложение, про которое можно сказать истинно оно или ложно. Будем обозначать высказывания заглавными латинскими буквами

В алгебре логики определены три операции:

1. Логическое сложение (дизъюнкция)—соответствует объединению высказываний союзом “или”. Обозначается . Читается “ или ”. истинно, если истинно хотя бы одно из высказываний или .

2. Логическое умножение (конъюнкция)—соответствует объединению высказываний союзом “и”. Обозначается . Читается “ и ”. истинно, когда истинны и .

3. Отрицание--одноместная операция. Обозначается . Читается “не ”. истинно, когда ложно.

В результате применения операций 1-3 к какому-либо исходному набору элементов получаются сложные высказывания, которые называются булевыми функциями от соответствующих аргументов: и т. д.

Рассмотрим некоторые булевы функции:

1. Импликация:

Допустим, что истинное высказывание, тогда, если --истинно, то и также истинно, если ложно, то --тоже ложно. Однако, если истинно, то может быть как истинно, так и ложно. Читается “если то ”, или “из следует ”. Записывается .

2. Эквивалентность:

Пусть это высказывание истинно, тогда и имеют одинаковые значения истинности, т. е. и либо оба истинны, либо оба ложны. Читается “ эквивалентно ”, Записывается .

1. Тавтология—всегда истинная булева функция при любых комбинациях значений истинности аргументов:

Все тавтологии обозначаются , поэтому

Вместе с этим символ используется для обозначения связей между элементами:

-- это то же, что и ;

--означает эквивалентность .

Отрицание , т. е. --тавтологически ложный элемент.

Правила булевой алгебры.

Учебный вопрос №2. БАЗИС И ИЗОБРАЖАЮЩИЕ ЧИСЛА БУЛЕВЫХ ФУНКЦИЙ.

Булева функция считается заданной, если мы можем указать значения истинности этой функции при всех возможных комбинациях значений истинности входящих в нее элементов.

Таблица чисел, которая представляет все возможные комбинации значений истинности заданного набора элементов называется базисом для этих элементов. Строка этой таблицы, соответствующая, например, элементу , называется изображающим числом и обозначается . Обозначим 1—истина, 0—ложь, тогда для одного элемента для двух

и т. д.

Для n элементов базис будет содержать столбцов. Колонки базиса можно занумеровать теми двоичными числами, которые представляют сами колонки. Если номера колонок упорядочены по возрастанию слева направо, то базис называется стандартным:

и обозначается .

Учебный вопрос №3. ОПЕРАЦИИ НАД ИЗОБРАЖАЮЩИМИ ЧИСЛАМИ.

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

В базисе

2. . Поразрядно по правилу:

3. поразрядно по правилу:

Теперь можно вычислять изображающие числа функции по отношению к базису , например:

номера колонок базиса

Следовательно, данная функция истинна только при таких комбинациях значений истинности элементов которые соответствуют 3,4.5 и 7 столбцам базиса.

Изображающим числом является , а 0--

Заметим, что тогда и только тогда, когда и тогда и только тогда, когда имеет единицы, по крайней мере, в тех разрядах, в которых содержит единицы (или ).

Учебный вопрос №4. НАХОЖДЕНИЕ ЯВНОГО ВИДА БУЛЕВОЙ ФУНКЦИИ ПО ИЗОБРАЖАЮЩЕМУ ЧИСЛУ.

а). Представление булевой функции в дизъюнктивной нормальной форме.

Составим всевозможные, так называемые, элементарные произведения для трех элементов A,B и C и выпишем их изображающие числа :

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

б) Представление булевой функции в конъюнктивной нормальной форме.

Составим всевозможные элементарные суммы для A, B и C и выпишем их изображающие числа:

СОДЕРЖАНИЕ ЗАНЯТИЯ №2.

Учебный вопрос №1. ЛОГИЧЕСКАЯ ЗАВИСИМОСТЬ И НЕЗАВИСИМОСТЬ ВЫСКАЗЫВАНИЙ.

Опр. булевых функций

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

Чтобы установить, зависимы или нет функции , нужно относительно вычислить:

Колонки набора (*) будем рассматривать как двоичные числа. Тогда, если в наборе содержатся все чисел от 0 до , то функции независимы, в противном случае зависимы.

Рассмотрим следующий пример:

Базис для двух элементов:

В наборе нет чисел 0 и 3, поэтому и --зависимы. Найдем явный вид зависимости этих функций в форме . Отсутствие чисел 0 и 3 говорит о том, что и --не могут принимать значения нулевого и третьего столбцов базиса .

Положим, относительно , откуда имеем . Действительно, .

Итак, для построения в базисе необходимо в те разряды , номера которых содержатся в наборе (*) поставить единицы, а в остальные—нули, или, другими словами, принимает значение “истина” для всех возможных комбинаций значений истинности функций и значение “ложь” для комбинаций, которых вообще не может быть, поэтому для всех возможных комбинаций значений истинности высказываний ...

Учебный вопрос №2. РЕШЕНИЕ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИЙ.

Примеры:

1).

--либо 0, либо 1,

отсюда: или

2). , отсюда

Заметим, что уравнение в форме импликации всегда можно записать как соотношение эквивалентности:

или

Общий подход к решению булевых уравнений рассмотрим на следующем примере:

Составим таблицу: Таблица 1

Изображающие числа Изображающие числа

коэффициентов относит. неизвестных относит :

i=01234567 j=0123

Левая

часть

уравнения

Правая

часть

уравнения

Найдем и относительно : Таблица 2

При для пары имеем для левой части уравнения, а для правой для этой пары уравнение не удовлетворяется;

Для пары уравнение удовлетворяется. Запишем эту пару в таблицу 2 и т. д. Окончательно получим пар решений исходного уравнения. Запишем теперь решения задачи в матричной форме:

для левой части

для правой части

Для каждого ищем , при котором и по находим пару , удовлетворяющую нашему уравнению.

При решении системы из “n” булевых уравнений проверяется “n” равенств --номер уравнения. Если все “n” равенств выполняются, то, как и раньше, по находим изображающие числа переменных.

Учебный вопрос №3. ПРИМЕНЕНИЕ ПЕРЕСТАНОВОЧНЫХ МАТРИЦ.

Замена переменных осуществляется посредством соотношений:

Функции перехода независимы.

Например, относительно

Функции и независимы, следовательно, данное преобразование допустимо.

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

В более общем случае требуется одновременно преобразовать несколько функций, например, и от переменных к переменным

Замена переменных в функциях и эквивалентна переходу от и , вычисленных относительно к и , вычисленных относительно . Этот переход сводится просто к перестановке столбцов в наборе

так, что получается набор

Перестановка столбцов выполняется с помощью перестановочной булевой матрицы

В нашем примере переход от к приводит к следующему равенству:

Заметим, что столбец переходит в столбец ;

тогда

Квадратная перестановочная матрица , содержащая ровно одну 1 в каждой строке и каждом столбце имеет обратную равную транспонированной . Тогда .

Лекции составил:

подполковник В. Ярошенко.