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

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

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

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

Х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) = [ НЕ (X1)] ИЛИ [НЕ (X2)]

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

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

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

Таблица. 3.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 строки. Таблица истинности рассматриваемого логического выражения имеет следующий вид: