Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
31. Сколькими способами из группы в 30 человек можно сформировать 5 коа- лиций по 6 человек? 32. Сколько натуральных чисел от 20 до 1000 делятся ровно на одно из чисел 7, 11 или 13? 33. Сколько трехзначных чисел делятся хотя бы на одно из чисел: a) 7, 11, 13; б) 6, 8, 21? 34. Найти общее решение рекуррентного уравнения: а) a n+2 + 3a n = 0; б) a n+2 − a n+1 − a n = 0; в) a n+2 + 2a n+1 + a n = 0; г) a n+3 + 10a n+2 + 32a n+1 + 32a n = 0; д) a n+3 + 3a n+2 + 3a n+1 + a n = 0; е) a n+2 + 4a n+1 + 4a n = n 2 − 3n + 1. 35. Найти решение рекуррентного уравнения с начальными условиями: а) a n+2 − a n = 0, a 0 = 0, a 1 = 2; б) a n+2 − 6a n+1 + 9a n = 0, a 1 = 6, a 2 = 27; в) a n+2 + a n+1 − 2a n = n, a 0 = 1, a 1 = −2; г) a n+2 − 4a n+1 + 4a n = 3 n , a 0 = 5, a 1 = 7; д) a n+2 + 2a n+1 − 8a n = 27 · 5 n , a 1 = −9, a 2 = 45. Глава 6 АЛГЕБРА ЛОГИКИ § 6.1. Формулы алгебры логики Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно. В качестве примеров высказываний приведем предложения “НГТУ — крупнейший вуз Новосибирска” и “Снег зеленый”. Первое высказывание яв- ляется истинным, а второе — ложным. Поставим в соответствие высказыванию P логическую переменную x, которая принимает значение 1, если P истинно, и 0, если P ложно. Если имеется несколько высказываний, то из них можно образовать раз- личные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логиче- ских переменных можно составлять различные конструкции, которые обра- зуют формулы алгебры логики. Итак, пусть {x i | i ∈ I} — некоторое множество логических переменных. Определим по индукции понятие формулы алгебры логики: 1) любая логическая переменная является формулой (называемой ато- марной); 2) если ϕ и ψ — формулы, то выражения ¬ϕ, (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ), (ϕ ↔ ψ) являются формулами; 3) никаких других формул, кроме построенных по пп. 1 и 2, нет. Если формула ϕ построена из логических переменных, лежащих в мно- жестве {x 1 , x 2 , . . . , x n }, то будем писать ϕ(x 1 , . . . , x n ). Символы ¬, ∧, ∨, →, ↔, использованные в определении, называются ло- гическими операциями или связками и читаются соответственно: отрицание или инверсия, конъюнкция, дизъюнкция, импликация и эквивалентность. 6.1. ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ 181 Введенные в п. 2 формулы следующим образом интерпретируются в рус- ском языке: ¬ϕ — “не ϕ”, (ϕ ∧ ψ) — “ϕ и ψ”, (ϕ ∨ ψ) — “ϕ или ψ”, (ϕ → ψ) — “если ϕ, то ψ”, (ϕ ↔ ψ) — “ϕ тогда и только тогда, когда ψ”. Вместо ¬ϕ часто пишут ϕ, вместо (ϕ ∧ ψ) — (ϕ & ψ), (ϕ · ψ) или (ϕψ), а вместо (ϕ → ψ) — (ϕ ⊃ ψ). Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, составляющих формулу, и соответствующее этому набору значение полученной формулы: ϕ ¬ϕ 0 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 1 Приведенные таблицы истинности называются также интерпретациями логических операций и составляют семантику формул (т. е. придание смыс- ла формулам) в отличие от синтаксиса формул (т. е. формальных законов их построения, данных в определении формулы). Исходя из таблиц истинности для логических операций можно строить таблицы истинности для произвольных формул. Пример 6.1.1. Построить таблицу истинности для формулы ϕ = ((x → y) ∧ ((y → z) → x)). Будем строить таблицу истинности последовательно в соответствии с ша- гами построения формулы ϕ: 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 0 Легко заметить, что таблица истинности для ϕ совпадает с таблицей ис- тинности для x. В дальнейшем выяснится причина этого совпадения. ¤ 182 Глава 6. АЛГЕБРА ЛОГИКИ Расширим понятие формулы, введя новые, не менее важные логические операции: • (ϕ | ψ) — штрих Шеффера или антиконъюнкция, по определению (ϕ | ψ) ¬(ϕ ∧ ψ); • (ϕ ↓ ψ) — стрелка Пирса или антидизъюнкция, по определению (ϕ ↓ ψ) ¬(ϕ ∨ ψ); • (ϕ ⊕ ψ) — кольцевая сумма, логическое сложение или сложение по мо- дулю 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. 6.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 183 § 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 184 Глава 6. АЛГЕБРА ЛОГИКИ Булева функция 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 ) 6.2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 185 • • • • • • • • • • • • • • • © © © © © © 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 определим по следующему правилу: 186 Глава 6. АЛГЕБРА ЛОГИКИ 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 |