Математическая логика и теория алгоритмов

Понятие логического следствия тесно связано с понятием выполнимости.

Определение. Множество формул {F₁,F₂,…,F_l} называется выполнимым, если существует интерпретация j такая, что j(F₁)=j(F₂)=…=j(F_l)=1.

Проверку выполнимости множества формул {F₁,F₂,…,F_l} можно провести построением совместной таблицы истинности этих формул. Если найдется хотя одна строка, в которой в столбцах формул F₁,F₂,…,F_l стоят единицы, то это множество формул выполнимо. Если такой строки нет, то множество формул невыполнимо. Так, множество формул {F₁,F₂,F₃,G} из предыдущего примера выполнимо, поскольку в таблице 1.4 в первой строке в столбцах этих формул стоят единицы.

Теорема 1.2 Формула G является логическим следствием формул F₁,F₂,…,F_k тогда и только тогда, когда множество формул

L={F₁,F₂,…,F_k,ØG}

невыполнимо.

 

Задачи для самостоятельной работы

 

1. Будут ли следующие формулы тождественно истинны:

а) X & Y ® X,	б) X Ú Y ® Х,	в) X & Y ® Х Ú Y ,
г) X Ú Y ® X & Y,	д) (Х®Y)®(Y®Х),	е) (Х®ØX)®X,
ж) (ØX®X)®X ,	з) (X®Y)®(ØY®ØX),	и) Ø(X«Y)®(ØX«ØY)?

 

2. Существует ли формула F такая, что формула G тождественно истинна:

а) G = X & Y ® Ø (F & Z);	б) G = (F & Y®ØZ) ®(Z®ØY);
в) (F&Z) ∨ (¬F&¬Y&¬Z)

 

3. Будут ли следующие формулы равносильны:

а) Х ® Y и ØY ®ØX,	б) ØX ®Y и ØY ® Х
в) Х® (Y®Z) и (Х®Y) ®Z,	г) Х ® (Y ® Z) и X & Y® Z,
д) Ø(X ® Y ) и ØX ®ØY,	е) X«Y и ØX«ØY?

 

4. Доказать равносильность формул:

а) Ø[(XÚY)&(X&ØZ)] и X®Z,	б) (X&ØY)ÚØ(X&Y) и Ø(X&Y)
в) Ø[(XÚØY)&Y]&Ø(ØX&Y) и ØY	г) Ø [(X & Y) Ú ØZ] и Ø (Z®X) Ú Ø(Z®Y),
д) (X & Y) Ú (ØX & Y) Ú (X & ØY) и Х Ú Y,
е) (ØX & Y & Z) Ú (ØX & ØY & Z) Ú (Y & Z) и (ØXÚY)&Z.

5. Доказать, что формула G является логическим следствием формул F₁,F₂,...,F_n:

а) F1=X ® Y Ú Z, F2=Z®W, F3=ØW, G=X®Y;

б) F1=XÚYÚØZ, F2=X®X1, F3=Y®Y1, F4=Z, G=X1ÚY1;

в) F1=X®Y&Z, F2=Y®Z1ÚZ2, F3=Z®Z1, F4=ØZ1, G=X®Z2;

г) F1=Z®Z1, F2=Z1®Y, F3=X®YÚZ, G=X®Y.

 

6. Доказать, что формула G не является логическим следствием формул F₁,F₂,…,F_n:

а) F1=X®YÚZ, F2=Y®W, F3=Z®X, G=X ® W;

б) F1=X®Y, F2=Y®Z, F3=Z®Z1ÚZ2, G=X®Z1;

в) F1=XÚYÚZ, F2=X®X1, F3=Y®Х1ÚY1, F4=ØY1, G=Z®X1.

 

7. Определить, какая логическая связка используется в следующих выражениях: "А, если В", "коль скоро А, то В", "в случае А имеет место В", "как А, так и В", "для А необходимо В", "для А достаточно В", "А вместе с В", "А не имеет места", «A, только если B», «или A, или B», «A одновременно с B», «A – то же самое, что и B».

 

Варианты  задач по бригадам

Записать следующие рассуждения в виде последовательности формул логики высказываний. Будет ли логичным рассуждение?

1. Профсоюзы  штата будут поддерживать губернатора,  если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.

2. Если мы  не будем продолжать политику сохранения цен, то мы потеряем голоса фермеров. Если же мы будем продолжать эту политику и не прибегнем к контролю над производством, то продолжится перепроизводство. Без голосов фермеров нас не переизберут. Значит, если нас переизберут, и мы не прибегнем к контролю над производством, то продолжится перепроизводство.

3. Если завтра  будет хорошая погода, то я  буду кататься на коньках или  я пойду на лыжах. Если я  пойду на лыжах, то лучше  поехать за город, а если  буду кататься на коньках, то  останусь в городе. Мне не хочется завтра в выходной день оставаться в городе. Следовательно, если завтра будет хорошая погода, то я пойду на лыжах.

4. Если Джонс не встречал этой ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Эксперты установили, что убийство произошло до полуночи. Следовательно, Смит был убийцей.

5. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.

6. Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.

7. Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен и волнения не прекратятся до тех пор, пока участникам волнений это не надоест, и власти не начнут примирительные действия. Следовательно, если губернатор не желает взять на себя ответственность и участникам волнений это не надоест, то волнения не прекратятся.

 

Инструкция по установке и выполнению программы

На компьютере должен стоять интерпретатор Ruby. Его можно скачать с сайта ruby-lang.org.

Программа запускается из командной строки. Пример запуска программы:

ruby tautology.rb "(x -> y) <=> ((not y)->(not x))"

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

При задании функции  используются следующие обозначения:

and  - конньюнкция

or - дизьюнкция

not - отрицание

-> - импликация

<=> - эквиваленция.

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

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

Для сохранения результатов в файл следует перенаправить стандартный вывод командой >>. Например:

ruby tautology.rb "(x -> y) <=> ((not y)->(not x))" >> res.txt

Лабораторная  работа № 2. Логика предикатов

 

Цель  работы – научиться переводить выражения на естественном языке на язык логики предикатов. Научиться приводить предикат к нормальным формам. Научиться использовать логику предикатов для формализации информационных систем.

 

Порядок выполнения

1. Ознакомиться с методическими указаниями.
2. Решить цикл задач для самостоятельной работы.
3. Провести формализацию задачи (вариант задачи определяется номером бригады).
4. Составить необходимые запросы к информационной системе в логике предикатов. Привести формулы к ПНФ.
5. Поверить правильность запросов на ЭВМ (использовать программу predicate.rb).
6. Оформить отчет.

 

Методические  указания

Логика высказываний обладает довольно слабыми выразительными возможностями. Рассмотрим, например, следующее умозаключение. «Всякое  целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

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

Рассмотрим примеры. Пусть М есть множество натуральных  чисел N. Тогда выражения «x – простое число», «x – четное число», «x – больше 10» являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д. Выражения «x больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x плюс y равно z», «|x-y|£z».

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

Надо отметить, что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение «существует число x такое, что y=2x» на множестве натуральных чисел определяет одноместный предикат. По смыслу этого выражение в нем можно заменять только переменную y. Например, замена y на 6 дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».

Предикат с  заменяемыми переменными x₁,…,x_n будет обычно обозначаться заглавной латинской буквой. После которой в скобках указаны эти переменные. Например, P(x₁,x₂), Q(x₂,x₃), R(x₁). Среди переменных в скобках могут быть и фиктивные.

На совокупности всех предикатов, заданных на множестве М, вводятся знакомые операции конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция.

В логике предикатов первого порядка вводятся и две  новые операции. Называются они квантором  общности и квантором существования. Эти операции рассмотрим вначале на примерах. Пусть дано выражение «существует х такой, что x+y=10». На множестве натуральных чисел это предложение определяет одноместный предикат P(y), так Р(2) и Р(9) – истинные высказывания, Р(11) – ложное. Если обозначить предикат «x+y=10» через S(x,y) (а это предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x,y)». В этом случае говорят, что предикат P(y) получен из предиката S(x,y) навешиванием квантора существования на x и пишут P(y)=($x)S(x,y). Рассмотрим другой пример. Выражение «для всех х справедливо, что y³-х²» определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y³-х²» обозначить через T(x,y), то Q(y) можно записать так: «для всех x справедливо T(x,y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x,y) навешиванием квантора общности на х и пишут Q(y)=("x)T(x,y).

Определение. Пусть P(x₁,…,x_n) – предикат, заданный на множестве M, y – переменная. Тогда выражение «для всякого y выполняется P(x₁,…,x_n)» – предикат, полученный из P навешиванием квантора общности на переменную y, а выражение «существует y такой, что выполняется P(x₁,…,x_n)» – предикат, полученный из P навешиванием квантора существования на переменную y.

Заметим, что  в определении не требуется, чтобы y была одна из переменных x₁,…,x_n, хотя в содержательных примерах, которые будут ниже, квантор навешивается на одну из переменных x₁,…,x_n. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x₁,…,x_n, то после навешивания квантора на y новый предикат является (n-1)-местным, если yÏ{ x₁,…,x_n}, то местность нового предиката равна n.

Если предикат W(x₁,…,x_n) получен из предикатов U(x₁,…,x_n) и V(x₁,…,x_n) с помощью связок, то истинность высказывания W(a₁,…,a_n) определяется таблицами истинности этих связок. Пусть W(x₁,…,x_n)=("y)U(x₁,…,x_n,y). Тогда высказывание W(a₁,…,a_n) истинно тогда и только тогда, когда для любого bÎM истинно высказывание U(a₁,…,a_n,b). Если же W(x₁,…,x_n)=($y)U(x₁,…,x_n,y), то высказывание W(a₁,…,a_n) истинно в том и только в том случае, когда найдется bÎM, для которого высказывание U(a₁,…,a_n) истинно.

Понятие предиката  – весьма широкое понятие. Это  видно уже из приведенных выше примеров. Тем не менее мы это еще раз подчеркнем, показав, что n-местная функция может рассматриваться как (n+1)-местный предикат. Действительно, функции y=f(x₁,…,x_n), заданной на множестве М можно поставить в соответствие выражение «y равно f(x₁,…,x_n)». Это выражение есть некоторый предикат P(x₁,…,x_n,y). При этом если элемент b есть значение функции в точке (a₁,…,a_n), то высказывание P(a₁,…,a_n,b) истинно, и обратно. (Подобное «превращение» функции в предикат мы уже делали выше для сложения натуральных чисел.)

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

Во-первых, предикат можно представить отношением следующим  образом. Пусть предикат P(x₁,…,x_n) задан на множестве M. Рассмотрим прямую степень этого множества Mⁿ=MxMx…xM и подмножество D_p множества Mⁿ, определяемое равенством:

D_p={(a₁,…,a_n)ÎMⁿ½высказывание P(a₁,…,a_n) истинно}.

Отношение D_p можно назвать областью истинности предиката P. Во многих случаях предикат P можно отождествить с отношением D_p. При этом, правда возникают некоторые трудности при определении операций над отношениями, аналогичными операциям над предикатами.

Во-вторых, предикат P(x₁,…,x_n), заданный на M, можно отождествить с функцией f_p:Mⁿ®{0,1}, определяемой равенством

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

Формулы логики первого порядка 

Будем исходить из следующих трех множеств: F,R,V. Элементы множества F – символы (или имена) функций, элементы R – символы (или имена) предикатов, элементы множества V – переменные. Будем считать, что каждому символу функции и предиката поставлено в соответствие натуральное число или ноль – местность (т.е. число аргументов) этого символа. Допускаются нульместные символы функций, которые называются константами, и нульместные символы предикатов (последние будут играть роль атомарных формул логики высказываний). Объединение F и R будем называть сигнатурой. Сигнатуру заранее фиксировать не будем, она будет определяться содержанием решаемой задачи. Множество V предполагается бесконечным, для обозначения его элементов будут использоваться, как правило, буквы x,y,z,u,y,w с индексами и без них.