|
Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
1
, b
2
, . . .,
b
ν
∗
(G)
:
K =
b
11
b
1m b
21
b
2m b
ν
∗
(G),1
. . . Поскольку каждый фундаментальный разрез K
i содержит ровно одну ветвь, а именно u i
, матрица K имеет вид =
b
11
b
1,ν
∗
(G)
b
21
b
2,ν
∗
(G)
b
ν
∗
(G),1
. . . b
ν
∗
(G),ν
∗
(G)
1 0
1 Таким образом, K = (K
1
|K
2
), где K
2
— единичная матрица порядка. Отметим, что если C = (C
1
|C
2
) — соответствующая матрица фундаментальных циклов, то K
1
= Пример. Найдем матрицу фундаментальных разрезов графа G = M; R , изображенного на рис. 3.36. Поскольку ν
∗
(G) =
6 − 1 = 5, имеется пять фундаментальных разрезов. Ребру 4 соответствует коцикл K
1
= {1, 4}, так как при удалении ребра 4 из остова множество вершин M разбивается на две части {a
1
} и M \ а ребра 1 и 4 образуют разрез по разбиению {{a
1
}, M \ {a}}. Аналогично ребру 5 соответствует коцикл K
2
= {5}, ребру 6 — коцикл
K
3
= {1, 2, 3, 6}, ребру 7 — коцикл K
4
= {2, 3, 7}, ребру 8 — коцикл
K
5
= {3, 8}. Следовательно, матрица фундаментальных разрезов име-
Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ ет вид = 1 2 3 4 5 6 7 8 K 1 K 2 K 3 K 4 K 5 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 Отметим также, что приумножении матрицы фундаментальных циклов C на транспонированную матрицу фундаментальных разрезов K T в поле строка a умножается на столбец b по правилу внутреннего произведения и (a i , b j ) = 0. Это означает, что C · K T = 0, а также · C T = Упражнение. Проверить, что для матриц C и K из примеров и 3.10.1 справедливо C · K T = 0. § Раскраски графов Пусть G = M ; R — неорграф без петель. Раскраской (вершин) графа называется такое задание цветов вершинам G, что если [a, b] ребро, то вершины a и b имеют различные цвета. Хроматическим числом) графа G называется минимальное число цветов, требующееся для раскраски Пример. Так как в полном графе K n любые две различные вершины связаны ребром, то χ(K n ) = Многие практические задачи сводятся к построению раскрасок гра- фов. П р им ер. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор. Построим граф G, вершины которого биек- тивно соответствуют лекциями две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно χ(G). 3.11. РАСКРАСКИ ГРАФОВ 2. Рассмотрим граф G, вершины которого — страны, а ребра соединяют страны, имеющие общую границу. Числу χ(G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны небыли окрашены в один цвет. Существуют и практические задачи, связанные с раскраской ребер в мультиграфе. Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа Для произвольного неориентированного мультиграфа G = M, U, реберным мультиграфом L(G) называется тройка U, M, P , где P ⊆ U × M × U, и выполняется (u, a, v) ∈ P тогда и только тогда, когда в мультиграфе G вершина a является концом ребер u и v. Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G). П р им ер. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами — проводники. Неорграф G называется бихроматическим, если χ(G) = 2. Неор- граф G = M; R называется двудольным, если множество всех ребер графа G образует разрез графа G, те. для некоторого разбиения множества вершин {M 1 , M 2 } концы любого ребра принадлежат разным частям разбиения. Теорема 3.11.1. Пусть G — неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны) G — бихроматический граф) G — двудольный граф) G не содержит циклов нечетной длины. Следствие 3.11.2. Если G — лес, то Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа Теорема 3.11.3. Для любого неорграфа G без петель выполняется неравенство χ(G) deg(G) + Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным. Алгоритм последовательной раскраски. Произвольная вершина графа G принимает цвет 1. 2. Если вершины a 1 , . . . , a раскрашены l цветами 1, 2, . . . , l, l тоновой произвольно взятой вершине a припишем минимальный Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
цвет, неиспользованный при раскраске вершин из множества {a j
|
ρ(a i+1
, a j
) = 1, j < Для некоторых классов графов последовательная раскраска является минимальной. В общем случае это не так Планарные графы
Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек,
кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости называется плоским. Таким образом, если граф имеет плоское изображение, то он является планарным.
П р им ер. Граф риса) планарен, поскольку может быть изображен, как показано на рис. 3.39б.
Граф, описанный в примере 3.11.2, п. 2, является планарным. Также планарным является граф, вершины которого — отверстия печатной платы, а ребра — проводники печатной платы, соединяющие отвер- стия.
Рассмотрим операцию подразбиения ребра в графе G = M; R После подразбиения ребра [a, b] ∈ R получается граф G = M ; R где M = M ∪ {ab}, R = (R \ [a, b]) ∪ [a, ab] ∪ [ab, b], те. ребро [a, заменяется на (a, цепь длины два. Два графа называются гомео- морфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.
Не всякий неорграф является планарным. Критерий планарности описывает
Теорема 3.12.1 (теорема
Понтрягина—Куратовского). Граф G
планарен тогда и только тогда, когда G не содержит подграфа, го- меоморфного или рис. Эквивалентная форма критерия планарности описана в следующей теореме.
Теорема 3.12.2. Тогда и только тогда неорграф G планарен, когда не содержит подграфов, стягиваемых (те. получаемых по d
d d
d d
•
•
•
•
¡
¡
¡
¡
¡
¡
e e
e e
e e
d d
d а
б
Рис. 3.39
3.12. ПЛАНАРНЫЕ ГРАФЫ d d d d d d d d d d d ¨¨ ¨¨ ¨¨ ¨¨ ¨¨ ¨ ¨ rr rr rr rr rr Рис. 3.40 следовательностью отождествлений вершин, связанных ребрами) к графу или рис. Вместе стем трехмерного евклидова пространства оказывается достаточно для изображения любого конечного и счетного графа без пересечения дуг вне их концов. Теорема 3.12.3. Любой граф, состоящий не более чем из вершин, может быть изображен в пространстве без пересечения дуг вне их концов. Д ока за тел ь ст во. Пусть G = M; R — граф, для которого. Тогда имеем |R| 2 ω . Расположим все точки графа на некоторой прямой l и каждой дуге из R разнозначно сопоставим плоскость, содержащую прямую l. Искомое изображение графа G получается после проведения всех дуг в соответствующих плоскостях. Известна оценка хроматического числа планарных графов. Теорема 3.12.4 (теорема о четырех красках. Если G — планарный граф, то При исследовании принципиальной электрической схемы радиоэлектронного устройства сточки зрения возможности ее реализации с помощью печатного монтажа или монтажа на слоях микросхемы важно знать ответ наследующие вопросы 1) является ли граф, соответствующий рассматриваемой принципиальной схеме, планарным) если граф планарен, то как получить его изображение без пересечения ребер На первый вопрос принципиальный ответ дает теорема Понтрягина—Куратовского, а методы получения плоских изображений планарных графов можно найти в специальной литературе. Если граф G непланарен, то для его геометрической реализации удаляют отдельные ребра (переносят на другую плоскость. Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ребер наследующую плоскость и т. д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G
1
, G
2
, . . ., разбиение ведется по множеству ребер, называется толщиной графа Таким образом, толщина планарного графа равна Пример. Каждый из графов и имеет толщину 2.
§ Задачи и упражнения. Представить граф (рис. 3.41) в аналитической и матричной формах, списком дуги структурой смежности. Составить матрицу инцидентности для мультиграфа, изображенного на рис. Найти все неизоморфные подграфы и части графа K
3 4. Представить в геометрической и матричной формах графы G
1
∪ ∪G
2
, G
1
∩G
2
,
G
1
⊕ рис. 3.43).
5. Для графов и из предыдущей задачи найти G
1
× G
2
, G
1
[G
2
] и G
2
[G
1
].
6. С помощью матрицы смежности графа (рис. 3.44) найти его матрицы достижимости, контрдостижимости и сильных компонент. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 3.45.
•
•
•
•
•
d d
d d
d d
c
'
E
•
•
•
•
!
c
u
B
%
g
Рис. Рис. 3.42
•
•
•
¡
¡
¡
¡¡!
e e
e ee
1 2
3
G
1
•
•
•
•
'
e e
e ee
¡
¡
¡
¡
¡
1 2
3 4
G
2
•
•
•
•
d d
d s
c d
d d
h
1 2
3 Рис. Рис. 3.44
3.13 ЗАДАЧИ И УПРАЖНЕНИЯ d
d d
d d
•
•
•
•
•
&
&
&
&
b
c
E
d d
d d
d d
'
T
u
1 2
3 Рис. Рис. 3.46
•
•
•
•
•
•
•
i i
i i
i i
i i
¡
¡
¡
¡
¡
¡
•
•
•
•
•
•
•
d d
d
d d
d d
d d
i i
i i
i i
i Рис. Рис. 3.48 8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:
а) графа K
5
; б) графа, изображенного на рис. 3.47.
11. Построить все неизоморфные трех, четырех- и пятивершинные деревья. Найти остов минимального веса взвешенного графа (рис. 3.48).
13. Найти упорядоченный лес, соответствующий бинарному дереву, изображенному на рис. 3.49.
14. Найти матрицы фундаментальных циклов и фундаментальных разрезов графа (рис. 3.50).
15. Найти хроматическое число графа (рис. 3.51).
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
d d
©
© c c
©
d d
d d
d d
d d
©
©
©
©
d d
©
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16
•
•
•
•
•
•
•
t t
tt
1 2
3 4
5 9
7 8
6 Рис. Рис. 3.50
Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ d d d d d d d d ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ • • • • • • d d d d rr rr rr r rr rr rr Рис. Рис. 3.52 16. Найти толщину графа (рис. После изучения главы 3 выполняются задачи 8 и 9 контрольной работы. Задача 8 решается аналогично примерами, а задача 9 — аналогично примерами Глава АЛГЕБРА ЛОГИКИ Формулы алгебры логики Высказыванием называется повествовательное предложение, око- тором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно. В качестве примеров высказываний приведем предложения “НГТУ — крупнейший вуз Новосибирска и Снег зеленый. Первое высказывание является истинным, а второе — ложным. Поставим в соответствие высказыванию P логическую переменную x, которая принимает значение 1, если P истинно, и 0, если P ложно. Если имеется несколько высказываний, то из них можно образовать различные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры логики. Итак, пусть {x i | i ∈ I} — некоторое множество логических переменных. Определим по индукции понятие формулы алгебры логики) любая логическая переменная является формулой (называемой атомарной) если ϕ и ψ — формулы, то выражения ¬ϕ, (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ), (ϕ ↔ ψ) являются формулами) никаких других формул, кроме построенных по пп. 1 и 2, нет. Если формула ϕ построена из логических переменных, лежащих в множестве {x 1 , x 2 , . . . , x n }, то будем писать ϕ(x 1 , . . . , x Символы ¬, ∧, ∨, →, ↔, использованные в определении, называются логическими операциями или связками и читаются соответственно отрицание, конъюнкция, дизъюнкция, импликация и эквивалент- ность. Введенные в п. 2 формулы следующим образом интерпретируются в русском языке ¬ϕ — не ϕ”, (ϕ ∧ ψ) — “ϕ и ψ”, (ϕ ∨ ψ) — “ϕ или Глава 4. АЛГЕБРА ЛОГИКИ, (ϕ → ψ) — если ϕ, то ψ”, (ϕ ↔ ψ) — “ϕ тогда и только тогда, когда Вместо ¬ϕ часто пишут ϕ, вместо (ϕ∧ψ) — (ϕ&ψ), (ϕ·ψ) или (Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, составляющих формулу, и соответствующее этому набору значение полученной формулы 1 1 0 ϕ ψ (ϕ ∧ ψ) (ϕ ∨ ψ) (ϕ → ψ) (ϕ ↔ ψ) 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 Приведенные таблицы истинности называются также интерпретациями логических операций и составляют семантику формул (те. придание смысла формулам) в отличие от синтаксиса формул (те. формальных законов их построения, данных в определении формулы). Исходя из таблиц истинности для логических операций можно строить таблицы истинности для произвольных формул. П р им ер. Построить таблицу истинности для формулы ϕ = ((x → y) ∧ ((y → z) → Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы ϕ: x y z (x → y) (y → z) ((y → z) → x) ϕ 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 Легко заметить, что таблица истинности для ϕ совпадает с таблицей истинности для x. В дальнейшем выяснится причина этого совпа- дения. Расширим понятие формулы, введя новые, не менее важные логические операции (ϕ|ψ) — штрих Шеффера или антиконъюнкция, по определению ∧ ψ); — (ϕ ↓ ψ) — стрелка Пирса или антидизъюнкция, по определению ↓ ψ) ¬(ϕ ∨ ψ); — (ϕ ⊕ ψ) — кольцевая сумма, логическое сложение или сложение по модулю 2, по определению (ϕ ⊕ ψ) ¬(ϕ ↔ ψ). 4.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 89 Составим исходя из определений таблицы истинности для этих трех операций ↓ ψ) (ϕ ⊕ ψ) 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 Как видно из примера 4.1.1, даже при составлении несложных формул возникает обилие скобок. Чтобы избежать этого, в алгебре логики, также как ив арифметике, приня- ¬m |m ∨m →m ∧m ↓m ↔m ⊕m d d d d Рис. ты некоторые соглашения относительно расстановки скобок. Перечислим эти соглашения. Внешние скобки не пишутся. Например, вместо высказывания ((x ∨ y) → z) пишется (x ∨ y) → z. 2. На множестве {¬, ∧, ∨, →, ↔, |, ↓, ⊕} вводятся транзитивное отношение < быть более сильными отношение эквивалентности быть равносильным по правилам, показанным на рис. Согласно этим отношениям недостающие скобки в формуле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для равносильных связок расстановка скобок выполняется слева направо. П р им ер. В формуле x ∧ y ∨ z скобки расставляются следующим образом ((x ∧ y) ∨ z); в формуле x ∨ y ↔ z → u — ((x ∨ y) ↔ (z → u)), в формуле x ⊕ y ↔ z → u ∨ v ∧ w ↓ x|y — ((x ⊕ y) ↔ (z → (u ∨ (((v ∧ w) ↓ Отметим, что, например, в формуле x → (y → z) скобки убирать нельзя, поскольку в силу наших соглашений формуле x → y → z соответствует формула (x → y) → z. § Функции алгебры логики В предыдущем параграфе мы выяснили, что семантически формулы полностью характеризуются таблицами истинности. При этом можно забыть о синтаксической структуре самих формул и иметь дело с таблицами истинности. Таким образом, мы приходим к понятию функции алгебры логики, которое и будет исследоваться в дальней- шем. Функцией алгебры логики (ФАЛ) от n переменных x 1 , x 2 , . . . . . . , x называется любая функция f : {0, 1} n → {0, 1}, те. функция Глава 4. АЛГЕБРА ЛОГИКИ x
1
x
2
x n
E
f (x
1
, x
2
. . . , x n
)
E
y Рис. Рис. которая произвольному набору (δ
1
, δ
2
, . . . , δ
n
) нулей и единиц ставит в соответствие значение f (δ
1
, δ
2
, . . . , δ
n
) ∈ {0, Функции алгебры логики называются также булевыми функциями,
двоичными функциями и переключательными функциями.
Булевой функцией описываются преобразования некоторым устройством входных сигналов в выходные. Предположим, что устройство, показанное на рис. 4.2, имеет n входов x
1
, x
2
, . . ., x n
, на которые может подаваться или не подаваться токи один выход, на который ток подается или не подается в зависимости от подачи тока на входы.
При этом значение переменной x i
= 1 интерпретируется как поступление тока на й входа как непоступление тока. Значение f (δ
1
, δ
2
, . . . , δ
n
) равно 1, если приток на выход проходит, и f (δ
1
, δ
2
, . . . , δ
n
) = 0, если ток не проходит.
Например, операции конъюнкции x ∧ y соответствует устройство с двумя входами и одним выходом. При этом значение выхода равно тогда и только тогда, когда оба значения входов равны 1 (рис. Булева функция f (x
1
, x
2
, . . . , x n
) полностью определяется своей таблицей истинности n−1
x n
f (x
1
, x
2
, . . . , x n
)
0 0
0 0
0
f (0, 0, . . . , 0, 0)
0 0
0 0
1
f (0, 0, . . . , 0, 1)
1 1
1 1
0
f (1, 1, . . . , 1, 0)
1 1
1 1
1
f (1, 1, . . . , 1, В каждой строке таблицы вначале задается набор значений переменных, а затем — значение функции на этом наборе.
Если булева функция f и формула ϕ имеют одну и туже таблицу истинности, то будем говорить, что формула ϕ представляет функцию Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение Пример (голосование. Рассмотрим устройство, фиксирующее принятие некоторой резолюции комитетом трех. Каждый член комитета при одобрении резолюции нажимает свою кнопку. Ес-
4.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
91
ли большинство членов согласны, то резолюция принимается.
Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f (x, y, z), таблица истинности которой имеет вид x
0 0
0 0
1 1
1 1
y
0 0
1 1
0 0
1 1
z
0 1
0 1
0 1
0 1
f (x, y, z)
0 0
0 1
0 1
1 Полученную функцию f можно также задать следующей системой равенств f (0, 0, 0) = f (0, 0, 1) = f (0, 1, 0) = f (1, 0, 0) = Вектором значений булевой функции f (x
1
, x
2
, . . . , x n
) называется упорядоченный набор всех значений функции f , при котором значения упорядочены по лексикографическому порядку множества аргументов, В примере 4.2.1 вектором значений булевой функции f (x, y, z) является набор (0001 Отметим, что поскольку всего имеется 2
n наборов (δ
1
, . . ., δ
n
) нулей и единиц (|{0, 1}
n
| = 2
n
), существует ровно булевых функций f (x
1
, x
2
, . . . , x n
) от n переменных |f : {0, 1}
n
→ {0, 1}}| = |{0, 1}|
|{0,1}
n
|
= 2 см. операции над кардиналами в § Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.
Наборы (δ
1
, δ
2
, . . . , δ
n
) нулей и единиц можно представить в виде вершин мерных кубов (см. § 3.2) или в виде вершин 2-дерева
(рис. 4.4), каждая вершина которого представляет собой некоторый набор) нулей и единиц или пустое слово Λ. При этом с вершиной, смежны вершины (δ
1
, δ
2
, . . . , δ
n−1
),
(δ
1
, δ
2
, . . . , δ
n−1
, 0), (δ
1
, δ
2
, . . . , δ
n−1
, 1), с вершиной δ
1
— Λ, (δ
1
, 0) и, 1), с вершиной Λ — 0 и 1. На каждом этаже изображенного дерева rr r
r d
d d
d d
d
¡
¡
¡
e e
e
¡
¡
¡
e e
e
¡
¡
¡
e e
e
¡
¡
¡
e e
e
Λ
0 1
00 01 11 10 000 001 010 011 100 101 110 Рис. 4.4
Глава 4. АЛГЕБРА ЛОГИКИ располагаются всевозможные наборы (δ 1 , δ 2 , . . . , δ n ) нулей и единиц фиксированной длины Функция f (x 1 , x 2 , . . . , x n ) называется суперпозицией функций g(y 1 , . . . , y m ) и h 1 (x 1 , x 2 , . . . , x n ), . . ., h m (x 1 , x 2 , . . . , x n ), если f (x 1 , . . . , x n ) = g(h 1 (x 1 , . . . , x n ), . . . , h m (x 1 , . . . , x Пример. Функция f , соответствующая формуле x 1 x 2 ⊕ x 2 x 3 ⊕ x 4 x 1 , есть суперпозиция функции g, представляемой формулой y 1 ⊕ y 2 ⊕ y 3 , и функций h 1 , h 2 , h 3 , соответствующих формулам x 1 x 2 , x 2 x 3 , Булева функция f (x 1 , x 2 , . . . , x n ), принимающая значение 1 соответственно) на всех наборах нулей и единиц f (x 1 , x 2 , . . . . . . , x n ) соответственно f (x 1 , x 2 , . . . , x n ) ≡ 0), называется константой 1 (константой Опишем булеву алгебру B n функций алгебры логики от n переменных. В качестве носителя рассмотрим множество B n = {f | f : {0, 1} n → {0, 1}}. Отношение на множестве B n определим последующему правилу f 1 f 2 ⇔ f 1 (X) f 2 (X) для любого набора значений. Пересечением f ∧ g функций f и g называется такая функция h, что h(X) = min{f (X), g(X)} на любом наборе значений X = (δ 1 , . . . , δ n ). Объединением f ∨ g функций f и g называется такая функция h, что h(X) = = max{f (X), g(X)} на любом наборе X. Дополнение f функции f определяется следующим образом (X) = 0, если f (X) = 1, 1, если f (X) = В качестве 0 рассмотрим функцию, являющуюся константой 0, а в качестве возьмем константу 1. Система B n = B n ; ∧, ∨, , 0, 1 образует булеву алгебру функций алгебры логики от n переменных (алгебру булевых функций Эквивалентность формул Как показано в примере 4.1.1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы ϕ(x 1 , . . . , x n ) и ψ(x 1 , . . . , x n ) называются эквивалентными, если совпадают их таблицы истинности, те. совпадают представляемые этими формулами функции f ϕ (x 1 , . . . , x n ) и f ψ (x 1 , . . . , x n ).
4.3. ЭКВИВАЛЕНТНОСТЬ ФОРМУЛ
93
П р им ер. Построив таблицы истинности формул x → y и y → x, убеждаемся в том, что (x → y) ∼ (y → Легко видеть, что отношение является отношением эквивалентности, те. оно рефлексивно (ϕ ∼ ϕ), симметрично (ϕ ∼ ∼ ψ ⇒ ψ и транзитивно (ϕ ∼ ψ, ψ ∼ χ ⇒ ϕ Отметим основные эквивалентности между формулами) ((ϕ ∧ ψ) ∧ χ) ∼ (ϕ ∧ (ψ ∧ χ)), ((ϕ ∨ ψ) ∨ χ) ∼ (ϕ ∨ (ψ ассоциативность и ∨);
2) (ϕ ∧ ψ) ∼ (ψ ∧ ϕ), (ϕ ∨ ψ) ∼ (ψ ∨ ϕ) (коммутативность и ∨);
3) (ϕ ∧ ϕ) ∼ ϕ, (ϕ ∨ ϕ) ∼ ϕ (идемпотентность и ∨);
4) (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ)), (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ)∧
∧(ϕ ∨ χ)) (законы дистрибутивности) (ϕ ∧ (ϕ ∨ ψ)) ∼ ϕ, (ϕ ∨ (ϕ ∧ ψ)) ∼ ϕ (законы поглощения) ¬(ϕ ∧ ψ) ∼ ¬ϕ ∨ ¬ψ, ¬(ϕ ∨ ψ) ∼ ¬ϕ ∧ ¬ψ (законы де Моргана) ¬¬ϕ ∼ ϕ (закон двойного отрицания) ϕ → ψ ∼ ¬ϕ ∨ ψ;
9) ϕ ↔ ψ ∼ ((ϕ → ψ) ∧ (ψ → ϕ) ∼ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ);
10) (ϕ ∨ ¬ϕψ) ∼ (ϕ ∨ ψ), (¬ϕ ∨ ϕψ) ∼ (¬ϕ ∨ ψ);
11) ϕ(¬ϕ ∨ ψ) ∼ ϕψ, ¬ϕ(ϕ ∨ ψ) Формула ϕ(x
1
, x
2
, . . . , x n
) называется выполнимой (опровержимой),
если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно Пример. Формула x ∧ y является одновременно выполнимой и опровержимой, поскольку 0 ∧ 0 = 0, а 1 ∧ 1 = Формула ϕ(x
1
, . . . , x n
) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием, если эта формула принимает значение 1 (соответственно) при всех наборах значений переменных, те. функция f является константой 1 (константой Пример. Формула x ∨ x является тождественно истинной,
а формула x ∧ x — тождественно ложной x ∨ x x ∧ x
0 1
0 1
1 Если ϕ — тождественно истинная формула, то будем писать |= В противном случае пишем |= ϕ. Таким образом, |= x ∨ x, |= x ∧ y, и x Очевидным является следующее
Замечание 4.3.1. 1. Формула ϕ тождественно ложна тогда и только тогда, когда ¬ϕ тождественно истинна (|= ¬ϕ);
Глава 4. АЛГЕБРА ЛОГИКИ. Формула ϕ опровержима тогда и только тогда, когда она не является тождественно истинной (|= ϕ); 3. Формула ϕ выполнима тогда и только тогда, когда она не является тождественно ложной. Отметим, что тождественно истинные (соответственно тождественно ложные) формулы образуют класс эквивалентности по отношению Предложение 4.3.2. Если формула тождественно истинна тождественно ложна, то для любых формул ϕ и ψ справедливы следующие эквивалентности ∧ ϕ 1 ∼ ϕ; ϕ ∧ ϕ 0 ∼ ϕ 0 ; ϕ ∨ ϕ 1 ∼ ϕ 1 ; ϕ ∨ ϕ 0 ∼ ϕ; (ϕψ → ϕ) ∼ ϕ 1 ; (ϕ → ϕ ∨ ψ) ∼ ϕ 1 ; ϕ ⊕ ϕ ∼ ϕ 0 ; ϕ ⊕ ϕ 1 ∼ ϕ; ϕ ⊕ ϕ 0 ∼ ϕ. § Дизъюнктивные и конъюнктивные нормальные формыЕсли x — логическая переменная, δ ∈ {0, 1}, то выражение x δ = x, если δ = 1, x, если δ = называется литерой. Литеры x и x называются контрарными. Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер. П р им ер. Формулы x ∨ y ∨ z и x ∨ y ∨ x ∨ x — дизъюнкты, формулы и x 1 x 2 x 1 — конъюнкты, а x является одновременно и дизъюнктом, и конъюнктом. Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ). П р им ер. Формула xy ∨yz — ДНФ, формула (x∨z∨ ∨y)(x∨ ∨z)y — КНФ, а формула xy является одновременно КНФ и ДНФ. Теорема 4.4.1. 1. Любая формула эквивалентна некоторой ДНФ. 2. Любая формула эквивалентна некоторой КНФ. Опишем алгоритм приведения формулы к ДНФ. 1. Выражаем все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности и определения операций |, ↓ и ⊕.
4.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 2. Используя законы де Моргана, переносим все отрицания к переменными сокращаем двойные отрицания по правилу ¬¬x ∼ x.
3. Используя закон дистрибутивности (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ)∨
∨(ϕ ∧ χ)), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.
В результате применения пп. 1–3 получается ДНФ данной форму- лы.
П р им ер. Приведем к ДНФ формулу = ((x → y) ↓ ¬(y → Выразим логические операции → и ↓ через ∧, и ¬:
ϕ ∼ ((x ∨ y) ↓ ¬(y ∨ z) ∼ ¬((x ∨ y) ∨ ¬(y В полученной формуле перенесем отрицание к переменными сократим двойные отрицания ∼ (¬(x ∨ y) ∧ ¬¬(y ∨ z)) ∼ (x ∧ y) ∧ (y ∨ z) ∼ (x ∧ y) ∧ (y Используя закон дистрибутивности, приводим формулу к ДНФ:
ϕ ∼ (x ∧ y ∧ y) ∨ (x ∧ y Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется пункт . Используя закон дистрибутивности ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
П р им ер. Приведем к КНФ формулу = (x → y) ∧ ((y → z) → Преобразуем формулу ϕ к формуле, не содержащей →:
ϕ ∼ (x ∨ y) ∧ (¬(y → z) ∨ x) ∼ (x ∨ y) ∧ (¬(y ∨ z) В полученной формуле перенесем отрицание к переменными сократим двойные отрицания ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x) ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x).
Глава 4. АЛГЕБРА ЛОГИКИ По закону дистрибутивности получаем, что формула ϕ эквивалентна формуле ∨ y) ∧ (x ∨ y) ∧ (x являющейся КНФ. Упростим полученную формулу ∨ y) ∧ (x ∨ y) ∧ (x ∨ z) (1) ∼ ∼ (x ∨ (y ∧ y)) ∧ (x ∨ z) (2) ∼ x ∧ (x для преобразования (1) использовался закон дистрибутивности, для) — эквивалентность 4 предложения 4.3.2., для (3) — закон поглощения. Таким образом, формула ϕ из примера 4.1.1 эквивалентными преобразованиями приводится к формуле x (являющейся одновременно ДНФ и КНФ формулы Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ). Пусть (x 1 , . . . , x набор логических переменных = = (δ 1 , . . . , δ n ) — набор нулей и единиц. Конституентой единицы набора называется конъюнкт K 1 (δ 1 , . . . , δ n ) = x δ 1 1 x δ 2 2 . . . x δ n n Конституентой нуля набора ∆ называется дизъюнкт, . . . , δ n ) = x 1−δ 1 1 ∨ x 1−δ 2 2 ∨ . . . ∨ x 1−δ n Отметим, что K 1 (δ 1 , δ 2 , . . . , δ n ) = 1 (K 0 (δ 1 , δ 2 , . . . , δ n ) = 0) тогда и только тогда, когда x 1 = δ 1 , x 2 = δ 2 , . . ., x n = Совершенной ДНФ называется дизъюнкция некоторых конститу- ент единицы, среди которых нет одинаковых, а совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная x из набора {x 1 , . . . , x n } входит ровно один раз, причем входит либо сама x i , либо ее отрицание x Пример. Формула есть конституента единицы, 0, 1), формула x∨y∨z есть конституента нуля K 0 (0, 0, 1), формула СДНФ, формула (x∨y∨z)∧(x∨y ∨ ∨z)∧(x∨y∨z) — СКНФ, а формула не является СДНФ. Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле ϕ, предварительно рассмотрим разложения булевой
4.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
97
функции f (x
1
, x
2
, . . . , x n
) попеременным (для определенности по x
1
,
x
2
, . . ., x k
) — разложения Шеннона.
Теорема 4.4.2 (первая теорема Шеннона). Любая булева функция f (x
1
, x
2
, . . . , x n
) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x k
, x k+1
, . . . , x n
) по всем наборам i
)f (δ
1
, δ
2
, . . . , δ
k
, x k+1
, . . . , x В силу принципа двойственности для булевых алгебр справедлива
Теорема 4.4.3 (вторая теорема Шеннона). Любая булева функция) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x k
, x k+1
, . . . , x n
) по всем наборам i
∨ f (δ
1
, δ
2
, . . . , δ
k
, x k+1
, . . . , x В предельном случае, когда k = n, получаем представление булевой функции f (x
1
, x
2
, . . . , x n
), неравной нулю, в виде совершенной ДНФ:
f (x
1
, x
2
, . . . , x n
) по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых f (δ
1
,...,δ
n
)=1
(
n
∧
i=1
x
δ
i Аналогично получаем представление булевой функции f (x
1
, x
2
, . . .
. . . , x n
), неравной единице, в виде совершенной КНФ:
f (x
1
, x
2
, . . . , x n
) по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых f (δ
1
,...,δ
n
)=0
(
n
∨
i=1
x
1−δ
i Приведенные формулы позволяют сформулировать следующую теорему Глава 4. АЛГЕБРА ЛОГИКИ
Теорема 4.4.4 (о функциональной полноте. Для любой булевой функции f найдется формула ϕ, представляющая функцию f . Если f ≡ 0, то существует представляющая ее формула ϕ, находящаяся в СДНФ:
ϕ =
f (δ
1
,...,δ
n
)=1
K
1
(δ
1
, . . . , и такое представление единственно с точностью до порядка следования конституент единицы. Если f ≡ 1, то существует представляющая ее формула ϕ, находящаяся в СКНФ:
ϕ =
f (δ
1
,...,δ
n
)=0
K
0
(δ
1
, . . . , и такое представление единственно с точностью до порядка следования конституент нуля.
П р им ер. Найти СДНФ и СКНФ функции f (x, y, z), заданной следующей таблицей истинности 0
0 0
1 1
1 1
y
0 0
1 1
0 0
1 1
z
0 1
0 1
0 1
0 1
f (x, y, z)
1 0
0 1
0 1
0 По теореме о функциональной полноте СДНФ имеет вида СКНФ — ϕ
2
= (x ∨ y ∨ z)(x ∨ y ∨
∨z)(x ∨ y ∨ z)(x ∨ y Итак, для нахождения СДНФ и СКНФ исходной формулы ϕ составляется ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма.
В примере 4.4.6, имея, скажем, СДНФ для функции f , можно составить ее таблицу истинности и по ней найти СКНФ Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
Для нахождения СДНФ данную формулу приводим сначала к ДНФ,
а затем преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;
б) если в конъюнкт одна и та же литера входит несколько раз,
то удаляем все литеры x
δ
, кроме одной;
в) если в некоторый конъюнкт x
δ
1 1
. . . x
δ
k не входит переменная y, то этот конъюнкт заменяем на эквивалентную формулу x
δ
1 1
. . . x
δ
k k
∧(y ∨y)
4.5. ДВУХЭЛЕМЕНТНАЯ БУЛЕВА АЛГЕБРА
99
и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (y г) если в полученной ДНФ имеется несколько одинаковых консти- туент единицы, то оставляем только одну из них. В результате получается СДНФ.
П р им ер. Найдем СДНФ для ДНФ ϕ = xx∨x∨yzy. Имеем ∼ x ∨ yz ∼ (x(y ∨ y) ∨ yz(x ∨ x)) ∼ (xy ∨ xy ∨ xyz ∨ xyz) ∼ (xy(z ∨ z)∨
∨xy(z ∨ z) ∨ xyz ∨ xyz) ∼ (xyz ∨ xyz ∨ xyz ∨ xy z ∨ xyz ∨ xyz) ∼
∼ (xyz ∨ xyz ∨ xyz ∨ xy z Описание алгоритма приведения КНФ к СКНФ аналогично вышеизложенному описанию алгоритма приведения ДНФ к СДНФ и оставляется читателю в качестве упражнения Двухэлементная булева алгебра.
Фактор-алгебра алгебры формул
Рассмотрим множество B
0
= {0, 1} и определим на нем операции, согласно таблицам истинности формул x ∧ y, x ∨ y, x. Тогда система B
0
= B
0
; ∧, ∨, , 0, 1 является двухэлементной булевой алгеброй (см. пример 2.5.2, п. 1). Формулы алгебры логики, содержащие лишь логические операции ∧, ∨, , являются термами в B
0
. По теореме о функциональной полноте в булевой алгебре с помощью терма можно задать любую булеву функцию.
Обозначим через Φ
n множество всех формул алгебры логики с переменными из множества {x
1
, x
2
, . . . , x n
}. На множестве Φ
n определены двухместные операции конъюнкции и дизъюнкции — ∧: (ϕ, ψ) → ϕ∧ψ,
∨: (ϕ, ψ) → ϕ ∨ ψ — и одноместная операция отрицания : ϕ → Выделим на множестве Φ
n две константы x ∧ x и x ∨ x. Тем самым получается алгебра формул F
n
= Φ
n
; ∧, ∨, , x ∧ x, x ∨ x . Нетрудно заметить, что отношение эквивалентности формул является конгру- энцией на алгебре F
n
, и поэтому можно задать фактор-алгебру F
n
/ На фактор-множестве Φ
n
/ операции ∧, и определяются следующим образом ∼ (ϕ)∧ ∼ (ψ) = ∼ (ϕ ∧ ψ), ∼ (ϕ)∨ ∼ (ψ) = ∼ (ϕ ∨ ψ),
¬ ∼ (ϕ) = ∼ (¬ϕ). На множестве Φ
n
/ выделяются две константы = ∼ (x ∧ x) и 1 = ∼ (x ∨ x). Полученная система Φ
n
/ ∼; ∧, ∨, , 0, является фактор-алгеброй F
n
/ Теорема 4.5.1. Фактор-алгебра F
n
/ изоморфна алгебре булевых функций B
n
Глава 4. АЛГЕБРА ЛОГИКИ По теореме о функциональной полноте каждой функции f ∈ не являющейся константой 0, соответствует некоторая СДНФ ψ, принадлежащая классу ∼ (ϕ) = ξ −1 (f ) формул, представляющих функцию. Возникает задача нахождения в классе ∼ (ϕ) дизъюнктивной нормальной формы, имеющей наиболее простое строение Минимизация булевых функций в классе ДНФ Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза. П р им ер. Формула x 2 x 3 x 4 — элементарное произведение, а формула элементарным произведением не является. Формула ϕ(x 1 , x 2 , . . . , x n ) называется импликантой формулы, x 2 , . . . , x n ), если ϕ — элементарное произведение и ϕ∧ψ ∼ ϕ, т. е. для соответствующих формулами функций и справедливо неравенство f ϕ f ψ . Формула ϕ(x 1 , . . . , x n ) называется импликантой функции f , если ϕ — импликанта совершенной ДНФ, представляющей функцию f . Импликанта ϕ(x 1 , . . . , x n ) = x δ 1 i 1 x δ 2 i 2 · · · x δ k i k формулы называется простой, если после отбрасывания любой литеры из ϕ не получается формула, являющаяся импликантой формулы Пример. Найдем все импликанты и простые импликанты для формулы ϕ(x, y) = x → y. Всего имеется 8 элементарных произведений с переменными x и y. Ниже приведены их таблицы истинности y ϕ = x → y x y xy xy xy x y x y 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 Из таблиц истинности заключаем, что формулы x y, xy, xy, x, y все импликанты формулы ϕ, а из этих импликант простыми являются формулы x и y (формула x y, например, не является простой импли- кантой, поскольку отбрасывая литеру y, получаем импликанту Дизъюнкция всех простых импликант данной формулы (функции) называется сокращенной ДНФ.
4.6. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ДНФ
101
Теорема 4.6.1. Любая булева функция, не являющаяся константой, представима в виде сокращенной ДНФ.
В примере 4.6.2 функция, соответствующая формуле x → y, представима формулой x ∨ y, которая является ее сокращенной ДНФ.
Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной
ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.
Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МДНФ).
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции операция полного склеивания — ϕ · x ∨ ϕ · x ∼ ϕ(x ∨ x) ∼ ϕ;
— операция неполного склеивания · x ∨ ϕ · x ∼ ϕ(x ∨ x) ∨ ϕ · x ∨ ϕ · x ∼ ϕ ∨ ϕx ∨ ϕx;
— операция элементарного поглощения — ϕ · x
δ
∨ ϕ ∼ ϕ, δ ∈ {0, Теорема 4.6.2 (теорема Квайна). Если исходя из совершенной ДНФ
функции произвести всевозможные операции неполного склеивания,
а затем элементарного поглощения, тов результате получится сокращенная ДНФ, те. дизъюнкция всех простых импликант.
П р им ер. Пусть функция f (x, y, z) задана совершенной
ДНФ ϕ = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz. Тогда, производя в два этапа всевозможные операции неполного склеивания, а затем элементарного поглощения, имеем ∼ xy(z ∨ z) ∨ yz(x ∨ x) ∨ yz(x ∨ x) ∨ xz(y ∨ y)∨
∨xy(z ∨ z) ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼
∼ xy ∨ yz ∨ yz ∨ xz ∨ xy∨
∨xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼
∼ y(x ∨ x) ∨ y(z ∨ z) ∨ xy ∨ yz ∨ yz ∨ xz ∨ xy∨
∨xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼
∼ y ∨ xy ∨ yz ∨ yz ∨ xz ∨ xy∨
∨xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∼ y Таким образом, сокращенной ДНФ функции f является формула y∨
∨xz.
Глава 4. АЛГЕБРА ЛОГИКИ На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие нив каком склеивании. П р им ер. Пусть функция f (x, y, z) задана совершенной ДНФ ϕ = x y z ∨ x yz ∨ xyz ∨ xyz. Тогда, производя операции склеивания, а затем элементарного поглощения, имеем ϕ ∼ x y(z ∨ z) ∨ yz(x ∨ x) ∨ xz(y ∨ y) ∼ x y ∨ yz Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строки столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. Для примера 4.6.4 матрица Квайна имеет вид Импликанты Конституенты единицы x y z x yz xyz xyz x В тупиковую ДНФ выбирается минимальное число простых импли- кант, дизъюнкция которых сохраняет все конституенты единицы, те. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импли- кант. В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменных. В примере 4.6.4 по матрице Квайна находим, что минимальная ДНФ заданной функции есть x y В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюнктивных нормальных форм (МКНФ). § Карты Карно Для формул с малым числом переменных имеется другой способ получения простых импликант (и, значит, нахождения с помощью матрицы Квайна минимальной ДНФ). Этот способ основан на использовании так называемых карт Карно
4.7. КАРТЫ КАРНО 00 . . . 0 00 . . . 1
. . . x
1
. . . x k
10 . . . 0 00 . . . 0
· · ·
00 . . . 1
· · ·
x k+1
. . . x k
· · ·
· · ·
· · ·
· · ·
10 . . . 0
· · Риса б
Рис. Карта Карно для n переменных служит эффективным средством иллюстративного представления куба. Она содержит 2
n ячеек, каждая из которых соответствует одной из 2
n возможных комбинаций значений логических переменных x
1
, x
2
, . . ., x n
. Карта строится в виде матрицы размера 2
n−k на 2
k так, что ее столбцы соответствуют значениям переменных x
1
, . . ., x k
, строки — значениям переменных x k+1
,
. . ., x n
, а соседние ячейки (как по вертикали, таки по горизонтали)
отличаются только значением одной переменной (рис. На рис. 4.6 приведены карты Карно для функций трех и четырех переменных соответственно. В этих картах все ячейки, отмеченные скобкой x по строке и столбцу, представляют входные комбинации с x i
= 1, а в неотмеченных строках и столбцах ячейки соответствуют комбинациям с x i
= 0 (см. риса, на котором разными способами изображена одна и та же карта. Например, на риса ячейка a соответствует набору 001 значений переменных x
1
, x
2
, x
3
. Отметим,
что для каждой функции может быть построено несколько различных карт. На рис. б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных, x
2
}, {x
3
, x
4
}}, а вторая — {{x
1
}, {x
2
, x
3
, x
4
}}.
Глава 4. АЛГЕБРА ЛОГИКИ
У каждой вершины куба есть ровно n смежных с ней вершин, т. е.
вершин, отличающихся от нее только одной координатой. Поскольку в карте Карно каждая ячейка может иметь не более четырех ячеек,
соседних по строке или столбцу, для представления точек, отличающихся только на одну координату, необходимо использовать и более удаленные ячейки. Например, точки b и c на рис. б отличаются только значением переменной x
3
, те. являются смежными.
Булева функция может быть представлена на карте Карно выделением ячеек (те. ячеек, в которых функция принимает значение,
равное 1). Подразумевается, что необозначенные ячейки соответствуют 0-точкам.
На рис. 4.7 изображена карта, представляющая булеву функцию f (x, y, z), для которой f (0, 0, 0) = f (1, 1, 0) = f (1, 1, 1) =
= f (1, 0, 1) = 0, f (0, 1, 0) = f (1, 0, 0) = = f (0, 0, 1) =
x
1
x
2
x
3 1
1 Рис. 4.7
f (0, 1, 1) = Для построения импликант берутся всевозможные наборы ячеек, образующих вершины некоторого куба те точек таких, что пары соседних отличаются ровно одной координатой. Совпадающие координаты образуют набор (δ
1
, . . . , и требуемая импликанта имеет вид x
δ
1
i
1
. . . x
δ
n−k где x j
— переменная, соответствующая значению Пример. Точки b и c на рис. б лежат в кубе, который определяет конъюнкт x
1
x
2
x
4
. Точки {d, e, f, g} образуют 2-куб,
представляющий импликанту Определение простых импликант функции сводится к нахождению всех кубов, которые не содержатся в кубах более высокого порядка.
П р им ер. Простые импликанты для карты Карно, приведенной на рис. 4.7, равны x
1
x
2
, x
1
x
2
x
3
, Пример. На рис. 4.8 показана карта Карно, простые им- пликанты которой имеют вид x
2
x
3
x
4
, x
1
x
2
x
3
, x
1
x
3
x
4
, x
1
x
2
x
4
, x
2
x
3
x
4
,
x
1
x
2
x
4
, x
1
x
3
. Заметим, что импликанты x
1
x
2
x
3
, x
1
x
2
x
3
, и не являются простыми, так как образуемые ими кубы содержатся в
2-кубе После нахождения простых импликант задача построения минимальной ДНФ сводится к изучению матрицы Квайна, как показано в 4.6. При наглядном размещении простых импликант в карте Карно удается непосредственно находить минимальную ДНФ, выбирая те простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных. Так, минималь-
4.8. ПРИНЦИП ДВОЙСТВЕННОСТИ ДЛЯ БУЛЕВЫХ ФУНКЦИЙ 1
1 1
1 1
1 1
1 1
'
&
$
%
Рис. ной ДНФ для функции, изображенной на рис. 4.8, является формула Карты Карно применимы и для не всюду опре- Рис. деленных функций. В этом случае выделяются максимальные кубы, покрывающие ненулевые ячейки и содержащие хотя бы одну единицу.
П р им ер. На рис. 4.9 представлена карта Карно для частичной функции f , зависящей от трех переменных x
1
, x
2
, x
3
. Сокращенная ДНФ
имеет вида МДНФ — или x
2
x
3
∨ x
1
x
2
∨ x
2
x
3
§ Принцип двойственности для булевых функций
В § 2.5 мы говорили о двойственности в классе булевых алгебр, которая проявляется в том, что на множестве B со структурой булевой алгебры B можно ввести структуру двойственной алгебры B
+
, в которой роль операции играет ∨, роль операции ∨ — ∧, а в качестве нуля (единицы) используется 1 (соответственно 0). При этом между алгебрами B и имеется изоморфизм ϕ : x → x. В этом параграфе мы рассмотрим соответствие булевых функций при изоморфизме Функция f
+
(x
1
, . . . , x n
) называется двойственной по отношению к функции f (x
1
, . . . , x n
), если f
+
(x
1
, . . . , x n
) = f (x
1
, . . . , x Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, те. в таблице истинности нужно заменить 0 на 1, а 1 на 0.
Глава 4. АЛГЕБРА ЛОГИКИ П р им ер. Двойственной к функции x∧y является функция, соответствующая формуле ¬(x ∧ y), те) или x ∨ y: (x ∧ y) + = x ∨ y. Аналогично (x ∨ y) + = x ∧ y, (x) + = Принцип двойственности. Если f (x 1 , . . . , x n ) = g(h 1 (x 1 , . . . , x n ), . . . , h m (x 1 , . . . , x то f + (x 1 , . . . , x n ) = g + (h + 1 (x 1 , . . . , x n ), . . . , h + m (x 1 , . . . , x Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций. Принцип двойственности удобен при нахождении двойственных функций, представленных формулами, содержащими лишь конъюнкции, дизъюнкции и отрицания. В этом случаев исходной формуле конъюнкции заменяются на дизъюнкции, а дизъюнкции — на конъюнкции. Таким образом, ДНФ соответствует КНФ, КНФ — ДНФ, СДНФ — СКНФ, СКНФ — СДНФ. П р им ер Отметим, что если формула ϕ эквивалентна формуле ψ: ϕ то Функция f (x 1 , . . . , x n ) называется самодвойственной, если f + (x 1 , . . . , x n ) = f (x 1 , . . . , x Пример. Покажем, что формула ϕ = xy ∨ xz ∨ yz задает самодвойственную функцию. С этой целью убедимся, что на всех противоположных наборах значений переменных (δ 1 , δ 2 , δ 3 ) и (1−δ 1 , 1−δ 2 , 1−δ 3 ) формула принимает противоположные значения. Действительно, составив таблицу истинности получаем ϕ(0, 0, 0) = ϕ(1, 1, 1), ϕ(0, 0, 1) = ϕ(1, 1, 0), ϕ(0, 1, 0) = = ϕ(1, 0, 1), ϕ(0, 1, 1) = ϕ(1, 0, 0). § Полные системы булевых функций Как мы уже знаем из теоремы о функциональной полноте, любая булева функция представима в виде формулы, содержащей лишь операции, те. в виде терма сигнатуры {∧, ∨, ¬}. В этом параграфе 4.9. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ107 будет дано описание сигнатур, позволяющих получать любые булевы функции. Система булевых функций F = {f 1 , f 2 , . . . , f n } называется полной, если любая булева функция представима в виде терма сигнатуры, f 2 , . . . , f n }, те. в виде суперпозиций функций из Из сказанного выше ясно, что система {∧, ∨, ¬} является полной. Ответ на вопрос о полноте произвольной системы F дает теорема Поста, формулируемая ниже. Введем определение классов Поста. Класс P 0 — это класс булевых функций, сохраняющих нуль, т. е. функций f (x 1 , . . . , x n ), для которых f (0, 0, . . . , 0) = 0: P 0 = {f | f (0, 0, . . . , 0) = 0}. 2. Класс P 1 — это класс булевых функций, сохраняющих единицу, т. е. функций f (x 1 , . . . , x n ), для которых f (1, 1, . . ., 1) = 1: P 1 = {f | f (1, 1, . . . , 1) = 1}. 3. Класс S — это класс самодвойственных функций = {f | f — самодвойственная функция. Класс M — это класс монотонных функций. Булева функция f (x 1 , . . . , x n ) называется монотонной, если для любых наборов нулей и единиц (α 1 , . . . , α n ) и (β 1 , . . . , β n ) из условий α 1 β 1 , . . ., α n β n следует f (α 1 , . . . , α n ) f (β 1 , . . . , β n ). Таким образом = {f | f — монотонная функция. Класс L — это класс линейных функций. Булева функция f (x 1 , . . . , x n ) называется линейной, если в булевом кольце, 1}; функция f представима в виде f (x 1 , . . . , x n ) = = c 0 ⊕ c 1 x 1 ⊕ c 2 x 2 ⊕ . . . ⊕ c n x n , где c 0 , c 1 , c 2 , . . ., c n ∈ {0, Таким образом = {f | f — линейная функция}. Коэффициенты c 0 , c 1 , . . ., c линейной функции определяются из следующих соотношений f (0, 0, . . . , 0), c 0 ⊕ c 1 = f (1, 0, . . . , 0), c 0 ⊕ c 2 = f (0, 1, . . . , 0), . . . , c 0 ⊕ c n = f (0, 0, . . . , 0, 1), Глава 4. АЛГЕБРА ЛОГИКИ т. е f (0, 0, . . . , 0), c 1 = c 0 ⊕ f (1, 0, . . . , 0), . . . , c n = c 0 ⊕ f (0, 0, . . . , Таким образом, проверка линейности сводится к нахождению коэффициентов по формулами сопоставлению таблиц истинности данной формулы f (x 1 , . . . , x n ) и полученной формулы c 0 ⊕ c 1 x 1 ⊕ . . . ⊕ c n x Пример. Проверим, является ли линейной функция Имеем c 0 = 0 ∨ 0 = 0, c 1 = 0 ⊕ (1 ∨ 0) = 1, c 2 = 0 ⊕ (0 ∨ 1) = Таким образом, c 0 ⊕ c 1 x ⊕ c 2 y = x ⊕ y. Сопоставляя таблицы истинности формул x ∨ y и x ⊕ y, убеждаемся, что они не совпадают. Вывод: функция x ∨ y нелинейна. Линейность функции можно также определить с помощью следующей теоремы. Теорема 4.9.1 (теорема Жегалкина). Всякая булева функция f (x 1 , . . . , x n ) представима полиномом Жегалкина, те. в виде f (x 1 , . . . , x n ) = (i 1 ,...,i k ) x i 1 x i 2 . . . x i k ⊕ c, где в каждом наборе (i 1 , . . . , i все i различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слага- емых. Полином Жегалкина называется нелинейным (линейным, если он (не) содержит произведения переменных. Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина. Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиомы булева кольца {0, 1}; и равенства, выражающие операции ∧, и ¬ через операции этого булева кольца x∨y = = x⊕y⊕xy, x(y⊕z) = xy⊕xz, x = x ⊕ 1, x ⊕ 0 = x, x ⊕ x = 1, xx = 0 и т.д. П р им ер. Определим, будет ли линейной функция f (x, y, z) = x yz ∨ xyz ∨ xy Имеем f (x, y, z) = (x yz ⊕ xyz ⊕ x yzxyz) ∨ xy z = (x yz⊕ xyz) ∨ ∨ xy z = x yz ⊕ xyz ⊕ xy z ⊕ (x yz ⊕ xyz)xy z = x yz ⊕ xyz⊕ xy z⊕ 0 = = xz(y ⊕ y) ⊕ xy z = xz · 1 ⊕ xy z = (x ⊕ 1)z ⊕ x(y ⊕ 1)(z ⊕ 1) = = xz⊕ 1· z⊕ xyz ⊕xz ⊕xy ⊕x = x⊕z ⊕xy ⊕xyz. Полученный полином Жегалкина является нелинейными, следовательно, функция f также нелинейна 4.9. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ 109 Заметим, что если в эквивалентности ϕ∨ψ ∼ ϕ⊕ψ ⊕ϕ· ψ формулы и ψ являются различными конституентами единицы, то их произведение равно 0, и тогда ϕ ∨ ψ ∼ ϕ ⊕ ψ. Следовательно, для получения полинома Жегалкина из СДНФ можно сразу заменить на Отметим, что каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, тес помощью этих операций из функций, принадлежащих данному классу, можно получить только функции из этого же класса. П р им ер. Определим, к каким классам Поста относится булева функция f (x, y) = Так как f (0, 0) = 1, а f (1, 1) = 0, то f (x, y) / ∈ и f (x, y) / ∈ Поскольку f (1, 0) = f (0, 1), то f (x, y) / ∈ S. Так как f (0, 0) > > f (1, то f (x, y) / ∈ M. Полином Жегалкина для функции f (x, y) = xy имеет вид 1 ⊕ xy в силу равенства x = 1 ⊕ x. Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу Функция Классы P 0 P 1 S M L x | y Нет Нет Нет Нет Нет Теорема 4.9.2 (теорема Поста. Система F булевых функций тогда и только тогда является полной, когда для каждого из классов, P 1 , S, M , L в системе F найдется функция, не принадлежащая этому классу. В силу теоремы Поста функция x|y образует полную систему, тес помощью штриха Шеффера можно получить любую булеву функцию. В частности, x ∼ x|x, x ∧ y ∼ ¬¬(x ∧ y) ∼ ¬(x|y) Система булевых функций F называется базисом, если она полна, а для любой функции f ∈ F система F \ {f } неполна. Теорема 4.9.3. Каждый базис содержит не более четырех булевых функций. П р им ер. Следующие системы булевых функций являются базисами {∧, ¬}, {∨, ¬}, {→, ¬}, {↓}, {|}, {↔, ∨, 0}, {⊕, ∧, Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции Глава 4. АЛГЕБРА ЛОГИКИ Логические сети
1.
Определение и реализация булевых функций. Мульти- граф G = M, U, R , в котором выделено k вершин (полюсов, называется полюсной сетью. Сеть G, задаваемая неориентированным мультиграфом с k полюсами, в которой каждое ребро помечено буквой из алфавита X = {x
1
, x
2
, . . . , x n
, x
1
, x
2
, . . . , x n
}, называется k- полюсной контактной схемой.
На рис. 4.10 приведен пример контактной схемы с двумя полюсами и a
6
(k + Полюсная схема, в которой один полюс выделен (он называется входным, а остальные полюса (выходные) равноправны, называется, k)-полюсником. Таким образом, если в приведенной на рис. 4.10 двухполюсной схеме рассматривать, например, полюс как входной, а полюс как выходной, то получаем (1, 1)-полюсник Ребра контактной схемы называются контактами. Контакт, соответствующий логической переменной x i
, называется замыкающими обозначается через −
∅
. Замыкающий контакт пропускает ток при x
i
= 1. Контакт, соответствующий литере x i
, называется размыкающими обозначается как −
∅
. Через него ток проходит при x i
= Таким образом, значение 1 интерпретируется как состояние переключателя ток проходит, а 0 — ток не проходит. Функции x i
∧x соответствует последовательное соединение контактов, а функции x i
∨ x параллельное соединение контактов.
Нетрудно заметить, что схеме, показанной на рис. 4.10, соответствуют электрическая схема, приведенная на риса также схема контактов, изображенная на рис. 4.12. На последнем рисунке показаны контакты, зависящие от значений переменных x
1
, x
2
, x
3
, а также схема соединений контактов rr Рис. 4.10
4.10. ЛОГИЧЕСКИЕ СЕТИ
111
Пусть a, b — полюса контактной схемы Σ, [a, b] — некоторая цепь изв конъюнкция литер, приписанных ребрам цепи [a, Функция f a,b
(X), определяемая формулой f a,b
(X) = =
[a,b]
K
[a,b]
, в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, называется функцией проводимости между полюсами и b схемы Σ. Говорят, что функция g(X) реализуется (1, k)- полюсником, если существует такой выходной полюс b i
, что f a,b i
(X) =
g(X), где a — входной полюс. (1, 1)-Полюсники называются эквивалентными, если они реализуют одну и туже булеву функцию. Сложностью, 1)-полюсника называется число контактов. (1, 1)-полюсник,
имеющий наименьшую сложность среди эквивалентных ему схем, называется минимальным. Сложность минимального (1, 1)-полюсника,
реализующего функцию f , называется сложностью функции f в классе, 1)-полюсников и обозначается через L
π
(f Заметим, что задача нахождения минимального (1, 1)-полюсника среди эквивалентных данному (1, 1)-полюснику Σ равносильна нахождению среди функций, реализуемых схемой Σ, функции, имеющей наименьшее число вхождений переменных. Действительно, функцию,
реализуемую (1, 1)-полюсником, нетрудно представить в виде форму-
•
•
x
1
x
2
x
1
•
•
x
1
x
2
x
2
•
x
3
E
x
3
x
3
•
Рис. Рис. 4.12
Глава 4. АЛГЕБРА ЛОГИКИ
•
x
1
x
2
x
1
x
2
x
3
x
3
x
3
E
•
•
x
1
x
2
x
1
x
2
•
x
3
x
3
E
•
а б
Рис. 4.13
лы, которая строится из литер в соответствии с контактной схемой и имеет ровно столько вхождений переменных, сколько контактов имеет схема. Например, изображенной на рис. 4.11 схеме соответствует булева функция f (x
1
, x
2
, x
3
) = (x
1
∨ x
2
) · ((x
1
∨ x
2
) · x
3
∨ x
3
) Таким образом, задача нахождения минимального (1, по- люсника сводится к минимизации соответствующей булевой функции.
Эффективное уменьшение числа контактов достигается с помощью нахождения минимальной ДНФ булевой функции.
Найдем минимальную ДНФ функции (4.2), реализуемой схемой рис. Придавая логическим переменным x
1
, x
2
, всевозможные значения, по схеме или формуле (4.2) получаем таблицу истинности 0
0 0
0 1
1 1
1
x
2 0
0 1
1 0
0 1
1
x
3 0
1 0
1 0
1 0
1
f
1 0
1 0
1 0
0 по которой определим совершенную ДНФ: x
1
x
2
x
3
∨x
1
x
2
x
3
∨ ∨x
1
x
2
x
3
∨
x
1
x
2
x
3
. Используя один из методов нахождения минимальной ДНФ,
получаем формулу x
1
x
3
∨ x
2
x
3
∨ x
1
x
2
x
3
, эквивалентную формуле (и соответствующую схеме, состоящей из семи контактов (рис. 4.13а).
Отметим, что схема, изображенная на риса, допускает упрощение, соответствующее формуле (x
1
∨ x
2
)x
3
∨ x
1
x
2
x
3
, которое приведено на рис. б и является минимальной схемой. Сложность минимальной схемы равна 6: L
π
(f ) = Схемы из функциональных элементов. Ориентированная бесконтурная сеть, в которой полюса делятся на входные (входы) и выходные (выходы, называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, — некоторым функциональным символом. При этом должны выполняться следующие условия если a — входной полюс, то полустепень захода вершины a равна нулю deg
−
(a) = 0;
4.10. ЛОГИЧЕСКИЕ СЕТИ если вершина a не является полюсом и помечена местным функциональным символом f , то deg
−
(a) = n и дуги, входящие в a, перенумерованы от 1 до Функциональным элементом называется всякий подмультиграф схемы, состоящий из невходного полюса a, помеченного соответствующим символом f , и вершины, из которых исходят дуги в вершину Пример. На риса представлена схема из функциональных элементов. Здесь входные символы помечены символами переменных одноместный функциональный символ, соответствующий операции отрицания & — двухместный символ, соответствующий операции конъюнкции f
3
— некоторый двухместный символ f
1
, f
2
, f
4
— некоторые трехместные символы. Вершины, помеченные символами f
1
, и f
4
, являются выходными полюсами . Им соответствуют термы f
1
(x
1
, x
2
, x
3
), f
3
(x
1
x
2
, f
1
(x
1
, x
2
, x
3
)),
f
4
(f
3
(x
1
x
2
, f
1
(x
1
, x
2
, x
3
), x
3
), x
3
, f
2
(f
1
(x
1
, x
2
, x
3
), f
1
(x
1
, x
2
, x
3
), На рис. б изображен функциональный элемент, определяемый вершиной, помеченной символом f
4
. Ему соответствует устройство, показанное на рис. 4.14в.
В примере 4.10.1 продемонстрировано, что каждый вывод схемы порождает некоторый терм.
Говорят, что функция f реализуется схемой Σ, если существует такой выход a схемы Σ, что функция f a
, соответствующая терму выхода a, эквивалентна функции f Схемы из функциональных элементов с одним выходом, у которых входные полюса помечены символами x
1
, x
2
, . . ., x n
, а вершины,
отличные от входных полюсов, — символами ∨, &, ¬, называются X
n
- функциональными схемами. Сложностью схемы из функциональных элементов называется число ее вершин, отличных от входных полю rr j
rr r
j
0
•
¨¨
¨¨
¨¨
B•
c
•
E r rr j•r rr j
e e
e e
ee
E
x
3
x
2
x
1
f
4
f
3
&
¬
f
1
f
2 1
1 1
1 2
3 3
3 2
2 1
2 1
2
•
E
d а б
в
Рис. 4.14
Глава 4. АЛГЕБРА ЛОГИКИ r
j rr r
j
¨¨
¨
B
•
•
¨¨
¨¨
¨¨
B
rr rr rr rr rr r
r Рис. сов. Функциональная схема Σ, реализующая функцию f , называется минимальной, если всякая другая функциональная схема, реализующая, имеет сложность, не меньшую, чем сложность схемы Сложность минимальной схемы, реализующей функцию f , называется сложностью функции f в классе схем из функциональных элементов и обозначается через L(f Пример. Сложность функции f = (совпадает со сложностью функциональной схемы, изображенной на рис. 4.15, и равна 8: L(f ) = 8.
§ Проверка теоретико-множественных соотношений с помощью алгебры логики
Проверка истинности теоретико-множественного тождества A = сводится к записи формул ϕ и ψ, соответствующих выражениями с последующей проверкой равенства f
ϕ
= Пример. С помощью алгебры логики проверим истинность соотношения (A ⊕ B) \ C = A ⊕ (B \ C) для любых множеств, B, Сопоставим множествами переменные x, y и z соответственно. Выражение (A ⊕ B) \ C соответствует формуле (x ⊕ y) а выражение A ⊕ (B \ C) — формуле x ⊕ (y ∧ z). Составив таблицы истинности x
0 0
0 0
1 1
1 1
y
0 0
1 1
0 0
1 1
z
0 1
0 1
0 1
0 1
(x ⊕ y) ∧ z
0 0
1 0
1 0
0 1
,
x
0 0
0 0
1 1
1 1
y
0 0
1 1
0 0
1 1
z
0 1
0 1
0 1
0 1
x ⊕ (y ∧ z)
0 0
1 0
1 1
0 убеждаемся, что (x ⊕ y) ∧ z ∼ x ⊕ (y ∧ z), и формулы имеют разные значения на наборе (1, 0, 1).
4.12. ЗАДАЧИ И УПРАЖНЕНИЯ
115
Это означает, что данное тождество неверно. Действительно, положив, получаем контрпример к тождеству ⊕ B) \ C = A \ A = ∅, а A ⊕ (B \ C) = A ⊕ ∅ = A.
§ Задачи и упражнения. Составить таблицу истинности формулы x ⊕ y → z ∨ x|y ∧ x.
2. Доказать тождественную истинность формулы → y) → ((x → z) → (x → y ∧ z)).
3. Доказать эквивалентность x ∧ (x ∨ z) ∧ (y ∨ z) ∼ (x ∧ y) ∨ (x ∧ z).
4. Привести к ДНФ, КНФ, СДНФ и СКНФ формулу ↓ x) ⊕ xy) ↔ (z → x).
5. Используя метод Квайна и карты Карно, найти МДНФ и МКНФ формулы xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz.
6. Найти СДНФ и МДНФ по карте Карно, изображенной на рис. 4.16.
7. Найти СКНФ и МКНФ по карте Карно, изображенной на рис. 4.17.
8. Найти полином Жегалкина для булевой функции f , заданной вектором значений. Определить, каким классам Поста принадлежит функция Рис. Рис. 4.17
Глава 4. АЛГЕБРА ЛОГИКИ. Проверить с помощью теоремы Поста полноту следующих систем булевых функций:
|
|
|
Скачать 1.36 Mb.