Дискретная математика (Конспекты 15 лекций)

Страница 2

I – вектор из одних единиц.

Логическое сложение

X&Y

X V Y

Отрицание

X = 0 Y = 0

_ _

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Утверждение

Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Следствие

Множество всех характеристических векторов является булевой алгеброй.

Булева алгебра высказываний (алгебра логики)

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

U = {1 2 3 4 5 6 7 8 9}

A = «число четное»

B = «число, меньшее пяти»

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

SA = {2 4 6 8}

SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

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

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

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

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

A B	A & B	A V B	Not A
Л Л	Л	Л	И
Л И	Л	И	И
И Л	Л	И	Л
И И	И	И	Л

Л – ложно.

И – истинно.

Утверждение (основа всей алгебры логики)

Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

1. P(U)

2. Bn

3. Множество классов эквивалентных высказываний.

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

Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).

Лекция 3

Определение и способ задания булевых функций

Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.

Способы задания функций

1. Табличный

X1 X2 X3 … XN	F(X)
0 0 0 0 0 0 0 0 0	g1
…	gi
1 1 1 1 1 1 1 1 1	gn

gi - значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

2. Векторный

F = (g1 .gn)

3. Геометрический

Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.

Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)

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

Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.

3. В виде формулы.

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

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

Фиктивные переменные у функции можно добавлять и исключать.

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

Строим таблицу функций при n = 1.