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

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

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.

Высказывание – это имеющее смысл языковое выражение (повествовательное предложение), относительно которого в данной ситуации можно утверждать, что оно либо истинно, либо ложно, т. е. каждому высказыванию можно приписать истинное значение И (истина) или Л (ложь), но не то и другое одновременно.

Знаки логических операций называют логическими связками (или просто связками). Логические связки могут быть одноместные (унарные), двухместные (бинарные), трехместные (тернарные) и т. д.

В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности, содержащих все наборы значений переменных и значения функции этих наборов. Алгебра логики не занимается обоснованием того, почему тому или иному элементарному высказыванию приписано значение истины или лжи. Этот вопрос решается за пределами алгебры логики.

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

Основными символами алгебры высказываний являются:

а) пропозиционные переменные Р1, Р2, Р3, …;

б) одноместная связка – (ù) и двуместные связки Ù (и), Ú (или), ®, Þ, Û;

в) скобки ().

Переменная, значениями которой являются высказывания, называется пропозиционной переменной.

Пусть А, В- некоторые элементарные высказывания.

Определим новое высказывание В (т. е. не А), будем называть его отрицанием (инверсия: , В), представим таблицы значений функции отрицания:

А	В

Рассмотрим наборы истинных значений элементарных функций на наборах аргументов:

№	Обозначение операции	Другие обозначения		Название логической опции и связки	Как читается	Арифметическая модель
	АÚВ	А+В Max (А, В)		Дизъюнкция, логическое сложение, «или»	А или В	A+B-A×B
	АÙВ	А&В А×В Min (А, В)		Конъюнкция, логическое умножение «и»	А и В	A×B
	А®В	АÊВ АÞВ		Импликация, логическое следование	Если А, то В А влечет В	1‑A+ A×B
	А~В	АºВ А«В АÛВ		Эквиваленция, эквивалентность	А тогда и только тогда, когда В; А эквивалентно В	1 – (A-B)2
	АÅВ	А+В АÚВ		Сумма по модулю 2, сумма Жегалкина	А плюс В; Либо А, либо В
	А½В			Штрих Шеффера, антиконъюнкция	Неверно, что А и В

Несмотря на то, что булевых функций от любого заданного числа m двоичных переменных конечное число, их слишком много, чтобы иметь запас преобразователей для любых встретившихся отображений. Рассмотрим сначала все возможные функции от одной двоичной переменной. Их четыре, две из них – константы (0 и 1), одна – тождественная функция и только одна – функция отрицания (функция НЕ) – является нетривиальной.

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

1. Закон тождества:

А=А

2. Занон непротиворечия:

3. Закон исключения третьего:

4. Закон двойного отрицания:

5. Законы истины и лжи (свойства констант):

6. Законы идемпотентности:

7. Коммутативные законы:

8. Ассоциативные законы:

– дизъюнкции

– конъюнкции

9. Дистрибутивные законы:

– 1‑ый дистрибутивный закон

– 2‑ой дистрибутивный закон

10. Законы поглощения:

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

12. Закон импликации:

13. Закон эквивалентности:

14. Свойства сложения «по модулю два»:

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