1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 47
Текст из файла (страница 47)
Независимость аксиомы АЗ: ААВ ~А. В нашей интерпретации логических формул иаменим определение конъюнкции. Будем считать, что к8 у=у. 224 ГЛ. 8. КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКОЕ ЛОГИКИ ' В результате конъюнкция получит следующую таблицу инстинмости: Рассмотрим исчисление ( без АЗ. Непосредственной проверкой по таблицам истинности убеждаемся, что полученное исчисление корректно в этой новой интерпретации.
В то же время формула (Хй У) ~Х не является общезначимой в этой же интерпретации (при Х = г и У = 1 значение функции равно $). Таким образом, эта формула, получающаяся из схемы аксиомы АЗ, не выводима в исчислении В без АЗ. Заключение. Подведем итог изложенному в этой главе. Мы привели ряд конкретных фактов из алгебры логики и исчисления высказываний, которые нам потребуются в дальнейшем. Далее, на примере математической логики мы рассмотрели способ построения формальной теории как средства конструктивного изучения абстрактных объектов и их свойств. Конструктивность подхода состояла в том„что мы связывали с абстрактным объектом (булевой функцией) некоторую конструкцию (формулу), имеющую вид текста в некотором языке (язык логических формул), заданном своей формальной грамматикой (синтаксические правила).
Связь формальных, но конструктивных объектов с содержатгльными, но абстрактными объектами устанавливается с помощью интерпретации. Одному формальному объекту может соответствовать-множество интерпретаций (разное число независимых переменных в булевых функциях, разные определения операций, как это было в доказательстве независимости). Язык обычно создает избыточный запас конструкций и для выделения в этом запасе полезных для изучения конструкций строятся исчисления. Исчисления — зто способ эффективного порождения формальных объектов, обладающих некоторым полезным свойством (например, свойством задавать одну и ту же функцию в алгребре логических формул или свойством быть общевначимой формулой в исчислении высказываний).
Исчисление задается с помощью аксиом, которые играют двоя- кую роль. Они вместе задают исходное множество объектов, » В.». исчислении Выси»зывлний 222 обладающих нужным свойством, а каждое само по себе является конструктивным носителем (постулатом) некоторого специального свойства абстрактного объекта. Правила вывода играют роль индуктивных определений, позволяющих строить (выводить) новые формальные конструкции по заданным, сохраняя при этом нужные свойства. При построении исчислений уделяется особое внимание возможности формулировать общие утверждения в формальной теории, т. е.
относящиеся сразу к множеству конструкций. Для этого вводятся или особые правила подстановки и замены, или схемы аксиом и рассуждений с использованием метапеременных. Стандартными вопросами для исчислений являются вопросы корректности (замкнутости относительно исследуемого свойства), полноты формальной теории и независимости аксиоматики. Для некоторых читателей эта глава может оказаться первым знакомством с математической логикой.
Перед ними автор должен особо извиниться за неп«)((ноту и некоторую поверхностность излон«ения. Формально этого материала достаточно, чтобы двигаться дальше, не теряя надежды понимать все до конца. Тем же, кого это наложение не удовлетворит, автор рекомендует несколько книг по математической логике, которые, кстати, служили и ему источником большинства определений и доказательств, помещенных в этой главе: 1. ХХ. А.
Лавров, Л. Л. Максимова. Задачи по теории множеств, математической логике и теории алгорит»шв. М., «Наука», 1975. Сжатая сводка основных понятий математической логики с хорошим ассортиментом познавательных и тренировочных задач. 2. П. С. Новиков. Элементы математической логики. М., «Наука», 1973. Вступительный курс, написанный с болыпой заботой о начинающем читателе.
3. Э. )(1«ндельсон. Введение в математическую логику. М., «Наука», 1976. Современный и хорошо организованный вводный курс с весьма концентрированным изложением. 4. С. К. Клики. Введение в метаматематику. М., ИЛ, 1957. Непревзойденный по полноте и отличающийся строгостью куро повышенного типа, но вполне доступный для детального знакомства с основными понятиями. ГЛАВА 7 ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА $7А. Начальные наблюдения Логические операторы в программах. Программа — это конструкция, побуждающая автоматическую машину к действию. Командная часть программы указывает содержание действия, а объектная часть — те данные (объекты), с которыми совершаются действия. В первой части книги мы изучали, в весьма упрощенной постановке, проблему экономного размещения данных в памяти машины.
Размьппляя о командной части программ, мы усматриваем в ней прежде всего два вида действий — преобразование данных (счет) и проверка свойств данных (управленне). Свойства данных в программе задают условия выбора дальнейшего навравления вычислений. Когда программист начинает решать задачу„~ он находит эти условия в содержательной формулировке: «является ли л простым?», «матрица симметрична или нет?», «центром какой области является данный город?», «зацеплены ли компоненты связности информационного графа?», «сломается ли мост при заданной нагрузке?», «выигрышна ли данная шахматная позиция?» Цель нашего исследования во второй части книги — построить некоторую общую теорию программирования условий. Глянув' на приведенный выше список, мы видим, что первое, что нам надо сделать — это разумным образом, сузить задачу. Условия слишком разнообразны, а главное, скрывают в себе решение хотя и частных по отношению к общей программе"задач, но самих по себе достаточно сложных.
Один из подходов к уточнению постановки — это разделить способы формулирования и проверки условий от способов использования результатов проверки для выбора направления вычислений. В любом строгом определении программы это разделение достигается следующим образом.
Вводится особый внд операторов, которые называются логическими операторами. Каждый оператор А состоит из двух частей: (1) некоторой произвольной функции ?, определенной на объектах програм'мы и принимающей одно из и допустимых заранее известных значений с„..., с„, и (2) некоторого множества из к возможных ;преемников г„..., г„оператора А. Функция 1 называется п:вначным предикатом.
Правила языка программирования делают $ ТЛ. НАЧАЛЬНЫЕ НАВЛЮДЕННЯ 227 ив ранее (т. е. при написании программы) известным отображение области значений предиката (сы..., с„) на множество преемников (з„..., з„)е). Работа логического оператора состоит в вычислении значения предиката и в передаче управления на один из операторов з„ ..., ь„, соответствующий вычисленному значению. Следующий шаг состоит в выделении важнешпего частного случая двоичного выбора, к которому по схеме, показанной на рис.
7Л, может быть сведен в-значный выбор (в скобках заметны, угугуу а) Ряс. 7Л. Двои шые реализации я-значного выбора. ° )я-значный выбор. б) Последовательная реализация. е)Каскадная резлизацвяе что крайние случаи последовательной и каскадной реализаций в-аначного выбора требуют одного и того же числа логических операторов в программе, однако среднее число двоичных выборов в первом случае будет порядка л72, а во втором — порядка 1изп). Логические операторы'с двоичными предикатами хороши не' только тем, что они просты, но и тем, что позволяют для своей за-' писи использовать язык логических формул.
При таком подходе' выражения предикатов имеют как бы двухъярусное строение., Первый ярус образуют так называемые влементарвыв логические «) Строго говоря, число преемников не больше числа значений предз~- иата, так как не будет противоречий, если епереключательная сила» предиката будет недонспользована, т.
е. разным его значениям будет соответатве- вать один преемник. Й28 ГЛ.7. ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА предикаты. Вторым ярусом предиката является произвольная логическая формула, в которой выражения элементарных предикатов играют роль независимых переменных, чьи значения истинности вычисляются некоторым внешним по отношению к логическому оператору способом. Такое использование предикатов первого яруса объясняет, почему они называются алементарнымн. Реально же, особенно в языках, допускающих произвольные функциональные обозначения, элементарный предика к может быть сколь угодно сложной вычислительной процедурой.
Весьма развитой является структура логических предикатов в алголе 60. Ниже в бэкусово-науровой форме приведен синтаксис (простого логического выражения) алгола 60. Такие понятия как (неременная), (указатель функции) (т. е. обозначения вычисления функции для заданных значений аргументов) и (простое арифметическое выражение) (т. е. выражение, не содержащее условий) считаются известными *): (знак операции отношения):: = ((( ( = () ( )„-г, (отношение) и = (простое арифметическое 1«ыражение) (знак операции отношения) (простое арифметическое выражение) (логическое значение):: = истина ( ложь (первичное логическое выражение):: = (логическое значение) ( (переменная) ( (указатель функции) ! (отношение) ) ((логическое выражение)) (вторичное логическое выражение)::~ = (первичное логическоэ выражение) ! ) (Первичное логическое выражение) (логический одночлен):: = (вторичное логическое выражение) ( (логический одночлен) б«(вторичное логическое выражение> (логический терм):: = (логический одночлен) ( (логический терм) ~/ (логический одночлен) (импликация) и = (логический терм) ( (импликация) =э (логический терм) (простое логическое выражение):: = (импликация) ( (простое логическое выражение) — (импликация).
Приведем несколько примеров предикатов. а) Условие, что х принадлежит отрезку (О, 1): (х ( 1) 8« (х ) О) . *) Выписано с вамвной английских служебных слое иа руксияв и вилка/~ иа знак А ив публикации «Алгоритмический язык алгол 80. Пврвсмотрвииов сообщвнивв. М., «Мир«, вэбб. 5 Х!.НАЧАЛЬНЫЕ НАБЛЮДЕНИЯ б) Условие, что у находится за пределами полуинтервалов [а, Ь) и (2а, ЗЬ): ) (а(уй у( Ь \/ 2 х а(у8с у(З Х Ь). в) Условие, что точка (Х, г') находится в пределах тригонометрического круга, в его'1-й или 3-й четверти: (Х у 2+ У ) 2(1) й(Х х У) О). г) «Машина голосования» — булеза функция, истинная, когда по крайней мере два из трех логических аргументов истинны. Найти ее выражение проще всего, построив таблицу истинности: По таблице сразу находится совершенная нормальная форма: ~х1йх,йх ~/х181 ~х,йх,~/хгйхзй 1х ~/х181ха8сх.
Правила построения логического оператора всегда предусматривают два возможных направления вычислений, назовем их плюс- направлением и минус-направлением. Плюс-направление связывается с истинным значением предиката-условия, а минус- направление — с ложным. В одних алгоритмических языках плюс-направление указывается меткой, а минус-направление означает следующий текстуально оператор; в других языках оба направления указываются метками, причем первая метка считается плюс-меткой, а вторая— минус-меткой. В алголе 60 плюс-направление указывает на оператор (он может быть, как известно, составной), стоящий между словом то и словом иначе или; .
В случае; минус-направление не требует никаких действий, и происходит переход к следующему текстуально оператору. В случае иначе минус-направление указывает на оператор, стоящий сразу за иначе. Логический оператор в алголе 60 называется условным онератором и вадается о помощью следующего синтаксиса: (условие)н если (логическое выражение) то (безусловный оператор) н (основной оператор) ( (соста- вной оператор> ( (блок) ГЛ., 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
