Математический аппарат инженера

x1	0 0 0 0 1 1 1 1
x2	0 0 1 1 0 0 1 1
x3	0 1 0 1 0 1 0 1
x1 ∨ x2	0 0 1 1 1 1 1 1
x̅3	1 0 1 0 1 0 1 0
x2 → x̅3	1 1 1 0 1 1 1 0
(x1 ∨ x2)(x2 → x̅3)	0 0 1 0 1 1 1 0

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

Например, x ∨ x̅ = 1; xx̅ = 0; xx̅ ∨ xx̅y =0; ((xy ∨y̅z → z̅) ∨ (x∨y̅)z = 1; x(x → y) → y = 1 и т. п.

9. Геометрическое представление. Область определения булевых функций от п переменных y = f(х₁, x₂, ...,x_n) можно рассматривать как совокупность n-мерных векторов (слов длины n), компонентами которых являются буквы 0 и 1 двоичного алфавита. При п = 3 каждый вектор представляется вершиной единичного куба в трехмерном пространстве (рис. 188).

В общем случае совокупность векторов (х₁, x₂, ...,x_n) отображается на множество вершин n-мерного куба.Всетакие вершины образуют логическое пространство.

Рис. 188. Отображение булевой функции y = (х₁ ∨ х₂) × (х₂ → х̅₃) на трехмерном кубе.

Булева функция отображается на n-мерном кубе путем выделения вершин, соответствующих векторам (х₁, x₂, ...,x_n) на которых булева функция y = f(х₁, x₂, ...,x_n) принимает значения 1. Обычно такие вершины отмечают жирными точками. Так, на рис. 188 отображена функция (х₁ ∨ х₂)(х₂ → х̅₃) в соответствии с таблицей из (8).

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

- 511 -

Важным примером неоднородных функций являются двузначные n-местные предикаты (1.5.9). Предикат Р (x₁, x₂, ..., x_n) принимает одно из двух значений - «истинно» (1) или «ложно» (0) в зависимости от конкретных значений, приписываемых переменным x₁, x₂, ..., x_n. Если значения переменных выбираются из некоторого множества М (универсума), то n-местный предикат можно рассматривать как n-местное отношение, определенное на этом множестве.

Одноместный предикат P(x) задает некоторое свойство элементов множества М и вполне определяется подмножеством P ⊂ M тех объектов x ∈ M, на которых он принимает значение «истинно».

Рис. 189. Характеристические подмножества, соответствующие операциям над предикатами (область истинных значений заштрихована).

Множество объектов, на которых предикат P(x) принимает значение «ложно», соответствует дополнению множества P, т.е. P̅. Очевидно, если P(x) истинно, то P̅(x) — ложно и наоборот. Например, если на множестве натуральных чисел определен предикат P(x) = «x — четное число», то P̅(x) - «x — нечетное число». Таким образом, одноместный предикат, определенный на множестве М разбивает это множество на два подмножества P и P̅. Подмножество P ⊂ M, на котором предикат P(x) принимает значение «истинно», называется характеристическим подмножеством.

Пусть на М определены два предиката P(x) и Q(x), характеристическими подмножествами которых являются соответственно P и Q. Рассматривая предикаты как двузначные функции, можно с помощью операций алгебры логики строит новые одноместные предикаты на множестве М. Конъюнкция P(x) и Q(x) — это предикат R(x) = P(x) ∧ Q(x), который истинен для тех и только тех объектов из М, для которых оба предиката P(x) и Q(x) истинны.

- 512 -

Характеристическим множеством предиката R(x) является пересечение P ∩ Q. Подобным образом вводятся и операции дизъюнкции P(x) ∨ Q(x), импликации P(x) → Q(x), эквиваленции P(x) ~ Q(x) и др. На рис. 189 показаны соответствующие этим операциям характеристические подмножества (область истинных значений заштрихована). Их легко получить из таблиц соответствия для функций двух переменных. Имеют место также соответствия между различными операциями, вытекающие из зависимостей между булевыми функциями: P(x) → Q(x) соответствует P̅(x) ∨ Q(x), P̅(x) ~ Q(x) соответствует (P(x) ∨ Q̅(x)) (P̅(x) ∧ Q̅(x)) или P(x)Q(x) ∨ P̅(x)Q̅(x) и т.п.

2. Алгебра логики

1. Двойственность формул булевой алгебры. Из свойств, приведенных в (1.5.5), видно, что в булевой алгебре, как и в алгебре множеств, имеет место принцип двойственности. Взаимно двойственными операциями являются дизъюнкция и конъюнкция. Заменяя в некоторой формуле каждую операцию на двойственную ей, получаем двойственную формулу. Например, из формулы x(y ∨ z(u ∨ v)) имеем x ∨ y(z ∨ uv).

На основе законов де Моргана выводится следующее положение:

если φ(x₁, x₂, ..., x_n) и φ*(x₁, x₂, ..., x_n) - двойственные формулы, то φ̅*(x₁, x₂, ..., x_n) равносильна φ(x̅₁, x̅₂, ..., x̅_n). Отсюда следует, что