Процесс доказательства методом резолюций.
Используется доказательство методом от противного. Отрицание заключения принимается в качестве дополнительной посылки.
1. Все посылки и отрицания заключения привести к нормальной форме. Для этого используются следующие равносильности:
При необходимости применяются законы де Моргана:
.
2. Все полученные в 1–м пункте дизъюнкты записываются с новой строки (включая отрицание заключения). В результате получается последовательность формул или последовательность дизъюнктов.
3. В полученной последовательности находим любые две формулы, в одной из которых находится атом, а в другой отрицание атома. Положение атомов в формуле роли не играет. Эти две формулы соединяем с помощью правила резолюций и получаем новую формулу без этого атома.
4. Затем ищут следующую пару формул аналогичным образом, в одной из которых атом, а в другой отрицание, и соединяют эти две формулы с помощью правила резолюций и т.д.
Аналогичным образом продолжают до тех пор, пока не появится пустой дизъюнкт , который и выражает противоречие.
Преимущества использования правила резолюций:
1) В этом методе используется лишь одно правило – это правило резолюций. Не надо запоминать многочисленные правила вывода и теоремы классического исчисления высказываний.
2) В процессе доказательства не надо использовать различные равносильности для проведения простых преобразований.
3) Метод прост в реализации.
Замечание. На основе этого правила разработан язык логического программирования – Пролог.
Пример. 
. Доказать выводимость.
1) 
; 
;
2) 
– гипотезы
Дизъюнкты: 1. 
;
2. 
;
3. 
;
4. 
;
5. 
;
3) 6. 
(2, 4)
7. 
(3, 5)
8. 
(1, 6)
9. 
– ложь.
При практической реализации этого метода, несмотря на простоту метода доказательства, может возникнуть ряд проблем. Последовательность может содержать большое количество формул. Возникает проблема, какие формулы соединить с помощью правила резолюции и как быстрее достичь цели. Для решения этих проблем разработаны специальные методики поиска.
5. ЛОГИКА ПРЕДИКАТОВ
5.1. Определение предиката
Понятие предиката обобщает понятие высказывания, а логика предикатов представляет собой дальнейшее развитие логики высказываний.
Предикат – предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить истинно оно или ложно. Дадим определение предиката.
Определение 1. n–местным предикатом, заданным на множестве М1´М2´…´Мn называется выражение, содержащее n переменных x1, х2, ..., хn, которое становится высказыванием при подстановке вместо этих переменных элементов а1, а2, ..., аn, из множеств М1, М2, ..., Мn соответственно.
Предикаты обозначаются как Р(х1, х2, ..., хn) и представляют собой отображения Р: М1´М2´…´Мn 
{0,1}. То есть, упорядоченному набору элементов (а1, а2, ..., аn) из множества М1´…´Мn ставится в соответствие один из элементов множества {0,1}, причем 0, если Р(а1, а2, ..., аn) – ложное высказывание и 1, если истинное. Переменные х1, х2, ..., хn называются предметными, а элементы из множеств М1, М2, …, Мn, которые эти переменные пробегают – конкретными предметами. Местностью предиката называется число различных аргументов, от которых зависит предикат. Предикат является функцией многих переменных.
Примеры
1. Предложение "х – четное число" представляет собой одноместный предикат, заданный на множестве целых чисел, то есть Р: Z®{0, 1}. Областью определения предиката Р является множество целых чисел Z, областью значений – множество {0, 1}.
2. Отношения "х < у" и "х делится на у"представляют собой двуместные предикаты, заданные на множествах R´R и Z´Z соответственно.
Определение 2. Множеством истинности предиката Р(х1, х2, ..., хn), заданного на множестве М1´М2´…´Мn, называется совокупность таких упорядоченных наборов элементов (а1, а2, ..., аn) из М1´М2´…´Мn, для которых высказывание Р(а1, а2, ..., аn) является истинным.
Обозначение: P+ ={(а1, а2, ..., аn): l( Р(а1, а2, ..., аn)) =1}.
Примеры.
1. Множеством истинности двухместного предиката Р(х, у):"х делится на у", заданного на множестве М´М,
где М = {1, 2, 3, 4, 5, 6}, является следующее множество Р+ = {(1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (4, 2), (6, 2), (6,3)}.
2. Множество истинности двуместного предиката Р(х,y): "x < у", заданного на множестве М1´М2, где М1 = {1, 2, 3}, М2 = {2, 4, 6}, равно P+ = {(1,2), (1,4), (1,6), (2,4), (2,6), (3,4), (3,6)}.
Определение 3.Два предиката Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn), заданные на одном и том же множестве М1´М2´…´Мn, называются равносильными, если оба предиката принимают истинные значения на одних и тех же наборах (а1, а2, ..., аn) из множества М1´М2´…´Мn, то есть, если Р+= Q+. Предикат Q(х1, х2, ..., хn), заданный на множестве М1´М2´…´Мn называется следствием предиката Р(х1, х2, ..., хn), заданного на том же множестве, если он становится истинным высказыванием при всех значениях переменных х1, х2, ..., хn из соответствующих множеств М1, М2, ..., Мn, при которых истинным высказыванием становится предикат Р(х1, х2, ..., хn), то есть, если 
.
5.2. Логические операции над предикатами
Определение 4. Отрицанием предиката Р(х1, х2, ..., хn), заданного на множестве М1´М2´…´Мn, называется новый предикат 
(х1, х2, ..., хn), заданный на том же множестве, который становится истинным высказыванием при таких значениях (а1, а2, ..., аn) из множества М1´М2´…´Мn, при которых Р(а1, а2, ..., аn) является ложным высказыванием и становится ложным высказыванием, если Р(а1, а2, ..., аn) является истинным высказыванием.
Например, отрицанием одноместного предиката Р(х): "х делится на 3", заданного на множестве М = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} будет предикат 
: "х не делится на 3". Множествами истинности предикатов Р и являются следующие множества Р+= {0, 3, 6, 9}, ( 
)+ = {1, 2, 4, 5, 7, 8}.
Множество истинности предиката является дополнением множества Р+,то есть 
( M – область определения предиката).
Определение 5. Конъюнкцией двух n–местных предикатов Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn), заданных на множестве М1´М2´…´Мn, называется новый n–местный предикат Р(х1, х2, ..., хn) 
Q(х1, х2, ..., хn), который становится истинным высказыванием только для таких элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn, для которых Р(а1, а2, ..., аn) и Q(а1, а2, ..., аn) являются истинными высказываниями.
Определение 6. Дизъюнкцией двух n–местных предикатов Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn), заданных на множестве М1´М2´…´Мn, называется новый n–местный предикат Р(х1, х2, ..., хn) Ú Q(х1, х2, ..., хn), который становится ложным высказыванием только для таких элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn, для которых Р(а1, а2, ..., аn) и Q(а1, а2, ..., аn) являются ложными высказываниями.
Определение 7. Импликациейдвух n–местных предикатов Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn), заданных на множестве М1´М2´…´Мn, называется новый n–местный предикат Р(х1, х2, ..., хn) 
Q(х1, х2, ..., хn), который становится ложным высказыванием только для таких элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn, для которых Р(а1, а2, ..., аn) является истинным высказыванием, а Q(а1, а2, ..., аn) является ложным. В остальных случаях – истинным.
Определение 8. Эквивалентностью двух n–местных предикатов Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn), заданных на множестве М1´М2´…´Мn, называется новый n–местный предикат Р(х1, х2, ..., хn) 
Q(х1, х2, ..., хn), который становится истинным высказыванием только для таких элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn, для которых высказывания Р(а1, а2, ..., аn) и Q(а1, а2, ..., аn) либо одновременно являются истинными, либо ложными. В остальных случаях – ложным.
Если предикаты Р(х1, х2, ..., хn) и Q(y1, y2, ..., ym) заданы на разных множествах, то в результате применения операций конъюнкции, дизъюнкции, импликации и эквивалентности к этим предикатам, получим (n + m – k)–местный предикат, где k – число переменных, общих для обоих предикатов.
Кванторные операции
Кроме операций отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности в логике предикатов имеются две кванторные операции: квантор всеобщности( 
) и существования( 
). Если Р(х) одноместный предикат, заданный на некотором множестве М, то в результате применения кванторов к предикату Р(х) получим новые предикаты P(x) и Р(х), означающие соответственно "все х из М обладают свойством Р"и "некоторые х из М обладают свойством Р".
Пример 1.Пусть Р(х) одноместный предикат "х делится на 7", заданный на множестве целых чисел Z. Применяя к этому предикату кванторы получим следующие предикаты: "все х из Z делятся на число 7" и "существуют х из Z, которые делятся на число 7". То есть, в результате применения кванторов ( ) и ( ) к одноместному предикату Р(х)получили высказывания, причем первое из них ложное, а второе – истинное. Высказывания являются нульместными предикатами.
Применение кванторов к предикатам понижает местность исходного предиката на единицу. Если Р(х1, х2, ..., хn) n–местный предикат, то в результате применения кванторов получим новые предикаты Q(х2, ..., хn)= 
Р(х1, х2, ..., хn), R(х2, ..., хn)= 
Р(х1, х2, ..., хn), которые зависят только от переменных х2, х2, ..., хn,то есть являются (n – 1)–местными предикатами.
Предметная переменная, которая связывается квантором, то есть входит в предикат и в квантор, называется связанной. Предметная переменная, не связанная никаким квантором, называется свободной переменной.
Пример 2.Пусть Р(х, y)двухместный предикат, заданный неравенством "х2 + у2 
1" на множестве R´R. Множеством истинности предиката Р(х, y)является множество всех точек координатной плоскости, расположенных внутри окружности радиуса 1, включая точки окружности. Найдем множества истинности предикатов Q(y)= 
x P(x, y), R(x)= 
у Р(х, у), S = x y P(x, y). Множеством истинности предиката Q(y)является множество таких у, для которых данное неравенство выполняется при любых х из R. Однако таких у не существует. Следовательно, множество истинности предиката Q не содержит ни одного элемента, то есть Q+ =Æ. Множеству истинности предиката R(x)принадлежат все такие х, для которых можно найти число у, удовлетворяющее данному неравенству. Такие значения х лежат в промежутке [–1, 1]. Следовательно, этот промежуток и будет множеством истинности предиката R. Предикат S – нульместный, то есть является высказыванием. В высказывании S говорится, что для любых х можно найти такое у, для которой выполняется данное неравенство. Однако это не верно. Например, для х,лежащих вне отрезка [–1, 1], такое у не существует. Тогда S – ложное высказывание.
5.3. Теоретико–множественный смысл предикатов
При определении множества истинности предиката, составленного из нескольких предикатов при помощи логических связок, можно воспользоваться соотношениями для их множеств истинности. Для двух n–местных предикатов Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn) заданных на множестве М1´М2´…´Мn, верны следующие соотношения для их множеств истинности:
1) множество истинности отрицания предиката Р равно дополнению множества истинности этого предиката, то есть 
;
2)множество истинности конъюнкции двух предикатов Р и Q равно пересечению множеств истинности Р+ и Q+, то есть 
;
3) множество истинности дизъюнкции двух предикатов Р и Q равно объединению множеств истинности Р+ и Q+, то есть 
;
4) множество истинности импликации двух предикатов Р и Q равно 
;
5) множество истинности эквивалентности двух предикатов Р и Q равно 
.
Пример. Пусть предикаты Р(х):"х кратно двум" и Q(x): "х кратно трем", заданы на множестве М = {1, 2, 3, 4, 5, 6, 7, 8}. Их множествами истинности являются следующие множества: Р+ = {2, 4, 6, 8}, Q+ = {3, 6}. Тогда, по соотношениям (1)–(5) получим
а) 
{1, 3, 5, 7}, 
{l, 2, 4, 5, 7, 8};
б) 
{3, 6} = {6};
в) 
= {2, 4, 6, 8} 
{3,6}= {2, 3, 4, 6, 8};
г) 
={1, 3, 5, 7} {3,6} ={1, 3, 5, 6, 7};
д) 
={1, 3, 5, 6, 7} {1, 2, 4, 5, 6, 7, 8}= {1,5,6,7}.
5.4. Классификация предикатов
Определение 9.Предикат Р(х1, х2, ... хn), заданный на множестве М1´М2´…´Мn, называется тождественно истинным, если для всех элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn высказывания Р(а1, а2, ..., аn) будут истинными и тождественно ложным, если для всех элементов (а1, а2, ..., аn) из множества М1´М2´…´Мn, высказывания Р(а1, а2, ..., аn) будут ложными. Предикат Р(х1, х2, ... хn), заданный на множестве М1´М2´…´Мn, называется выполнимым, если существует хотя бы один элемент (а1, а2, ..., аn) из множества М1´М2´…´Мn, для которого высказывание Р(а1, а2, ..., аn) будет истинным и опровержимым, если хотя бы для одного элемента (а1, а2, ..., аn) из множества М1´М2´…´Мn высказывание Р(а1, а2, ..., аn) будет ложным.
В соответствии с классификацией предикатов истинность нульместных предикатов, содержащих кванторы, можно определить следующим образом. Высказывание "x P(x) будет истинным, если предикат Р(х)является тождественно истинным предикатом. В противном случае – ложным. Высказывание $х Р(х) будет истинным, если предикат Р(х) – является выполнимым и будет ложным в противном случае.
5.5. Формулы логики предикатов.
Равносильность формул
Определение формулы логики предикатов имеет индуктивный характер. Сначала задается алфавит символов, из которых составляются формулы:
– предметные переменные: х, у, z, xi, yi, zi ( 
);
– нульместные предикатные переменные: Р, Q, R, Рi, Qi, Ri,
(i 
N);
– n–местные ( 
) предикатные переменные: Р(, ..., ), Q(, ..., ), R(, ..., ), Рi(, ..., ), Qi(, ..., ), Ri(, ..., ) (i N) с указанием числа свободных мест в них;
– символы логических операций: 
;
– кванторы: ", $;
– вспомогательные символы: (, ) – скобки; , – запятая.
Определение 10.(формулы логики предикатов).
1. Каждая нульместная предикатная переменная есть формула.
2. Любой n–местный предикат Р(х1, х2, ..., хn) есть формула.
3. Если F, G – формулы, не содержащие предметных переменных, которые связаны квантором в одной формуле и свободны в другой, то выражения ( 
), (F Ù G), (F Ú G), (F ® G ), (F « G) также являются формулами.
4. Если F формула, а х – предметная переменная, входящая свободно в F, то выражения "x F(x) и $x F(x) также являются формулами.
5. Никаких других формул в логике предикатов нет.
Формулы, в которых нет свободных переменных, называются замкнутыми, а формулы, содержащие свободные переменные, – открытыми.
Из определения формулы логики предикатов следует, что все формулы алгебры высказываний являются также формулами логики предикатов.
Определение 11.Две формулы F и G называются равносильными, если при подстановке в эти формулы вместо предикатных переменных конкретных предикатов, а вместо предметных переменных конкретных элементов, эти формулы преобразуются в высказывания с одинаковыми логическими значениями, то есть либо оба в истинные высказывания, либо оба в ложные.
Все основные равносильности логики высказываний верны также и для формул логики предикатов. Кроме них, в логике предикатов имеются равносильности, связанные с кванторами:
1. Законы отрицания: 
, 
.
2. Законы дистрибутивности:
;
.
3.Если предикат Q не зависит от переменной х, то верны следующие законы:
, 
;
, 
.
4. Законы переименования связанных переменных:
, 
.
5.Законы перестановки кванторов:
, 
.
5.6. Классификация формул логики предикатов
Определение 12.Формула F логики предикатов называется выполнимой (опровержимой) на множестве М, если можно найти такие конкретные предикаты, заданные на том же множестве, при подстановке которых вместо предикатных переменных, она преобразуется в выполнимый (опровержимый) предикат. Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом же множестве, она преобразуется в тождественно истинный (тождественно ложный) предикат. Формула логики предикатов называется тавтологией (противоречием), если при подстановке вместо предикатных переменных любых конкретных предикатов, заданных на любом множестве, она преобразуется в тождественно истинный (тождественно ложный) предикат.
Критерием равносильности формул F и G является тавтологичность формулы (F« G).
Пример 1.Вычислить значение формулы 
, если предикат 
имеет значение 
– «число x меньше числа y» и определен на множестве 
, N= 
.
Так как при указанном значении предиката высказывание 
означает утверждение, что «для любого натурального числа x найдется натуральное число y, большее числа x», то это высказывание истинно. Высказывание 
означает утверждение, что «существует натуральное число x, которое меньше любого натурального числа y». Это высказывание ложно. Поэтому получаем, что исходная формула ложна.
Пример 2. Доказать, что формула 
выполнима.
Для доказательства выполнимости формулы A достаточно найти область определения двухместного предиката 
и такое его значение, что в этой области формула принимает истинные значения. Такой областью определения предиката, в частности, будет множество . Действительно, если - предикат «y:x», то формула A тождественно истинна в области М, и, следовательно, выполнима в этой области. Однако, если в качестве предиката взять предикат «y<x», то формула A будет тождественно ложной в области М и, следовательно, невыполнимой в области М. при этом ясно, что формула A не общезначима.
Пример 3. Доказать, что формула 
является общезначимой.
Считая, что формула A определена на любой области M, проведем равносильные преобразования:
.
То есть формула A тождественно истинна для любых одноместных предикатов 
и 
и в любой области.
Пример 4. Доказать, что формула 
тождественно ложна.
Так как формула 
, а формула 
, очевидно, тождественно ложна, то ложна и формула A.
Определение 13.Формула F', равносильная F, называется ее приведенной формой, если F' из логических связок содержит только отрицание, конъюнкцию и дизъюнкцию, а отрицание относится только к предикатным переменным и к высказываниям. Предваренной нормальной формой (ПНФ) формулы F называется такая ее приведенная форма, в которой все кванторы вынесены в начало формулы, а область действия каждого квантора распространяется до конца формулы.
ПНФ – это формула вида 
, где 
– один из кванторов " или $ ( 
), а формула F не содержит кванторов и является приведенной формой.
Для формул логики предикатов справедлива следующая теорема.
Теорема. Для каждой формулы логики предикатов существует равносильная ей ПНФ.
Предваренные нормальные формы формул в логике предикатов используются для выяснения равносильности формул и для решения проблемы классификации формул.
Одной из задач классификации формул является проблема разрешимости, которая состоит в следующем. Необходимо найти алгоритм, при помощи которого для произвольной формулы логики предикатов можно определить, будет она тавтологией или нет. В отличие от алгебры высказываний, для формул логики предикатов общего алгоритма не существует. Это было доказано в 1936 году американским математиком А. Чёрчем. Несмотря на отсутствие алгоритма в общем случае, в некоторых частных случаях такой алгоритм существует. Например, для формул, содержащих только одноместные предикаты.
6. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ (ИП)
Понятие формулы в ИП вводится так же, как оно вводилось в логике предикатов.
Аксиоматическая теория начинается с выбора системы аксиом. Как и в случае высказываний, этот выбор может быть осуществлен по-разному. Одной из таких систем аксиом может служить система, состоящая из трех аксиом рассмотренного выше формализованного исчисления высказываний и двух дополнительных аксиом (схем аксиом):
(P1) 
;
(P2) 
,
где формула t не содержит свободной переменной x.
К правилу вывода modus pones(MP) добавляются еще два правила вывода:
| – правило введения квантора общности ("–правило); |
| – правило введения квантора существования ( $– правило), |
где х не входит свободно в формулу F.
Понятия вывода и теоремы определяются аналогично соответствующим понятиям исчисления высказываний.
Возможны и другие системы аксиом и правил вывода.
Рассмотрим пример вывода в исчислении предикатов.
Пример. Доказать, что
.
Решение.Построим вывод второй формулы из первой:
Библиографический список
1.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник – практикум и решения: Учебное пособие. 3 – е изд., испр. – СПб.:Издательство «Лань», 2008. – 288 с.
2.Дискретная математика: Теория, задачи, приложения / Я.М. Ерусалимский. – 7-е изд. – М.: Вузовская книга, 2005. – 268 с.: ил.
3.Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб.пособие для студ. высш.учеб.заведений / В.И.Игошин. – 2-е изд.,стер. –М. : Издательский центр «Академия», 2006. – 304 с.
4.Игошин В.И. Математическая логика и теория алгоритмов: Учеб.пособие для студ. высш.учеб.заведений / В.И.Игошин. –М. : Издательский центр «Академия», 2004. – 448 с.
5.Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – 2-е изд. – М.: ФИЗМАТЛИТ, 2002. – 128 с.
6.Математическая логика и теория алгоритмов. Ч. I: Метод. указания / Казан. гос. технол. ун-т; Сост. А.В.Садыков. Казань, 2005. 48 с.
Содержание
1. ЛОГИКА ВЫСКАЗЫВАНИЙ …….………….…….… 3
1.1. Высказывания и операции над ними …………………3
1.2. Формулы алгебры высказываний …………………… 5
1.3. Классификация формул. Равносильные формулы….. 6
1.4. Нормальные формы ……………………………….....11
1.5. Логическое следование ………………………………18
1.6. Правила вывода ………………………………………21
2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ И ИХ ПРИЛОЖЕНИЯ …………………………………………….25
2.1. Функции алгебры логики ……………………………25
2.2. Специальные замкнутые классы функций
алгебры логики ……………………………….…...… 30
2.3. Приложение булевых функций к анализу
и синтезу релейно-контактных схем.................……. 33
3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ ……..….……… 35
4. ПРАВИЛО РЕЗОЛЮЦИЙ…….………………………41
5. ЛОГИКА ПРЕДИКАТОВ ………………..…….……. 43
4.
5.
5.1. Определение предиката ……………………….……. 43
5.2. Логические операции над предикатами …….……... 45
5.3. Теоретико-множественный смысл предикатов…..…48
5.4. Классификация предикатов …………………….….. 50
5.5. Формулы логики предикатов.
Равносильность формул …………………….……… 50
5.6. Классификация формул логики предикатов……… 52
6. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ……………….…… 55
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ………………….. 57
Учебное издание
Садыков Айдар Вагизович