Лекция 4. Булевая алгебра. Алгебра логики

Лекция 4. Булевая алгебра. Алгебра логики

План лекции

4.1. Понятие высказывания. Простое и составное высказывание

4.2. Логические выражения и логические операции над высказываниями

4.3. Равносильность логических операций.

4.4. Формулы алгебры логики. Функции алгебры логики

4.5. Формы представления высказываний

4.6. Полнота системы булевых функций

4.7. Минимизация высказываний методом Квайна

Понятие высказывания. Простое и составное высказывание

 

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

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

Определение. Высказывание — это повествовательное предложение, выражающее суждение. Если суждение, составляющее содержание (смысл) некоторого высказывания, истинно, то и о данном высказывании говорят, что оно истинно. В противном случае, если суждение, составляющее содержание некоторого высказывания, ложно, то и о данном высказывании говорят, что оно ложно.

Истинность и ложность называются логическими, или истинностными, значениями высказываний.

ПРИМЕРЫ.

1. Число 100 делится на 5. (Истина)

2. Число 3 больше числа 5. (Ложь)

3. Сегодня светит солнце. (Не является высказыванием)

4. Вечером мы пойдем в кино. (Не является высказыванием)

5. Я лгу. (Не является высказыванием)

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

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

 

Формы представления высказываний

Полином Жегалкина

Пусть M – некоторое произвольное подмножество булевого куба , , – номер вектора ,  – его вес, – номера отличных от нуля координат вектора .

Определение. Формула вида ,                               (4.1)

где суммирование ведется по модулю два, а коэффициенты равны либо 0, либо 1, называется полиномом Жегалкина от n переменных.

Если суммирование в формуле (4.1) ведется по всем булевым векторам длины n, слагаемые идут в порядке возрастания номеров булевых векторов и , то говорят, что полином Жегалкина записан в канонической форме.

Теорема 4.3. Каждая булева функция от n переменных может быть реализована в виде канонического полинома Жегалкина от n переменных, причем единственным образом.

Например, полином Жегалкина от двух переменных  в канонической форме запишется так: .

Для представления булевой функции в форме полинома Жегалкина воспользуемся треугольником Паскаля.

ПРИМЕР. Построим полином Жегалкина для функции f = (10011110).

Полином Жегалкина можно получить с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответствует набору (101). В качестве слагаемого многочлена берем x ₁ x ₃. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

N	x 1 x 2 x 3	f	Треугольник Паскаля
1 x 3 x 2 x 2 x 3 x 1 x 1 x 3 x 1 x 2 x 1 x 2 x 3	000 001 010 011 100 101 110 111	1 0 0 1 1 1 1 0	1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1

 

Тогда

 

Лекция 4. Булевая алгебра. Алгебра логики

План лекции

4.1. Понятие высказывания. Простое и составное высказывание

4.2. Логические выражения и логические операции над высказываниями

4.3. Равносильность логических операций.

4.4. Формулы алгебры логики. Функции алгебры логики

4.5. Формы представления высказываний

4.6. Полнота системы булевых функций

4.7. Минимизация высказываний методом Квайна