авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

УДК 002;

004.3(075.8)

МИНОБРНАУКИ РОССИИ ББК 32.81;

32.97я73

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

У 91

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА»

(ФГБОУ ВПО «ПВГУС»)

Кафедра «Информационный и электронный сервис»

Рецензент д.т.н., проф. Иванов В. В.

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине «Алгоритмы построения функциональных структур»

для студентов направления 230100.68 «Информатика и вычислительная техника»

Учебно-методический комплекс по дисциплине «Алгоритмы У 91 построения функциональных структур» / сост. В. И. Воловач, М. В. Шакурский. – Тольятти : Изд-во ПВГУС, 2012. – 160 с.

Для студентов направления 230100.68 «Информатика и вы Одобрено числительная техника». УМК разработан в соответствии с требо Учебно-методическим ваниями ФГОС направления подготовки магистратуры 230100. Советом университета «Информатика и вычислительная техника»

Научно-техническим Советом университета Составители: Воловач В. И., Шакурский М. В.

© Воловач В. И., Шакурский М. В., составление, © Поволжский государственный университет сервиса, Тольятти СОДЕРЖАНИЕ 1. Рабочая учебная программа дисциплины………………………………………...

1.1. Цели и задачи дисциплины………………………………...…………………….

1.2. Структура и объем дисциплина…....…………………………………………… 1.3. Содержание дисциплины…………………………...…………………………… 1.4. Требования к уровню освоения дисциплины и формы текущего и промежу- точного контроля…………………………………………………………………………… 1.5. Содержание самостоятельной работы………………………..………………… 2. Учебно-методическое пособие……………………………………..………………......

2.1. Теоретические сведения...………………...……..……………………………… 2.1.1. Теория дискретных структур. Логика высказываний………………………..

2.1.2. Булевы функции……………………………………………………………….. 2.1.3. Формальные языки. Комбинаторика…………………………………………. 2.1.4. Теория графов…………..……………………………………………………… 2.1.5. Логика предикатов. Методы доказательств………………………………….. 2.1.6. Множества и отношения…………………………………….………………… 2.2. Руководство по практическим занятиям………………………………………..

2.2.1. Распознавание типов формальных языков и грамматик…………………….

2.2.2. Построение конечного автомата по регулярной грамматике...……………..

2.2.3. Минимизация конечных автоматов…………………………………………...

2.2.4. Эквивалентные преобразования контекстно-свободных грамматик……….

2.2.5. Построение автомата с магазинной памятью по контекстно-свободной грамматике…………………………………………………………………………………...

2.2.6. Моделирование функционирования распознавателя LL(1)-грамматик…….

2.2.7. Моделирование функционирования распознавателя для грамматик про- стого предшествования……………………………………………………………………..

3. Учебно-методическое обеспечение дисциплины...………………………...………..

3.1. Перечень основной и дополнительной литературы…………………………… 3.2. Методические рекомендации преподавателю………………………………….

3.3. Методические указания студентам по изучению дисциплины……………….

3.4. Учебно-методическая карта дисциплины……………………………………… 3.5. Материально-техническое обеспечение дисциплины………………………… 3.6. Программное обеспечение использования современных информационно- коммуникативных технологий………………………………..…………………………… 3.7. Технологическая карта дисциплины…………………………………………… Приложения……………………………...…………………………………………………..

1. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ 1.1. Цели и задачи дисциплины Цель преподавания дисциплины «Алгоритмы построения функциональных структур»

состоит в изучении и применении в практической деятельности фундаментальных понятий, методов и алгоритмов дискретной математики, составляющих теоретический и методиче ский базис информационных технологий, изучении типовых логических элементов ЭВМ, реализующих названные методы и алгоритмы, а также применение методов моделирования для анализа и оптимизации проектных решений.

В результате освоения содержания дисциплины «Алгоритмы построения функциональ ных структур» в соответствии с требованиями Государственного образовательного стандарта в части содержания аннотированной магистерской программы 230106 «Элементы и устрой ства вычислительной техники и информационных систем» направления 230100.68 «Инфор матика и вычислительная техника» студент должен знать: цифровые автоматы, представляе мые как математические модели дискретных систем;

связь автоматов с формальными языка ми и грамматиками;

способы задания и принципы построения цифровых автоматов, а также методы и средства их разработки;

алгоритмические основы построения функциональных структур;

теорию дискретных структур;

методы анализа и оптимизации проектных решений;

применение методов моделирования для их описания.

В результате изучения дисциплины «Алгоритмы построения функциональных струк тур» студент должен знать: о представлении информации логическими сигналами;

последо вательном и параллельном импульсном и потенциальном кодах;

о системах логических эле ментов и о построении функциональных структур с использованием логических элементов и типовых узлов;

теорию дискретных структур;

логику высказываний;

булевы функции;

логи ку предикатов;

формальные языки и комбинаторику;

методы анализа и оптимизации проект ных решений;

применение методов моделирования.

Создание современных автоматизированных средств и систем управления основывается на следующих двух научных направлениях: теории преобразования информации и теории построения различного рода преобразователей информации.

Первое направление включает в себя общую теорию алгоритмов, абстрактную теорию автоматов. В нем рассматриваются общие вопросы формализации процессов обработки информации.

Второе направление включает в себя элементы математической логики, структурную теорию автоматов. В нем рассматриваются принципы и методы построения автоматов, которые реализуют алгоритмы обработки информации, полученные на этапе абстрактного синтеза автоматов.

Для изучения дисциплины необходимы знания по следующим дисциплинам: «Схемо техника ЭВМ»;

«Сигналы, алгоритмы и устройства вычислительной техники и информаци онных систем»;

«Компьютерные технологии в науке и образовании».

Полученные в ходе изучения дисциплины знания используются в следующих дисцип линах: «Микропроцессорные системы», «Интеллектуальные системы», а также в ходе подго товки магистерской диссертации.

Компетенции обучающегося, формируемые в результате освоения дисциплины:

В результате освоения дисциплины обучающийся должен:

знать: методы оптимизации и принятия проектных решений (ПК-1);

уметь: разрабатывать математические модели процессов и объектов, методы их исследо вания, выполнять их сравнительный анализ (ПК-1);

владеть: методами научного поиска (ПК-1).

1.2. Структура и объем дисциплины Распределение фонда времени по семестрам, неделям, видам занятий № Количество часов по плану Количество часов в неделю Самостоятельная семе- работа недель Число стра всего лекции практ. лабор. всего лекции практ. лабор. часов часов занят. занят. занят. занят. всего в неделю очное отделение 1 72 16 20 1 17 - 2 1 - 1.3. Содержание дисциплины Распределение фонда времени по темам и видам занятий Аудиторные занятия Самост. работа Лабораторные Практические Всего № Наименование разделов по темам Лекции 2 1. 12 Цифровой автомат.

Представление информации логическими сигналами;

по следовательный и параллельный импульсный и потенциаль ный коды. Понятие о комбинационной схеме и цифровом ав томате. Основы теории формальных грамматик. Структурная схема цифрового автомата. Машины Тьюринга. Абстрактный конечный автомат. Автоматы Мили и автоматы Мура. Струк турный конечный автомат. Комбинационные логические эле менты. Функциональная полнота при построении цифрового автомата. Элементы с выходами с тремя состояниями. Мик ропрограммирование. Проблемы отображения времени при программировании. Сети Петри.

1 2. Логические элементы и типовые узлы.

Системы логических элементов. Триггеры;

синхронные и асинхронные триггеры. Т-триггер;

D-триггер;

JK-триггер. Ре гистры;

прием информации в регистр в парафазном коде;

пе редача слова из одного регистра в другой;

сдвигающий ре гистр. Счетчики;

несинхронизируемый двоичный счетчик с последовательным переносом;

синхронизируемый двоичный счетчик с параллельным переносом. Дешифраторы;

дешифра тор с инверсными выходами;

каскадный дешифратор. Муль типлексоры. Сумматоры;

комбинационный одноразрядный сумматор;

сумматор с параллельным переносом;

сумматор с групповым переносом.

Построение функциональных структур с использованием логических элементов и типовых узлов.

1 2 3. Теория дискретных структур. Логика высказываний.

Высказывание;

связки;

истинность;

тавтология и противо речие;

эквивалентность пропозициональных форм;

законы де Моргана;

полные системы связок. Понятие исчисления выска зываний;

понятие формальной аксиоматической теории;

логи ческий вывод, аксиомы и правила вывода.

4. 2 4 Булевы функции.

Высказывание;

логические операции. Построение таблиц истинности. Функция, порождаемая пропозициональной фор мой;

построение формы, порождающей заданную функцию.

Упрощения в записях пропозитарных форм. Пары равносиль ных пропозитарных форм. Нормальны формы. Совершенные нормальные формы. Понятие булевой алгебры, примеры.

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

5. 2 8 Формальные языки. Комбинаторика.

Основные понятия и определения формальной грамматики и языка. Классификация формальных грамматик;

классифика ция грамматик и языков по Хомскому;

соотношения между типами грамматик;

соотношения между типами языков. При меры грамматик и языков. Конечный автомат и регулярные языки. Недетерминированные конечные автоматы и опреде ляемые ими языки.

Размещения, перестановки, сочетания, сочетания с повто рениями. Бином Ньютона.

6. 2 4 Теория графов.

Граф и его разновидности. Ориентированные / неориенти рованные графы, подграфы, степень вершины, теоремы о сумме степеней и о количестве нечетных вершин в графе. Пу ти, цепи и контуры: эйлеровы и гамильтоновы контуры – тео ремы и следствия существования в ориентированных и неори ентированных графах. Маршруты, циклы, связность графов.

Представление графов с помощью матриц инцидентности.

Теорема о степени матрицы инцидентности.

7. 2 4 Логика предикатов. Методы доказательств.

Общие сведения и определения. Логические операции над предикатами. Высказывания с кванторами;

квантор всеобщ ности;

квантор существования;

истинность;

отрицание выска зываний с кванторами. Численные кванторы. Понятие исчис ления предикатов (понятие формальной аксиоматической тео рии;

логический вывод, аксиомы и правила вывода). Значение формулы логики предикатов. Равносильные формулы логики предикатов. Законы логических операций. Нормальные фор мы формул логики предикатов. Общезначимость и выполни мость формул;

проблема разрешимости. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.

Структура формальных доказательств. Прямое доказатель ство. Доказательство с помощью контрпримеров. Доказатель ство от противного. Доказательство посредством контрапози ции. Математическая индукция. Использование принципа ма тематической индукции.

8. Множества и отношения.

Множество натуральных чисел;

конечные и бесконечные множества. Мощность множества. Принадлежность, включе ние, равенство, операции над множествами, тождества, зако ны де Моргана. Диаграммы Эйлера-Венна. Отношения, би нарные отношения. Отношение эквивалентности на множест ве. Порождаемое им разбиение на смежные классы, их свой ства. Отношение порядка.

9. Деревья.

Определения, каркасы и свойства. Графы с весами. Алго ритм построения каркаса минимального веса (алгоритм Kruskal’а). Бинарные деревья, полные бинарные деревья и их свойства. Организация хранения упорядоченных данных в ви де бинарного дерева. Алгоритмы поиска, вставки и удаления узлов в деревьях. Определение, преимущества организации хранения упорядоченных данных в виде бинарного сбаланси рованного дерева. Алгоритм балансировки.

10. Методы анализа и оптимизации проектных решений.

Применение методов моделирования.

Основные понятия методов анализа и оптимизации про ектных решений. Методология анализа проектных решений;

математические модели. Методика проведения анализа;

мето дика оптимизации;

адекватность математической модели;

концептуальные модели. Программные средства для решения задач анализа оптимизации;

использование экспертных сис тем. Применение методов моделирования для анализа и опти мизации проектных решений. Статистическое моделирование на ЭВМ. Оценка точности и достоверности результатов моде лирования через языки и системы моделирования. Инстру ментальные средства реализации моделей. Анализ и интер претация результатов моделирования на ЭВМ.

16 20 36 Итого 1.4. Требования к уровню освоения дисциплины и формы текущего и промежуточного контроля Текущий и промежуточный контроль знаний осуществляется путем проведения тести рований, контрольных работ, отчетов по выполненным практическим работам. В связи с этим, для успешного освоения дисциплины студентам необходимо:

– регулярно посещать лекционные занятия;

– осуществлять регулярное и глубокое изучение лекционного материала, учебников и учебных пособий по дисциплине;

– активно работать на практических занятиях;

– выступать с сообщениями по самостоятельно изученному материалу;

– участвовать с докладами на студенческой научной конференции.

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

Промежуточный контроль знаний студентов осуществляется в форме межсессионной аттестации. Межсессионная аттестация проводится в сроки и в соответствии с требованиями действующего Положения о проведении межсессионной аттестации в Университете.

Уровень знаний оценивается баллами, набранными студентами в контрольных точках.

Балльная оценка соответствующих контрольных точек приводится далее (п. 3.7) в техноло гической карте дисциплины.

Итоговый контроль знаний по дисциплине проводится в форме письменного зачета.

Для подготовки к зачету студенты используют приводимый ниже перечень вопросов для подготовки к зачету, который соответствует содержанию ГОС дисциплины. Вместе с тем, конкретная формулировка вопросов зачета, не выходя за пределы изученных на аудиторных занятиях и в ходе самостоятельной работы материалов, может отличаться от представленно го перечня.

Примерный перечень вопросов для подготовки к зачету по дисциплине «Алгоритмы построения функциональных структур»

1. Представление информации логическими сигналами;

последовательный и парал лельный импульсный и потенциальный коды.

2. Понятие о комбинационной схеме и цифровом автомате.

3. Основы теории формальных грамматик.

4. Структурная схема цифрового автомата.

5. Машины Тьюринга.

6. Абстрактный конечный автомат.

7. Автоматы Мили и автоматы Мура.

8. Структурный конечный автомат.

9. Комбинационные логические элементы.

10. Функциональная полнота при построении цифрового автомата.

11. Элементы с выходами с тремя состояниями.

12. Микропрограммирование.

13. Проблемы отображения времени при программировании.

14. Сети Петри.

15. Системы логических элементов.

16. Триггеры;

синхронные и асинхронные триггеры. Т-триггер;

D-триггер;

JK-триггер.

17. Регистры;

прием информации в регистр в парафазном коде;

передача слова из одно го регистра в другой;

сдвигающий регистр.

18. Счетчики;

несинхронизируемый двоичный счетчик с последовательным переносом;

синхронизируемый двоичный счетчик с параллельным переносом.

19. Дешифраторы;

дешифратор с инверсными выходами;

каскадный дешифратор.

20. Мультиплексоры.

21. Сумматоры;

комбинационный одноразрядный сумматор.

22. Сумматор с параллельным переносом;

сумматор с групповым переносом.

23. Построение функциональных структур с использованием логических элементов и типовых узлов.

24. Высказывание;

связки;

истинность;

тавтология и противоречие;

эквивалентность пропозициональных форм.

25. Законы де Моргана. Полные системы связок.

26. Понятие исчисления высказываний. Понятие формальной аксиоматической теории.

27. Логический вывод, аксиомы и правила вывода.

28. Высказывание. Логические операции.

29. Построение таблиц истинности.

30. Функция, порождаемая пропозициональной формой;

построение формы, порож дающей заданную функцию.

31. Упрощения в записях пропозитарных форм.

32. Пары равносильных пропозитарных форм.

33. Нормальны формы. Совершенные нормальные формы.

34. Понятие булевой алгебры, примеры.

35. Приложение алгебры высказываний к анализу и синтезу контактных (переключа тельных) схем.

36. Цифровые логические схемы (типы вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы).

37. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов.

38. Основные понятия и определения формальной грамматики и языка.

39. Классификация формальных грамматик;

классификация грамматик и языков по Хомскому;

соотношения между типами грамматик;

соотношения между типами языков.

40. Примеры грамматик и языков.

41. Конечный автомат и регулярные языки.

42. Недетерминированные конечные автоматы и определяемые ими языки.

43. Размещения, перестановки, сочетания, сочетания с повторениями.

44. Бином Ньютона.

45. Граф и его разновидности. Ориентированные / неориентированные графы, подгра фы, степень вершины, теоремы о сумме степеней и о количестве нечетных вершин в графе.

46. Пути, цепи и контуры: эйлеровы и гамильтоновы контуры – теоремы и следствия существования в ориентированных и неориентированных графах.

47. Маршруты, циклы, связность графов.

48. Представление графов с помощью матриц инцидентности. Теорема о степени мат рицы инцидентности.

49. Логические операции над предикатами.

50. Высказывания с кванторами;

квантор всеобщности;

квантор существования;

истин ность;

отрицание высказываний с кванторами.

51. Численные кванторы.

52. Понятие исчисления предикатов (понятие формальной аксиоматической теории;

ло гический вывод, аксиомы и правила вывода).

53. Значение формулы логики предикатов. Равносильные формулы логики предикатов.

54. Законы логических операций. Нормальные формы формул логики предикатов.

55. Общезначимость и выполнимость формул;

проблема разрешимости.

56. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.

57. Структура формальных доказательств. Прямое доказательство.

58. Доказательство с помощью контрпримеров. Доказательство от противного.

59. Доказательство посредством контрапозиции.

60. Математическая индукция. Использование принципа математической индукции.

61. Множество натуральных чисел;

конечные и бесконечные множества. Мощность множества.

62. Принадлежность, включение, равенство, операции над множествами, тождества, за коны де Моргана. Диаграммы Эйлера-Венна.

63. Отношения, бинарные отношения.

64. Отношение эквивалентности на множестве. Порождаемое им разбиение на смежные классы, их свойства.

65. Отношение порядка.

66. Определения, каркасы и свойства графов. Графы с весами.

67. Алгоритм построения каркаса минимального веса (алгоритм Kruskal’а).

68. Бинарные деревья, полные бинарные деревья и их свойства.

69. Организация хранения упорядоченных данных в виде бинарного дерева.

70. Алгоритмы поиска, вставки и удаления узлов в деревьях.

71. Определение, преимущества организации хранения упорядоченных данных в виде бинарного сбалансированного дерева. Алгоритм балансировки.

72. Основные понятия методов анализа и оптимизации проектных решений. Методоло гия анализа проектных решений;

математические модели.

По результатам проведенного зачета выставляется оценка:

«зачтено» – студентам, владеющим знаниями по основным и дополнительным вопро сам дисциплины, активно работающим на практических занятиях, выполняющим различные индивидуальные задания, в достаточной мере разбирающимся в знаниях, полученных в ходе самостоятельной работы (51 баллов и выше);

«незачтено» – студентам, не посещающим аудиторные занятия без уважительной при чины, не владеющим основными вопросами изучаемой дисциплины, выполняющим практи ческие работы на низком уровне, слабо разбирающихся в вопросах, вынесенных на само стоятельное изучение (менее 50 баллов).

1.5. Содержание самостоятельной работы В разделе «Самостоятельная работа» раскрывается содержание каждого вида самостоя тельной работы и указывается время, необходимое для его выполнения.

Распределение самостоятельной работы студентов по темам с указанием времени № Наименование темы Коли п/п чество часов 1 Цифровой автомат. 2 Логические элементы и типовые узлы. 3 Теория дискретных структур. Логика высказываний. 4 Булевы функции. 7 Формальные языки. Комбинаторика. 8 Теория графов. 5 Логика предикатов. Методы доказательств. 6 Множества и отношения. 9 Деревья. 10 Методы анализа и оптимизации проектных решений. Применение методов моделирования.

Итого Содержание каждого вида самостоятельной работы и вида контроля Самостоятельная работа выполняется в течение всего семестра изучения дисциплины и предусматривает самостоятельное изучение по учебной литературе, а также в глобальной сети Интернет отдельных вопросов вышеназванных тем дисциплины, подготовку студентов по конспектам лекций, учебной и учебно-методической литературе к практическим занятиям и выполнению индивидуальных заданий по дисциплине в пределах самостоятельной работы.

Содержание Вид Наименование темы.

самостоят. контроля Изучаемые вопросы работы 1. Цифровой автомат Основы теории формальных грамматик. Структурная схема Работа с ли- Кон цифрового автомата. Машины Тьюринга. Абстрактный конечный тературой, спект, автомат. Элементы с выходами с тремя состояниями. Микропро- поиск ин- защита граммирование. Проблемы отображения времени при программи- формации в практи ровании. Сети Петри. Internet ческих Литература: [9], с. 8-60;

[15], с. 9-25;

[22];

[27];

[35];

[42];

[43]. работ 2. Логические элементы и типовые узлы Счетчики;

несинхронизируемый двоичный счетчик с последо- Работа с ли- Кон вательным переносом;

синхронизируемый двоичный счетчик с тературой, спект, параллельным переносом. Дешифраторы;

дешифратор с инверс- поиск ин- опрос на ными выходами;

каскадный дешифратор. Мультиплексоры. Сум- формации в лекции маторы;

комбинационный одноразрядный сумматор;

сумматор с Internet параллельным переносом;

сумматор с групповым переносом.

Литература: [1], с. 83-227;

[3], с. 27-231;

[4];

[13].

3. Теория дискретных структур. Логика высказываний Полные системы связок. Понятие исчисления высказываний;

Работа с ли- Кон понятие формальной аксиоматической теории;

логический вывод, тературой, спект, аксиомы и правила вывода. поиск ин- сообще Литература: [5], с. 103-142;

[6], с. 26-81;

[8];

[10];

[11]. формации в ние Internet 4. Булевы функции Упрощения в записях пропозитарных форм. Пары равносиль- Работа с ли- Кон ных пропозитарных форм. Нормальны формы. Совершенные тературой, спект, нормальные формы. Понятие булевой алгебры, примеры. Прило- поиск ин- тестиро жение алгебры высказываний к анализу и синтезу контактных формации в вание (переключательных) схем. Цифровые логические схемы (типы Internet вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы). Приложение алгебры высказываний к анали зу и синтезу схем из функциональных элементов.

Литература: [9], с. 299-343;

[14], с. 187-293;

[17], с. 42-84;

[18], с. 204-280.

5. Формальные языки. Комбинаторика Примеры грамматик и языков. Конечный автомат и регуляр- Работа с ли- Кон ные языки. Недетерминированные конечные автоматы и опреде- тературой, спект, ляемые ими языки. поиск ин- защита Размещения, перестановки, сочетания, сочетания с повторе- формации в практи ниями. Бином Ньютона. Internet ческих Литература: [22], с. 15-72;

[27];

[34], с. 320-390;

[35];

[47]. работ 6. Теория графов Пути, цепи и контуры: эйлеровы и гамильтоновы контуры – Работа с ли- Кон теоремы и следствия существования в ориентированных и неори- тературой, спект, ентированных графах. Маршруты, циклы, связность графов. поиск ин- кон Представление графов с помощью матриц инцидентности. Теоре- формации в трольная ма о степени матрицы инцидентности. Internet работа Литература: [6], с. 41-83;

[10], с. 94-132;

[14], с. 172-204;

[58].

7. Логика предикатов. Методы доказательств Равносильные формулы логики предикатов. Законы логиче- Работа с ли- Кон ских операций. Нормальные формы формул логики предикатов. тературой, спект, Общезначимость и выполнимость формул;

проблема разрешимо- поиск ин- тестиро сти. Применение языка логики предикатов для записи математи- формации в вание ческих предложений, определений, построения отрицания пред- Internet ложений.

Структура формальных доказательств. Прямое доказательство.

Доказательство с помощью контрпримеров. Доказательство от противного. Доказательство посредством контрапозиции. Мате матическая индукция. Использование принципа математической индукции.

Литература: [5], с. 244-271;

[6], с. 132-159;

[11], с. 139-155;

[19].

8. Множества и отношения Законы де Моргана. Диаграммы Эйлера-Венна. Отношения, Работа с ли- Кон бинарные отношения. Отношение эквивалентности на множестве. тературой, спект, Порождаемое им разбиение на смежные классы, их свойства. От- поиск ин- сообще ношение порядка. формации в ние Литература: [18], с. 344-371;

[48], с. 132-159;

[50], с. 439-455. Internet 9. Деревья Алгоритмы поиска, вставки и удаления узлов в деревьях. Оп- Работа с ли- Кон ределение, преимущества организации хранения упорядоченных тературой, спект, данных в виде бинарного сбалансированного дерева. Алгоритм поиск ин- опрос на балансировки. формации в лекции Литература: [6], с. 244-271;

[10], с. 132-159;

[18], с. 319-354;

Internet [49].

10. Методы анализа и оптимизации проектных решений. Применение методов моделирования Программные средства для решения задач анализа оптимиза- Работа с ли- Кон ции;

использование экспертных систем. Применение методов мо- тературой, спект, делирования для анализа и оптимизации проектных решений. поиск ин- итоговое Статистическое моделирование на ЭВМ. Оценка точности и дос- формации в тестиро товерности результатов моделирования через языки и системы Internet вание моделирования. Инструментальные средства реализации моделей.

Анализ и интерпретация результатов моделирования на ЭВМ.

Литература: [38], с. 187-211;

[40], с. 132-159;

[31];

[61].

Используемые интерактивные образовательные технологии: изучение материалов, используя Интернет-ресурсы по дисциплине и компьютерное моделирование.

2. УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ В учебно-методическое пособие по дисциплине включены теоретические сведения для изучения дисциплины, в которых содержаться основные вопросы по темам курса, перечень литературы, необходимой для их изучения, руководство по практическим занятиям по дис циплине, включающее 7 практических работ. Теоретические сведения по ряду разделов дисциплины – «Понятие о цифровом автомате», «Логические элементы и типовые узлы», «Деревья», «Методы анализа и оптимизации проектных решений. Применение методов мо делирования» в настоящем комплексе не рассматриваются, поскольку представляют собой сведения в целом ранее изученные студентами в других дисциплинах. Для изучения данных материалов рекомендуем обратиться к соответствующим источникам, например [4].

2.1. Теоретические сведения 2.1.1. Теория дискретных структур. Логика высказываний 2.1.1.1. Логика высказываний «Если число рационально, то – алгебраическое число. Но оно не алгебраическое.

Значит, не рационально». Мы не обязаны знать, что такое число, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно – в том смысле, что из двух сформулированных посылок действительно вытекает заключение.

Такого рода ситуации – когда некоторое утверждение верно независимо от смысла входящих в него высказываний – составляют предмет логики высказываний.

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

Высказывание – это мысль, выраженная повествовательным предложением. Например, «2 + 1 – простое число» – истинное высказывание, а «232 + 1 – простое число – ложное (это число делится на 641). Про высказывание «существует бесконечно много простых p, для ко торых p + 2 – также простое» никто не берется сказать наверняка, истинно оно или ложно.

Заметим, что «х делится на 2» в этом смысле не является высказыванием, пока не сказано, чему равно х;

при разных х получаются разные высказывания, одни истинные (при четном), другие – ложные (при нечетном).

Высказывания можно соединять друг с другом с помощью «логических связок». Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1.1). От метим также, что в импликации А В высказывание А называют посылкой, или антецеден том импликации, а В – заключением, или консеквентном.

Говорят также, что высказывание имеет истинностное значение И (истина), если оно истинно, или Л (ложь), если оно ложно. Иногда вместо И употребляется буква T (true) или число 1, а вместо Л – буква F (false) или число 0.

Логические связки позволяют составлять сложные высказывания из простых. При этом истинность составного высказывания определяется истинностью его частей в соответствии с табл. 1.2.

Те же правила можно изложить словесно. Высказывание А В истинно, если оба вы сказывания А и В истинны. Высказывание А В истинно, если хотя бы одно из высказыва ний А и В истинно. Высказывание А В ложно в единственном случае: если А истинно, а В ложно. Наконец, ¬А истинно в том и только том случае, когда А ложно.

Из всех связок больше всего вопросов вызывает импликация. В самом деле, не очень понятно, почему надо считать, скажем, высказывания «если 2 2 = 5, то 2 2 = 4 » и «если 2 2 = 5, то 3 3 = 1 » истинными. (Именно так говорят наши таблицы: Л И = Л Л = И). Следующий пример показывает, что в таком определении есть смысл.

Таблица 1. Логические связки, обозначения и названия Общепризнано, что если число х делится на 4, то оно делится на 2. Это означает, что высказывание (х делится на 4) (х делится на 2) истинно при всех х. Подставим сюда х = 5:

обе части ложны, а утверждение в целом истинно. При х = 6 посылка импликации ложна, а заключение истинно, и вся импликация истинна. Наконец, при х = 8 посылка и заключение истинны и импликация в целом истинна. С другой стороны, обратное утверждение (если х делится на 2, то х делится на 4) неверно, и число 2 является контрпримером. При этом по сылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью ее частей (а не наличи ем между ними каких-то причинно-следственных связей), то все строки таблицы истинности обоснованы. Чтобы подчеркнуть такое узко-формальное понимание импликации, философ ски настроенные логики называют ее «материальной импликацией».

Таблица 1. Таблицы истинности для логических связок Теперь от неформальных разговоров перейдем к определениям. Элементарные выска зывания (из которых составляются более сложные) мы будем обозначать маленькими латин скими буквами и называть пропозициональными переменными. Из них строятся пропози циональные формулы по таким правилам:

- Всякая пропозициональная переменная есть формула.

- Если А – пропозициональная формула, то ¬А – пропозициональная формула.

- Если А и В – пропозициональные формулы, то ( А В), и ( А В) – пропозицио нальные формулы.

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

Пусть формула содержит п пропозициональных переменных р1, р2,..., рп. Если под ставить вместо этих переменных истинностные значения (И или Л), то по таблицам можно вычислить истинностное значение формулы в целом. Таким образом, формула задает неко торую функцию от п аргументов, каждый из которых может принимать значения Л и И. Зна чения функции также лежат во множестве {Л, И}, которое мы будем обозначать B. Мы будем следовать уже упоминавшейся традиции и отождествлять И с единицей, а Л – с нулем, тем самым В есть {0, 1}. Формула задает отображение типа В п В. Такие отображения на зывают также булевыми функциями п аргументов.

Пример 1.1. Рассмотрим формулу ( р (q ¬r )). Она истинна в единственном случае – когда р и q истинны, а r ложно (табл. 1.3).

Таблица 1. Таблица истинности q ( q ¬r ) ( p (q ¬r )) ¬r р r 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 0 Некоторые формулы выражают логические законы – составные высказывания, истин ные независимо от смысла их частей. Такие формулы (истинные при всех значениях входя щих в них переменных) называют тавтологиями.

Пример 1.2. Формула (( p q) p) является тавтологией (это можно проверить, на пример, составив таблицу). Она выражает такой логический закон: из конъюнкции утвер ждений следует первое из них.

1. Как выглядит симметричное утверждение для дизъюнкции, и какая формула его вы ражает?

Две формулы называют эквивалентными, если они истинны при одних и тех же значе ниях переменных (другими словами, если они задают одну и ту же булеву функцию). На пример, формула ( р ( p q )) истинна лишь при p = q = И, и потому эквивалентна форму ле ( p q ).

Рассмотрим формулу (( p q) q ). Она истинна, если переменная q истинна, и ложна, если переменная q ложна. Хотелось бы сказать, что она эквивалентна формуле q, но тут есть формальная трудность: она содержит две переменные и потому задает функцию от двух ар гументов (типа B B B ), в, то время как формула q задает функцию одного аргумента.

Мы не будем обращать на это внимания и будем считать эти формулы эквивалентными. Во обще, если есть список переменных p1,..., pn, содержащий все переменные некоторой фор мулы (и, возможно, еще какие-то переменные), можно считать, что формула задает функцию от n аргументов, возможно, на деле зависящую не от всех аргументов (постоянную по некоторым аргументам) После сделанных оговорок легко проверить следующий факт: формулы и эквива лентны тогда и только тогда, когда формула (( ) ( )) является тавтологией. Ис пользуя сокращение ( p q) для (( p q) (q p)), можно записывать утверждения об эквивалентности формул в виде тавтологий. Вот несколько таких эквивалентностей:

Теорема 1.1. Формулы ( p q ) (q p);

(( p q) r ) ( p (q r ));

( p q) (q p);

(( p q) r ) ( p (q r ));

( p (q r )) (( p q) ( p r ));

( p (q r )) (( p q) ( p r ));

¬( p q) (¬p ¬q);

¬( p q) (¬p ¬q);

( p ( p q)) p;

( p ( p q)) p;

( p q) (¬q ¬p);

p ¬¬p являются тавтологиями.

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

Следующие два свойства, законы Де Моргана, легко проверить, зная, что конъюнкция истинна, а дизъюнкция ложна лишь в одном случае. Эти свойства иногда выражают словами:

«конъюнкция двойственна дизъюнкции».

Далее следуют два очевидных закона поглощения (один из них мы уже упоминали).

За ними идет правило контрапозиции, которое говорит, в частности, что утверждения «если x совершенно, то x четно» и «если x нечетно, то x несовершенно» равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связаны любопытные па радоксы.

Вот один из них. Биолог А выдвинул гипотезу: все вороны черные. Проверяя ее, он вышел во двор и обнаружил на дереве ворону. Она оказалось черной. Биолог А радуется – гипотеза подтверждается. Биолог Б переформулировал гипотезу так: все не-черные предметы – не вороны (применив наше правило контрапозиции) и не стал выходить во двор, а открыл холодильник и нашел там оранжевый предмет. Он оказался апельсином, а не вороной. Био лог Б обрадовался – гипотеза подтверждается – и позвонил биологу А. Тот удивляется – у него тоже есть апельсин в холодильнике, но с его точки зрения никакого отношения к его гипотезе апельсин не имеет.

Другой парадокс: с точки зрения формальной логики утверждения «кто не с нами, тот против нас» и «кто не против нас, тот с нами» равносильны.

Последнее (и очевидное) правило 𠬬р называется снятием двойного отрицания.

2. Перечисленные эквивалентности соответствуют равенствам для множеств: напри мер, первая гарантирует, что Р Q = Q P для любых множеств Р и Q. Какие утверждения соответствуют остальным эквивалентностям?

3. Две формулы, содержащие только переменные и связки, и ¬, эквивалентны.

Докажите, что они останутся эквивалентными, если всюду заменить на и наоборот.

Далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула ( p q) ( q p) является тавтологией (если одно из утверждений p и q ложно, то из него следует все, что угодно;

если оба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции – почему, собственно, из двух никак не связанных утвержде ний одно влечет другое?

Еще более загадочна тавтология (( p q) p ) p (хотя ее ничего не стоит проверить с помощью таблиц истинности).

Отступление о пользе скобок. На самом деле наше определение истинности содержит серьезный пробел. Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в фор мулах? Представим себе, что мы изменим определение формулы, и будем говорить, что P Q и P Q являются формулами для любых P и Q. Останутся ли наши рассуждения в силе?

Легко понять, что мы столкнемся с трудностью при определении булевой функции, со ответствующей формуле. В этом определении мы подставляли нули и единицы на место пе ременных и затем вычисляли значение формулы с помощью таблиц истинности для связок.

Но теперь, когда мы изменили определение формулы, формула p q r может быть полу чена двумя способами – из формул p q и r с помощью операции и из формул p и q r с помощью операции. Эти два толкования дадут разный результат при попытке вычислить значение 0 0 1.

Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтакси ческого разбора формулы. Точнее говоря, верно такое утверждение:

Теорема 1.2 (однозначность разбора). Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из четырех видов ( A B), ( A B), ( A B) или ¬A, где A и B – некоторые формулы, причем A и B (в первых трех случаях) восстанавливаются однозначно.

Формальное доказательство можно провести так: назовем скобочным итогом разницу между числом открывающихся и закрывающихся скобок. Индукцией по построению форму лы легко доказать такую лемму:

Лемма 1.1. Скобочный итог формулы равен нулю. Скобочный итог любого начала формулы неотрицателен и равен нулю, лишь если это начало совпадает со всей формулой, пусто или состоит из одних символов отрицания.

Слова «индукцией по построению» означают, что мы проверяем утверждение для пе ременных, а также доказываем, что если оно верно для формул A и B, то оно верно и для формул ( A B), ( A B) и ¬A.

После того как лемма доказана, разбор формулы проводится так: если она начинается с отрицания, то может быть образована лишь по третьему правилу. Если же она начинается со скобки, то надо скобку удалить, а потом искать непустое начало, имеющее нулевой скобоч ный итог и не оканчивающееся на знак логической операции. Такое начало единственно (как легко проверить, используя лемму). Это начало и будет первой частью формулы. Тем самым формула разбирается однозначно.

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

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

4. Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, (a + b) (c + (d )) в его обозначениях запишется как + ab + c de. Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов. Покажите, что в обоих случаях порядок действий восстанавливается одно значно.

2.1.1.2. Полные системы связок Рассматриваемая нами система пропозициональных связок (,, ) полна в сле дующем смысле:

Теорема 1.3 (Полнота системы связок). Любая булева функция n аргументов может быть записана в виде пропозициональной формулы.

Проще всего пояснить это на примере. Пусть, например, булева функция ( p, q, r ) за дана табл. 1. (¬p ¬q ¬r ) (¬p q r ) ( p q r ) Таблица 1. Булева функция и задающая ее формула ( p, q, r ) p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 В таблице есть три строки с единицами в правой колонке – три случая, когда булева функция истинна (равна 1). Напишем три конъюнкции, каждая из которых покрывает один случай (а в остальных строках ложна), и соединим их дизъюнкцией. Нужная формула по строена.

Ясно, что аналогичная конструкция применима для любой таблицы (с любым числом переменных).

Для формул подобного вида есть специальное название: формулы в дизъюнктивной нормальной форме. Более подробно: литералом называется переменная или отрицание пере менной, конъюнктом называется произвольная конъюнкция литералов, а дизъюнктивной нормальной формой называется дизъюнкция конъюнктов. В нашем случае в каждый конъ юнкт входит n литералов (где n – число переменных), а число конъюнктов равно числу строк с единицами и может меняться от нуля (тогда, правда, получается не совсем формула, а «пустая дизъюнкция», и ее можно заменить какой-нибудь всегда ложной формулой типа р ¬р ) до 2n (если булева функция всегда истинна).

5. Длина построенной в доказательстве теоремы 3 формулы зависит от числа единиц:

формула будет короткой, если единиц в таблице мало. А как написать (сравнительно) корот кую формулу, если в таблице мало нулей, а в основном единицы?

Иногда полезна конъюнктивная нормальная форма, которая представляет собой конъ юнкцию дизъюнктов. Каждый дизъюнкт состоит из литералов, соединенных дизъюнкциями.

Теорему 1.3 можно теперь усилить так:

Теорема 1.4. Всякая булева функция может быть выражена формулой, находящейся в дизъюнктивной нормальной форме, а также формулой, находящейся в конъюнктивной нор мальной форме.

Первая часть утверждения уже доказана. Вторая часть аналогична первой, надо только для каждой строки с нулем написать подходящий дизъюнкт.

Можно также представить функцию ¬ в дизъюнктивной нормальной форме, а затем воспользоваться законами Де Моргана, чтобы внести отрицание внутрь.

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

если, например, переменная и ее отрицание входят в одну конъюнкцию, то эта конъюнкция всегда ложна и ее можно выбросить.) 7. Приведите пример булевой функции n аргументов, у которой любая дизъюнктивная или конъюнктивная нормальная форма содержит лишь члены длины n. Заметим, что при до казательстве теоремы 3 мы обошлись без импликации. Это и не удивительно, так как она вы ражается через дизъюнкцию и отрицание:

( p q) (¬p q ).

Мы могли бы обойтись только конъюнкцией и отрицанием, так как ( p q) ¬(¬p ¬q), или только дизъюнкцией и отрицанием, так как ( p q ) ¬(¬p ¬q) (обе эквивалентности вытекают из законов Де Моргана;

их легко проверить и непосредст венно). Как говорят, система связок, ¬, а также система связок, ¬ являются полными.

(По определению это означает, что с их помощью можно записать любую булеву функцию.) 8. Докажите, что система связок ¬, полна. (Указание: как записать через них дизъ юнкцию?) А вот без отрицания обойтись нельзя. Система связок,, неполна – и по очень простой причине: если все переменные истинны, то любая их комбинация, содержащая толь ко указанные связки, истинна. (Как говорят, все эти связки «сохраняют единицу».) 9. Легко понять, что любая формула, составленная только с помощью связок и, задает монотонную булеву функцию (в том смысле, что от увеличения значения любого из аргументов значение функции может только возрасти – или остаться прежним). Покажите, что любая монотонная булева функция может быть выражена формулой, содержащей только и.

10. Пусть – тавтология. Покажите, что найдется формула, которая включает в себя только общие для и переменные, для которой формулы ( ) и ( ) явля ются тавтологиями. (Более общий вариант этого утверждения, в котором рассматриваются формулы с кванторами, называется леммой Крейга.) В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Лю бая булева функция может играть роль связки. Например, можно рассмотреть связку ( p notand q), задаваемую эквивалентностью ( p notand q) ¬( p q ) (словами: ( p notand q) ложно, лишь если р и q истинны). Через нее выражается отрицание ( p notand p ), после чего можно выразить конъюнкцию, а затем, как мы знаем, и вообще любую функцию.

Другая интересная полная система связок – сложение по модулю 2, конъюнкция и кон станта 1 (которую можно считать 0-арной связкой, задающей функцию от нуля аргументов).

Представленные в этой системе булевы функции становятся полиномами с коэффициентами в кольце вычетов по модулю 2. Идея рассматривать булевы функции как полиномы (оказав шаяся неожиданно плодотворной в последние годы) была высказана в 1927 г. российским математиком Иваном Ивановичем Жегалкиным.

Назовем мономом конъюнкцию любого набора переменных или константу 1 (которую естественно рассматривать как конъюнкцию нуля переменных). Название это естественно, так как при наших соглашениях (1 обозначает истину, 0 – ложь) конъюнкция соответствует умножению.

Назовем полиномом сумму таких мономов по модулю 2 (это значит, что 0 0 = 0, 0 1 = 1 0 = 1 и 1 1 = 0 ). Ясно, что два повторяющихся монома можно сократить (ведь сложение по модулю 2), так что будем рассматривать только полиномы без повторяющихся мономов. При этом, естественно, порядок членов в мономе (как и порядок мономов в поли номе) роли не играет, их можно переставлять.


Теорема 1.5 (о полиномах Жегалкина). Всякая булева функция однозначно представ ляется таким полиномом.

Существование искомого полинома следует из теоремы 4, так как конъюнкция есть ум ножение, отрицание – прибавление единицы, а дизъюнкцию можно через них выразить (по лучится p + q + pq ). Надо только заметить, что степени не нужны: переменные принимают значения 0 и 1, так что xn можно заменить на x.

Можно также сослаться на известное из алгебры утверждение о том, что всякая функ ция с аргументами из конечного поля (в данном случае это двухэлементное поле вычетов по модулю 2) задается полиномом. (Отсюда, кстати, получается новое доказательство теоремы 3.) Далее можно заметить, что полиномов столько же, сколько булевых функций, а именно 2n 2. В самом деле, булева функция может принимать любое из двух значений в каждой из 2n точек булева куба Вп, а многочлен может включать или не включать любой из 2n мономов.

(Мономов ровно 2n, потому что каждый моном включает или не включает любую из n пере менных.) Поэтому избытка полиномов нет, и если любая функция представима полиномом, то единственным образом.

Можно и не ссылаться на сведения из алгебры и теорему 4, а дать явную конструкцию.

Это удобно сделать индукцией по n. Пусть мы уже умеем представлять любую булеву функ аргументов с помощью полинома. Тогда ( p1,..., pn ) можно представить как цию от ( p1,..., pn ) = (0, p2,..., pn ) + [ (0, p2,..., pn ) + (1, p2,..., pn )] p2.

Остается заметить, что правую часть можно представить полиномом по предположению ин дукции.

Для единственности также есть другое доказательство: пусть два многочлена (имею щие степень 1 по каждой переменной) равны при всех значениях переменных. Тогда их сум ма (или разность – вычисления происходят по модулю 2) является ненулевым многочленом (содержит какие-то мономы), но тождественно равна нулю. Так не бывает, и это легко дока зать по индукции. В самом деле, любой многочлен A( p1,..., pn ) можно представить в виде A( p1,..., pn ) = B( p2,..., pn ) + p1C ( p2,..., pn ), где B и C – многочлены от меньшего числа пере менных. Подставляя сначала p1 = 0, а затем p1 = 1, убеждаемся, что многочлены B и C равны нулю во всех точках, и потому (согласно предположению индукции) равны нулю как много члены (не содержат мономов).

11. Пусть F – произвольное поле. Назовем мультилинейной функцией полином от n пе ременных с коэффициентами из F, в котором все показатели степеней равны либо 0, либо 1.

(Таким образом, каждый моном в ней есть произведение коэффициента и некоторого набора переменных без повторений.) Будем рассматривать B = {0, 1} как подмножество F. Докажи те, что всякая булева функция B n B однозначно продолжается до мультилинейной функ ции F n F, и коэффициенты мультилинейной функции можно считать целыми числами.

Если рассматривать произвольные булевы функции в качестве связок, возникает во прос: в каком случае набор булевых функций образует полный базис? (Это значит, что любая булева функция представляется в виде композиции функций из набора, т. е. записывается в виде формулы, где связками служат функции набора.) Подобные вопросы вызывали в свое время большой интерес и были хорошо изучены. Начальным этапом явилось такое утвер ждение:

Теорема 1.6 (критерий Поста). Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из пяти следующих "предполных классов":

• монотонные функции;

• функции, сохраняющие нуль;

• функции, сохраняющие единицу;

• линейные функции;

• самодвойственные функции.

(Функция f монотонна, если она монотонно неубывает по каждому из своих аргумен тов. Функция f сохраняет нуль/единицу, если f (0, …, 0) = 0 (соответственно f (1, …, 1) = 1).

Функция f линейна, если она представима многочленом, в котором все мономы содержат не более одной переменной. Наконец, функция f называется самодвойственной, если f (1 p1,...,1 pn ) = 1 f ( p1,..., pn ).

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

У нас есть функция, не сохраняющая нуль. Подставим вместо всех аргументов одну и ту же переменную. Получится функция от одного аргумента, отображающая нуль в единицу, то есть либо константа 1, либо отрицание. Сделав то же самое с функцией, не сохраняющей единицу, получим либо константу нуль, либо отрицание. Таким образом, у нас либо есть от рицание, либо обе константы 0 и 1.

Если есть обе константы, то все равно можно получить отрицание. Возьмем немоно тонную функцию. Легко понять, что она должна менять значение с единицы на нуль при из менении какого-то одного аргумента с нуля на единицу (в самом деле, будем увеличивать аргументы по одному, в какой-то момент значение функции уменьшится.) Зафиксировав значения остальных аргументов (ведь мы считаем, что константы есть), получаем отрицание.

Имея отрицание и несамодвойственную функцию, легко получить константы (если их не было). В самом деле, несамодвойственность означает, что f ( x1,..., xn ) = f (1 x1,..., 1 xn ) для каких-то значений x1,..., xn {0, 1}. Вместо нулевых значений переменных x1,..., xn под ставим p, вместо единиц подставим ¬p, получится одна из констант. Вторая получится от рицанием.

Теперь у нас есть константы, отрицание и нелинейная функция f ( p1,..., pn ). Нелиней ность означает, что в ее представлении в виде многочлена есть моном, состоящий более чем из одной переменной. Пусть, например, этот моном содержит переменные p1 и p 2. Сгруп пируем члены по четырем группам и получим выражение p1 p2 A( p3,...) + p1B( p3,...) + p2C ( p3,...) + D( p3,...).

При этом многочлен A( p3,...) заведомо отличен от нуля, поэтому можно так подставить константы вместо p3,..., pn, чтобы первое слагаемое не обратилось в нуль. Тогда получим либо p1 p2 + d, либо p1 p2 + p1 + d, либо p1 p2 + p2 + d, либо p1 p2 + p1 + p2 + d. Свободный член d можно менять, если нужно (у нас есть отрицание), так что получается либо p1 p (конъюнкция, и все доказано), либо p1 p2 + p1 = p1 ( p2 + 1) = p1 ¬p2 (убираем отрицание, по p1 p2 + p лучаем конъюнкцию, все доказано), либо (аналогично), либо p1 p2 + p1 + p2 = (1 + p1 )(1 + p2 ) 1 = ¬(¬p1 ¬p2 ) = p1 p2 (дизъюнкция, все доказано).

2.1.1.3. Исчисление высказываний (ИВ) Каковы бы ни были формулы A, B, C, следующие формулы называют аксиомами ис числения высказываний:

A ( B A);

(1.1) ( A ( B C )) (( A B) ( A C ));

(1.2) ( A B) A;

(1.3) ( A B) B;

(1.4) A ( B ( A B));

(1.5) A ( A B);

(1.6) B ( A B);

(1.7) ( A C ) (( B C ) ( A B C ));

(1.8) ¬A ( A B);

(1.9) ( A B) (( A ¬B) ¬A);

(1.10) A ¬A. (1.11) Как говорят, мы имеем здесь одиннадцать "схем аксиом";

из каждой схемы можно по лучить различные конкретные аксиомы, заменяя входящие в нее буквы на пропозициональ ные формулы.

Единственным правилом вывода исчисления высказываний является правило со сред невековым названием "modus ponens" (MP). Это правило разрешает получить (вывести) из формул A и ( A B) формулу B.

Выводом в исчислении высказываний называется конечная последовательность фор мул, каждая из которых есть аксиома или получается из предыдущих по правилу modus ponens.

Вот пример вывода (в нем первая формула является частным случаем схемы (1), вторая – схемы (2), а последняя получается из двух предыдущих по правилу modus ponens):

( p (q p)), ( p (q p )) (( p q ) ( p p )), (( p q ) ( p p )).

Пропозициональная формула A называется выводимой в исчислении высказываний, или теоремой исчисления высказываний, если существует вывод, в котором последняя фор мула равна A. Такой вывод называют выводом формулы A. (В принципе можно было бы и не требовать, чтобы формула A была последней – все дальнейшие формулы можно просто вы черкнуть.) Как мы уже говорили, в исчислении высказываний выводятся все тавтологии и только они.

Обычно это утверждение разбивают на две части: простую и сложную. Начнем с про стой:

Теорема 1.7 (о корректности ИВ). Всякая теорема исчисления высказываний есть тав тология.

Несложно проверить, что все аксиомы – тавтологии. Для примера проделаем это для самой длинной аксиомы (точнее, схемы аксиом) – для второй. В каком случае формула ( A ( B C )) (( A B) ( A C )) (где A, B, C – некоторые формулы) могла бы быть ложной? Для этого посылка A ( B C ) должна быть истинной, а заключение ( A B) ( A C ) – ложным. Чтобы заключение было ложным, формула A B должна быть истинной, а формула A C – ложной. Последнее означает, что A истинна, а C ложна.

Таким образом, мы знаем, что A, ( A B) и ( A ( B C )) истинны. Отсюда следует, что B и ( B C ) истинны, и потому C истинна – противоречие. Значит, наша формула не бывает ложной.

Корректность правила MP также очевидна: если формулы ( A B ) и A всегда истинны, то по определению импликации формула B также всегда истинна. Таким образом, все фор мулы, входящие в выводы (все теоремы) являются тавтологиями.

Гораздо сложнее доказать обратное утверждение.

2.1.1.4. Исчисление высказываний Известен ряд аксиоматических систем исчисления высказываний (Д. Гильберта, С.

Клини, Г. Фреге, П.С. Новикова). Здесь будет рассматриваться исчисление высказываний Я.

Лукасевича (кратко: исчисление L), основанное на использовании функционально полной системы связок (¬, ). Исчисление высказываний Я. Лукасевича описывает множество то ждественно истинных формул (тавтологий), построенных с использованием указанной сис темы связок, что соответствует реальному положению вещей, например, в математике, где теоремы как высказывания являются тождественно истинными формулами (проанализируй те для примера любую из геометрических теорем о признаках равенства треугольников).


Язык исчисления L как формальной аксиоматической теории включает перечень упот ребляемых символов и определение понятия формулы. Символами исчисления L являются счетное множество символов пропозициональных переменных xi, i = 1, 2,..., символы логиче ских операций ¬, и вспомогательные символы скобок (, ). Знаки других логических опе раций (см. раздел 2.1) рассматриваются как обозначения формул, построенных с применени ем операций ¬ и. Например, запись ( A B) рассматривается как обозначение формулы ((¬A) B ), а запись ( A & B) – как обозначение формулы (¬( A (¬B ))).

Понятие формулы исчисления L определяется индуктивно:

а) пропозициональные переменные xi, i = 1, 2,..., являются формулами;

б) если A и B – формулы, то выражения ¬A и ( A B) – тоже формулы;

в) других формул, кроме выражений, построенных согласно пунктам а) и б), нет.

Систему аксиом исчисления L составляет бесконечное счетное множество формул ис числения, построенных с использованием следующих трех схем аксиом:

( A1) ( Z1 ( Z 2 Z1 ));

( A2) (((Z1 ( Z 2 Z 3 )) (( Z1 Z 2 ) ( Z1 Z 3 )));

( A3) ((¬Z1 ¬Z 2 ) ((¬Z1 Z 2 ) Z1 )).

Аксиомой считается каждая формула, полученная подстановкой в схему аксиом любых формул исчисления L вместо переменных Z1, Z2, Z3.

Правилом вывода исчисления L является правило заключения (modus ponens), по кото рому из формул A и ( A B) выводится формула B (в краткой записи: A, A B | B ). В дальнейшем при ссылках на это правило будем использовать обозначение МР.

Полнота исчисления высказываний Я. Лукасевича трактуется как совпадение множест ва теорем этого исчисления с множеством тавтологий. Доказательство этого положения, как часто бывает, строится в два этапа: сначала показывается, что всякая теорема исчисления L является тавтологией, затем – что всякая тавтология выводима в исчислении L как его теоре ма. Обратимся к рассмотрению этих этапов.

Теорема 1.8. Если формула A – тавтология, зависящая от переменных x1, x2,..., xn, а формула B получена из A подстановкой формул C1, C2,..., Cn вместо x1, x2,..., xn, соответствен но, то формула B – тоже тавтология (т.е. подстановка в тавтологию порождает тавтологию).

Доказательство. Пусть задан произвольный набор значений переменных, входящих в B. Формулы C1, C2,..., Cn, содержащиеся в B, примут на этом наборе некоторые значения a1, a2,..., an. По построению истинностное значение формулы B будет совпадать с истинностным значением формулы A, если значения a1, a2,..., an придать переменным x1, x2,..., xn формулы A.

Так как формула A – тавтология, то этим одинаковым для A и B значением будет "истина", а так как набор значений переменных формулы B был выбран произвольно, то "истина" будет значением формулы B на любом наборе значений ее переменных. Следовательно, формула B – тавтология.

Теорема 1.9. Каждая аксиома исчисления L – тавтология.

Доказательство. Каждая схема аксиом исчисления L – тавтология, в чем можно убе диться непосредственно построением истинностных таблиц для этих схем. Так как другие аксиомы образуются подстановкой формул исчисления в схемы аксиом, то, согласно теореме 2.5, все они будут тавтологиями.

Теорема 1.10. Если формулы A и ( A B) – тавтологии, то формула B – тоже тавтоло гия (т. е. из тавтологий-посылок по правилу вывода получаются тавтологии – заключения).

Доказательство. Пусть формулы A и ( A B) – тавтологии. Предположим, что, вопре ки утверждению теоремы, B – не тавтология. Тогда найдется набор значений переменных, входящих в A и B, такой, что формула B примет значение "ложь". Так как A – тавтология, то на том же наборе A примет значение "истина", а формула ( A B) – значение "ложь", что противоречит условию теоремы о том, что ( A B) – тавтология. Следовательно, формула B – тавтология.

Теорема 1.11. Каждая теорема исчисления L – тавтология.

Доказательство. Следует из теоремы 2.6 и теоремы 2.7. Для доказательства обратного положения (о том, что всякая тавтология является теоремой исчисления L) потребуется вы вод в качестве теорем исчисления L основных законов алгебры логики и производных от ос новного правил вывода. Учитывая уже состоявшееся знакомство с законами алгебры логики, мы лишь покажем на примерах, как это делается. Приведем краткий перечень правил выво да, доказываемых в исчислении L как его теоремы.

1. Правило введения (теорема дедукции): если Г, А | B, то Г | А B.

2. Правило удаления (теорема редукции): если Г | А B то Г, А | B.

3. Правило введения ¬ : если Г, ¬А | B и Г, ¬А | ¬B, то Г | ¬A.

4. Правило удаления ¬ : если Г, ¬А | B и Г, ¬А | ¬B, то Г | A.

5. Правило контрапозиции: если Г, A | B, то Г, ¬А | ¬B.

6. Правило введения : Г, A | A B.

7. Правило удаления : если Г, ¬А | B и Г, ¬А | ¬B, то Г | A.

8. Правило введения &: Г, А, B | A & B.

9. Правило удаления &: Г, А & B | A.

Законы алгебры логики указывают на эквивалентность левой и правой формул. По скольку эквивалентность ( A B) равносильна конъюнкции импликаций ( A B) & ( B A), то вывод большинства законов алгебры логики в исчислении L требует доказательства двух теорем. Так, для вывода закона снятия двойного отрицания требуется доказать теоремы:

A | ¬¬A и ¬¬A | A. Для вывода законов коммутативности связок и & также требуется доказать по две теоремы:

A B | B A и B A | A B;

A & B | B & A и B & A | A & B.

Исключением является вывод закона ¬A A 1, получение которого в исчислении L равносильно доказательству теоремы A A.

Теорема 1.12. | A A для любой формулы A исчисления L.

Доказательство. Построим вывод формулы A A в исчислении L. Расположим по следовательность формул, доказывающих A A, для удобства по вертикали:

B1 : ( A (( A A)) – аксиома по схеме (A1);

B 2 : (( A (( A A) A)) (( A ( A A)) ( A A))) – аксиома по схеме (A2);

B3 : (( A ( A A) ( A A)) – из B1 и B2 по правилу MP;

B 4 : ( A ( A A)) – аксиома по схеме (A1);

B5 : ( A A) – из B4 и B3 по правилу MP.

В комментариях к доказательству приняты следующие обозначения: через (A1) и (A2) обозначены первая и вторая схемы аксиом, через MP отмечено применение правила modus ponens. Для получения формулы B1 в схему (A1) произведена подстановка: Z1 = A, Z 2 = ( A A). Для получения формулы B2 в схему (A2) произведена подстановка: Z1 = A, Z 2 = ( A A), Z3 = A. Для получения формулы B4 в схему (A1) произведена подстановка: Z = A, Z2 = A.

Следующая теорема иллюстрирует применение метода математической индукции для получения одного из перечисленных выше правил ввода.

Теорема 1.13. (теорема дедукции). Если Г, A | B, то Г | A B.

Доказательство. Пусть B1, B2,..., Bn=B – вывод B из Г,A. Индукцией по i докажем Г | A B, i = 1, 2,...,n.

Сначала покажем, что Г | A B1. Возможны три случая:

а) формула B1 является аксиомой;

б) формула B1 является гипотезой из множества Г;

в) формула B1 является формулой A.

В случаях а) и б) по схеме аксиом (A1) образуем аксиому ( B1 ( A B1 )). Тогда из B и ( B1 ( A B1 )) по MP получим искомое: Г | A B1. Случай в) соответствует уже дока занной теореме 1.12.

Далее предположим, что теорема верна для всех k i, и покажем, что тогда она верна для i. Для формулы Bi возможны уже четыре случая:

а) Bi – аксиома;

б) Bi – гипотеза из Г;

в) Bi есть A;

г) Bi следует по MP из некоторых Bj и Bm, j, m i.

Доказательство первых трех случаев для формулы Bi полностью аналогично их доказа тельству для формулы B1. Остается доказать последний случай. Так как j, m i, то (по пред положению индукции) верны формулы: Г | A B j и Г | ( A ( B j Bi )), где ( B j Bi ) = Bm, поскольку по предположению Bi получена из Bj и Bm по правилу MP. Тогда, используя аксиому (( A ( B j Bi )) (( A B j ) ( A Bi ))) по схеме (A2) с указанными формулами и применяя дважды правило MP, получим последовательность формул, приво дящую к искомому результату:

C1 : ( A ( B j Bi ) – по предположению индукции;

C 2 : (( A ( B j Bi )) (( A B j ) ( A Bi ))) – аксиома по (A2);

C 3 : (( A B j ) ( A Bi )) – из C1 и C2 по MP;

C 4 : ( A B j ) – по предположению индукции;

C 5 : ( A Bi ) – из C4 и C3 по MP.

Согласно методу математической индукции, это означает, что утверждение верно для каждого i, i = 1, 2,..., n, и, следовательно, теорема доказана.

Приведем для иллюстрации применения теоремы дедукции два ее весьма полезных следствия.

Следствие 1.1. ( A B), ( B C ) | ( A C ).

Доказательство. В качестве доказательства служит приводимая ниже последователь ность формул:

D1 : ( A B) – формула, данная как гипотеза;

D 2 : ( B C ) – формула, данная как гипотеза;

D3 : A – дополнительно вводимая гипотеза;

D 4 : B – следствие из D3 и D1 по MP;

D5 : C – следствие из D4 и D2 по MP;

D 6 : ( A C ) – по теореме дедукции из D1, D2, D3, D4, D5.

Следствие 1.2. ( A ( B C )), B | ( A C ).

Рассмотренные примеры доказательств теорем 1.12, 1.13 и следствий 1.1, 1.2 призваны, как уже отмечалось, проиллюстрировать способы построения выводов законов алгебры ло гики и производных правил вывода в исчислении L.

Теорема 1.14. Если A – тавтология, зависящая от переменных x1,..., xn, то для каждой элементарной дизъюнкции ее к.н.ф. существует i, i = {1,..., n}, такое, что ¬xi и xi входят в состав этой дизъюнкции.

Доказательство. По известной теореме каждая пропозициональная формула предста вима в виде к.н.ф. Если формула A – тавтология, то по закону для конъюнкции каждая ее элементарная дизъюнкция – тавтология. Но, если бы в к.н.ф. формулы A нашлась элементар ная дизъюнкция, не соответствующая утверждению теоремы, то ее можно было бы обратить в "ложь", придав переменным, входящим в нее без отрицания, значение "ложь", а перемен ным, входящим в нее с отрицанием – значение "истина", что противоречило бы условию тео ремы о том, что A – тавтология.

Результат, полученный в теореме 2.13, позволяет определить общий принцип построе ния доказательств тавтологий как теорем исчислений L, который и применяется в доказа тельстве следующей теоремы.

Теорема 1.15. Если A – тавтология, то A – теорема исчисления L.

Доказательство. Пусть A – тавтология, представленная в виде к.н.ф.

Согласно теореме 1.14, в каждой элементарной дизъюнкции этой к.н.ф. найдется пере менная xi такая, что ¬xi и xi входят в состав этой дизъюнкции. Так как (¬xi xi ) ( xi xi ), а ( xi xi ), согласно теореме 1.12, выводима в исчислении L, то каждая элементарная дизъ юнкция тавтологии выводима по теореме 1.12 и правилу введения дизъюнкции, а вся к.н.ф.

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

Теорема 1.16 (о полноте). Формула A тогда и только тогда теорема исчисления L, ко гда она тавтология.

Доказательство следует из теоремы 1.11 и теоремы 1.15.

Поскольку множество теорем исчисления L и множество тавтологий совпадает, исчис ление L – разрешимая теория. Эффективная процедура, позволяющая за конечное число ша гов определять, является ли данная пропозициональная формула теоремой исчислений L, со стоит в построении истинностной таблицы этой формулы, что для формулы конечной длины всегда можно осуществить за конечное число шагов.

Непротиворечивость исчисления L легко устанавливается на основе теоремы о полно те.

Теорема 1.17 (о непротиворечивости). Исчисление L непротиворечиво, т. е. не суще ствует формулы A исчисления L такой, чтобы формулы A и ¬A одновременно были теоре мами этого исчисления.

Доказательство следует из теоремы о полноте. Если A – тавтология, то ¬A – противо речие, если же ¬A – тавтология, то A – противоречие. Поскольку теоремами исчисления L являются только и только тавтологии, то одновременно теоремами исчисления L эти форму лы быть не могут. Что и требовалось доказать.

Независимость аксиом исчисления L устанавливается через обращение к многозначным логикам. Логика называется многозначной, если полагается, что переменные принимают бо лее двух "истинностных" значений. Простой пример многозначности – люстра с нескольки ми вариантами включения. Переход к многозначной логике (в данном случае будет исполь зована трехзначная) позволяет приданием нового смысла связкам ¬ и выявить структур ную специфику каждой схемы аксиом и тем самым продемонстрировать независимость каж дой из них.

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

Теорема 1.18. Каждая из схем аксиом (A1), (A2), (A3) независима.

Доказательство. Для доказательства независимости схем аксиом рассмотрим их при следующих трех интерпретациях связок ¬ и.

Независимость схемы аксиом (A1). Используем следующие "истинностные" таблицы для связок ¬ и, представленные на рис. 1.1.

Рис. 1.1. «Истинностные» таблицы связок ¬ и к доказательству независимости схемы аксиом (A1) Представленные на рис. 1.1 таблицы позволяют при всяком распределении значений 0,1,2 переменных, входящих в формулу A, найти соответствующее значение формулы A. На зовем формулу A выделенной, если она принимает значение 0 на любом наборе значений своих переменных. Можно показать, как это сделано в теоремах 1.8 – 1.11 в отношении тав тологий, что всякая аксиома, полученная по схеме (A2) или (A3), является выделенной и что правило вывода modus ponens сохраняет свойство выделенности. Следовательно, выделен ной является и всякая формула, выводимая из аксиом, полученных по схемам (A2) – (A3).

Однако формула ( x1 ( x2 x1 )), представляющая собой аксиому по схеме (A1), не является выделенной, ибо она принимает значение 2, когда x1 принимает значение 1 и x2 принимает значение 2. Таким образом, подмножество аксиом, порождаемых схемой (A1), независимо.

Независимость схемы аксиом (A2). Для доказательства независимости данной схемы аксиом используем следующие "истинностные" таблицы для связок ¬ и, представленные на рис. 1.2.

Рис. 1.2. «Истинностные» таблицы связок ¬ и к доказательству независимости схемы аксиом (A2) Всякую формулу, принимающую согласно этим таблицам значение 0 на любом наборе значений ее переменных, назовем гротескной. Аналогично тому, как это было сделано в пре дыдущем случае, можно показать, что все аксиомы, порождаемые схемами (A1) и (A3), и формулы, выводимые из этих аксиом по правилу modus ponens, гротескны. Однако аксиома (( x1 ( x2 x3 )) (( x1 x2 )) ( x1 x3 ))) по схеме (A2) не является гротескной, ибо при нимает значение 2, когда x1, x2, x3 получают, соответственно, значения 0,0,1. Из этого факта следует, что подмножество аксиом, порождаемых схемой (A2), независимо.

Независимость схемы аксиом (A3). Пусть A – произвольная формула исчисления L и h(A) – формула, полученная из A удалением из нее всех связок отрицания. Для всякой аксио мы A по схеме (A1) и (A2) h(A) есть тавтология. Правило modus ponens сохраняет свойство A иметь в качестве h(A) тавтологию, ибо если h(A) и h( A B) тавтологии, то h(B) – тавтоло гия (следует заметить, что h( A B ) совпадает с h( A) h( B) ). Следовательно, всякая фор мула A, выводимая из (A1), (A2) с помощью правила modus ponens, имеет в качестве h(A) тав тологию. Однако результат операции h((¬x ¬x) ((¬x x) x)) совпадает с (( x x) (( x x) x)), а эта последняя формула не является тавтологией. Таким обра зом, поскольку A = ((¬x ¬x) ((¬x x) x)) – аксиома по схеме (A3) и h(A) невыводи ма из (A1) и (A2) с помощью h и modus ponens, то схема аксиом (A3) независима.

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

2.1.1.5. Формальные аксиоматические теории Многие научные теории (не обязательно математические) строятся по следующему принципу. Сначала предлагаются некоторые основные понятия и некоторые начальные зако ны (аксиомы), присущие основным понятиям. Далее формулируются производные понятия и по определенным правилам доказываются некоторые утверждения (теоремы), относящиеся к основным и производным понятиям. Совокупность основных и производных понятий, акси ом и теорем, построенная таким способом, называется аксиоматической системой.

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

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

Во-первых, каждая формальная аксиоматическая теория имеет свой формальный язык.

Чтобы определить язык такой теории, надо, прежде всего, указать (счётное) множество его символов. Любая конечная последовательность символов языка называется выражением это го языка. Среди выражений выделяется подмножество выражений, именуемых формулами языка, под которыми подразумеваются осмысленные предложения языка, утверждающие не который факт. Язык формальной аксиоматической теории считается полностью определен ным, когда заданы символы и описаны формулы языка.

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

Система аксиом независима, если в ней нет аксиом, выводимых из остальных аксиом систе мы. О полноте системы аксиом можно говорить в синтаксическом и в семантическом плане.

Система аксиом синтаксически полна, если присоединение к ней в качестве новой аксиомы любой невыводимой в данной теории формулы делает теорию противоречивой. Система ак сиом семантически полна в том случае, если из нее можно вывести все истинные суждения, выраженные в терминах данной формальной теории и составляющие совокупность знаний той области, на которую распространяется данная система аксиом. Требование непротиворе чивости системы аксиом является обязательным, так как в противном случае теория стано вится бесполезной. Выполнение требования независимости аксиом позволяет строить более изящные теории, но использование более богатого набора даже зависимых аксиом позволяет строить более эффективные в научном плане теории. Требование полноты также не является обязательным для формальных теорий, поскольку практически полезными являются многие неполные формальные системы. О полноте же формальной теории в семантическом плане можно говорить лишь по отношению к текущему состоянию научного знания, относящегося к предмету теории, но не в абсолютном смысле, ибо доказана невозможность полной форма лизации научного знания (теорема Гёделя о принципиальной неполноте формализованного знания).



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.