Основы дискретной математики В.А. Осипова (552659), страница 14
Текст из файла (страница 14)
(гх)А(х) ~<„,, „> — — И. (2.7) 'А(х) ~<аа,аьаг,...,а„> Отсюда (Зх) 1А (х) ~ <ад, аг, ..., а„> (Чх)А(х) ~<аг „, а„> — — Л. ~А(х) ~<а,аьаг, ...,а„> = Л. 76 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2. Вынос квантора за скобки. Пусть формула А(х).содержит свободнуго переменную х, формула В не содержит переменной х и обе они удовлетворяют и. 3 определения формул. Тогда Заметим, что если не требовать, чтобы формула В не содержала переменной х, то будут выполняться только две равносильности: (Чх)(А(х)ЙВ(х)) = (Ух)А(х)ЫгУх)В(х); (Зх)(А(х) у В(х)) = (Зх)А(х) ч (Зх)В(х).
3. Перестановка одноименных кванторов: ~4у)(Чх)А(х, у) = (г7х)(гУу)А(х, у); (Зу)(Зх)А(х, у) = — (Зх)(Зу)А(х, у). 4. Переименование связанных переменных. Заменяя связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А. Докажем для примера выполнимость правила переноса кван- тора через отрицание. Сначала докажем равносильность (2.5), Пусть х;„х;г, ... ..., х;„— множество (быть может, пустое) всех свободных переменных формулы А, отличных от х. Пусть И =< М, 7" > — произвольная интерпретация. Докажем, что на любом наборе значений своих свободных переменных < аь аг, ..., а„>, а; Е М, формулы — (Чх)А(х) и (Зх).
А(х) принимают одинаковые истинностные значения. Возможны два случая: 1) для любого элемента а е М А(х) ~<а,а,,а, „> — — И; 2) для некоторого элемента ае Е М А(х) ~<аа, аыаг,, а > = Л. В первом случае для любого элемента а Е М С другой стороны, в этом случае Отсюда ~(Чх) 4(х) ~<аьаг, .,а > = Л. Во втором случае для элемента ао Е М С другой стороны, в этом случае Отсюда (Чх)А(х) ~<аг а ... а > = И. Равносильность (2.5) доказана. Докажем теперь равносильность (2.6).
Применим равносильность (2.5) к формуле — А(х). Тогда (дх) А(х) = (Зх) А(х) = (Зх)А(х) и применив равносильность 11 основных равносильностей логи- ки высказываний, получим (Зх)А(х) = (Чх) А(х) = (Чх) А(х). 2.3.3. Выполнимость и общезначимость. Проблема разрешимости Рассмотрим некоторую интерпретацию 9Л с множеством М.
Говорят, что формула А выполнима в данной интерпретации, если существует набор < аы а2, ..., а„>, а; Е М, значений свободных переменных х;„х;„..., х;„формулы А такой, что 4 ~<аг, аг,..., а„> Говорят, что формула А истинна в данной интперпретации, если она принимает значение И на любом наборе < аь аг, ... ..., а„>, а; Е М, значений свободных переменных х;„х;„... ..., Хг„° 79 2.3. Логика предккатоа 78 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Говорят, что формула А общезначима или тождественно- истинна (в логике предикатов), если она истинна в каждой интерпретации. Говорят, что формула А выполнима (в логике предикатов), если существует интерпретация, в которой А выполнима.
Формула А общезначима тогда и только тогда, когда формула - А не является выполнимой, и формула А выполнима тогда и только тогда, когда формула — А не является общезначимой. Отметим, что общезначимую формулу называют логическим законом. Очевидно, что если Р и С вЂ” равносильные (в логике предикатов) формулы, то г С вЂ” общезначимая формула. Применив это утверждение к формулам, равносильность которых доказана в рвзд. 2.3.2, получим общезначимые формулы. Приведем несколько примеров общезначимых формул. Формула (Чх)А(х) з А(у), где переменная у не входит в формулу А(х), общезначима.
Формула А(у) ~ (Бх)А(х), где переменная у не входит в формулу А(х), общезначима. Как говорилось выше„одноименные кванторы можно переставлять, следовательно, формулы (Зх)(Зу)А(х, у) (Зу)(Зх)А(х, у), (Ча) (Чу) А(х, у) (Чу) (Чх)А(х, у) общезначимы, Общезначимой является также формула (Зх)(Чу)А(х, у) ~ (Чу)(Зх)А(х, у). Однако формула (Чх)(Зу)А(х, у) ~ (Зу)(Чх)А(х, у) не является общезначимой. Действительно, пусть формула 12) А(х, у) — атомарная формула А~~ (х, у). Рассмотрим интерпретацию, областью которой является множество целых чисел; Р) символу А) поставим в соответствие предикат х ( у.
Тогда формула (Чх)(Зу)А (х, у) истинна в этой интерпретации, а (2) формула (Зу)(Чх)А (х, у) ложна. Задача распознавания общезначимости формул логики предикатов существенно сложнее, чем формул логики высказываний. Так же, как и в логике высказываний, она называется проблемой разрегиимости и ставится следующим образом: указать эффективный способ (алгоритм) распознавания общезначимых формул. Подробнее о понятии алгоритма будет говориться в следующем разделе. В общем случае эта проблема в логике предикатов неразрешима.
Это было установлено американским математиком Алонзо Черчем в 1936 году. Теорема смерча. Не существуетп алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет. Однако в некоторых частных случаях ответ на проблему разрешимости положительный.
Например, если рассматривать формулы логики предикатов, содержащие только одноместные предикатные символы, то такой алгоритм существует. Логика, в которой употребляются только одноместные предикаты, соответствуют логике, описанной еще Аристотелем. 2.3.4. Эффективная вычислимость Для решения однотипных задач иногда целесообразно использовать чисто механические вычислительные процессы. С их помощью искомые величины вычисляются последовательно из данных величин по определенным правилам. Описание таких процессов принято называть алгоритмами.
Вообще говоря, под алгоритмом интуитивно понимается некоторое формальное предписание, действуя согласно которому можно получить решение задачи. Типичными примерами алгоритмов служат решения следующих задач: 1) нахождение наибольшего общего делителя двух положительных натуральных чисел; 2) извлечение квадратного корня из рационального числа с заданной степенью точности; 3) вычисление ранга целочисленной матрицы; 4) определение тождественной истинности формулы логики высказываний.
80 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Перечисленные алгоритмы имеют ряд общих черт, которые естественно считать присущими любому алгоритму: 1) элементарность шагов алгоритма: решение задачи разбивается на этапы, каждый из которых должен бьггь простым и локальным; 2) детерминированность алгоритма: после выполнения очередного этапа однозначно определено, что делать на следующем этапе; 3) направленность алгоритма: должно бьггь указано, что считать результатом применения алгоритма; 4) массовость алгоритма: алгоритм служит для решения не какой-то одной задачи, а целого класса однотипных задач.
Интуитивное понятие алгоритма, хотя и не строго, но настолько ясно, что всегда можно определить, является ли данный процесс алгоритмом. Поэтому удовлетворительным доказательством существования алгоритма считается описание фактического процесса решения какой-либо задачи. Однако для некоторых известных проблем (например, для проблемы установления общезначимости формул логики предикатов) не удавалось найти разрешающего алгоритма. Безуспешные попытки найти такие алгоритмы привели к предположению, что их не существует. Но для того чтобы доказать несуществование алгоритма, надо точно знать, что такое алгоритм. Начиная с 30-х годов было предложено несколько уточнений понятия алгоритма. Считается, что все они достаточно полно отражают основные черты интуитивного понятия алгоритма.
Действительно, все формальные определения алгоритма в некотором смысле эквивалентны друг другу, все алгоритмы в точном смысле являются алгоритмами в интуитивном смысле, и, как показывает опыт, все известные алгоритмы можно задать алгоритмами в точном смысле. Одно из уточнений понятия алгоритма связано с машинами Тьюринга.
Машина Тьюринга — это математическая модель идеализированного вычислительного устройства. Приведем сначала неформальное ее описание: 1. Пусть имеется лента, т. е, полоса, разбитая на конечное число ячеек. В каждой ячейке ленты в каждый момент времени записан один из символов (2.8) ао,ам ...,а„. 2.3. Логика предвквтов Совокупность этих символов называется внешним алфавитом машины. Символ ао — пустой (его обычно обозначают символом 0). В процессе работы машины к существующим ячейкам могут пристраиваться новые пустые ячейки, так что ленту можно считать неограниченной в обе стороны.
2. Каждая машина обладает внутренней памятью, которая может находиться в конечном числе состояний. Состояния внутренней памяти обозначают символами (2.9) Чо Чы -" Чп, отличными от символов (2.8), и называют внутренними состояниями машины. Одно из таких состояний (обычно оо) называют заключительным, а другое (обычно о1) — начальным. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
