вфцвфцввц. Математическая логика
 Скачать 2.56 Mb.
|
х2) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х1 х2.Преобразуем эту формулу, используя соответствующие эквивалентностиU Изобразим схему, соответствующую заключительной формуле B A 4. Булевы функции Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B={1, 0}. Функцией алгебры логики (логической функцией) или булевой функцией f(x1,x2,...,xn) называетсяотображение f : B nB, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через Pn – множество булевых функций n переменных. Логическую функцию n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части – значения функции на этих наборах.
При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть , т.е. | | = . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1). Пусть F={ } – некоторое множество булевых функций. Его можно выбрать в качестве основного набора, называемого базисом. Формулой над базисом F (обозначается [F]) называется выражение вида [F]= , где F, а либо переменная, либо формула над F. Таким образом, всякая формула является суперпозицией базисных функций, для её представления обычно применяется форма записи с логическими операциями | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| x | 0 | 1 | 2 | 3 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| х1 | x2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0(х1,х2) 0 и 15 (х1,х2) 1.
1(х1,х2) = х1 х2 . Эта функция называется ещё логическим умножением и обозначается, также, х1х2.
2(х1.х2) = (х1х2).
3(х1,х2) = х1.
4(х1.х2) = (х2х1).
5(х1,х2) = х2.
6(х1,х2) = (х1
7(х1.х2) = х1 х2 .
8(х1.х2) = (х1х2) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х1х2.
9(х1.х2) = х1х2 . Эту функцию называют еще равнозначностью и обозначают х1х2 .
10(х1.х2) = .
11(х1.х2) = х2х1.
12(х1.х2) = .
13(х1.х2) = х1х2.
14(х1.х2) = (х1х2) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х1 | х2.
Формулы, реализующие одну и ту же функцию, называются равносильными. Отношение равносильности формул является отношением эквивалентности и обозначается .
Фиктивной переменной (несущественной) функции f(x1, . . . , xn) называется переменная хi, изменение значения которой не меняет значения функции, то есть f(x1, . . . , хi-1, 1, xi+1, . . . , xn) = f(x1, . . . , хi-1, 0, xi+1, . . . , xn).
Например, в функциях 3 и 12 переменная х2 фиктивна, а в функциях 5 и 10 фиктивна переменная х1.
Функция f(x1, . . . , xn), имеющая фиктивную переменную xi, по существу зависит от (n–1)-й переменной, т.е. представляет собой функцию g(x1, . . . , хi-1, xi+1, . . . , xn). В этом случае говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными.
Пусть f (x1, , xn) Pn – булева функция. Тогда функция f*(x1, , xn), определенная следующим образом
f *(x1, , xn) = ,
называется двойственной к функции f.
Теорема (Принцип двойственности). Пусть F={ }. Тогда, если формула [F] реализует функцию f, то формула * над базисом F*={ }, полученная из формулы заменой функций fi на двойственные им функции fi*, реализуют функцию f *.
5. Нормальные формы
Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами, определим их.
Элементарной конъюнкцией называется конъюнкция, в которой участвуют высказывательные переменные или их отрицания.
Элементарной дизъюнкцией называется дизъюнкция, в которой участвуют высказывательные переменные или их отрицания.
Терема 4.1. 1) Элементарная конъюнкция тождественно ложна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.
2) Элементарная дизъюнкция тождественно истинна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.
Доказательство. Докажем утверждение 1. Пусть элементарная конъюнкция тождественно ложна, предположим противное, что она не содержит никакую высказывательную переменную вместе с её отрицанием. Тогда можно построить интерпретацию, на которой эта конъюнкция истинна, придав переменным входящим в неё без отрицаний значение 1, а с отрицанием – 0. Следовательно, получено противоречие с предположением о тождественной ложности элементарной конъюнкции.
Обратное утверждение непосредственно следует из закона противоречия 9 и свойств констант 6.
Утверждение 2 доказывается аналогично.
Дизьюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Коньюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.
Примеры.
1. - КНФ.
2. - ДНФ.
3. приведенная формула, но не является ни ДНФ, ни КНФ.
4. является и ДНФ, и КНФ.
Теорема 4.2. Для всякой формулы U существуют эквивалентные ей КН-форма и ДН-форма.
Алгоритм построения нормальных форм.
Преобразовать формулу к приведенному виду (см. п.2).
Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности 5 операций конъюнкции и дизъюнкции.
Например ДНФ формулы примера 1 получим непосредственно по свойству 5 . Упростив формулу примера 3 по закону обобщенного склеивания , получим КН- и ДН-форму.
Задание 1. Построить нормальные формы формулы
.
Решение. Преобразуем формулу к приведенному виду и затем упростим ее.
Полученная формула является КН- и ДН-формой.
ДНФ и КНФ не единственны. Существуют формулы, к которым можно привести любую логическую формулу единственным образом с точностью до порядка элементарных дизъюнкций или конъюнкций и элементов в них. Такими формулами являются совершенные нормальные формы.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ в каждой конъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие конъюнкции называются полными.
Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ в каждой дизъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие дизъюнкции называются полными.
Теорема 4.3. 1) Всякая элементарная дизъюнкция высказывательных переменных , не являющаяся ТИ-формулой, эквивалентна некоторой СКН-форме от этих высказывательных переменных.
2) Всякая элементарная конъюнкция высказывательных переменных , не являющаяся ТЛ-формулой, эквивалентна некоторой СДН-форме от этих высказывательных переменных.
Доказательство. Докажем утверждение 1. Так как элементарная дизъюнкция не является тождественно истинной, то в силу теоремы 4.1 она не содержит никакую высказывательную переменную вместе с её отрицанием. Если некоторая переменная (или её отрицание ) входит в элементарную дизъюнкцию несколько раз, то в силу идемпотентности операции дизъюнкции, оставим только одно её вхождение. Если же некоторая переменная не содержится в элементарной дизъюнкции, то, воспользовавшись законом склеивания 13
, получим КНФ. Если полученная форма не является совершенной, то для каждой её элементарной дизъюнкции повторим данную операцию. Таким образом, за конечное число применений закона склеивания получим СКНФ.
Утверждение 2 доказывается аналогично.
Следствие. Для всякой формулы, образованных из высказывательных переменных не являющейся тождественно истинной и тождественно ложной, существуют эквивалентные им СКН-форма и СДН-форма .
Доказательство теоремы 4.3 содержит алгоритм построения совершенных нормальных форм. Для этого нужно построить соответствующую нормальную форму, а если она не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13.
Обе нормальные формы, построенные в задании 1, не являются совершенными. Приведем их к совершенному виду.
– СКН-форма.
– СДН-форма.
С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы.
Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.
Сформулируем изложенные выше утверждения для булевых функций. Для этого введем следующие обозначения .
Легко проверить, что , .
Теорема 5.4 (о разложении булевых функций). Любую булеву функцию можно представить в виде
(5.1)
где дизъюнкции берутся по всем возможным наборам ( ).
Доказательство. Покажем, что правая часть равенства (5.1) совпадает с левой на произвольном фиксированном наборе значений переменных ( ). Подставив эти значения в левую часть (5.1), получим
,
так как, если хотя бы одно из значений отличается от , то , а, следовательно, обращается в 0 и вся конъюнкция. Таким образом, отличной от 0 будет только конъюнкция на наборе ( ) = ( ), а так как , то
.
Положив в (5.1) m = n, получим
f (x1 , …, хn) = (x1 1) … (xn n) f (1 , …, n) .
1,.., n
Очевидно, среди всех дизъюнкций нужно оставить только те, в которых f (1 , …, n) = 1. Окончательно получим
(5.2)
Полученная формула разложения является совершенной дизъюнктивной нормальной формой булевой функции.
Теорема 5.5. Всякая булева функция (кроме 0) имеет единственную СДН-форму
.
С помощью принципа двойственности легко доказать представление функции СКН-формой.
Теорема 5.6. Всякая булева функция (кроме 1) имеет единственную СКН-форму
. (5.3)
Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.
Например, функция f переменных x1, x2, x3, заданная в таблице
| x1 | x2 | x3 | f |
| 0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 | 1 1 0 0 1 0 1 1 |
имеет следующие совершенные нормальные формы:
– СКН-форма;
– СДН-форма.
Упростив любую из этих формул, можно получить простейшую формулу, реализующую данную функцию.
Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Хi или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее.
В ЭВМ совершенные формы представляются в виде матрицы размера kn, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f.
Пусть х – массив пропозиционных переменных. Предположим, хi получили некоторые значения и необходимо вычислить значение нормальной формы f. Предлагаются следующие правила:
Эффективность данного алгоритма проявляется также в том, что цикл можно прервать, как только будет найдено необходимое значение i или j.
Например, вычислим значение функции f(x1, x2) = x1 x2 при x1 = 0; x2 = 1. Запишем таблицу истинности функции f:
| x1 | x2 | f |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Тогда FСДНФ = ; FСКНФ = . Поскольку ни одна из строк FСДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями хj, то f (0, 1) = 0.
Тоже самое можно определить и по СКНФ, так как первая строка FСКНФ совпадает со значениями хj, то f (0, 1) = 0.
Определение. Булеву функцию называют импликантой булевой функции , если для любых наборов значений переменных из следует .
Если функция представлена ДНФ, то любая её элементарная конъюнкция будет её импликантой.
Определение. ДНФ называется минимальной, если она содержит наименьшее число вхождений переменных среди всех ДНФ, эквивалентных ей.
Определение. Длиной ДНФ называют число входящих в неё элементарных конъюнкций. ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.
Минимальная ДНФ всегда является кратчайшей, обратное неверно.
5. Полные системы операций. Алгебра Жегалкина
Система операций называется полной, если любая логическая операция может быть представлена формулой над .
Так как всякая формула может быть представлена приведенной формулой, то система 0 = {, , } - полна.
Система сводится к *, обозначается *, если все операции системы * представимы формулами над системой . Если * полна, то и полна.
Последнее утверждение даёт один из способов доказательства полноты системы операций – сведение её к известной полной системе, например к 0. То есть полной будет система , через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.
Так в силу законов де Моргана, полными будут и системы 1 = { , } и 2 = {, }.
Алгебра над множеством логических функций с двумя операциями и называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:
, ,
, ,
а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант.
Задание. Доказать полноту системы 5 = {, }.
Решение. Сведем систему 5 к полной системе 0.
.
Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все возможные упрощения, то получится формула, имеющая вид суммы произведений, то есть полинома по mod 2. Такая формула называется полиномом Жегалкина для данной функции. Линейной называется функция, полином Жегалкина которой линеен.
Сводимость к полной системе операций является необходимым условием полноты системы операций. Необходимое и достаточное условие полноты системы операций формулируется в терминах булевых функций.
Система булевых функций F называется полной, если любая функция может быть реализована формулой над F.
Замыканием множества F (обозначается [F]) называется множество всех булевых функций, реализуемых формулами над F. Класс функций называется замкнутым, если [F] = F.
Примеры замкнутых классов.
Класс функций, сохраняющих 0.
.
Класс функций, сохраняющих 1.
.
Класс самодвойственных функций.
.
Класс монотонных функций.
, где
.
Класс линейных функций.
.
Принадлежность некоторых функций этим классам оформим в виде таблицы.
| Функция | Принадлежность классу | ||||
| T0 | T1 | T* | T | TL | |
| 0 1 | + + | + + | + | + + + | + + + |
Замкнутые классы попарно различны, не пусты и не совпадают с .
Теорема 6.1 (Поста). Система булевых функций полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую 0, хотя бы одну функцию, не сохраняющую 1, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию.
Доказательство.
Необходимость. Предположим противное, т.е. система булевых функций F полна ( [F] = ) и входит в один из замкнутых классов ( F F F F F ). Обозначим через Ti тот класс, для которого справедливо включение F . Тогда [F] = , что противоречит тому, что ни один из классов не совпадает с .
Достаточность. Пусть система булевых функций F содержит хотя бы по одной функции, не принадлежащих каждому из замкнутых классов. Т.е. F = , причем функции не обязательно различны и не обязательно исчерпывают F. Покажем, что отрицание и конъюнкция, которые образуют полную систему булевых функций, реализуются формулами над F.
1) Проведем вначале построение вспомогательных формул над F. Реализуем константы 0 и 1, которые будут использоваться в формуле для конъюнкции.
Для реализации 1 воспользуемся функцией . Обозначим . Так как , то . Если , то возможны 2 случая:
a) и тогда реализует 1;
b) . В этом случае реализует отрицание, для построения формулы 1 воспользуемся функцией . Так как она несамосопряженная, то существует набор , на котором значение функции отличается от значения двойственной функции , тогда . Рассмотрим функцию , для которой . Следовательно, является константой, если , то она реализует 1, если , то реализацией 1 будет функция .
Константа 0 строится аналогично с использованием функции .
2) Для построения формулы, реализующей функцию отрицания, воспользуемся немонотонной функцией . Так как , то , такие что . Неравенство означает, что либо соответствующие координаты векторов , совпадают, либо и . Так как , то , а, следовательно, найдутся такие индексы, что . Обозначим через I множество таких индексов. Определим функцию , где , если , и , если . Вычислим значение функции в 0 и 1: , . Так как , то , а это означает, что .
3) Для построения формулы, реализующей конъюнкцию, будем использовать нелинейную функцию . Так как , то её полином Жегалкина содержит слагаемое, являющееся конъюнкцией, по крайней мере, двух переменных. Выберем произвольное слагаемое, содержащее наименьшее число переменных пусть это . Рассмотрим функцию, полученную заменой всех переменных, не вошедших в этот набор, нулями, т.е. . Её полином Жегалкина имеет вид
. Рассмотрим функцию
, где , , . Определим функцию
,
Такое представление корректно, так как являются константами 0 или 1, определенными ранее формулами над F, а сложение по модулю 2 с константой дает либо функцию, либо её отрицание, которое также выражено формулой над F. Преобразуем , воспользовавшись представлением ,
. Таким образом, функция реализует конъюнкцию.
6. Выводимость
Пусть задано множество формул от высказывательных переменных
( ), ( ), . . . , ( ). (1)
Это множество формул назовем системой посылок.
Определение.Формула ( ) называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . , , тогда и только тогда, когда формула
(2)
является ТИ-высказыванием, т.е. .
Из определения следует, что если конъюнкция
(3)
тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула.
Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных.
Нетрудно доказать следующие свойства выводимости.
Если и то .
Если и , то .
Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием.
Теорема 7.1. Формула ( ) тогда и только тогда выводима из системы формул (1), когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) относительно высказывательных переменных .
Так как теорема 1 формулирует необходимое и достаточное условие выводимости формулы, то на основе нее можно сформулировать алгоритм доказательства выводимости формулы.
Из системы посылок (1) строится конъюнкция (3).
Находим СКН-форму от высказывательных переменных для формулы (3).
Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).
Задание 1. Доказать выводимость .
Решение.
Обозначим = X, = . Строим их конъюнкцию .
Найдем СКН-форму эквивалентную этой конъюнкции.
V
Получим СКН-форму для формулы B .
Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана.
Замечание. Выводимость формулы можно получить и без нахождения ее СКН-формы. Для этого нужно преобразовать с помощью известных эквивалентностей формулу (3) или даже конъюнкцию некоторых полных дизъюнкций из этой СКН-формы. Например, конъюнкция 1-ой и 3-ей полных дизъюнкций формулы из задания 1 преобразуется с помощью формулы склеивания к искомой формуле.
Кроме того, воспользовавшись теоремой 1, можно построить все СКН-формы выводимые из данной системы посылок. Для этого требуется небольшая модификация алгоритма доказательства выводимости формулы. После построения СКН-формы для формулы (3) необходимо
3. Из полных элементарных дизъюнкций полученной СКН-формы строим различные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из системы посылок (1).