1 - Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики (1075769), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Согласно теореме 1.6,базис Жегалкина — полное множество.Представление булевой функции через базис Жегалкина — это представление ее в видемногочлена в поле Z2 , при этом все переменные в многочлене имеют степень 1, поскольку в Z2имеем xk = x для любого элемента x. Учитывая это, заключаем, что для функции f (x1 , . . . , xn )от n аргументов соответствующий многочлен имеет не более 2n слагаемых (одно слагаемоенулевой степени, n слагаемых 1-й степени, Cn2 слагаемых 2-й степени и т.д.). Например, дляфункции трех переменных многочлен Жегалкина имеет вид:ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓИсходя из стандартного базиса можно строить и другие базисы.

Один из них — базисЖегалкина, состоящий из сложения по модулю 2 ⊕“, умножения (она же конъюнкция)”·“, и нульарной операции (постоянной функции) 1. Отметим, что алгебраическая система”({0, 1}, {⊕, ·}) есть поле Z2 вычетов по модулю 2, а формулы, построенные на операциях ⊕“”и ·“ представляют собой многочлены в Z2 (их называют многочленами Жегалкина).”Нетрудно прямой проверкой убедиться в том, чтоÌÃÒÓÔÍ-12Следствие 1.3. Каждая булева функция является истинностной функцией какой-либо пропозициональной формулы.ÔÍ-12ÌÃÒÓÌÃÒÓ11J Структура самой формулы не имеет значения. Пусть x1 , x2 , . .

. , xn — список всех переменных, входящих в формулу, и f (ξ1 , ξ2 , . . . , ξn ) истинностная функция этой формулы (ξi —истинностное значение переменной xi ).Отметим, что элементарная конъюнкция xσ1 1 ∧xσ2 2 ∧. . .∧xσnn истинна при ξ1 = σ1 , x2 = σ2 , . . . ,ξn = σn и ложна при любом другом варианте истинностных значений переменных. Поэтому вСДНФ при заданном наборе истинностных значений переменных максимум одна элементарнаяконъюнкция имеет истинностное значение 1.Для каждого набора σ1 , σ2 , . .

. , σn , для которого f (σ1 , σ2 , . . . , σn ) = 1 составляем элементарную конъюнкцию xσ1 1 ∧ xσ2 2 ∧ . . . ∧ xσnn , а затем из них составляем СДНФ. Получим формулу,для которой f (ξ1 , ξ2 , . . . , ξn ) является истинностной функцией. Значит, эта СДНФ эквивалентнаисходной формуле. Для построения СДНФ требуется лишь, чтобы истинностная функция хотябы при одном наборе истинностных значений переменных принимала значение 1, т.е. исходнаяформула не должна быть противоречием.Утверждение о КНФ является двойственным утверждением о ДНФ и может быть полученовзаимной заменой в рассуждениях дизъюнкции и конъюнкции. Ix ⊕ y ≡ xy + xy ≡ (¬x ∧ y) ∨ (x ∧ ¬y),ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121.

АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓJ Необходимость сформулированного критерия установлена выше. Поэтому сосредоточим внимание на доказательстве достаточности критерия. Это доказательство сводится к построениюна основе множества F функций стандартного базиса, причем можно ограничиться только отрицанием и умножением, поскольку сложение (дизъюнкция) выражается через отрицание иумножение:x + y = x y.ÔÍ-12ÌÃÒÓÔÍ-12Пусть F не является подмножеством ни одного из классов Поста. Для каждой функцииf ∈ F рассмотрим формулу g(x) = f (x, x, .

. . , x). Поскольку F не содержится в T0 и в T1 ,в F , во-первых, есть непостоянные функции, а во-вторых есть хотя бы одна функция f1 , длякоторой g1 (0) = 1, и есть хотя бы одна функция f2 , для которой g2 (1) = 0. Это возможно, еслиодна из функций g1 (x) и g2 (x) есть отрицание, либо обе функции постоянны и представляютконстанты0 и 1. Рассмотрим оба случая.Пусть функции g1 (x) и g2 (x) являются константы 0 и 1. Тогда для любой функции f ∈ Fформула f (α1 , α2 , . . . , αi−1 , x, αi+1 , . .

. , αn ), в которой αj — константы, есть формула над F .Выберем функцию f , не являющуюся монотонной. Тогда существуют два булевых вектора p и q,удовлетворяющие условиям p < q и f (p) = 1, f (q) = 0. Векторы p и q можно соединить цепочкойp = p0 , p1 , . . . , pk = q непосредственно предшествующих друг другу векторов (соседних). В этойцепочке найдется два соседних вектора pj−1 и pj , которые отличаются только одной компонентойс некоторым номером i и на которых f (pj−1 ) = 1, f (pj ) = 0. Пусть αj , j 6= i, одинаковыекомпоненты этих векторов. Тогда формула f (α1 , α2 , .

. . , αi−1 , x, αi+1 , . . . , αn ) представляет собойоперацию отрицания.Предположим, например, что функция g1 (x) является отрицанием. Тогда мы можем составлять формулы вида f (x ⊕ σ 1 , . . . , x ⊕ σn ), где x ⊕ σ есть переменная x при σ = 0 и ееотрицание при σ = 1. Выберем функцию f ∈ F , не являющуюся самодвойственной. Тогдаможно указать такой булев вектор p ∈ Bn , что f (p) 6= f (p), откуда f (p) = f (p). Пусть σ1 , . . .

,σn — компоненты вектора p. Рассмотрим функцию g(x) = f (x ⊕ σ 1 , . . . , x ⊕ σn ), определяемуювыбранной несамодвойственной функцией f и вектором p. Так как 0 ⊕ σi = σi , 1 ⊕ σi = σ i ,то g(0) = f (p) = f (p) = f (σ1 ⊕ 1, . . . , σn ⊕ 1) = g(1). Следовательно, функция g(x) являетсяконстантой. Пусть, например, g(x) = 1. Тогда g(x) = 0 — другая константа.Итак, мы показали, что множество F , не являющееся подмножеством классов T0 , T1 , S, M ,позволяет получить в виде формул отрицание и обе константы.

Для построения формулы дляÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Теорема 1.8 (критерий Поста). Множество F булевых функций полно тогда и толькотогда, когда оно не является подмножеством ни одного из классов Поста.ÌÃÒÓÌÃÒÓВведем пять так называемых классов Поста. Класс T0 содержит все функции, удовлетворяющие условию f (0, 0, . . . , 0) = 0, т.е. функции, принимающие нулевое значение при нулевыхзначениях всех аргументов. Аналогично T1 — это класс функций, удовлетворяющих условиюf (1, 1, . . .

, 1) = 1. Класс S — это класс самодвойственных функций, т.е. функций, удовлетворяющих условию f (x1 , . . . , xn ) = f (x1 , . . . , xn ), где x = 1 − x — отрицание. Вектор значенийсамодвойственной функции удовлетворяет условию b1 b2 . . . bn = bn bn−1 . . . b1 .Для двух булевых векторов a = a1 a2 . . . an и b = b1 b2 . . . bn полагаем a 6 b, если ai 6 bi ,i = 1, n. Булеву функцию f (x) = f (x1 , x2 , .

. . , xn ) назовем монотонной, если f (x) 6 f (y) приx 6 y. Множество всех монотонных функций составляют класс M .Наконец, класс L линейных функций составляют функции, у которых полином Жегалкина имеет степень не выше первой.Каждый из классов Поста является замкнутым множеством. Доказательство можно провести методом индукции по построению формулы. При этом ни один из классов не совпадаетс множеством P2 всех булевых функций. Отсюда вытекает, что если заданное множество Fбулевых функций включено в один из классов Поста, то оно не является полным, посколькуего замыкание также будет включено в этот класс Поста.

Мы получили необходимое условиеполноты множества булевых функций. Оказывается, что это условие является и достаточным.ÌÃÒÓÔÍ-12ÌÃÒÓ12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ13произведения выберем функцию f ∈ F , не являющуюся линейной. Составляя формулы видаf (X1 , X2 , . . .

, Xn ), где Xi — это либо переменная x, либо переменная y, мы получим функциидвух аргументов. Покажем, что среди таких функций есть нелинейные. В полиноме Жегалкина, представляющем функцию f , выберем нелинейное (степени два или выше) слагаемоенаименьшей степени. Пусть это слагаемое имеет вид xi1 xi2 .

. . xik . В формуле f (X1 , X2 , . . . , Xn )положим Xi1 = x, Xij = y, j = 2, k, а для остальных переменных, не вошедших в выбранное слагаемое выберем значение 0. Тогда выбранное слагаемое преобразуется в xy, остальныенелинейные слагаемые обнулятся, и мы получим функцию вида g(x, y) = xy ⊕ αx ⊕ βy ⊕ γ.Так какg(x, y) = xy ⊕ αx ⊕ βy ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ αβ ⊕ γ = (x ⊕ β)(y ⊕ α) ⊕ γ 0 ,заключаем, что g(x ⊕ β, y ⊕ α) ⊕ γ 0 = xy. Но x ⊕ σ — это переменная x при σ = 0 и ееотрицание x при σ = 1. Поэтому, если g(x, y) принадлежит замыканию F , то и функцияg(x ⊕ β, y ⊕ α) ⊕ γ 0 = xy, т.е. конъюнкция, принадлежит замыканию F .Итак, мы показали, что если множество F не является подмножеством никакого классаПоста, то формулами над F можно представить отрицание и конъюнкцию, а значит, и дизъюнкцию.

В этом случае, согласно теореме 1.6, множество F полное. IПример 1.2. Полное множество составляет единственная функция x | y = ¬(x ∧ y), называемая штрихом Шеффера. Проверка критерия Поста здесь элементарна, и мы на этомне будем останавливаться.

Нетрудно также с помощью этой функции представить функциистандартного базиса:xy = x | y = (x | y) | (x | y),x + y = xy = x | yАналогична стрелка Пирса. Она тоже составляет базис.ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Пример 1.3. В математической логике ключевой операцией является импликация. Совместно с отрицанием она составляет базис: отрицание не попадает в классы T0 , T1 , M , аимпликация оказывается за бортом классов S и L. Впрочем, как и в случае других базисов,можно через импликацию и отрицание представить дизъюнкцию и конъюнкцию, а затем сослаться на теорему 1.6.ÌÃÒÓx = xx = x | x,ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121.

Характеристики

Список файлов лекций