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

Формально интерпретация - это структура вида"

Ш=< M;Pi,...,P-J„...J > .

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

1.2.3. Истинность и выполнимость формул. Модели, общезначимость, логическое следствие

Рассмотрим формулу Л{х1, ...,Хп) и некоторую ее интерпретацию Ш.

Формула A{xi, ...,Хп) называется истинной е интерпретации Ш1 =< М; Pi,Pj,; fl,>, если она истинна при любом выборе Xi = ai,...,Xn = an, где ai,...,Q„ G М.

Формула называется выполнимой в интерпретации Ш1, если она истинна при некотором выборе переменных a;i = a-i ,...,Xn = an, где ai,an e M.

Интерпретация Ш1 называется моделью для совокупности формул Al, ...,Ат-, если они истинны в Ш1. Символически это записывается в виде

m\=Ai,...,Am.

Формула А общезначима, если она истинна в любой интерпретации. Для общезначимой формулы пишем

"0 понятии математической структуры см. в книге Н.Бурбаки «Теория множеств».

Если формула А общезначима, то формула ~iA называется логически ложной, шш противоречием.

Пусть даны две формулы А{х\ , ...,х„) и В{х\ , ...,х„). Формула В является логическим следствием формулы А, если во всякой интерпретации формула В выполнена на каждом наборе переменных х\ = ai,...,Xn = а„, на котором выполнена формула А. Символически для логического следствия используют обозначение

А[=В.

Теорема 1.5. Л [= В тогда и только тогда, когда [= (Л В) .

Формулы A{xi, ...,х„) и B{xi, ...,х„) называются равносильными, ecjm Л [= В и В [= Л. Для равносильных формул используется запись: А = В.

Примеры равносильных формул:

УхА{х)кВ = ЩА{х)кВ] ЧхА{х)кВ = Чх[А{х)кВ\ УхА{х) V В = ЩА{х) V В] БхА{х) УВ = Зх[А{х) V В] (УхА(х) В) = х[А(х) В] {ЗхА{х) В) = Ух[А{х) В] (В УхА{х)) = Ух[В А{х)\ (В ЧхА{х)) = Чх[В А{х)] -,УхА{х) = ЗхА{х) ~пЗхА{х) =Ух~пА{х).

1.2.4. Готлоб Фреге

Готлоб Фреге (Frege) (1848 - 1925) - немецкий логик, математик и философ, основоположник логицизма. Дал первую аксиоматику логики высказываний и предикатов, построил первую систему формализованной арифметики. Один из основоположников логической семантики.

«В неопубликованной при жизни работе «Новая попытка обоснования арифметики» Фреге пришел к выводу, что «арифметика и геометрия и, следовательно, вся математика, проистекают из одного и того же, а именно геометрического источника познания, который

(1.5)

тем самым обретает степень подлинного математического источника познания, при этом, естественно, логический источник познания постоянно выступает вместе с ним» (см.: Frege G. Schriften zur Logik. Aus dem Nachlass. Berlin, 1973. S. 243).

Заслуживает внимания видение рассматриваемой проблемы известным геометром А.Д.Александровым. Он считал, что геометрия в своем существе есть не что иное, как органическое соединение строгой логики с наглядным представлением. Наглядное представление в геометрии пронизывается строгой логикой, а логика Оживляется наглядным представлением» 1301. Рис. 1.3: Г.Фреге (1848- 1925).

1.2.5. Сколемовские функции и сколемизация формул

Формулу А с помощью тождеств (1.5) можно привести к равносильной формуле в предваренной форме, в которой кванторы E,V не перемешиваются, а встречаются группами и все «вынесены влево», т.е. либо к виду

3X1...ЗХп, \/yi...\/yn3zl...4Zns ...Bixi, Xni , 2/1, Уп , 21, «„3, ...),

либо к виду

\/ui...\/UniJvi...4Vn2Wl...\/Wns--IS{ui, ...,Uni,Vl, ...,Vn2,Wl, ..., №„3 , ...)

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

21, ...) = Ем[В(Ж1, 21, ...)&Х(м)],

где Х(м) - произвольная общезначимая формула.

Будем теперь «снимать» в формуле А последовательно группы кванторов слева направо, заменяя их на функции. Путеводной здесь является идея, что пара кванторов VmEd это функция V = /(и). Следовательно, набору кванторов V2/i...V2/n2Зг отвечает функция Zi = ffi(г/1, г/па)- Если самой левой группой кванторов