Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
ϕ совпадает с таблицей ис- тинности для x. В дальнейшем выяснится причина этого совпадения. ¤ 6.1. ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ 185 Расширим понятие формулы, введя новые, не менее важные логические операции: • (ϕ | ψ) — штрих Шеффера или антиконъюнкция, по определению (ϕ | ψ) ¬(ϕ ∧ ψ); • (ϕ ↓ ψ) — стрелка Пирса или антидизъюнкция, по определению (ϕ ↓ ψ) ¬(ϕ ∨ ψ); • (ϕ ⊕ ψ) — кольцевая сумма, логическое сложение или сложение по мо- дулю 2, по определению (ϕ ⊕ ψ) ¬(ϕ ↔ ψ). Составим исходя из определений таблицы истинности для этих трех опе- раций: ϕ ψ (ϕ | ψ) (ϕ ↓ ψ) (ϕ ⊕ ψ) 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 Как видно из примера 6.1.1, даже при составлении несложных формул возникает обилие скобок. Чтобы избежать этого, в ал- гебре логики, так же как и в арифметике, приняты неко- ¬m |m ∨m →m ∧m ↓m ↔m ⊕m ¡ ¡ @ @ ¡ ¡ @ @ @ @ ¡ ¡ ∨ ∨ ∨ ∼ ∼ ∼ ∨ ∨ ∨ ∨ ∨ ∨ Рис. 6.1 торые соглашения относительно расстановки скобок. Пе- речислим эти соглашения. 1. Внешние скобки не пишутся. Например, вместо вы- сказывания ((x ∨ y) → z) пишется (x ∨ y) → z. 2. На множестве {¬, ∧, ∨, →, ↔, |, ↓, ⊕} вводятся тран- зитивное отношение < “быть более сильным” и отношение эквивалентности ∼ “быть равносильным” по правилам, показанным на рис. 6.1. Согласно этим отношениям недостающие скобки в фор- муле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для рав- носильных связок расстановка скобок выполняется слева направо. Пример 6.1.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))). ¤ Отметим, что, например, в формуле x → (y → z) скобки убирать нельзя, поскольку в силу наших соглашений формуле x → y → z соответствует формула (x → y) → z. 186 Глава 6. АЛГЕБРА ЛОГИКИ § 6.2. Функции алгебры логики В предыдущем параграфе мы выяснили, что семантически формулы пол- ностью характеризуются таблицами истинности. При этом можно забыть о синтаксической структуре самих формул и иметь дело с таблицами истин- ности. Таким образом, мы приходим к понятию функции алгебры логики, которое и будет исследоваться в дальнейшем. Функцией алгебры логики (ФАЛ) от n переменных x 1 , x 2 , . . . , x n назы- вается любая функция f : {0, 1} n → {0, 1}, т. е. функция, которая произволь- ному набору (δ 1 , δ 2 , . . . , δ n ) нулей и единиц ставит в соответствие значение f (δ 1 , δ 2 , . . . , δ n ) ∈ {0, 1}. Функции алгебры логики называются также булевыми функциями, дво- ичными функциями и переключательными функциями. Булевой функцией описываются преобразования некоторым устройст- вом входных сигналов в выходные. Предположим, что устройство, по- казанное на рис. 6.2, имеет n входов x 1 , x 2 , . . ., x n , на которые может подаваться или не подаваться ток, и один выход, на который ток подается или не подается в зависимости от подачи тока на входы. При этом значе- ние переменной x i = 1 интерпретируется как поступление тока на i-й вход, а x i = 0 — как непоступление тока. Значение f (δ 1 , δ 2 , . . . , δ n ) равно 1, если при x 1 = δ 1 , . . ., x n = δ n ток на выход проходит, и f (δ 1 , δ 2 , . . . , δ n ) = 0, если ток не проходит. Например, операции конъюнкции x ∧ y соответствует устройство с двумя входами и одним выходом. При этом значение выхода равно 1, тогда и только тогда, когда оба значения входов равны 1 (рис. 6.3). f x 1 x 2 x n - f (x 1 , x 2 . . . , x n ) - y x & Рис. 6.2 Рис. 6.3 6.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 187 Булева функция f (x 1 , x 2 , . . . , x n ) полностью определяется своей табли- цей истинности: x 1 x 2 x 3 . . . x 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, 1) В каждой строке таблицы вначале задается набор значений переменных (δ 1 , δ 2 , . . . , δ n ), а затем — значение функции на этом наборе. Если булева функция f и формула ϕ имеют одну и ту же таблицу истин- ности, то будем говорить, что формула ϕ представляет функцию f . Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1. Пример 6.2.1 (голосование). Рассмотрим устройство, фиксирующее при- нятие некоторой резолюции “комитетом трех”. Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов согласны, то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию 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 1 Полученную функцию f можно также задать следующей системой равенств: f (0, 0, 0) = f (0, 0, 1) = f (0, 1, 0) = f (1, 0, 0) = 0. ¤ Вектором значений булевой функции f (x 1 , x 2 , . . . , x n ) называется упоря- доченный набор всех значений функции f , при котором значения упорядо- чены по лексикографическому порядку множества аргументов {0, 1} n В примере 6.2.1 вектором значений булевой функции f (x, y, z) является набор (0001 0111). Отметим, что поскольку всего имеется 2 n наборов (δ 1 , . . ., δ n ) нулей и еди- ниц (|{0, 1} n | = 2 n ), существует ровно 2 (2 n ) булевых функций f (x 1 , x 2 , . . . , x n ) 188 Глава 6. АЛГЕБРА ЛОГИКИ • • • • • • • • • • • • • • • © © © © © © HH HH H H ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ @ @ @ ¢ ¢ ¢ A A A ¢ ¢ ¢ A A A ¢ ¢ ¢ A A A ¢ ¢ ¢ A A A Λ 0 1 00 01 11 10 000 001 010 011 100 101 110 111 Рис. 6.4 от n переменных: |{f | f : {0, 1} n → {0, 1}}| = |{0, 1}| |{0,1} n | = 2 2 n (см. опе- рации над кардиналами в § 1.4). Таким образом, имеется, например, 16 булевых функций от двух пере- менных, 256 — от трех и т. д. Наборы (δ 1 , δ 2 , . . . , δ n ) нулей и единиц можно представить в виде вершин n-мерных кубов (см. § 4.2) или в виде вершин 2-дерева (рис. 6.4), каждая вершина которого представляет собой некоторый набор (δ 1 , δ 2 , . . . , δ n ) нулей и единиц или пустое слово Λ. При этом с вершиной (δ 1 , δ 2 , . . . , δ n−1 , δ n ), n > 2, смежны вершины (δ 1 , δ 2 , . . . , δ n−1 ), (δ 1 , δ 2 , . . . , δ n−1 , 0), (δ 1 , δ 2 , . . . , δ n−1 , 1), с вершиной δ 1 — Λ, (δ 1 , 0) и (δ 1 , 1), с вершиной Λ — 0 и 1. На каждом этаже изображенного 2-дерева располагаются всевозможные наборы (δ 1 , δ 2 , . . . , δ n ) нулей и единиц фиксированной длины n. Функция f (x 1 , . . . , x n ) называется суперпозицией функций g(y 1 , . . . , y m ) и h 1 (x 1 , . . . , x n ), . . . , h m (x 1 , . . . , x n ), если f (x 1 , . . . , x n ) = g(h 1 (x 1 , . . . , x n ), . . . , h m (x 1 , . . . , x n )). Пример 6.2.2. Функция 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 , x 4 x 1 . ¤ Булева функция f (x 1 , x 2 , . . . , x n ), принимающая значение 1 (соответствен- но 0) на всех наборах нулей и единиц: f (x 1 , x 2 , . . . , x n ) ≡ 1 (соответственно f (x 1 , x 2 , . . . , x n ) ≡ 0), называется константой 1 (константой 0). Опишем булеву алгебру B n функций алгебры логики от n переменных. В качестве носителя рассмотрим множество B n = {f | f : {0, 1} n → {0, 1}}. Отношение 6 на множестве B n определим по следующему правилу: 6.3. ЭКВИВАЛЕНТНОСТЬ ФОРМУЛ 189 f 1 6 f 2 ⇔ f 1 (X) 6 f 2 (X) для любого набора значений X = (δ 1 , . . . , δ n ). Пересечением 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 определяется следующим образом: f (X) = ( 0, если f (X) = 1, 1, если f (X) = 0. В качестве 0 рассмотрим функцию, являющуюся константой 0, а в качестве 1 возьмем константу 1. Система B n = hB n ; ∧, ∨, , 0, 1i образует булеву алгебру функций алгебры логики от n переменных (алгебру булевых функций). § 6.3. Эквивалентность формул Как показано в примере 6.1.1, различные формулы могут иметь одинако- вые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы ϕ(x 1 , . . . , x n ) и ψ(x 1 , . . . , x n ) называются эквивалентными (ϕ ∼ ψ), если совпадают их таблицы истинности, т. е. совпадают представ- ляемые этими формулами функции f ϕ (x 1 , . . . , x n ) и f ψ (x 1 , . . . , x n ). Пример 6.3.1. Построив таблицы истинности формул x → y и y → x, убеждаемся в том, что (x → y) ∼ (y → x). ¤ Легко видеть, что отношение ∼ является отношением эквивалентности, т. е. оно рефлексивно (ϕ ∼ ϕ), симметрично (ϕ ∼ ψ ⇒ ψ ∼ ϕ) и транзитивно (ϕ ∼ ψ, ψ ∼ χ ⇒ ϕ ∼ χ). Отметим основные эквивалентности между формулами: 1) ((ϕ∧ψ)∧χ) ∼ (ϕ∧(ψ∧χ)), ((ϕ∨ψ)∨χ) ∼ (ϕ∨(ψ∨χ)) (ассоциативность ∧ и ∨); 2) (ϕ ∧ ψ) ∼ (ψ ∧ ϕ), (ϕ ∨ ψ) ∼ (ψ ∨ ϕ) (коммутативность ∧ и ∨); 3) (ϕ ∧ ϕ) ∼ ϕ, (ϕ ∨ ϕ) ∼ ϕ (идемпотентность ∧ и ∨); 4) (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ)), (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ)∧ ∧(ϕ ∨ χ)) (законы дистрибутивности); 5) (ϕ ∧ (ϕ ∨ ψ)) ∼ ϕ, (ϕ ∨ (ϕ ∧ ψ)) ∼ ϕ (законы поглощения); 6) ¬(ϕ ∧ ψ) ∼ ¬ϕ ∨ ¬ψ, ¬(ϕ ∨ ψ) ∼ ¬ϕ ∧ ¬ψ (законы де Моргана); 7) ¬¬ϕ ∼ ϕ (закон двойного отрицания); 190 Глава 6. АЛГЕБРА ЛОГИКИ 8) ϕ → ψ ∼ ¬ϕ ∨ ψ; 9) ϕ ↔ ψ ∼ ((ϕ → ψ) ∧ (ψ → ϕ) ∼ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ); 10) (ϕ ∨ ¬ϕψ) ∼ (ϕ ∨ ψ), (¬ϕ ∨ ϕψ) ∼ (¬ϕ ∨ ψ); 11) ϕ(¬ϕ ∨ ψ) ∼ ϕψ, ¬ϕ(ϕ ∨ ψ) ∼ ¬ϕψ. Формула ϕ(x 1 , x 2 , . . . , x n ) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула при- нимает значение 1 (соответственно 0). Пример 6.3.2. Формула x∧y является одновременно выполнимой и опро- вержимой, поскольку 0 ∧ 0 = 0, а 1 ∧ 1 = 1. ¤ Формула ϕ(x 1 , . . . , x n ) называется тождественно истинной, общезначи- мой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах зна- чений переменных, т. е. функция f является константой 1 (константой 0). Пример 6.3.3. Формула x ∨ x является тождественно истинной, а фор- мула x ∧ x — тождественно ложной: x x ∨ x x ∧ x 0 1 0 1 1 0 Если ϕ — тождественно истинная формула, то будем писать |= ϕ. В про- тивном случае пишем 6|= ϕ. Таким образом, |= x ∨ x, 6|= x ∧ y, и 6|= x ∧ x. Очевидным является следующее Замечание 6.3.1. 1. Формула ϕ тождественно ложна тогда и только тогда, когда ¬ϕ тождественно истинна (|= ¬ϕ); 2. Формула ϕ опровержима тогда и только тогда, когда она не является тождественно истинной (6|= ϕ); 3. Формула ϕ выполнима тогда и только тогда, когда она не является тождественно ложной. Отметим, что тождественно истинные (соответственно тождественно лож- ные) формулы образуют класс эквивалентности по отношению ∼. Предложение 6.3.2. Если формула ϕ 1 тождественно истинна, ϕ 0 — тождественно ложна, то для любых формул ϕ и ψ справедливы следующие эквивалентности: ϕ ∧ ϕ 1 ∼ ϕ; ϕ ∧ ϕ 0 ∼ ϕ 0 ; ϕ ∨ ϕ 1 ∼ ϕ 1 ; ϕ ∨ ϕ 0 ∼ ϕ; (ϕψ → ϕ) ∼ ϕ 1 ; (ϕ → ϕ ∨ ψ) ∼ ϕ 1 ; ϕ ⊕ ϕ ∼ ϕ 0 ; ϕ ⊕ ϕ 1 ∼ ϕ; ϕ ⊕ ϕ 0 ∼ ϕ. 6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ 191 В заключение настоящего параграфа приведем список всевозможных бу- левых функций от двух переменных, а также основных формул, представ- ляющих эти функции: 0 0 1 1 x 0 1 0 1 y 0 0 0 0 x ∧ ¬x — константа 0 0 0 0 1 x ∧ y — конъюнкция 0 0 1 0 ¬(x → y) — запрет по y 0 0 1 1 x — повтор x 0 1 0 0 ¬(y → x) — запрет по x 0 1 0 1 y — повтор y 0 1 1 0 x ⊕ y — логическое сложение 0 1 1 1 x ∨ y — дизъюнкция 1 0 0 0 x ↓ y — стрелка Пирса 1 0 0 1 x ↔ y — эквивалентность 1 0 1 0 ¬y — отрицание y 1 0 1 1 y → x — обратная импликация 1 1 0 0 ¬x — отрицание x 1 1 0 1 x → y — прямая импликация 1 1 1 0 x | y — штрих Шеффера 1 1 1 1 |