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

Представление булевой функции формулой логики высказываний

• Определение. Булевой функцией называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

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

Пример.

Для n=3 булеву функцию можно задать таблицей .

Таблица

... Смотреть решение »

Аксиомы булевой алгебры

Джордж Буль — ирландский математик и логик (1815—1864) —  впервые сформулировал основные положения алгебры логики

Таким образом , полный список аксиом , которыми будем пользоваться в дальнейшем , имеет вид

1. $0+0=0;$
2. $0+1=1;$
3. $1+0=1;$
4. $1+1=0;$
5. $0\cdot 0=0;$
6. $0\cdot 1=0;$
7. $1\cdot 0=0;$
8. $1\cdot 1=1;$
9. $\bar{0}=1;$
10. $\bar{1}=0;$

В литературе встречаются иные системы аксиом булевой алгебры . Например , Р . Сикорский в список своих аксиом включает свойства коммутативности , ассоциативности , дистрибутивности и др . Ещё одним примером является система аксиом Хантингтона. По мнению автора , наиболее естественной является система аксиом , приведённая в данной статье.

Пример. Найти значения выражений булевой алгебры:

1. $0+1+1+0=1;$
2. $0+0+\bar{1}+\bar{1}=0;$
3. $\bar{0}+1+0=1;$
4. $1\cdot\bar{1}+\bar{0}\cdot1=1.$

 

ДНФ и КНФ

Дизъюнктивные и конъюнктивные формы

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

Например , выражения

$AB+ CDE;$

$A+B+ CD;$

$A+B(C+D)+P;$

$A+B+ T+K;$

представлены в дизъюнктивной форме , а выражения

$(A+B)(C+D);$

$(AB+ C)(E+F+K);$

$ABC(D+E);$

— в конъюнктивной .

 

• Если булева формула записана в виде дизъюнкции выражений , каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо конъюнкцию некоторых аргументов , то эта формула является представленной в дизъюнктивной нормальной форме (ДНФ).  Например , выражения
  • $AB+C\bar{D};$
  • $A+\bar{B}+C\bar{D}E;$
  • $A+B+C+\bar{D};$  - представлены в ДНФ .
  • а формула $A+B(C+\bar{D})$ к ДНФ не относится , так как второе слагаемое не является ни отдельным аргументом , ни конъюнкцией переменных .
• Если булева формула записана в виде конъюнкции выражений , кажд ... Смотреть решение »