Студопедия
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Раздел 5. Теория алгоритмов.

Читайте также:
  1. A. Раздел специальной психологии, изучающей психическое развитие у умственно отсталых людей и возможности его коррекции.
  2. A. теория познания
  3. I БӨЛІМ. КЛАССИКАЛЫҚ ЭКОНОМИКАЛЫҚ ТЕОРИЯНЫҢ НЕГІЗДЕРІ
  4. I раздел.
  5. I Раздел. Определение провозной способности судна.
  6. I. Общая теория статистики
  7. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  8. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  9. I. Организационно - методический раздел
  10. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  1. Примитивно рекурсивные функции. Примеры.
  2. Частично рекурсивные функции. Примеры.
  3. Алгоритмические проблемы. Тезисы Черча и Тьюринга.
  4. Машина Поста.
  5. Машина Тьюринга.

 


ЛИТЕРАТУРА

1. Лихтарникова Л.М.,Сукачева Т.Г. Математическая логика. Курс лекций.

Задачник-практикум и решения. Санкт-Петербург,1999, 288 стр.

2. Гиндикин С.Г. Алгебра логики в задачах. Москва, 1972, 288 стр.

3. Нефедов В.Н., Осипова В.А. Курс дискретной математики, 264 стр. Изд-во МАИ, Москва, 1992

4. Лихтарникова Л.М., Сукачева Т.Г. Математическая логика, 299 стр. СПб,

Изд-во “Лань”,1999

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 255 стр. Издательская фирма “физ.-мат. литература, Москва, 1995

6. Дискретная математика и математические вопросы кибернетики. Под ред.

Яблонского С.В. и Лупанова О.Б., 312 стр. Изд.-во “Наука”, Москва, 1974.

7. Ю.Л. Ершов Математическая логика, М: Наука, 1987.

8. Н.К. Верещагин, А.Шень Лекции по математической логике и теории алгоритмов, часть 1, М: МЦНМО, 1999.

9. Н.К. Верещагин, А.Шень Лекции по математической логике и теории алгоритмов. Языки и исчисления, М: МЦНМО, 2000.

10. Н.К. Верещагин, А.Шень Лекции по математической логике и теории алгоритмов. Вычислимые функции, М: МЦНМО, 1999.

11. А.И. Мальцев Алгоритмы и рекурсивные функции, М.:Наука1986

12. В. Н. Пушкин. Математическая логика и теория алгоритмов часть 1 Ухта УГТУ 2010

 


 

.РЕШЕНИЕ ТИПОВЫХ ПРИМЕРОВ.

 

В этом разделе мы приведем некоторые полезные комментарии к типовым задачам.

 

1. Рассмотрим типовой пример задач 1 - 20. Пусть f(x) - произвольная фиксированная функция, и пусть имеет смысл . Рассмотрим следующие предикаты: Р (х, d): | х - а |< d, Q (x, e): | f(x) - A | < e, R (e): e > 0.

Тогда утверждение о том, что число А - предел функции f(x) при х ® а, записывается формулой:

(" e)($ d)(" х)((R (e) × Р (х, d)) Þ Q (х, e)). (1)

б) Выражение ¹ А является отрицанием формулы (1), т. е. может быть записано в виде

ù ((" e)($ d)(" х)((R (e) × Р (х, d)) Þ Q (х, e))). (2)

Найдём приведённую нормальную формулу, равносильную (2). Проводя отрицание через кванторы, получим:

($ e)(" d)($ х)ù ((R (e) × Р (х, d)) Þ Q (х, e))).

Выражая импликацию через дизъюнкцию и отрицание, получим:

($ e)(" d)($ х)ù (ù(R (e) × Р (х, d)) Ú Q (х, e))).

Применяя правило де Моргана, окончательно получим:

($ e)(" d)($ х)(R (e) × Р (х, d) × ù Q (х, e)). (3)

Это и есть приведённая нормальная формула для формулы (2).

Словесное выражение формулы (3) таково: ¹ А означает, что существует такое e > 0, что для любого d > 0 существует х из области

| х - а |< d, для которого | f(x) - A | ³ e.

 

2. Разберем теперь пример решения задач типа 21-40.

Напомним сначала, что область действия квантора (если нет дополни-тельных скобок) - это ближайший предикат, содержащий переменную, стоящую под знаком квантора. Поэтому связанную переменную необходимо переименовывать, если ее обозначение совпадает с обозначением другой свободной или связанной переменной, стоящей вне области действия первого квантора. Вообще при решении этих задач используются действия с кванторами - главные из которых

а) при переносе квантора через отрицание - квантор меняет свой смысл и

б) в конъюнкции (дизъюнкции) двух выражений квантор, стоящий перед одним из них можно выносить за скобки, если в другое выражение не входит эта связанная переменная.

 

Пример. Пусть имеется формула:

($ х) А(х,у) Þ ù (" х) В(х) (1)

Здесь буквой х обозначены две связанные переменные с разной областью действия кванторов. Поэтому одну из них надо переименовать и обозначить, например, буквой z. Получим формулу (равносильную (1)):

($ х) А(х,у) Þ ù (" z) В(z) (2)

Здесь x и z - связанные переменные, а у - свободная.

Длина формулы (2) (также как и формулы (1)) равна общему числу символов предикатов, кванторов и логических символов и значит равна 5.

Теперь найдем приведенную нормальную формулу, равносильную

формуле (2). Для этого“убираем” символ Þ, исходя из равенства

(А Þ В)º (ù А Ú В);

поэтому (2) равносильна формуле

ù ($ х) А (х, у) Ú ù (" z) B (z). (3)

Теперь, чтобы формула (3) стала приведённой, нужно, чтобы отрицания встали непосредственно перед значениями предикатов. Так как перенос квантора через отрицание означает перемену квантора, получаем:

(" х)(ù А (х, у)) Ú ($ z)(ù B (z)). (4)

Теперь формула (4) является приведённой. Для того, чтобы она стала нормальной, нужно, чтобы кванторы стояли в её начале. Так как от связанной переменной х переменная z не зависит, то получаем:

(" х)($ z)(ù А (х, у)) Ú ù B (z)). (5)

Формула (5) является приведённой нормальной; её длина равна 6.

б) Ясно, что формула (5), так же как и (1), является выполнимой (в данной интерпретации: А (х, у) - “ у = 2 х ”, В (х) - “ х чётно”). Более того, формула (5), а значит, и формула (1), тождественно истинны в этой интерпретации, так как $ z такое, что В (z) ложно (независимо от А (х, у)).

Например, можно взять z = 3.

Заметим, что при решении задач, где есть символ эквивалентности ~, обычно используется равенство:

(А ~ В) º (А × В)Ú(ù А × ù В).

 

3). В задачах 41-60 требуется, используя правила де Моргана привести к ДНФ выражение, содержащее конъюнкции, дизъюнкции и отрицания и, затем, сократить ДНФ, если это возможно. Для этих задач есть точный алгоритм решения: мы “понижаем” отрицания по правилам де Моргана до тех пор пока они не окажутся над одной переменной. После этого раскрываем скобки (используя естественные свойства конъюнкций, дизъюнкций и отрицаний а также поглощение) и затем уже сокращаем ДНФ по правилу Блейка.

Заметим, что часто в наших примерах приходится раскрывать скобки вида

(х Ú у Ú z) (x Ú u). Здесь необходимо учитывать, что дизъюнктные слагаемые, содержащие х поглощаются слагаемым х. Поэтому, после раскрытия скобок получится

выражение x Ú yu Ú zu.

Пример Привести выражение L к ДНФ, а затем сократить ее (если это возможно).

 

Решение:

Далее, раскрываем скобки (мы видим, что удобнее сначала раскрать произведение второй

и третьей скобки. Поэтому получаем . По правилу Блейка

(так как имеются дизъюнктные слагаемые, содержащие у и ) к последнему выражению можно добавить слагаемое z, котороепоглотит второе слагаемое в L.

Таким образом: .

 

4).задачи 61-80

Пример а) Дана ДНФ . Требуется для этой функции найти полином Жегалкина и перейти от ДНФ к КНФ, а затем и к СКНФ. Сначала найдем полином Жегалкина (вторым способом). Для этого по правилам де Моргана “убираем” дизъюнкцию, а потом “убираем” отрицания по правилу . После этого раскравем скобки, учитывая при этом, что четное число слагаемых (по модулю 2) равно 0, а нечетное - одному такому слагаемому. Тогда

= ((x+ 1)(y +1)+1)(xy (z +1)+1)+1=(xy+x+y+ 1+1)(xyz+xy+ 1)+1=

= (xy+x+y)(xyz+xy+ 1)+1= yz + xyz + xyz + xy+xy+ xy+x+ = xyz+x+y+ 1.

Последнее выражение и является полиномом Жегалкина.

Для того, чтобы перейти к КНФ для выражения L (в соответствии со сказанным в п.3) мы опять ставим над L два отрицания и, оставляя временно верхнееотрицание

безизменения, приводим оставшееся выражение к ДНФ. Затем, по правилу де Моргана, получаем КНФ. Таким образом, мы можем получить

Далее, заметим что по правилу Блейка мы можем из последнего выражения исключить

yz. Тогда получим: . Это и есть КНФ.

Чтобы из последнего выражения получит СКНФ нужно в первой и второй дизъюнкции добавить , а в третьей .Затем нужно воспользоваться распределительным законом. Тогда получим

 

Последнее выражение и есть СКНФ.

 

Пример б).Пусть имеется выражение . Требуется записать

L в виде ДНФ, а затем перейти к СДНФ.

Ясно, что ДНФ можно получить простым раскрытием скобок. Так как в обоих скобках есть , которое поглощает слагаемые, содержащие то . Это и есть ДНФ. Для того чтобы получить СДНФ мы умножаем на , а

умножаем на и раскрываем скобки.Тогда

 

 

Заметим, что мы с самого начала позаботились о правильном порядке переменных, что требуется для СДНФ. Однако последнее выражение еще не является СДНФ, так как содержит два одинаковых слагаемых. После уничтожения одного из них мы получим нужное выражение. Окончательный ответ:

 

.

5). В задачах 101 - 120 требуется по карте Карно для функции 4-х переменных составить сокращённую ДНФ. Надо иметь в виду, что карты Карно соединяются по кругу. Число единиц, которые мы можем объединять, равно 2, 4, 8, … (прямая, плоскость и т. д.)

Пример.

х1 , х2 х3 , х4   00 01 11 10
00 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 1

 

Получаем всего 4 объединения, т. е. 4 конъюнкции в ДНФ:

.

Заметим, что при правильно составленном объединении единиц правило Блейка может привести только к ДНФ с тем же числом символов переменных (в нашем примере их 11).

 

 

6). Задачи типа 101-120

 




Дата добавления: 2015-01-12; просмотров: 95 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2025 год. (0.013 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав