Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Логика высказываний и логика предикатов.

Формулы. Синтаксис и семантика формул.

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

При определении используется алфавит, состоящий из символов:

1) буквы U,V,W,X,Y,Z и др.

2) цифры 0 -9;

3) символы истины и лжи (могут быть изображены цифрами 1 и 0, если это не вызывает противоречий);

4) логические связки: &, v, , É, ~;

5) скобки: (, );

Определение 2.1.1. Атомарными формулами логики высказываний называются буквы U,V,W,X,Y,Z и др. с индексами (цифрами) и без них, а также символы истины и лжи.

Определение 2.1.2. Формулами логики высказываний называются

1) атомарные формулы;

2) выражения вида (F&G), (FvG), (F), (FÉG), (F~G), где F и G –

формулы логики высказываний.

Пример 2.1.1

(X&Y)É(XvZ), ((X&Y)ÉZ) –формулы,

X&YvZ, X~YÉZ – не формулы

Соглашение о скобках.

Для уменьшения количества скобок

q во-первых, самые внешние скобки в формуле можно опускать,

q во вторых, вводится приоритет связок.

o имеет наивысший приоритет,

o & и v имеют более низкий одинаковый приоритет,

o É и ~ имеют также одинаковый еще более низкий приоритет.

Таким образом, формулу ((X&Y) ÉZ) можно записать так: X&YÉZ.

Определение 2.1.3. Подформулой атомарной формулы является она сама. Подформулами формулы F являются она сама и все подформулы формулы F. Подформулами формул F&G, FvG, FÉG, F~G являются они сами и все подформулы формул F и G/

Пример 2.1.2

Формула F=X&YÉXvZ имеет шесть подформул: X, Y, Z, X&Y, XvZ, X&YÉXvZ.

Семантика.

Неформально семантика формул логики высказываний определяется следующим образом:

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

· (F&G) - называется конъюнкцией высказываний F и G; соответствует высказыванию «F и G»;

· (FÚG) - называется дизъюнкцией высказываний F и G; соответствует высказыванию «F или G»;

· F - называется отрицанием высказывания F; соответствует высказыванию «не F»;

· (FÉG) - называется импликацией высказываний F и G; соответствует высказыванию «если F то G»;

· (F~G) - называется эквиваленцией высказываний F и G. соответствует высказыванию «F тогда и только тогда, когда G».

Формально семантика формул логики высказываний определяется с использованием понятия «интерпретация» (см. далее).

Перейдем теперь к изложению теории, которая является расширением логики высказываний и называется логикой предикатов первого порядка. Для краткости ее называют просто логикой предикатов или просто логикой первого порядка. Отличие и преимущество логики предикатов в том, что простые высказывания в ней не являются неделимыми, как в логике высказываний, а выражаются в виде отношений между предметными переменными и константами. Например, следующие высказывания «Всякое целое число является рациональным», «Число 2 – целое», «2 – рациональное число» с точки зрения логики высказываний являются различными, не связанными друг с другом. С точки зрения логики предикатов высказывания «Всякое целое число» и «Число 2 – целое» связаны с общим отношением «Быть целым числом». Также связаны высказывания «Число является рациональным» и «2 – рациональное число».

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

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

При определении используется алфавит, состоящий из символов:

1) предметные переменные, обозначаются буквами x, y, z и др. и предметные константы;

2) функциональные символы, обозначаются буквами f, g, h и др.;

3) предикатные символы, обозначаются буквами P, Q, R и др.;

4) символы истины и лжи;

5) логические связки: &, v, , É, ~;

6) скобки: (, );

7) кванторы

Определение 2.1.4. Термом называется

1) предметная переменная или константа;

2) выражение вида f(t₁,…,t_n), где t₁,…,t_n – термы, а f – n-местный функциональный символ.

Определение 2.1.5. Атомарной формулой называется выражение вида P(t₁,…,t_n), где t₁,…,t_n – термы, P – символ n-местного предиката.

Определение 2.1.6. Формулой логики первого порядка называется

1) атомарная формула,

2) выражения вида (F)&(G), (F₁)v(G), (F), (F)É(G),(F) ~ (G), , где F и G – формулы логики предикатов, x – переменная.

Формула F в двух последних выражениях называется областью действия квантора по переменной x.

Примем соглашение о приоритете операций, в котором к принятому в логике высказываний (см. выше «Соглашение о скобках»), добавим следующее:

o кванторы имеют одинаковый приоритет, который выше приоритета всех связок.

Пример 2.1.3

P(f(x,y),g(x))&Q(x,y), , ((P(f(x,y),g(x))&Q(x,y))ÉR(g(x))) –формулы,

Q(x,y)& Q(x,y)v Q(x,y), Q(x,y)~ Q(x,y)É Q(x,y) – не формулы

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

Пример 2.1.4

,

Первое и второе вхождение переменной x свободны, третье связано. Все вхождения переменной y связаны.

Определение 2.1.8. Переменная называется свободной в формуле, если существует хотя бы одно свободное вхождение переменной в формулу.

Если x₁,…,x_n – свободные переменные формулы F, то эту формулу будем обозначать через F(x₁,…,x_n).

Для неформального представления о семантике формул логики предикатов к соответствующему описанию для логики высказываний (см. выше «Семантика») добавим следующее:

· предметные переменные и константы обозначают некоторые объекты рассматриваемой предметной области, например, числа, люди, автомобили и т. д., в зависимости от того, какая задача решается;

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

· предикатные символы обозначают отношения между объектами, например, отношения сравнения чисел (<, >, и т. д.), отношения между людьми (родственные, дружеские, производственные и т. д.), отношения между людьми и автомобилями (автомобиль принадлежит человеку и т. д.);

· соответствует высказыванию «Для каждого x выполняется F», квантор называется квантором всеобщности;

· соответствует высказыванию «Существует x, для которого выполняется F», квантор называется квантором существования.

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