Презентация: Булевы функции

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

План:

• Понятие булевой функции. Способы задания.
• Понятие нормальных форм.
• Методика представления булевой функции в нормальной форме и совершенной нормальной форме.

• Понятие булевой функции. Способы задания.

Джордж Буль (1815–1864) – известный английский математик, чьи работы способствовали созданию современной символической логики.

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

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

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

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

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

Понятие булевой функции.

Логической (булевой) функцией (или просто функцией) n переменных y = f(x 1 , x 2 , … , x n ) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

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

• табличный;
• графический;
• аналитический.

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

• Таблицей истинности формулы называется сводная таблица всех значений входящий в нее высказываний и соответствующих значений самой формулы.

• Таблица содержит 2 n строк, где n – число простых высказываний .

• Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

На рисунке 2.1 вершины, соответствующие набору булевых переменных, на котором функция принимает значение 1, обозначаются закрашенными точками. Для функции от одного аргумента f(x) на рисунке 2.1, а нет ни одной закрашенной вершины, следовательно, это функция «тождественный нуль»

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

В) аналитический

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

x 1

0

x 2

0

0

 0

1

0

 1

1

0

 2

1

0

0

0

 3

0

1

0

0

0

0

 4

0

0

1

1

 5

0

0

0

 6

1

1

0

0

1

1

 7

 8

0

1

0

0

1

1

1

 9

1

 10

1

0

1

0

1

 11

1

0

0

0

1

0

0

 12

1

1

 13

1

0

 14

1

0

1

1

1

1

 15

0

1

0

0

1

1

1

1

1

0

1

1

В общем случае переменная х i (функции n переменных) называется несущественной ( фиктивной ) в функции f(x 1 , ... , x i , ... ,x n ), если f(x 1 , ... , 0, ... ,x n ) = f(x 1 , ... , 1, ... ,x n ) при любых наборах остальных аргументов.

Очевидно, что в этом случае мы получим функцию n -1 переменных.

В) аналитический

1. конъюнкция (функция И)

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x & y или x Ù y ;

Конъюнкция

• Конъюнкцией n переменных f  ( x 1 , x 2 , …, x n ) = x 1 x 2 …x n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

6. сложение по модулю 2

7. дизъюнкция (функция или)

Дизъюнкция

• Дизъюнкцией n переменных f  ( x 1 , x 2 , … , x n ) = x 1Ú x 2Ú … Ú x n называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

8.стрелка Пирса

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”

9. эквивалентность или подобие

Эта f 9 = 1 тогда и только тогда, когда х = у.

13. импликация (следование)

если х = 0 (т. е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным.

Л юбая теорема всегда фактически содержит эту логическую функцию

14. штрих Шеффера

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции)

2. Понятие нормальных форм.

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

Элементарная дизъюнкция (ЭД) – дизъюнкция k логических переменных или их отрицаний (k ≥1) .

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

Например: А, А ∨В , А ∨ В ∨ С – элементарные дизъюнкции.

Элементарная конъюнкция (ЭК) – конъюнкция k логических переменных или их отрицаний

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

Например: А, А ∧В , А ∧ В ∧ С – элементарные конъюнкции

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

ДНФ функции может быть не единственной

Примеры формул в виде ДНФ: А; (А ∧ С) ∨ В; ( A ∧ B) ∨(B ∧ D) .

Конъюнктивная нормальная форма (КНФ) – форма записи алгебры высказываний, представленная в виде конъюнкции элементарных дизъюнкций.

КНФ функции может быть не единственной

Примеры формул в виде КНФ: А; (А ∨ С) ∧ В ; (A ∨B) ∧ (B ∨ D) .

Любую формулу логики высказываний можно привести равносильными преобразованиями к ДНФ и КНФ.

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

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

3.Методика представления булевой функции в нормальной форме и совершенной нормальной форме.

• Приведение к ДНФ осуществляется последовательным применением свойства дистрибутивности и закона Моргана, с помощью которых все отрицания “опускаются” до переменных.

• Затем раскрываются скобки, удаляются лишние конъюнкции, повторения переменных в конъюнкциях и удаляются константы.