Логические выражения

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

Пример: Построим логическое выражение из простых логических операций для описания сложного логического умозаключения «Я буду читать, если есть хорошая книга и есть свободное время или если я ищу ответ на интересующий меня вопрос и надеюсь найти его в этой книге».

Введем следующие обозначения:

Х1 — переменная, характеризующее фактор «есть хорошая книга», 1 – есть, 0 – нет;

Х2 — переменная, определяющая условие «есть свободное время», 1 – есть, 0 – нет;

Х3 — параметр «ищу ответ на вопрос», 1 – да (ищу), 0 –нет (не ищу);

Х4 — фактор «надеюсь найти ответ», 1 – да (надеюсь), 0 – нет (не надеюсь);

Ф(Х1, Х2, Х3, Х4) — логическое выражение, описывающее приведенное высказывание.

Тогда сложная функция, определяющая условие, при котором я буду читать, может быть записывается с помощью логического выражения:

Ф(Х1, Х2, Х3, Х4) = (Х1 И X2) ИЛИ (X3 И X4),

при этом таблица истинности такого выражения имеет вид:

Таблица. 3.2.

X1	X2	X3	X4	Ф(Х1, Х2, Х3, Х4)
Нет (0)	Нет (0)	Нет (0)	Нет (0)	Нет (0)
Да (1)	Нет (0)	Нет (0)	Нет (0)	Нет (0)
Нет (0)	Да (1)	Нет (0)	Нет (0)	Нет (0)
Нет (0)	Нет (0)	Да (1)	Нет (0)	Нет (0)
Нет (0)	Нет (0)	Нет (0)	Да (1)	Нет (0)
Да (1)	Да (1)	Нет (0)	Нет (0)	Да (1)
Да (1)	Нет (0)	Да (1)	Нет (0)	Нет (0)
Да (1)	Нет (0)	Нет (0)	Да (1)	Нет (0)
Нет (0)	Да (1)	Да (1)	Нет (0)	Нет (0)
Нет (0)	Да (1)	Нет (0)	Да (1)	Нет (0)
Нет (0)	Нет (0)	Да (1)	Да (1)	Да (1)
Да (1)	Да (1)	Да (1)	Нет (0)	Да (1)
Да (1)	Да (1)	Нет (0)	Да (1)	Да (1)
Да (1)	Нет (0)	Да (1)	Да (1)	Да (1)
Нет (0)	Да (1)	Да (1)	Да (1)	Да (1)
Да (1)	Да (1)	Да (1)	Да (1)	Да (1)

Утверждение. В булевой алгебре существуют определенные взаимоотношения между логическими функциями И, ИЛИ, НЕ, которые позволяют производить замену функций И функцией ИЛИ и наоборот. Это взаимоотношения известны как теоремы де Моргана:

НЕ (X1 И X2) = [ НЕ (X1)] ИЛИ [НЕ (X2)]

НЕ (X1 ИЛИ X2) = [ НЕ (X1)] И [НЕ (X2)]

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

Вот эти наиболее важные теоремы булевой алгебры [12] ⁾:

Таблица. 3.3.

1а `0 = 1	1б `1 = 0
2а Х Ú 0 = Х	2б Х & 1= Х
3а Х Ú 1 = 1	3б Х & 0 = 0
4а Х Ú Х = Х	4б Х & Х = Х
5а Х Ú`Х = 1	5б Х &`Х = 0
6а Х1 Ú Х2 = Х2 Ú Х1	6б Х1 & Х2 = Х2 & Х1
7а Х1 Ú (Х1 & Х2) = Х1	7б Х1 & (Х1 Ú Х2) = Х1
8а Х1 Ú (`Х1 & Х2) = Х1 Ú Х2	8б Х1 & (`Х1 Ú Х2) = Х1 & Х2
9а (Х1 Ú Х2) Ú Х3 = Х1 Ú (Х2 Ú Х3)	9б (Х1 & Х2) & Х3= Х1 & (Х2 & Х3)
10а Х1 Ú (Х2 & Х3) = (Х1 Ú Х2) & (Х1 Ú Х3)	10б Х1 & (Х2 Ú Х3)=(Х1 & Х2) Ú (Х1 & Х3)

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

Пример: Пусть имеется следующее логическое выражение

(X1 Ú X2) & (X1 Ú`X2) Ú X3.

Учитывая теорему 10а, получим

(X1 Ú X2) & (X1 Ú`X2) Ú X3 = (X1 Ú X2 &`X2) Ú X3.

Далее по теореме 5а имеем X2 &`X2 = 0, тогда

(X1 Ú X2) & (X1 Ú`X2) Ú X3 = X1 Ú 0 Ú X3,

а по теореме 2а X1 Ú 0 = X1 и

(X1 Ú X2) & (X1 Ú`X2) Ú X3 = X1 Ú X3.

Утверждение. По некоторому наперед заданному булевому выражению можно легко построить его таблицу истинности. Для этого в выражение подставляют вместо переменных их возможные значения и вычисляют значение выражения.

Примечание.

Количество состояний логической функции (или строк), которые должны быть отражены в таблице истинности определяется по формуле 2ⁿ, где n — количество логических переменных.

Пример: Пусть необходимо построить таблицу истинности для выражения

Ф(Х1, Х2) = (`X1 & X2) Ú (X1 &`X2)

Поскольку Ф(Х1, Х2) является функцией от двух переменных, то таблица истинности должна содержать 2² = 4 строки. Таблица истинности рассматриваемого логического выражения имеет следующий вид: