Описание всех лабораторных работ (1006390), страница 4
Текст из файла (страница 4)
Оказывается нет. Докажем это для случая, когда F(x) и G(x) – атомарные формулы. Пусть основное множество – множество натуральных чисел N, F(x) – предикат «x – четное число» , G(x) – предикат «x – нечетное число». Обозначим эту интерпретацию буквой . Тогда (x)(F(x)G(x))]=1, но [(x)F(x)(x)G(x)=0. Аналогично, (x)(F(x)&G(x))]=0 и (x)F(x)&(x)G(x)]=1.
Рассмотрим законы 24 и 25. Они утверждают, что одноименные кванторы можно менять местами. Можно ли переставлять местами разноименные кванторы, сохраняя равносильность. Другими словами, равносильны ли формулы
(x)(y)(F(x,y) и (y)(x)F(x,y)?
Оказывается, тоже нет. В качестве основного множеств возьмем опять множество натуральных чисел, F(x,y) будем считать атомарной формулой и поставим ей в соответствие предикат «x меньше y». Тогда левая формула будет истинной, правая – ложной.
Вернемся к законам 22 и 23. Мы отмечали, что квантор существования – через конъюнкцию. Тем не менее, если одна из формул F или G не содержит переменной x, то это делать можно. Запишем соответствующие законы:
28) (x)(F(x)G) равносильна (x)(F(x)G,
29) (x)(F(x)&G) равносильна (x)(F(x)&G, где G не содержит x.
Законы 22, 23, 28, 29 можно записать в общем виде:
30) (Q1x)(Q2z)(F(x)G(z)) равносильна (Q1x)F(x)(Q2z)G(z)
31) (Q1x)(Q2u)(F(x)&G(u)) равносильна (Q1x)F(x)&(Q2u)G(u),
где Q1, Q2 кванторы V или Э, u не входит в F(x), а x не входит в G(u). Для доказательства равносильности двух формул могут оказаться полезными следующие законы:
Рассмотрим формулу F(x)=(y)P(x,y)P(x,c), где P – символ двухместного отношения, с – константа. Докажем, что формула F(x) тождественно истинна. Возьмем интерпретацию с областью М и элемент а из М. Высказывание (F)(a) равно (y)(P)(a,y)(P)(a,(c)). Если посылка (y)(P)(a,y) ложна, то вся импликация (F)(a) истинна. Предположим, что посылка (y)(P)(a,y) истинна. Это означает, что для всякого yM высказывание (P)(a,y) истинно, в том числе истинно это высказывание и для y=(c). Следовательно, истинно заключение (P)(a,(c)) и вся импликация (F)(a). Мы доказали, что высказывание (F)(a) истинно для любого aM. Это означает, что формула F(x) является тождественно истинной.
Понятия равносильности и тождественной истинности в логике первого порядка связаны точно так же, как и в логике высказываний.
Теорема 3.1 Формулы F(x1,…,xn) и G(x1,…,xn) равносильны тогда и только тогда, когда формулы F(x1,…,xn)G(x1,…,xn) тождественно истинны.
Законы замены переменных:
32) (x)F(x) равносильна (z)F(z),
33) (x)F(x) равносильна (z)F(z).
В законах 32 и 33 переменная z не входит в F(x), а переменная x не входит в F(z).
В логике высказываний мы применяли два способа доказательства равносильности формул: построение совместной таблицы истинности и переход от одной формулы к другой с помощью законов. В случае логики первого порядка остается только второй способ.
Проиллюстрируем его на примере следующей задачи: доказать равносильность формул:
F=(x)(y)[S(x)&P(x,y)(z)(T(z)&P(x,z))]
G=(x)(y)[S(x)&P(x,y)&(z)(T(z)P(x,z))].
Применим к формуле F последовательно законы логики предикатов, получим, что формула F равносильна формуле
F1=(x)(y)[(S(x)&P(x,y))(z)(T(z)&P(x,z))].
Далее, используя законы логики предикатов из F1, получим формулу
F2=(x)(y)[S(x)&P(x,y)&(z)(T(z)&P(x,z))].
Осталось заметить, что в формуле F2 подформулу (T(z)&P(x,z)) можно заменить на T(z)P(x,z).
Доказательство равносильности двух формул будем проводить с помощью законов логики первого порядка. Доказательство того, что формулы неравносильны, будем осуществлять построением интерпретации, при которой одна формула истинна, другая ложна. Например, так, как это было сделано выше для доказательства неравносильности формул (x)(F(x)G(x)) и (x)F(x)(x)G(x). Разумеется, до построения интерпретации формулы можно предварительно преобразовывать с помощью законов.
Логическое следствие
Определение. Формула G(x1,…,xn) называется логическим следствием формул F1(x1,…,xn),…,Fk(x1,…,xn), если для любой интерпретации с областью М и любых a1,…,anM из истинности высказываний (F1)(a1,…,an),…,(Fk)(a1,…,an) следует истинность высказывания (G)(a1,…,an).
Приведем примеры. Пусть F1=(x)(P(x)Q(x)&R(x)), F2=P(c), G=Q(c). Покажем, что формула G является логическим следствием формул F1 и F2. Возьмем интерпретацию с областью М такую, что высказывания F1 и F2 истинны. Элемент (c) обозначим буквой b. Истинность F2 означает, что высказывание (P)(b) истинно. А истинность высказывания F1 означает, что для любого элемента xM истинно высказывание (P)(x)(Q)(x)&(R)(x). Поскольку это высказывание истинно для любого х, то, в частности, истинно для x=b. Мы видим, что истинна импликация (P)(b)(Q)(b)&(R)(b) и ее посылка (P)(b). Из таблицы истинности импликации следует истинность заключения (Q)(b)&(R)(b). Следовательно, истинно высказывание (Q)(b). А это и есть G. Мы доказали, что если истинны высказывания F1 и F2, то истинно высказывание G, т.е. что G –логическое следствие F1 и F2.
В качестве второго примера докажем нелогичность рассуждения о первокурсниках. Мы записали это рассуждение в виде последовательности формул Н1,Н2, и Н3. Для доказательства нелогичности рассуждения надо найти интерпретацию , при которой формулы Н1 и Н2 истинны, а формула Н3 ложна. Пусть множество М состоит из трех элементов 2,3,4. Символы С, Л и П проинтерпретируем следующим образом:
(С)(х)=«х – простое число»,
(Л)(х)=«х – четное число»,
(П)(х)=’’х>4»,
т.е. П интерпретируется как тождественно ложный предикат. Тогда формулы Н1 и Н2 истинны, поскольку посылки импликаций этих формул ложны при любом х. А формула Н3 ложна. Чтобы убедиться в этом достаточно взять х=2. Следовательно, рассуждение о первокурсниках нелогично.
Определение. Множество формул
K={F1(x1,…,xl),…,Fm(x1,…,xl)}
называется выполнимым, если существует интерпретация с областью М и элементы a1,…,alM такие, что все высказывания (F1)(a1,…,al),…,(Fm)(a1,…,al) истинны.
Множество формул K = { F1=(x)(y)(P(y)&Q(x,y)), F2=(y)Q(c,y), F3=P(c) } выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P,Q и C проинтерпретируем следующим образом:
(P)(u)=«u – простое число»,
(Q)(u,v)=«u меньше или равно v»,
(C)=1.
Тогда высказывание F1 означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание F2 означает, что 1 –наименьшее натуральное число, а высказывание F3 означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.
Понятия логического следствия и выполнимости в логике первого порядка связаны точно так же, как и в логике высказываний.
Теорема 3.2. Формула G(x1,…,xn) является логическим следствием формул F1(x1,…,xn),…,Fk(x1,…,xn) тогда и только тогда, когда множество формул {F1(x1,…,xn),…,Fk(x1,…,xn),G(x1,…,xn)} невыполнимо.
Нормальные формы
Как и в логике высказываний, в логике первого порядка вводятся нормальные формы. Мы рассмотрим две из них: предваренную нормальную и сколемовскую нормальную формы.
Определение. Формула G имеет предваренную нормальную форму (сокращенно: ПНФ), если
G(Q1,x1)…(Qn,xn)H,
где Q1,…,Qn кванторы, а формула H не содержит кванторов.
Например, формула (x)(y)(P(x,y)&Q(y)) имеет предваренную нормальную форму, а формула (x)(T(x)&S(x,y)) не имеет.
Теорема 3.3. Для всякой формулы F существует формула G, равносильная F и имеющая предваренную нормальную форму.
Алгоритм приведения к предваренной нормальной форме
Шаг 1. Используя законы логики исключить эквиваленцию и импликацию.
Шаг 2. Занести отрицание к атомарным формулам.
Шаг 3. С помощью законов 22-23, 28-31 вынести кванторы вперед, используя при необходимости переименование связанных переменных (законы 32-33).
Рассмотрим пример. Пусть
F=(x)P(x)(y)(z)(P(y)&Q(y,z)).
Выполнив шаг 1, получим формулу
F1=(x)P(x)(y)(z)(P(y)&Q(y,z)).
С помощью закона 26 перейдем к формуле
F2=(x)P(x)(y)(z)(P(y)&Q(y,z)).
Тем самым, шаг 2 также выполнен. Применим закон 30 слева направо Q1=, Q2=, u=y, получим формулу
F3=(x)(y)[P(x)(z)(P(y)Q(y,z))].
(Пользуемся тем, что P(x) не содержит y, а (z)(P(y)&Q(Y,z)) не содержит х. Так как формула P(x) не содержит z, то применение закона 26 слева направо дает формулу
F4=(x)(y)(z)[P(x)(P(y)&Q(y,z))].
Это и есть искомая формула, имеющая ПНФ и равносильная формуле F.
В предыдущем примере выполнение шага 3 можно организовать по-другому. В формуле F2 связанную переменную y заменим на переменную х (закон 33), получим формулу
F3=(x)P(x)(x)(z)(P(x)&Q(x,z)).
Используя закон 23, перейдем к формуле
F4=(x)[P(x)(z)(P(x)&Q(x,z))].
Затем, как и в предыдущем абзаце, с помощью закона 28 вынесем квантор по z за квадратную скобку. Получим формулу
F5=(z)(z)[P(x)(P(x)&Q(x,z)].
Формула F5, как и формула F4, имеет предваренную нормальную форму и равносильна формуле F. В некоторых ситуациях формула F5 предпочтительнее формулы F4, поскольку содержит меньше кванторов. (Кстати, бескванторную часть формулы F5 можно упростить).
Перейдем к изучению сколемовской нормальной формы. Отметим вначале, что в логике первого порядка понятие конъюнктивной нормальной формы вводится точно так же, как и в логике высказываний. Сохраняется полностью алгоритм приведения к КНФ и утверждение теоремы 1.3.
Определение. Формула G имеет сколемовскую нормальную форму (сокращенно: СНФ), если
G=(x)…(xn)H,
где формула Н не содержит кванторов и имеет конъюнктивную нормальную форму.
Например, формула (x)[P(x)(P(y)&Q(x,y)] имеет сколемовскую нормальную форму, а формулы (x)(y)Q(x,y), (x)[P(x)&(P(y)Q(x,y)] не имеют.
В отличие от предыдущего случая предваренной нормальной формы мы здесь вначале рассмотрим алгоритм приведения к СНФ, а затем сформулируем теорему.
Алгоритм приведения к сколемовской нормальной форме
Шаг 1 – Шаг 3 – те же, что и в предыдущем алгоритме.
Шаг 4. Бескванторную часть привести к конъюнктивной нормальной форме.
Шаг 5. Исключить кванторы существования.
Этот шаг изложим на примере. Пусть после выполнения четвертого шага имеем формулу
F=(x)(y)(z)(u)(v)H(x,y,z,u,v),
где Н – не содержит кванторов. Предположим, что формула не содержит константы с, символов одноместной функции f и двухместной функции g. Тогда в формуле Н заменим х на с, z – на f(y), v заменим на g(y,u). Все кванторы существования вычеркнем. Получим формулу
G=(y)(u)H(c,y,f(y),u,g(g,u)).
Это и есть результат выполнения шага 5.
Приведем пример приведения к СНФ. Пусть
F=(x)(y)[P(x,y)(z)(Q(x,z)&R(y))].
Применяя закон 23, получаем формулу
F1=(x)(y) )(z)[P(x,y)(Q(x,z)&R(y))].
Она имеет предваренную нормальную форму. Приводим бескванторную часть к КНФ:
F2=(x)(y) )(z)[P(x,y)(Q(x,z)&(P(x,y)(R(y))].
Сделаем подстановку x=a, z=f(y), получим искомую формулу
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
