Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по булевым функциям - файл 1.doc


Лекции по булевым функциям
скачать (869 kb.)

Доступные файлы (1):

1.doc869kb.19.11.2011 15:00скачать

содержание
Загрузка...

1.doc

  1   2   3
Реклама MarketGid:
Загрузка...
Конспект лекций

по дискретной математике
Булевы функции

- Булевы переменные и функции.

- Операции булевой алгебры.

- Эквивалентные формулы.

- Основные эквивалентности.

- Дизъюнктивная нормальная форма (ДНФ).

- Совершенная ДНФ. Минимизация ДНФ.

- Конъюнктивная нормальная форма (КНФ).

- Совершенная КНФ. Минимизация КНФ.

- Полиномиальное разложение: СПНФ.

- Канонический полином Жегалкина.

- Арифметический полином.

Булевы функции
Основные понятия и определения
Переменная х, принимающая значения 0 или 1, называется булевой (или логической, двоичной). Функция F, зависящая от булевых переменных и принимавшая также значения 0 или 1, называется булевой (или логической, двоичной) и обозначается .
Булевы функции F от n переменных могут быть заданы посредством таблицы истинности, содержащей строк и столбцов. В левой части таблицы содержатся наборы значений n переменных, расположенные в порядке возрастания их десятичного эквивалента, а в правой ее части - значения функции F на соответствующих наборах значений переменных.
В качестве примера рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных , и .








F

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1


Булева функция n переменных F однозначно определяется - разрядным булевым вектором ее значений w(F) (т.е. w(F) - таблица истинности функции F). Например, в этом примере имеем w(F)=(00100111).
Рассматриваемая булева функция F принимает значения 0 на наборах 000, 001, 011 и 100, а значение 1 - на наборах 010, 101, 110 и 111.

Множество наборов, на которых функция ^ F принимает значение 1, называется характеристическим и обозначается через NF. В настоящем примере имеет место NF = (010, 101, 110, 111).
Общее число различных булевых функций F от n переменных равно .

Т.е. число булевых функций от двух переменных равно , от трех переменных .

^ Элементарные булевы функции
Булевых (или логических) функций от одной переменной . Они приведены в следующей таблице:




0



отрицание



1

0

0

0

1

1

1

0

1

0

1


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






конъюнк

ция



дизъюнк

ция



имплика

ция

эквивалентность

сложение по модулю два

стрелка

Пирса

штрих

Шеффера

0

0

0

0

1

1

0

1

1

0

1

0

1

1

0

1

0

1

1

0

0

1

0

0

1

0

1

1

1

1

1

1

1

0

0

0



Функция называется конъюнкцией, ее обозначают также , но чаще всего знак конъюнкции аналогично знаку умножения опускают и пишут . Конъюнкция равна единице, только если =1 и =1 одновременно, поэтому ее часто называют функцией И. Еще одно название конъюнкции ― логическое умножение, поскольку ее таблица истинности действительно совпадает с таблицей обычного умножения для чисел 0 и 1.
Функция называется дизъюнкцией. Дизъюнкция равна единице, только если =1 или =1 (т.е. хотя бы одна переменная равна единице), поэтому ее часто называют функцией ИЛИ.
Кроме таблицы истинности булевы функции могут быть заданы аналитически с помощью формул. Например, .
Если формула a реализует булеву функцию F, которая тождественно равна единице, то она называется тождественно истинной. Если формула a реализует булеву функцию F, которая тождественно равна нулю, то она называется тождественно ложной.
Если формулы a и b, зависят от одних и тех же переменных и реализуют одну и ту же булеву функцию F, то формулы a и b называются равносильными.
Основные равносильности
Закон двойного отрицания

.
Идемпотентность

, .
Коммутативность

, .
Ассоциативность

, .
Дистрибутивность

, .
Законы де Моргана

, .
Формулы с константами

, , ,

, , .

Дополнительные равносильности
,

,

,

,

,

,

,

,

, (законы склеивания),

(закон поглощения).

(закон обобщенного склеивания).

Переменная булевой функции F называется (или фиктивной), если , то есть если изменение значения в каждом наборе значений не меняет значения функции. При этом существует такая формула, реализующая эту булеву функцию, в которой отсутствует .
Пример. С помощью основных равносильностей доказать, что в булевой функции F = переменная является фиктивной.

Решение. Применяя закон поглощения и закон склеивания, получим:

F =.

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
















0

0

0

1

1

1

1

0

1

0

1

1

0

1

1

0

0

1

0

1

1

1

1

1

0

0

0

0


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

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

Решение. Применяя основные равносильности получим:

.

^ Дизъюнктивные нормальные формы
Определение. Элементарной конъюнкцией называется конъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу.
Например, конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0.

Следующие конъюнкции: , , , , 0 не являются элементарными.
Определение. Элементарная конъюнкция булевой функции содержащая n литералов, называется полной (или минтермом).
Определение. Дизъюнкция любого конечного множества элементарных конъюнкций булевой функции F называется дизъюнктивной нормальной формой (ДНФ) функции F. Число элементарных конъюнкций (слагаемых, термов), составляющих ДНФ, называется длиной ДНФ.
Например, ДНФ имеет длину, равную 3.
Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее ДНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д.
Определение. Две (или несколько) ДНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными).
Например, для функции , заданной приведенной выше таблицей истинности, существуют следующие эквивалентные ДНФ:

, (1)

, (2)

, (3)

, (4)

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

Отметим, что СДНФ является единственной (с точностью перестановки слагаемых) для конкретной булевой функции ^ F .
Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к ДНФ, а затем к СДНФ.
Пример. Привести к виду СДНФ булеву функцию F=.
Решение. С помощью основных равносильностей преобразуем к ДНФ:

====

= - ДНФ.
Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции , до полных элементарных конъюнкций:

=.
Т.к. , после сокращения одинаковых конъюнкций, получаем СДНФ: F=.
Составим таблицу истинности для булевой функции F=(функция из предыдущего примера). Отметим связь между СДНФ и таблицей истинности.
Таблица истинности СДНФ











F=

Элементарные конъюнкции СДНФ

0

0

0

1

0

0




0

0

1

1

0

0




0

1

0

1

0

1



0

1

1

1

0

1



1

0

0

0

1

1



1

0

1

0

0

0




1

1

0

0

1

0




1

1

1

0

0

1




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

Пример. По таблице истинности составить СДНФ








F

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1


Решение: СДНФ: .

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





Т.к. , после сокращения одинаковых конъюнкций, получаем СДНФ:

.
Таблица истинности СДНФ













Элементарные конъюнкции СДНФ

0

0

0

1

0

0




0

0

1

1

0

0




0

1

0

1

1

1



0

1

1

1

0

0




1

0

0

0

1

1



1

0

1

0

0

1



1

1

0

0

1

1



1

1

1

0

0

1


  1   2   3



Скачать файл (869 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации