Равносильные преобразования формул логики предикатов

Содержание
TOC \o "1-3" \h \z \u Введение PAGEREF _Toc72403198 \h 31 Теоретические основы логики предикатов PAGEREF _Toc72403199 \h 41.1 Понятие предиката PAGEREF _Toc72403200 \h 41.2 Законы логики предикатов PAGEREF _Toc72403201 \h 71.3 Построение формул логики предикатов PAGEREF _Toc72403202 \h 81.4 Применение предикатов для записи предложений PAGEREF _Toc72403203 \h 101.5 Метод резолютивного вывода PAGEREF _Toc72403204 \h 132 Равносильные преобразования формул логики предикатов PAGEREF _Toc72403205 \h 152.1 Формы записи формул логики предикатов PAGEREF _Toc72403206 \h 152.2 Решения задач с помощью равносильных преобразований формул логики предикатов PAGEREF _Toc72403207 \h 18Заключение PAGEREF _Toc72403208 \h 23Список использованных источников PAGEREF _Toc72403209 \h 24
ВведениеИзучение математической логики необходимо студентам как для будущей профессиональной деятельности в качестве учителей математики, так и для развития собственной математической культуры, логики и эрудиции. Математическая логика является необходимой основой для последующего изучения следующих дисциплин: дискретная математика, программирование, теория алгоритмов. В работе рассмотрим понятия и способы преобразования формул логики предикатов, раздела современной символической логики, изучающего рассуждения и др. языковые контексты с учётом внутренней структуры входящих в них простых высказываний.
Цель работы: исследовать способы преобразования формул логики предикатов.
Задачи:
изучить понятие формулы логики предикатов;
рассмотреть различные виды записи формулы логики предикатов;
описать алгоритмы изучить преобразования формул логики предикатов;
привести алгоритмы построения стандартных форм формул логики предикатов;
Объектом курсовой работы являются формулы логики предикатов.
Предметом курсовой работы являются способы преобразования формул логики предикатов.
Курсовая работа состоит из введения, двух частей, заключения, списка использованных источников.

1 Теоретические основы логики предикатов1.1 Понятие предикатаПусть А – множество объектов произвольной природы (предметная область предиката), n-местный предикат – произвольное отображение
, .
Пример. Предикат A(x) =«x ≤ 2» на множестве X = R – одноместный. Предикат B(x, y) =«xy > 0» на множестве X = – двуместный.
Если X = {0,1}, то n-местный предикат является n-местной булевой функцией. Нульместный предикат представляет собой высказывание.
Для предикатов определены операции специального вида, которые называются кванторами.
Пусть дан n-местный предикат на множестве X, означающий, что для набора выполнено свойство A, и пусть – одна из переменных. Тогда запись означает, что для всех значений переменной свойство A выполнено. Символ называется квантором всеобщности (общности). Предикат является (n-1)-местным. Он зависит от переменных . Если дан одноместный предикат P(x), то утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.
Для n-местного предиката на множестве X и переменной запись означает, что существует значение переменной , для которой свойство A выполнено. Символ называется квантором существования. Предикат является (n-1)-местным, зависит от переменных , для одноместного предиката P(x) утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.
Пример. На множестве X = R дан предикат A(x) =«x≤2». Высказывание x(x ≤ 2) – ложно, x(x ≤ 2) – истинно.
Запись xA (xA) не подразумевает, что в формуле A есть переменная x.
Переменная x называется переменной в кванторе, а A – областью действия квантора.
Предикат тождественно истинный (тождественно ложный), если при всех возможных значениях переменных он принимает значение 1(0).
Пример. Предложение – одноместный предикат, определенный на множестве N.
– «существует х, для которого верно » – истинное высказывание;
– «для всех x верно » – ложное высказывание.
Предложение – двухместный предикат, определенный на множестве А.
Предикат называется выполнимым, если при некоторых значениях переменных он принимает значение истина.
Пример. Найти значение высказывания .
Трехместный предикат определен на множестве N. Решение:
Пусть = 1. Эквивалентность имеет место тогда и только тогда, когда для некоторого , и предикат является тождественно истинным относительно y, то есть исходное высказывание истинно.
Пусть A – формула, – переменная, которая входит в формулу A (один или несколько раз). Вхождение в формулу A называется связанным, если либо – переменная в кванторе, либо находится в области действия квантора. Если вхождение в A не связано, то оно называется свободным.
В формуле вхождения обеих переменных свободные, в формуле вхождение переменной x связано, а вхождение переменной у свободно.
Для каждого предиката A областью истинности называется множество Y = {x X , A(x) = 1}, на котором предикат принимает значение 1.
Множество истинности предиката ,
.
Для предиката A(x) =«x ≤ 2» на множестве X= областью истинности является множество Y = {x R, x ≤ 2}.
Для предиката B(x, y) =«xy > 0» на множестве X = область истинности Y = {(x, y) , xy > 0}.
Для области истинности пересечения и объединения предикатов верны соотношения:
, .
Следующие предложения означают: – «для всех m верно: m делится на n» или «любое натуральное ненулевое число делится на n» – одноместный предикат, зависит от n, выполнимый предикат, область его истинности – {n=1}, так как все числа делятся на 1;
– «существует m, для которого верно: m делится на n» или «найдется натуральное ненулевое число, которое делится на другое натуральное ненулевое число» – одноместный предикат, зависит от n, тождественно истинный предикат, область его истинности – А;– «для всех n верно: m делится на n» или «натуральное ненулевое число делится на любое натуральное ненулевое число» – одноместный предикат, зависит от m, тождественно ложный предикат, область его истинности –пустое множество;
– «существует n, для которого верно: m делится на n» или «натуральное ненулевое число делится на некоторое натуральное ненулевое число» – одноместный предикат, зависит от m, тождественно истинный предикат, область его истинности – А.1.2 Законы логики предикатовПоскольку множество значений любого предиката лежит во множестве {0,1}, то с предикатами можно производить все операции алгебры логики, и все известные свойства логических операций обобщаются для предикатов. Рассмотрим эти свойства (для удобства в свойствах записываются одноместные предикаты):
1. Коммутативность:
P(x)Q(x) = Q(x) P(x), P(x) Q(x) = Q(x) P(x).
2. Ассоциативность:
P(x) (Q(x) R(x))=(P(x) Q(x)) R(x),
P(x) (Q(x) R(x))=(P(x) Q(x)) R(x).
3. Дистрибутивность:
P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)),
P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)).
4. Идемпотентность: P(x) P(x) = P(x), P(x) P(x) = P(x).
5. Закон двойного отрицания: ¬¬P(x) = P(x).
6. Закон исключения третьего: P(x) ¬P(x) = 1.
7. Закон противоречия: P(x) ¬P(x) = 0 .
8. Законы де Моргана:
¬(P(x) Q(x)) = ¬P(x) ¬Q(x),
¬(P(x) Q(x)) = ¬P(x) ¬Q(x).
9. Свойства операций с логическими константами:
P(x) 1 = 1, P(x) 0= P(x), P(x) 1= P(x), P(x) 0 = 0.
Здесь P(x), Q(x) и R(x) – любые предикаты,
– объединение предикатов,
– пересечение предикатов,
– следствие предикатов,
– эквиваленция предикатов.
Имеют место эквивалентности:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
9) x(P(x) Q(x)) =xP(x) xQ(x);
10) x(P(x) Q(x)) = xP(x) xQ(x);
11) xP(x)xQ(x) = xP(x)yQ( y) =x(P(x) yQ( y)) =
= xy (P(x) Q( y));
12) xP(x) xQ(x) = xP(x) yQ( y) =x(P(x) yQ( y)) =
=xy (P(x) Q( y)).
1.3 Построение формул логики предикатовОпределение формулы логики предикатов:
1) Каждая нульместная предикатная переменная есть формула;
2) если  P – n-местная предикатная переменная, то P(x1,x2…xn) есть формула, в которой все предметные переменные  x1,x2…xn свободны;
3) если  F формула, то  ¬F также формула. Свободные (связанные) предметные переменные в формуле  ¬F те и только те, которые являются свободными (связанными) в F;
4) если  F1,  F2-формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения
F1⋁F2,F1⋀F2,F1→F2,F1↔F2также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул F1,F2 , называются свободными (связанными) и в новых формулах;
5) если  F – формула и  x – предметная переменная, входящая в  F свободно, то выражения  ∀xF, ∃xFи  также являются формулами, в которых переменная  связанная, а все остальные предметные переменные, входящие в формулу  F свободно или связанно, остаются и в новых формулах соответственно такими же;
6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.
Пример. Пользуясь определением формулы логики предикатов проверить, что  выражение является формулой. В формуле указать свободные и связанные переменные. Привести формулу к предваренной форме.
∀yAx,y⋁∃x∀yBx,yРешение:
Таким образом:
Ax,y,Вx,y-формулы, х,у – предметные переменные (свободные);
∀yAx,y- формула, х – свободная переменная,у – связанная;
∃x∀yBx,y- формула, х , у – связанные переменные;
∀yAx,y⋁∃x∀yBx,y- формула, х – свободная переменная в подформуле ∀yAx,y; х , у – связанные переменные в подформуле ∃x∀yBx,y.Приведем формулу к предваренной форме.
Т.к. х – свободная переменная в подформуле ∀yAx,y; х, у – связанные переменные в подформуле ∃x∀yBx,y, чтобы не нарушать связанность и свободность переменных, в первой подформуле переобозначим переменные:
∀tAs,t⋁∃x∀yBx,y.
Вынесем вперед кванторы: ∀t∃x∀y(As,t⋁Bx,y).
Ответ: выражение является формулой, предваренная форма ∀t∃x∀y(As,t⋁Bx,y).
1.4 Применение предикатов для записи предложенийС помощью предикатов можно записывать различные предложения, в том числе математические утверждения.
При этом квантор «» обозначает слова – «любой», «все», «каждый», квантор «» обозначает слова – «существует», «некоторый», «какой-либо», сочетание «» – значит «не все», «» – «никакой».Предложение разбивается на логические части, выбираются переменные, свойства предметных переменных записываются одноместным (двухместным, трехместным) предикатом с помощью кванторов.
Пример. Записать предложение «Все маленькие собаки кусаются, некоторые большие кошки тоже» с помощью предикатов.
Решение:
Предметные переменные – кошки и собаки, свойства – маленькие, большие, кусаются.
Предикаты:
P(x) – x кошка,
Q(x) – x собака,
F(x) – x маленький,
L(x) – x большой,
R(x) – x кусается.
Предложение запишется в виде:
Пример. Записать предложение «Не всякий человек имеет друзей, так как не на всех людей можно положиться» с помощью предикатов.
Решение:
Предметная переменная – человек, свойства – друг, можно положиться.
Предикаты:
P(x) – x человек,
Q(x,у) – x друг у,
F(x) – на x можно положиться.Предложение запишется в виде: .
Пример. Записать предложение «Не все то золото, что блестит» с помощью предикатов.
Решение:
Предметная переменная – золото, свойства – блестит.
Предикаты:
P(x) – x– золото,
Q(x) – x– блестит.
Предложение запишется в виде: .
Запись обозначает – «не все золото блестит», что является ложным.
Пример. Записать предложение «Любые две непараллельные прямые пересекаются в одной точке» с помощью предикатов.
Решение:
Предметные переменные – прямая, точка, свойства – пересекается в точке.
Предикаты:
P(x) – x прямая,
Q(x) – x точка,
L(x,y,z) – x и y пересекаются в z.
Предложение запишется в виде:
.
Пример. Записать утверждение: «числовая последовательность {} имеет пределом число a» формулой логики предикатов и найти инверсию формулы.
Решение:
Запишем данное утверждение с помощью кванторов и обозначим его A:
A = εNn(ε >0→ (n > N → < ε )).
Запишем инверсию (отрицание) данного высказывания:
¬A = εNn (ε >0→ (n > N → < ε ))=
= ε ¬Nn (ε >0→ (n > N → < ε ))=
= εN ¬n (ε >0→ (n > N → < ε ))=
= εN n ¬ (ε >0→ (n > N → < ε )).
Инверсия импликации преобразуется следующим образом:
¬(K → M)= ¬(¬K M)= ¬¬K ¬M = K ¬M .
Отсюда получаем:
¬A = εN n (ε >0¬ (n > N → < ε)) =
= εN n (ε >0¬ (n > N ¬( < ε))) =
= εN n (ε >0¬ (n > N ε)) .
Утверждение ¬A означает, что число a не является пределом числовой последовательности {}.Многие теоремы формулируются в виде условного предложения: «Если любой элемент обладает свойством P(x), то он обладает свойством Q(x)»: .
Очевидно, что если данная теорема неверна, то будет истинным утверждение: .
Поэтому для доказательства несправедливости теоремы нужно указать хотя бы один элемент из множества M , при котором условие P(x) истинно, а значение Q(x) ложно. Другими словами, нужно привести контрпример.
Две теоремы и называются взаимно обратными, так как условие P(x) одной теоремы является заключением второй, а условие Q(x) второй теоремы является заключением первой. При этом одна из них называется прямой теоремой, другая – обратной.
Теоремы и называются взаимно противоположными. В них условие P(x) и заключение Q(x) одной являются отрицанием соответствующего условия и заключения другой. Теоремы и равносильны, на этом факте основывается метод доказательства от противного.
Известно, что если то предикат Q(x) есть следствие предиката P(x):.
Отсюда следует, что предикатявляется истинным для При этом предикат P(x) называют достаточным условием для Q(x), а предикат Q(x) – необходимым условием для предиката P(x).
Если, то , предикаты равносильны.
В этом случае взаимно обратные теоремы истинны при Условие P(x) является необходимым и достаточным для Q(x). Аналогично, условие Q(x) является необходимым и достаточным для P(x).
Пример. Записать на языке предикатов формулировку теоремы о необходимом признаке сходимости числового ряда , .
Решение:
Пусть P(x) – свойство x быть сходящимся рядом, где M = {x} – множество всех числовых рядов; Q(x) – общий член при n. Тогда формула есть запись формулировки данной теоремы.
1.5 Метод резолютивного выводаИдея метода резолюций заключается в том, что доказательство истинности или ложности выдвинутого предположения, например:

ведется методом от противного. Для этого в исходное множество предложений включают аксиомы формальной системы и отрицание доказываемой гипотезы:

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

Любое предложение, из которого образуется клаузальное множество, является совокупностью атомарных предикатов или их отрицаний, соединенных символом дизъюнкции:
Предикат или его отрицание называется дизъюнктом, литералом, атомом, атомарной формулой.
Сущность метода резолюций состоит в проверке того факта, содержит ли клазуальное множество пустое предложение, если не содержащее литер. Если клазуальное множество содержит пустое предложение, то множество противоречиво (невыполнимо). Контрарная пара литер и удаляется из множества, а из оставшихся частей формируется новое предложение (например из и выводится ).

2 Равносильные преобразования формул логики предикатов2.1 Формы записи формул логики предикатовРассмотрим предикат P(x), для него верны формулы пронесения отрицания через кванторы:

Предикатная формула находится в приведенной форме, если в ней использованы только кванторные операции, а также операции инверсии, конъюнкции, дизъюнкции, причем инверсия относится только к предикатным буквам.
Предикатная формула находится в предваренной форме (предваренной нормальной форме), если она имеет вид , где – кванторы всеобщности или существования, а формула A находится в приведенной форме и не содержит кванторов.
Пример. Записать формулу А в предваренной нормальной форме:
A = xy P(x, y) →xy Q(x, y) R(x).
Решение:
A = xy P(x, y) x y Q(x, y) R(x) =
= xy P(x, y) xy Q(x, y) R(x) =
= xy P(x, y) xy Q(x, y) R(x).
Полученная формула записана в приведенной форме. Для того чтобы квантор всеобщности можно было вынести за скобки, переобозначим переменные и выполним преобразования:
A = ty P(t, y) zy Q(z, y) R(x) =
= t(y P(t, y) zy Q(z, y) R(x)) =
= tz (y P(t, y) y Q(z, y) R(x)) =
= tzy( P(t, y) y Q(z, y) R(x)) – предваренная форма.
Пример. Записать формулу в предваренной нормальной форме: .
Решение:
= ==
==
==
==
= =
==.
Это преобразование предназначено для исключения из предикатных формул кванторов существования при сохранении семантики.
Рассмотрим формулу , поскольку квантор существования находится внутри области действия квантора всеобщности, допускается, что х, который «существует», может зависеть от значения у. Пусть эта зависимость определяется явно с помощью некоторой функции f(у), отображающей каждое значение у в х, который существует. Такая функция называется функцией Сколема. С её помощью формула примет вид .
Общее правило исключения из предикатной формулы квантора существования состоит в замене всюду в ней переменной, относящейся к квантору существования, функцией Сколема, аргументами которой служат переменные, относящиеся к тем кванторам всеобщности, области действия которых охватывают область действия исключаемого квантора существования. Функции Сколема не должны совпадать с теми буквами, которые уже имеются в формуле.
Пример. Приведем к сколемовской форме формулу.
Приоритетность действий кванторов, имеющихся в префиксной форме представления, определяются слева направо, следовательно:.
Аналогично ;

Если переменная, связанная квантором существования, является крайней слева, то она заменяется на константу.
Если подобным образом исключить связанные квантором существования переменные, то любые другие переменные, которые встречаются в формуле, будут связаны только квантором всеобщности и поэтому уже не понадобится пояснять это обстоятельство связыванием переменных кванторами. Иначе говоря, так как порядок расположения кванторов всеобщности несущественен, то можно эти кванторы явным образом не указывать (то есть опустить). Такое формальное представление предикатных формул называют сколемовской нормальной формой.
Любое выражение, записанное в СКНФ (сколемовской конъюнктивной нормальной форме), можно представить в виде конъюнкции конечного множества дизъюнкций предикатов и (или) их отрицаний. Для этого необходимо к СКНФ несколько раз применить правило
.
Клаузальной формой называется часть сколемовской формы, ограниченная скобками (часть предикатов, связанных дизъюнкцией). Если, например, если сколемовская форма имеет вид:,
то части формулы, соединенные конъюнкцией, образуют множество:
.
Таким образом, КНФ исходной формулы можно разложить на предложения. Множество предложений, полученных в результате разложения, называется клаузальным множеством. Поскольку любое предложение совершенно независимо от всех других, то между этими предложениями отсутствуют какие-либо взаимосвязи. Поэтому в общем нельзя говорить об эквивалентности формулы логики предикатов и клаузального множества.
2.2 Решения задач с помощью равносильных преобразований формул логики предикатовПример 1.
¬∃xRx∨∀xQx→∀x∃ySx,y∨¬∃xQx→∃xRxДля заданной формулы построить эквивалентную ей предваренную нормальную формуРешение
Преобразуем формулу по законам логики предикатов
¬∃xRx∨∀xQx→∀x∃ySx,y∨¬∃xQx→∃xRx==¬¬∃xRx∨∀xQx⋁∀x∃ySx,y∨¬¬∃xQx⋁∃xRx==∃xRx∨∀xQx⋁∀x∃ySx,y∨¬¬∃xQx∧¬∃xRx==∃xRx∨∀xQx⋁∀x∃ySx,y∨∃xQx∧∀x¬Rx==∃xRx∨∀xQx⋁∀x∃ySx,y∨∃xQx∧∀x¬Rx==(∃xRx∨∃xQx)∨∀xQx⋁∀x(∃ySx,y∧¬Rx)==∃x(Rx∨Qx)∨∀xQx⋁∀x∃y(Sx,y∧¬Rx)==∃t(Rt∨Qt)∨∀sQs⋁∀x∃y(Sx,y∧¬Rx)==∃t∀s∀x∃y(Rt∨Qt∨Qs⋁Sx,y∧¬Rx)==∃t∀s∀x∃y((Rt∨Qt∨Qs⋁Sx,y)∧(Rt∨Qt∨Qs⋁¬Rx))-ПНФ
Ответ:
∃t∀s∀x∃y((Rt∨Qt∨Qs⋁Sx,y)∧(Rt∨Qt∨Qs⋁¬Rx))Пример 2. Привести формулу логики предикатов сначала в ПНФ, затем в СНФ: F=¬∃x(¬∃yPy,a↔Qx)Решение
Применим законы логики высказываний и логики предикатов
Перейдем от операции эквиваленции к дизъюнкции, конъюнкции и отрицанию
F=¬∃x(∃yPy,a&¬Qx˅¬∃yPy,a&Qx)Пронесем отрицание через квантор
F=∀x¬(∃yPy,a&¬Qx˅¬∃yPy,a&Qx)Применим закон де Моргана
F=∀x(¬∃yPy,a˅Qx&(∃yPy,a˅¬Qx))Пронесем отрицание через квантор
F=∀x(∀y¬Py,a˅Qx&(∃yPy,a˅¬Qx))Переобозначим связанную переменную y во второй подформулеF=∀x(∀y¬Py,a˅Qx&(∃sPs,a˅¬Qx))Вынесем вперед кванторы
F=∀x∀y∃s(¬Py,a˅Qx&(Ps,a˅¬Qx)) – ПНФ
Проведем сколемизацию кванторов
F=∀x∀y(¬Py,a˅Qx&(Pf(x,y),a˅¬Qx)) – СНФ
Пример 3. Привести формулу к ПНФ и СНФ.

Решение
Преобразуем формулу согласно законам логики предикатов.
¬∀xAx↔∀x∃yBx,y∃x∀yCx,y==∀xAx+∀x∃yBx,y∃x∀yCx,y==¬(∀xAx)&(∀x∃yBx,y)(∀xAx)&¬(∀x∃yBx,y)∃x∀yCx,y==(∃x¬Ax)&(∀x∃yBx,y)(∀xAx)&(∃x∀y¬Bx,y)∃x∀yCx,y==(∃s¬As)&(∀x∃yBx,y)(∀tAt)&(∃n∀p¬Bn,p)∃l∀mCx,y==∃s∀x∃y∀t∃n∀p(¬As&Bx,yAt&¬Bn,p)∃l∀mCl,m==∃s∀x∃y∀t∃n∀p∃l∀m¬As&Bx,yAt&¬Bn,pCl,m-ПНФ
Проведем сколемизацию:
∃s∀x∃y∀t∃n∀p∃l∀m¬As&Bx,yAt&¬Bn,pCl,m==¬Aa&Bx,f(x)At&¬Bb,pCc,m- ССФ
с константами a,b,c, переменными x,t,p,m.
Ответ:
∃s∀x∃y∀t∃n∀p∃l∀m¬As&Bx,yAt&¬Bn,pCl,m¬Aa&Bx,f(x)At&¬Bb,pCc,mПример 4. Проверить общезначимость формулы методом резолюций.
(∀xQx,y→∃yQx,y)∃xR(x,y)Решение:
¬∀xQx,y→∃yQx,y∃xRx,y=Запишем отрицание формулы и приведем его к сколемовской форме:
¬¬∀xQx,y∃yQx,y∃xRx,y==¬¬∀xQx,y∃yQx,y&¬∃xRx,y==¬¬∀xQx,y&¬∃yQx,y&¬∃xRx,y==∀xQx,y&∀y¬Qx,y&∀x¬Rx,y==∀xQx,y&∀y¬Qx,y&∀x¬Rx,y==∀x(Qx,y&¬Rx,y)&∀y¬Qx,y)==∀x(Qx,y&¬Rx,y)&∀t¬Qs,t)==∀x∀t(Qx,y&¬Rx,y&¬Qs,t)Составим множество дизъюнктов: Qx,y,¬Rx,y,¬Qs,t .
Qx,y,¬Rx,y,¬Qs,tУнифицируем дизъюнкты 1,3: Qx,y, ¬Qx,yРезольвентой дизъюнктов 1,3 является противоречивый дизъюнкт, значит согласно методу резолюции формула является общезначимой.
Ответ: формула является общезначимой.
Пример 5. Проверить общезначимость формулы ¬∃x∀yQx,y→∀y∃xQx,y методом резолюций.
Решение:
Запишем отрицание формулы и приведем его к сколемовской форме:
¬(¬∃x∀yQx,y∀y∃xQx,y)==(¬¬∃x∀yQx,y)&¬∀y∃xQx,y==∃x∀yQx,y&¬∀y∃xQx,y==∃x∀yQx,y&∃y∀x¬Qx,y==∃s∀tQs,t&∃y∀x¬Qx,y==∃s∀t∃y∀x(Qs,t&¬Qx,y==Qa,t&¬Qx,b- сколемовская форма.
Составим множество дизъюнктов: Qa,t,¬Qx,b .
Проведем унификацию дизъюнктов:
Qa,b ¬Qa,bПоскольку получен противоречивый дизъюнкт, т.е. согласно методу резолюции формула является общезначимой.
Ответ: формула является общезначимой.
Пример 6. Проверить рассуждение методом резолюций. Все умные люди учатся в вузе. Все, кто закончил школу с золотой медалью - умные. Иван Савельев закончил школу с золотой медалью. Значит, число Иван Савельев учится в вузе.
Решение:
Введем предикаты:
P(x) – x закончил школу с золотой медалью,
Q(x) – x учится в вузе,
R(x) – х – умный человек
Обозначим как константу А - Иван Савельев.
Схема рассуждения имеет вид:
∀x(R(x)→Q(x)),∀x(P(x)→R(x)), P(А)Q(А)Составим формулу к рассуждению:
∀xRx→Qx∩∀xPx→Rx∩ PА∩¬QА.Приведем ее к сколемовской форме:
∀xRx→Qx∩∀xPx→Rx∩ PА∩¬QА==∀x¬Rx∪Qx∩∀x¬Px∪Rx∩ PА∩¬QА==∀x(¬Rx∪Qx)∩(¬Px∪Rx)∩ PА∩¬QА)Составим множество дизъюнктов: ¬Rx∪Qx,¬Px∪Rx,PА,¬QА.
¬Rx∪Qx¬Px∪RxPА¬QАУнифицируем дизъюнкты 2 и 3: 4х, получим: ¬PА∪RА, резольвента дизъюнктов: RА.
Унифицируем дизъюнкты 1 и 4: 4х, получим: ¬RА∪QА, резольвента дизъюнктов: ¬RА.
Резольвентой дизъюнктов RА, ¬RА является противоречивый дизъюнкт, т.е. согласно методу резолюции формула общезначима, значит рассуждение верно.
Ответ: рассуждение верно.


ЗаключениеЦель курсовой работы достигнута, задачи решены, соотвественно можно сделать следующий вывод.
Логика предикатов первого порядка является дальнейшим развитием традиционной логики Аристотеля и логики высказываний. Одним из ключевых понятий логики высказываний является непосредственно высказывание, логика предикатов позволяет расчленить высказывание, представленное в виде предиката, на предикатный символ (выражение, означающее свойство сущности или тип отношения между сущностями) и терм/термы (выражение/выражения, означающие значение свойства сущности или связываемые отношением сущности).
Обладая всеми достоинствами логики высказываний, логика предикатов позволяет получить доступ к отдельным частям атомарных выражений, что, в свою очередь, расширяет возможности логического вывода.

Список использованных источниковГаврилов, Г. П., Задачи и упражнения по курсу дискретной математики / А. А. Сапоженко. – М.: ФИЗМАТЛИТ, 2006. − 416 с.
Игошин, В. И. Задачи и упражнения по математической логике и теории алгоритмов : учеб. пособие для вузов / В. И. Игошин. – М. : Академия, 2005. – 304 с.
Игошин, В. И. Математическая логика и теория алгоритмов / В. И. Игошин. – М. : Академия, 2004. – 448 с.
Киселева, Л. Г. Логические функции : учебно -методическое пособие. – Нижний Новгород : изд-во Нижегородского гос. ун-та, 2005. − 52 с.
Колмогоров, А. Н.   Введение в математическую логику : учеб. пособие для студ. матем. спец. вузов / А. Н. Колмогоров, А. Г. Драгалин. – М. : МГУ, 1982. – 255 с.
Кузнецов, О. П. Дискретная математика для инженера. – СПб : Лань, 2004. − 400 с.
Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов : учеб. пособие для вузов / И. А. Лавров. – М. : ФИЗМАТЛИТ, 2002. – 255 с.
Лавров, И. А. Математическая логика / И. А. Лавров ; под ред. Л. Л. Максимовой. – М. : Академия, 2006. – 240 с.
Марков, А. А. Введение в теорию кодирования. − М. : Наука, 1982. − 192 с.
Судоплатов, С. В. Математическая логика и теория алгоритмов : учебник / С. В. Судоплатов. – Новосибирск : НГТУ, 2008. – 224 с.
Спирина, М. С. Дискретная математика : учеб. для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. – М. : Академия, 2004. – 386 с.
Успенский, В. А. Вводный курс математической логики : учеб. пособие / В. А. Успенский. – М. : ФИЗМАТЛИТ, 2004. – 128 с.
Шоломов, Л. А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука, 1980. − 400 с.
Яблонский, С. В. Введение в дискретную математику. – М.: Наука, 2000. − 384 с.