Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

Среди множества формул, равносильных данной, выделяют формулы, имеющие ту или иную нормальные формы.

Дадим необходимые определения.


Определение. Литералом называется атомарная формула (кроме 1 и 0) или ее отрицание.

Элементарной конъюнкцией называется литерал или конъюнкция литералов.


Определение. Формула G имеет дизъюнктивную нормальную форму (сокращенно: ДНФ), если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций.

Например, формулы X,ØY,X&ØY,(X&ØY)Ú(ØX&Z) имеют ДНФ, а формулы Ø(X&Y), XÚYÚ1, X®Y не имеют.


Теорема 1.3. Для всякой формулы F существует формула G, равносильная F и имеющая дизъюнктивную нормальную форму.

Теорема легко следует из рассмотрения следующего алгоритма, который по данной формуле F выдает (одну из формул) G, удовлетворяющих условию теоремы.

Прежде, чем привести алгоритм, условимся не различать формулы, которые получаются одна из другой применением коммутативности и ассоциативности конъюнкции и дизъюнкции, т.е. законов 7-10.


Алгоритм приведения к ДНФ.

Шаг 1. Используя законы 21 и 20 исключить из исходной формулы эквиваленцию и импликацию.


Шаг 2. С помощью законов 17-19 занести отрицание к атомарным формулам.


Шаг 3. Если формула содержит подформулу вида

H1&(H2ÚH3),

то заменить ее на равносильную формулу

(H1&H2)Ú(H1&H3).


Применение алгоритма проиллюстрируем на примере формулы

F=Ø(X«Y)&X.


Выполним первый шаг. Для этого, используя закон 21, заменим X«Y равносильной ей формулой (X®Y)&(Y®X). Затем в полученной формуле с помощью закона 20 исключим связку ®. Мы получим формулу

F1=Ø[(ØXÚY)&(ØYÚX)]&X.


Перейдем ко второму шагу. Применение закона 17, приведет к формуле

F2=[Ø(ØXÚY)ÚØ(ØYÚX)]&X.


Затем дважды воспользуемся законом 18 и снимем двойное отрицание (закон 19), получим формулу

F3=[(X&ØY)Ú(Y&ØX)]&X.


Шаг 2 выполнен.


Выполнение шага 3 состоит из применения дистрибутивности к формуле F3. Это дает нам формулу

F4=(X&ØY&X)Ú(Y&ØX&X).


Алгоритм на этом завершен. Формула F4 имеет дизъюнктивную нормальную форму. Но эту формулу можно упростить. Действительно, формула Y&ØX&X в силу законов 15 и 3 равносильна 0, а формула X&ØY&X равносильна X&ØY (закон 5). Следовательно, формула F4 равносильна формуле

F5=X&ØY.

Формула F5, как и F4, имеет ДНФ и равносильна исходной формуле F.

Рассмотренный пример показывает, что формула F может иметь не одну равносильную формулу, именющую ДНФ. Иногда это обстоятельство является неудобным. Чтобы его исключить, вводится более узкое понятие, нежели ДНФ.


Определение. Формула G имеет совершенную дизъюнктивную нормальную форму (сокращенно: СДНФ) относительно атомарных формул X1,…,Xn, если выполнены следующие условия:

1) F=F(X1,…,Xn), т.е. в записи формулы участвуют только X1,…,Xn;

2) F имеет дизъюнктивную нормальную форму, т.е. F=C1ÚC2ÚÚCk, где C1,…,Ck – элементарные конъюнкции;

3) каждая элементарная конъюнкция содержит один и только один из литералов Xi или ØXi для любого i=1,…,n;

4) F не содержит одинаковых элементарных конъюнкций.

Например формулы X, ØX&Y, (ØX&Y)Ú(X&ØY) имеют СДНФ относительно содержащихся в них атомарных формул. Формулы Ø(X&Y), (X&Y)Ú(ØX&Z), (X&Y&X)&(ØX&ØY), (X&Y)Ú(X&ØY)&(Y&X) не имеют СДНФ (относительно содержащихся в них атомарных формул). Для первой формулы не выполняется второе условие, для второй и третьей – третье условие, для четвертой формулы не выполняется последнее условие из определения СДНФ.


Теорема 1.4. Для любой выполнимой формулы F существует равносильная ей формула G, имеющая совершенную дизъюнктивную нормальную форму.

Как и теорема 1.3, эта теорема легко следует из соответствующего алгоритма, который по формуле F выдает формулу G, удовлетворяющую условию теоремы 1.4.


Алгоритм приведения к СДНФ.

Шаг 1 – Шаг 3 – те же, что и в алгоритме приведения к ДНФ.


Шаг 4. Если элементарная конъюнкция С не содержит атомарной формулы Xi, ни ее отрицания для некоторого i=1,…,n, то заменить C на две элементарные конъюнкции (C&X)Ú(C&ØXi).

Шаг 5. Если элементарная конъюнкция C содержит два вхождения одного литерала, то одно из них вычеркнуть. Если же С содержит Xi и ØXi для некоторого i=1,…,n, то вычеркнуть всю элементарную конъюнкцию.


Шаг 6. Если формула содержит одинаковые элементарные конъюнкции, то вычеркнуть одну из них.

Напомним, что «одинаковость» понимается с точностью до коммутативности и ассоциативности конъюнкции и дизъюнкции.

В качестве примера рассмотрим ту же формулу F=Ø(X«Y)&X, что и в примере на предыдущий алгоритм. Как мы видели, выполнение шагов 1-3 приводит к формуле F4. Эта формула имеет ДНФ, но не имеет СДНФ, поскольку для нее не выполняется третье условие. Если для F4 выполнить шаг 4, то в первой элементарной конъюнкции будет зачеркнуто одно из вхождений литерала X, а вторая элементарная конъюнкция будет вычеркнута вся. В результате мы получим формулу F5. Она имеет СДНФ относительно X и Y.

Рассмотрим второй пример. Пусть G=(X&Y)Ú(X&ØZ). Эта формула имеет ДНФ, поэтому выполнение алгоритма приведения к СДНФ начинается с шага 4. При выполнении этого шага элементарная конъюнкция X&Y будет заменена на (X&Y&Z)Ú(X&Y&ØZ), а X&ØZ – на (X&ØZ&Y)Ú(X&ØZ&ØY). В результате получим формулу

G1=(X&Y&Z)Ú(X&Y&ØZ)Ú(X&ØZ&Y)Ú(X&ØZ&ØY).

Условия шага 5 для формулы G1 ложны, поэтому этот шаг формулы G1 не имеет. Формула G1 содержит одинаковые элементарные конъюнкции – вторую и третью. При выполнении шестого шага будет зачеркнута одна из них и получится формула

G2=(X&Y&Z)Ú(X&Y&ØZ)Ú(X&ØY&ØZ).

Это и есть формула, равносильная G и имеющая СДНФ относительно входящих в G атомарных формул.

Ответим на естественно возникающий вопрос о том, зачем в формулировке теоремы 1.4 требуется выполнимость формулы F? Нетрудно доказать, что если формула F невыполнима, т.е. при любой интерпретации j выполняется равенство j(F)=0, то после приведения F к ДНФ каждая элементарная конъюнкция будет содержать хотя бы одну пару противоположных литералов X и ØX. Но в таком случае на шаге 5 все элементарные конъюнкции будут вычеркнуты.

Имеется еще один способ приведения к СДНФ, основанный на построении таблицы истинности исходной формулы. Изложим этот способ на примере формулы

F=X1&(X2®X3)


составим таблицу истинности формулы F (таблицу 1.5).

Таблица 1.5

X1 X2 X3 X2®X3 F=X1&(X2®X3)
1 1 1 1 1
1 1 0 0 0
1 0 1 1 1
1 0 0 1 1
0 1 1 1 0
0 1 0 0 0
0 0 1 1 0
0 0 0 1 0

Выделим строки, в которых в столбце F стоит 1. (Хотя бы одна такая строка должна быть, так как формула F выполнима.) Это будут первая, третья и четвертая строки. Каждой из выделенных строк поставим в соответствие элементарную конъюнкцию X1a1X2aaX3a3, где Xiai=Xi, если в столбце Xi этой строки стоит 1, и Xiai=ØXi, если в столбце Xi этой строки стоит 0, где i=1,2,3. Так, первой строке будет поставлена в соответствие элементарная конъюнкция X1&X2&X3, третьей – X1&ØX2&X3, четвертой – X1&ØX2&ØX3. Формула

G=(X1&X2&X3)Ú(X1&ØX2&X3)Ú(X1&ØX2&ØX3)

имеет СДНФ относительно X1,X2,X3. В то же время G имеет ту же таблицу истинности, что и F. Это означает, что G равносильна F. Следовательно, G – искомая формула.

Из других нормальных форм рассмотрим конъюнктивную нормальную форму. Она получается из ДНФ заменой & на Ú и Ú на &. Дадим точные определения.


Определение. Элементарной дизъюнкцией (или дизъюнктом) называется литерал или дизъюнкция литералов.


Определение. Формула G имеет конъюнктивную нормальную форму (сокращенно: КНФ)Б если она является элементарной дизъюнкцией или конъюнкцией элементарных дизъюнкций.

Например, формулы X,ØY, XÚØY, X&ØY, (XÚØY)&(XÚZ) имеют КНФ, а формулы X®Y, Ø(XÚY), (X&ØY)Ú(X&ØZ) не имеют.

Для конъюнктивных нормальных форм справедливо утверждение, аналогичное теореме 1.3.


Теорема 1.5 Для всякой формулы F существует формула G равносильная F и имеющая конъюнктивную нормальную форму.


Доказательство теоремы легко следует из анализа алгоритма приведения к КНФ, который в свою очередь получается из алгоритма приведения к ДНФ, если шаг 3 заменить на


Шаг 3/. Если формула содержит подформулу вида

H1Ú(H2&H3),

то заменить ее на равносильную ей формулу

(H1ÚH2)&(H1ÚH3).


В силу очевидной аналогии между ДНФ и КНФ примеров приведения к КНФ здесь приводить не будем.

§6. Контактные схемы.

Задачи

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru