Язык логики предикатов

Примеры применения

Использование предикатов

Пусть предикат \(P(x, y)\): \(«x=y»\) обозначает отношение равенства, в котором x и y принадлежат множеству целых чисел. Тогда утверждение P будет истинным для всех равных x и y.
Дан предикат Работает \((x, y, z)\) для отношения «x работает в городе y в компании z».
Дан предикат Нравится \((x, y)\) для «x нравится y» для x и y, которые принадлежат множеству людей N.

Использование кванторов

Пусть предикат «x кратно 5». Тогда с помощью квантора общности можно записать ложные высказывания:

любое натуральное число делится на 5;
каждое натурально число делится на 5;
все натуральные числа делятся на 5.

В этом случае решение будет выглядеть так:

\((\forall_x\in N)P(x).\)

Чтобы обозначить истинные высказывания, используем квантор существования:

существуют натуральные числа, которые делятся на 5;
найдется натуральное число, которое делится на 5;
хотя бы одно натуральное число делится на 5.

В записи оно будет выглядеть так:

\((\exists_x\in N)P(x).\)

На множестве x простых чисел существует предикат: «Простое число является нечетным». Если мы поставим перед предикатом слово «любое», то получим ложное высказывание «Любое простое число является нечетным». Если мы поставим перед предикатом слово «существует», то получим истинное высказывание «Существует простое число, которое является нечетным».

Общая характеристика логики предикатов

Определение 1

Язык логики предикатов – это один из искусственных языков, используемый в современной логике для анализа логической структуры простых высказываний.

Как следует из названия, язык логики предикатов используется в конкретном разделе логики – логике предикатов.

Определение 2

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

Это значит, что выражения рассматриваются знаки функций или знаки аргументов функций

Важной особенностью логики предикатов является то, что в ней к одной категории знаков (категории предикаторов, или предметно-истинностных функторов) относят:. В логике предикатов осуществляется функциональная трактовка выражений языка

Это значит, что выражения рассматриваются знаки функций или знаки аргументов функций. Важной особенностью логики предикатов является то, что в ней к одной категории знаков (категории предикаторов, или предметно-истинностных функторов) относят:

В логике предикатов осуществляется функциональная трактовка выражений языка. Это значит, что выражения рассматриваются знаки функций или знаки аргументов функций

Важной особенностью логики предикатов является то, что в ней к одной категории знаков (категории предикаторов, или предметно-истинностных функторов) относят:

общие имена («человек», «поселок», «жидкость»),
знаки свойств («прозрачный», «белый», «маленький»),
знаки отношений («больше», «южнее», «более щелочная»).

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

Например, предикатор «животное семейства кошачьих» представляет собой функцию, которая кошке поставит в соответствие оценку «истина», а кролику – «ложь».

Функция же , ассоциированная с предикатором «южнее», сопоставляет значение «истина» такой паре географических точек, первая из которых находится южнее второй (например, паре «Сочи, Москва») и ложь другим парам географических точек (например, «Санкт-Петербург, Краснодар»).

Предикаторы могут отличаться «местностью» — количеством аргументов:

если в предикат входит один аргумент, такой предикат называют одноместным;
два аргумента – двухместным и т. д.

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

Существует ряд правил перевода высказываний с естественного языка на язык логики предикатов:

простое высказывание, в которому утверждается о наличии у отдельного предмета какого-либо свойства, записывается в виде формулы P(t), где P – одноместная предикаторная константа, отражающая это свойство, а t – терм, соответствующий имени предиката. Например, высказывание «Яблоко – это фрукт» на языке логики предикатов примет вид P(a), где а – предметная константа «яблоко», а P – предикатный символ «быть фруктом»;
простые высказывания, в которых отрицается наличие у отдельного предмета какого-либо свойства, записывают как отрицание предиката. Например: «Яблоко не является овощем» можно записать как ┐Q(a), где Q – предикатный символ «быть овощем»;
высказывания, утверждающие наличие между двумя или несколькими предметами отношения, записывается с помощью двухместного или n-местного предиката: R(a,b). Например: «Калининград западнее Омска» переведется как R(a,b), где a – Калининград, b – Омск, а предикатный символ R обозначать «быть западнее». Аналогично может быть построено и отрицание (отсутствие отношения);
если высказывание в естественном языке содержит слова «всякий», «каждый», «все» или «существует такой», «для некоторых», при переводе на язык логики предикатов используют кванторы. Квантор записывается перед предметной переменной, к которой он относится, а затем следует предикаторная константа. Квантифицируемые переменные «перебирают» множество всех объектов из универсума рассмотрения, а роль квантора сводится к указанию той части объектов этого универсума, для которой выполнено содержащееся в высказывании утверждение. Например, логическая форма высказывания «Кто-то умён» может быть выражена с использованием квантора существования ∃ и переменной x, пробегающей по множеству людей, так; ∃xP (x), где символ Ρ соответствует одноместному предикатору «умный», а форма высказывания «Каждый знает кого-нибудь» — посредством формулы ∀x∃ yR (x, y), где квантифицируемые переменные x и y пробегают по тому же множеству, а символ R соответствует двухместному предикатору «знает». В зависимости от типа сущностей, составляющих допустимые в теории области пробега квантифицируемых переменных, различают логику предикатов первого порядка и логику предикатов высших порядков.

Кванторные операции над предикатами

Прежде чем изучить квантовые операции, нужно разобраться, что из себя представляет сам квантор.

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание.

Кванторы впервые были определены немецким математиком Готлобом Фреге. Он упомянул их в своей работе «Begriffsschrift» («Исчисление понятий», 1879 года). Однако сам термин был изобретен английским логиком Чарльзом Пирсом в 1885 году. Вместе со словом «квантор» он ввел также и термин «квантификация», который означает измерение качеств признаков.

Обозначение кванторов

Символическое обозначение кванторов придумал итальянский математик Дж. Пеано в 90-е годы XIX века. Выглядят эти символы так:

\(\forall\) — «для любого», «для каждого», «для всех»;

\(\exists\) — «существует», «найдётся».

Кроме самих кванторов и вместе с ними используют обозначения \(«!», «:», «|»\), которые являются сокращениями:

! – «единственный»;

– «такой, что»;

| – «такой, что».

Знак «:» обычно используется в формулировках определений или теорем, которые записываются с помощью кванторов. Знак «|» применяется в определениях множеств.

Квантор общности \(\forall\)

Операция связывания квантором общности — это правило, в соответствии с которым каждому одноместному предикату P(x) во множестве N сопоставляется высказывание \((\forall x)(P(x))\), которое произносится, как «для всякого \(x — P(x)\) ».

Оно истинно только в том случае, когда \(P(x)\) — тождественно истинен. В ином случае данное высказывание ложно.

Операция связывания квантором общности по переменной \(x_1\) — это правило, в соответствии с которым каждому n-местному \((n\geqslant2)\) предикату \(P(x, x_2, …, x_n)\), на множествах \(N_1, N_2, …, N_n\), в соответствие ставится новый \((n-1)\) — местный предикат. Он обозначается как \((\forall x)(P(x, x_2, …, x_n)).\)

Оно истинно только в том случае, когда одноместный предикат \(P(x, a_2, …, a_n)\) на множестве \(N_1\) тождественно истинен. В противном случае оно ложно.

Квантор существования \( \exists\)

Операция связывания квантором существования — это правило, по которому каждому одноместному утверждению \(P(x)\) на множестве N соответствует высказывание \( (\exists)(P(x))\), которое звучит так: « существует \( x\), такое, что \( P(x)\), »).

Это высказывание ложно только, когда \(P(x)\), тождественно ложен. В противном случае оно истинно.

Операция связывания квантором существования по переменной \(x_1\) — это правило, в соответствие с которым каждому n-местному \((n\geqslant2)\) высказыванию \(P(x_1, x_2, …, x_n)\) на множествах \(N_1, N_2, …, N_n\) соответствует новый (n-1-местный предикат. Он обозначается как \((\exists)(P(x_1, x_2, …, x_n)\). Это высказывание ложно только в том случае, если одноместный предикат \((P(x_1, a_2, …, a_n)\) на множестве \(N_1\) тождественно ложен. В противном случае данное высказывание истинно.

Интерпретация[]

В классическом случае интерпретация формул логики первого порядка задается на модели первого порядка, которая определяется следующими данными

Несущее множество D{\displaystyle {\mathcal {D}}},
Семантическая функция σ{\displaystyle \sigma }, отображающая
- каждый n{\displaystyle n}-арный функциональный символ f{\displaystyle f} из F{\displaystyle {\mathcal {F}}} в n{\displaystyle n}-арную функцию σ(f)D×…×D→D{\displaystyle \sigma (f):{\mathcal {D}}\times \ldots \times {\mathcal {D}}\rightarrow {\mathcal {D}}},
- каждый n{\displaystyle n}-арный предикатный символ p{\displaystyle p} из P{\displaystyle {\mathcal {P}}} в n{\displaystyle n}-арное отношение σ(p)⊆D×…×D{\displaystyle \sigma (p)\subseteq {\mathcal {D}}\times \ldots \times {\mathcal {D}}}.

Обычно принято, отождествлять несущее множество D{\displaystyle {\mathcal {D}}} и саму модель, подразумевая неявно семантическую функцию, если это не ведет к неоднозначности.

Предположим s{\displaystyle s} — функция, отображающая каждую переменную в некоторый элемент из D{\displaystyle {\mathcal {D}}}, которую мы будем называть подстановкой. Интерпретация ts{\displaystyle \!]_{s}} терма t{\displaystyle t} наD{\displaystyle {\mathcal {D}}} относительно подстановки s{\displaystyle s} задается индуктивно

xs=s(x){\displaystyle \!]_{s}=s(x)}, если x{\displaystyle x} — переменная,
f(x1,…,xn)s=σ(f)(x1s,…,xns){\displaystyle \!]_{s}=\sigma (f)(\!\!]_{s},\ldots ,\!\!]_{s})}

В таком же духе определяется отношение истинности ⊨s{\displaystyle \models _{s}} формул на D{\displaystyle {\mathcal {D}}} относительно s{\displaystyle s}

D⊨sp(t1,…,tn){\displaystyle {\mathcal {D}}\models _{s}p(t_{1},\ldots ,t_{n})}, тогда и только тогда, когда σ(p)(x1s,…,xns){\displaystyle \sigma (p)(\!\!]_{s},\ldots ,\!\!]_{s})},
D⊨s¬ϕ{\displaystyle {\mathcal {D}}\models _{s}\neg \phi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } — ложно,
D⊨sϕ∧ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \land \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } и D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi } истинны,’
D⊨sϕ∨ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \lor \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } или D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi } истинно,
D⊨sϕ→ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \to \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } влечет D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi },
D⊨s∃xϕ{\displaystyle {\mathcal {D}}\models _{s}\exists x\,\phi }, тогда и только тогда, когда D⊨s′ϕ{\displaystyle {\mathcal {D}}\models _{s’}\phi } для некоторой подстановки s′{\displaystyle s’}, котрая отличается от s{\displaystyle s} только на переменной x{\displaystyle x},
D⊨s∀xϕ{\displaystyle {\mathcal {D}}\models _{s}\forall x\,\phi }, тогда и только тогда, когда D⊨s′ϕ{\displaystyle {\mathcal {D}}\models _{s’}\phi } для всех подстановок s′{\displaystyle s’}, котрые отличается от s{\displaystyle s} только на переменной x{\displaystyle x}.

Формула ϕ{\displaystyle \phi }, истинна на D{\displaystyle {\mathcal {D}}}, что обозначается как D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi }, если D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi }, для всех подстановок s{\displaystyle s}. Формула ϕ{\displaystyle \phi } называется общезначимой, что обозначается как ⊨ϕ{\displaystyle \models \phi }, если D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi } для всех моделей D{\displaystyle {\mathcal {D}}}. Формула ϕ{\displaystyle \phi } называется выполнимой , если D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi } хотябы для одной D{\displaystyle {\mathcal {D}}}.

Логические операции над предикатами

Так как предикаты принимают два значения, «истина» и «ложь» (1 и 0), к ним можно применить все операции алгебры логики.

Представим, что в неком множестве N определены два предикатаP(x) и Q(x). Рассмотрим все операции с ними по-отдельности.

Конъюнкция — предикат \(P(x)^Q(x)\), приминающий значение «истина» исключительно при значениях \(x\in N\), при которых каждый из предикатов принимает значение «истина», а значение «ложь» принимает во всех остальных случаях. Область истины предиката \(P(x)^Q(x)\) — пересечение областей истинности обоих предикатов: \(I_{P^Q}I_P\cap I_Q.\)

Дизъюнкция двух предикатов — предикат \(P(x)\vee Q(x)\), принимающий значение «ложь» исключительно при значениях, когда каждый предикат принимает значение «ложь». Во всех остальных случаях он принимает значение «истина».

Область истины в этом случае — объединение областей истинности обоих утверждений.

\(I_{P\vee Q}I_P\cap I_Q.\)

Отрицание высказывания P(x) — предикат \(\overline{P(x)}\), принимающий значение «истина» при всех значениях \(x\in N\), когда высказывание P(x) принимает значение «истина».

Область истины здесь — дополнение множества истинности утверждения P(x) до множества N, иначе говоря \(I_overline{P}=N\I_P=CI_P.\)

Импликация — предикат \(P(x)\rightarrow Q(x)\), который остается ложным исключительно при тех значениях \(x\in N\), в которых одновременно P(x) — истинно, а Q(x) — ложно, во всех остальных значениях истинно.

При каждом x справедливо равенство \(P(x)\rightarrow Q(x)=\overline{P(x)}\vee Q(x)\), а это значит, что область истинности \(P(x)\rightarrow Q(x)\) — объединение дополнения области истинности P(x) до множества N и области истинности предиката Q(x). Обозначается выражением: \(I_{P\rightarrow Q}=I_\overline P\cup I_Q.\)

Эквиваленция утверждений \(P(x) и Q(x) — P(x)\leftrightarrow Q(x)\), который делает истинным высказывание при всех \(x\in N\), где одновременно \(P(x)\) и \(Q(x)\) принимают одинаковые значения истинности.

При каждом фиксированном x справедливо равенство \(P(x)\leftrightarrow Q(x)=(\overline P\vee Q)\wedge(P\vee\overline{Q)}\). Это значит, что области истинности утверждения \(P(x)\leftrightarrow Q(x)\) — конъюнкция объединений дополнения области истинности \(P(x)\) до множества N и области истинности \(Q(x)\), а также области истинности \(Q(x)\) до множества N и ОИ \(P(x)7\). Обозначается формулой \(I_{P\leftrightarrow Q}=(I_\overline P\cup I_Q)\cap(I_\overline Q\cup I_P).\)