Интерпретации - раздел Философия, Глава 1. Основы теории множеств
Формулы Имеют Смысл Только Тогда, Когда Имеется Какая-Нибудь ...
Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов.
Определение. Под интерпретацией мы будем понимать всякую пару, состоящую из непустого множества M, называемого областью интерпретации, и какого-либо отображения, относящему каждому предикатному символу арности n некоторое n-местное отношение на M. При заданной интерпретации предметные переменные мыслятся пробегающими область M этой интерпретации, а связкам и кванторам придается их обычный смысл.
Для данной интерпретации всякая формула без свободных переменных представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации; это отношение может быть выполнено (истинно) для одних значений переменных из области интерпретации и не выполнено (ложно) для других.
Дадим индуктивное определение значения формулы (в данной интерпретации).
Значение формулы F на n-ке <a1, a2,…, an>, aiÎM, своих свободных переменных <x1, x2, …, xn> будем обозначать F|<a1, a2,…, an>.
Формула F есть атомарная переменная A(x1, x2, …, xn), где x1, x2, …, xn - свободные переменные, тогда F|<a1, a2,…, an> есть значение n-местного предиката, сопоставленного предикатному символу A, при соответствующем замещении его переменных элементами a1, a2,…, an.
Формула F имеет вид ØA. Пусть A|<a1, a2,…, an>=e, тогда F|<a1, a2,…, an> =Øe.
Формула F имеет вид AÚB, A&B, AÉB или A~B. Пусть A|<a1, a2,…, an>=a, B|<a1, a2,…, an>=b, тогда F|<a1, a2,…, an> равно соответственно aÚb, a&b, aÉb, a~b.
Формула F имеет вид "x A. Если x1, x2, …, xn - все свободные переменные формулы F, то x, x1, x2, …, xn - все свободные переменные формулы A. Значение "x A|<a1, a2,…, an> = И тогда и только тогда, когда для любого aÎM имеем A|<a, a1, a2,…, an> = И.
Формула F имеет вид $x A. Если x1, x2, …, xn - все свободные переменные формулы F, то x, x1, x2, …, xn - все свободные переменные формулы A. Значение $x A|<a1, a2,…, an> = И тогда и только тогда, когда существует такое aÎM, что A|<a, a1, a2,…, an> = И.
Пример 4.4. Рассмотрим три формулы:
1) A(x, y);
2) "y A(x,y);
3) $x "y A(x,y).
Возьмем в качестве области интерпретации множество целых положительных чисел и интерпретируем A(x, y) как x£y. Тогда первая формула - это предикат x£y, который принимает значение И для всех пар a, b целых положительных чисел таких, что a £ b. Вторая формула выражает свойство: "для каждого целого положительного числа y x£y", которое выполняется только при x=1. Наконец, третья формула - это истинное высказывание о существовании наименьшего целого положительного числа. Если бы в качестве области интерпретации мы рассматривали множество целых чисел, то третья формула была бы ложным высказыванием.
Пример 4.5. Пусть задана следующая интерпретация. M - множество натуральных чисел (0, 1, 2,…), предикатные символы S(x,y,z) и P(x,y,z) обозначают следующие предикаты "x + y = z" и "x ´ y = z" соответственно.
Запишем формулы, истинные на M тогда и только тогда, когда выполнены следующие условия:
1) x = 0;
2) x = 1;
3) x - четное число;
4) x - простое число;
5) x = y;
6) x £ y;
7) x делит y;
8) коммутативность сложения.
Ответы:
1) F1(x) = "y S(x, y, y), так как x+y=y для любого y тогда и только тогда, когда x = 0;
2) F2(x) = "y P(x, y , y);
3) F3(x) = $y S(y, y, x);
4) F4(x) = ØF1(x)&ØF2(x)&("y "z (P(y, z, x) É (F2(y)ÚF2(z)))), где F1, F2 - формулы, определенные в пп. 1 и 2;
5) F5(x, y) = "z "u (S(x, z, u) É S(y, z, u));
6) F6(x,y) = $z S(x, z, y);
7) F7(x,y) = $z P(x, z, y);
8) "x "y "z (S(x, y, z) É S(y, x, z).
Пример 4.6. Пусть f(x) - произвольная фиксированная функция, заданная на отрезке [a, b].
1. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,d) обозначает |x-x0|<d, Q(x, e) обозначает |f(x) - A|<e, R(e) обозначает e>0. Здесь x0 -фиксированный элемент отрезка [a,b]; A - некоторое фиксированное действительное число. Тогда утверждение о том, что A - предел функции f(x) при x®x0, записывается формулой
"e $d "x ((R(e)&P(x, d))É Q(x, e)).
2. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,d) обозначает |x-x0|<d, S(x, e) обозначает |f(x) - f(x0)|<e, R(e) обозначает e>0. Здесь x0 -фиксированный элемент отрезка [a,b]. Тогда утверждение о том, что функция f - непрерывна в точке x0 записывается в виде формулы
"e $d "x ((R(e)&P(x, d))É S(x, e)).
3. Рассмотрим интерпретацию: M - множество действительных чисел, P(x,x1,d) обозначает |x-x1|<d, S(x, x1, e) обозначает |f(x) - f(x1)|<e, R(e) обозначает e>0, D(x) обозначает xÎ[a,b]. Тогда утверждение о том, что функция f - непрерывна на отрезке [a,b] записывается в виде формулы
"x1 "e $d "x ((D(x1)&R(e)&P(x, x1, d))É S(x, x1, e)).
Все темы данного раздела:
Начальные понятия теории множеств
Понятие множества является основным, неопределяемым понятием, поэтому мы можем его только пояснить, например, с помощью следующего псевдоопределения.
Определение:
Интуитивный принцип объемности
Определение. Множества Aи B считаются равными, если они состоят из одних и тех же элементов.
Записывают A=B, если A и B равны, и A
Отношения
Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары <
Функции
Определим понятие "функция", следуя Дирихле. По сути дела при таком определении мы отождествляем функци
Эквивалентность
Одним из самых важных типов отношений является отношение эквивалентности на множестве.
Определение. Рефлексивное, симметричное и транзитивное отношение r н
Зачем мы изучаем математическую логику?
Логика есть наука о законах и формах познающего мышления. Логика изучает мышление, но не всякое мышление, а лишь те мыслительные процессы, которые направлены на обнаружение и обосно
Высказывания
Мы начинаем изучать математическую логику со сравнительно ограниченного и нетрудного ее раздела, чтобы затем иметь возможность продвигаться вширь и вглубь. Этот раздел посвящен изуч
Логические связки
Грамматическими средствами в разговорном языке из нескольких высказываний можно составить сложное (составное) высказывание. Например, с помощью союзов "и", "или"
Формулы логики высказываний
Мы определим формальный язык для описания логики высказываний. Это описание чисто синтаксическое и оно не требует, чтобы формулы логики высказывания имели какую-то семантику (смысл)
Равносильность формул
Пусть A и B - две формулы и {X1, X2,…, Xn} - множество всех выск
Определение.
· Формула называется выполнимой, если на некотором наборе распределения истинностных значений переменных она принимает значение И.
· Формула называется тождественно-ложной ил
Нормальные формы формул
Содержание этого параграфа изложим, следуя [24].
Будем рассматривать формулы, содержащие только логические операции &, Ú, Ø. Символы & и Ú назы
Разрешимость для логики высказываний
Проблемой разрешимости для логики высказываний называют следующую проблему: существует ли алгоритм, который позволил бы для произвольной формулы в конечное число шагов определить, я
Абстрактное определение булевых алгебр
Определение.Множество элементов B с заданным на нем двуместными операциями &Ugra
Модель исчисления высказываний
Пусть B - множество высказываний с обычными логическими операциями конъюнкции, дизъюнкции и отрицания и равенство высказываний интерпретируется как их равносильность.
Во второй главе показ
Булевы функции. Теорема о нормальной булевой форме
Рассмотрим еще одну модель булевой алгебры.
Определение. Пусть M - произвольная булева алгебра с базисными операциями Ù, Ú, Ø. Рассмот
Определение.
Если булева алгебра M - двухэлементна (т. е. содержит только Ë и Î), то булевы функции называются двоичными функциями.
Если в двухэлементной булевой алгебре элементы &Eum
Полные системы булевых функций
Определение.Система функций {f1, f2,…, fn} называется полной, если любая булева функция может быть выражена через функции f
Переключательные элементы
Пусть имеется "черный ящик" - некоторое устройство, внутренняя структура которого нас не интересует, а известно лишь, что оно имеет n упорядоченных "входов" (например, занумеров
Формулы логики предикатов
Существуют такие виды логических рассуждений, которые нельзя формализовать на языке логики высказываний. Вот примеры таких рассуждений:
1. Каждый любит сам себя. Значит, ко
Выполнимость и общезначимость
Определение.Формула A выполнима в данной интерпретации, если существует такой набор <a1, a2,…, an>, aiÎM, значений св
Формальные аксиоматические теории
Формальная теория представляет собой множество чисто абстрактных объектов (не связанных с внешним миром), в которой представлены
Исчисление высказываний
Оказывается множество тавтологий логики высказываний можно описать в рамках простой формальной аксиоматической теории - исчисления высказываний.
Определим исчисление высказ
Теорема 5.2
1. Любая аксиома в исчислении высказываний является тавтологией.
2. Любая теорема в исчислении высказываний является тавтологией.
Доказательство. То, что каждая аксиома A1-A3 явля
Исчисление предикатов
Исчисление предикатов - это аксиоматическая теория, символами которой являются, по существу, те же символы, что и в логике предикатов:
1) символы предметных переменных: x
Теорема 5.4
1. Аксиомы исчисления предикатов - общезначимые формулы.
2. Формула, получающаяся из общезначимых формулы по любому из правил вывода 1-4, является общезначимой.
3. Любая доказуема
Логический вывод
Терпеть не могу логики. Она всегда банальна и нередко убедительна.
Оскар Уайльд
Формальная математика основывается на аксиоматическом методе. Внача
Метод резолюций
Логическое программирование является, пожалуй, наиболее впечатляющим примером применения идей и методов математической логики (точнее, одного из ее разделов - теории логического выв
Неполнота математики
Таким образом, показано, что класс всех теорем исчисления предикатов совпадает с классом общезначимых формул. На этом примере мы видим силу формального аксиоматического метода. Но н
Понятие алгоритма и неформальная вычислимость
В этом разделе будет уточнено понятие алгоритма. Кроме того, будут даны строгие математические понятия, которые формализуют представление о том, что некоторые функции поддаются вычи
Определения
Этот подход к формализации понятия алгоритма принадлежит Гёделю и Клини (1936).
Основная идея Гёделя сос
Ламбда - исчисление
Значение ламбда-исчисления
Ламбда-исчисление было изобретено Алонсом Чёрчем около 1930 г. Чёрч первоначально строил l-исчисление как часть
Машины Тьюринга
Рассмотрим еще один способ определения вычислимых функций, следуя в изложении [29, стр. 12-14]. Ф
Тезис Чёрча
За последние 60 лет было предложено много различных математических уточнений интуитивного понятия алгоритма. Три из этих подхода мы разобрали. Перечислим некоторые другие альтернати
Некоторые алгоритмически неразрешимые проблемы
Определение. Предикат M(x) называется разрешимым, если его характеристическая функция, задаваемая формулой
cM(x
Сложность алгоритмов
Применение математики во многих приложениях, требует как правило, использования различных алгоритмов. Для решения многих задач не трудно придумать комбинаторные алгоритмы, сводящиес
NP-трудные и NP-полные задачи
Различные задачи, относящие к классу NP являются эквивалентными относительно некоторого отношения, которое мы сейчас определим.
Определение. Задача Q по
Трехзначная система Я. Лукасевича
Эта пропозиционная логика была построена Я. Лукасевичем в 1920 году [34]. Лукасевич обозначил «истину» за «1», «ложь» за «0» и ввел третье значение – «нейтрально» - ½. Основными функциями им
Логика Гейтинга
Из закона исключенного терьего в двузначной логике выводятся:
1. ØØх É х 2. х É ØØх
Гейтинг создал трехзначную пропозицио
Трехзначная система Бочвара Д.А.
Система создавалась Бочваром Д.А. [36] для разрешения парадоксов классической математической логики методом формального доказательства бессмысленности определенных высказываний. Нап
К - значная логика Поста Е.Л.
Логика Поста [37] является обобщением частного случая – двузначной логики, когда К=2. Действительно, по Посту значения истинности принимают значения 1, 2,…,К (при К ³ 2 и К – к
Цели и задачи дисициплины
Цели преподавания дисциплины является ознакомление студентов с основами математической логики, теории алгоритмов с методами оценки сложности алгоритмов и построения эффективных алгоритмов.
Наименование тем
Введение
История развития математической логики и теории алгоритмов. Математическая логика и основания математики. Теория алгоритмов и принципиальные возмож
КОНТРОЛЬНАЯ № 2
Вариант 1
1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний:
"Для того, чтобы x бы
Новости и инфо для студентов