Методические рекомендации рассмотрены и одобрены кафедрой вм и по 13 февраля 2008 г., протокол №5 Рецензент Кацуба В. С., канд физ мат наук, доцент кафедры высшей математики и программного обеспечения (стр. 4 из 10)
Множество высказываний с введенными для них логическими операциями и основными равносильностями называется алгеброй Буля.
Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквиваленция. Если над формулой стоит знак отрицания, то скобки тоже опускаются.
Пример. Упростить логическую формулу:
.Решение. Используем основные равносильности.
.Ответ: А º x Ú y.
1.3. Приложение алгебры логики. Релейно-контактые схемы
Релейно-контактной схемой (РКС) или переключательной схемой называется схематическое изображение устройства, состоящего из следующих элементов:
1) переключателей (контактов, реле, ламп и др.);
2) соединительных проводников;
3) входов-выходов (полюсов РКС).
Рассмотрим простейшую РКС, содержащую один переключатель Р. Если переключателю Р поставить в соответствие высказывание х: «Переключатель Р замкнут», то истинному значению х (х = 1) будет соответствовать замкнутое состояние переключателя, при котором РКС проводит ток, т.е. импульс, поступающий на вход, может быть снят на выходе. Значению х = 0 будет соответствовать разомкнутое состояние РКС (ток не проводится).
Каждой РКС, состоящей из нескольких переключателей, можно поставить в соответствие высказывание, выраженное некоторой формулой А, таким образом, что истинному значению формулы (А = 1) будет соответствовать замкнутое состояние РКС, а значению А = 0 – разомкнутое состояние. Примеры таких соответствий приведены в таблице.
Простейшие РКС и соответствующие им формулы логики.
| РКС | Формула | Значения |
| Переключатель х:  | Простейшее высказывание: х | х = 1, если переключатель замкнут; х = 0, если переключатель разомкнут |
| Переключатель   | Отрицание простейшего высказывания: | = 0, если переключатель замкнут; = 1, если переключатель разомкнут |
| Последовательное соединение:  (схема замкнута, когда оба переключателя замкнуты) | Конъюнкция высказываний: x Ù y | |
| Параллельное соединение:  (схема разомкнута, когда оба переключателя разомкнуты) | Дизъюнкция высказываний: x Ú y | |
| Схема, которая всегда разомкнута  | x Ù | x Ù  º 0 |
| Схема, которая всегда замкнута  | x Ú | x Ú º 1 |
Из простейших РКС путем их последовательного и параллельного соединения могут быть построены более сложные переключательные схемы.
Доказано, что любая формула алгебры логики может быть преобразована к виду, содержащему только операции отрицания, конъюнкции и дизъюнкции. Это позволяет изображать логические формулы при помощи РКС, а РКС задавать формулами.
Например, согласно формулам основных равносильностей
x ® y º
Ú y и x « y º (x ® y) Ù (y ® x),следовательно, логическим операциям импликации и эквиваленции соответствуют РКС, изображенные рис. 1.
Используя равносильные преобразования логической формулы, соответствующей некоторой РКС, можно упростить РКС, т.е. привести ее к виду, содержащему меньшее число переключателей. 
Пример. Упростить РКС, изображенную на рис. 2.Решение. Запишем соответствующую РКС формулу, используя таблицу простейших РКС и соответствующих им формул логики:
.Упростим формулу, используя основные равносильности:
.Таким образом,
. Построим РКС, соответствующую упрощенной формуле (рис. 3).2. Булевы функции
Будем рассматривать логические переменные x1, x2, …, xn, принимающие только два значения: «1» или «0».
Булевой функцией f (x1, x2, …, xn) называется произвольная функция, аргументами которой являются логические переменные и принимающая только одно из двух значений: «1» или «0».
Количество булевых функций одного аргумента равно 22 = 4, это функции:
f1(x) = 0, f2(x) =1, f3 (x) = x и f4(x) =
.Булевых функций двух аргументов всего 24 = 16, а количество булевых функций n аргументов равно
.Всякой формуле алгебры логики, составленной из элементарных высказываний x1, x2, …, xn соответствует булева функция f (x1, x2, …, xn), аргументы которой принимают значения истинности соответствующих элементарных высказываний: «1» или «0». Две равносильные формулы алгебры логики определяют одну и ту же булеву функцию, т.к. значения истинности этих формул совпадают для одинаковых значений входящих в них переменных.
Для булевых функций можно составлять таблицы значений – всякую булеву функцию n аргументов можно задать таблицей из 2n строк.
Например, таблица значений некоторых функций 2-х аргументов, соответствующих основным логическим операциям (отрицание одного аргумента, конъюнкция, дизъюнкция, импликация и эквиваленция) выглядит так:
| x1 | x2 |  | x1 Ù x2 | x1 Ú x2 | x1 ® x2 | x1 « x2 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Значение булевой функции f (x1, x2) при известных значениях аргументов устанавливается по строке таблицы, соответствующей заданным значениям x1 и x2. Например, для функции f (x1, x2) = x1 ® x2 значение f (1, 0) = 0, а значение f (1, 1) = 1.