Равносильность, законы логики первого порядка

Определение. Формулы F(x₁, …, x_n) и G(x₁, …, x_n) называются равносильными, если для любой интерпретации j с областью М высказывания (jF)(a₁, …, a_n) и (jG)(a₁, …, a_n) при любых a₁, …, a_n из М одновременно истинны или одновременно ложны.

Пусть F(x)=Ø (" y)P(x, y), G(x)=($y)Ø P(x, y), где Р – символ двухместного предиката. Докажем, что формулы F(x) и G(x) равносильны. Возьмем интерпретацию j с областью М. Пусть высказывание (jF)(a) истинно для aÎ M. Истинность этого высказывания одначает, что не для всякого yÎ M высказывание (jP)(a, y) истинно. Следовательно, найдется bÎ M, для которого высказывание (jP)(a, b) ложно. Если высказывание (jP)(a, b), ложно, то высказывание Ø (jP)(a, b) истинно. Отсюда следует, что найдется yÎ M такой, для которого высказывание Ø (jP)(a, y) истинно. Это означает истинность высказывания (jG)(a). Итак, мы доказали, что если высказывание (jF)(a) истинно, то высказывание (jG)(a) тоже истинно. Обратная импликация доказывается аналогично. Значения истинности высказываний (jF)(a) и (jG)(a) при любом aÎ M совпадают. Следовательно, формулы F(x) и G(x) равносильны.

 

Определение. Формула F(x₁, …, x_n) называется тождественно истинной, если для любой интерпретации j с областью М высказывание (jF)(a₁, …, a_n) при любых a₁, …, a_n из М является истинным.

Как и в случае логики высказываний. Приведем список основных равносильностей – законов логики предикатов. Прежде всего, получим законы логики предикатов из законов 1–21 логики высказываний, понимая под F, G, H – произвольные формулы логики предикатов. Дополним полученный список законами, специфичными для логики предикатов и получим полный список законов логики предикатов.

1. H ↔ G = (H → G) Ù (G → H)

2. H → G = ~H Ú G

3. H Ú G = G Ú H

4. H Ù G = G Ù H

5. (H Ú G) Ú S = H Ú (G Ú S)

6. (H Ù G) Ù S = H Ù (G Ù S)

7. H Ú (G Ù S) = (H Ú G) Ù (H Ú S)

8. H Ù (G Ú S) = (H Ù G) Ú (H Ù S)

9. H Ú 0 = H

10. H Ú 1 = 1

11. H Ù 1 = H

12. H Ù 0 = 0

13. H Ú ~H = 1

14. H Ù ~H = 0

15. ~(~H) = H

16. ~(H Ú G) = ~H Ù ~G

17. ~(H Ù G) = ~H Ú ~G

18. (H G) Ú (H ~G) = H

19. (H G) Ù (H ~G) = H

20. H Ú (H Ù G) = H

21. H Ù (H Ú G) = H

22. H Ú H = H

23. H Ù H = H

24. H → G = ~G → ~H

25. (" x)(H(x) Ù G(x)) = (" x)(H(x) Ù (" x)G(x)

26. ($x)(H(x)Ú G(x))= ($x)H(x)Ú ($x)G(x)

27. (" x)(" y)H(x, y) =(" y)(" x)H(x, y)

28. ($x)($y)H(x, y) = ($y)($x)H(x, y)

29. ~(" x)H(x) = ($x)~H(x)

30. ~($x)H(x) =(" x)~H(x)

31. (" x)(H(x)Ú G) = (" x)H(x)Ú G,

32. ($x)(H(x)& G) = ($x)(H(x)& G, где G не содержит x.

33. (Q₁x)(Q₂z)(H(x)Ú G(z)) = (Q₁x)H(x)Ú (Q₂z)G(z)

34. (Q₁x)(Q₂u)(H(x)& G(u)) = (Q₁x)H(x)& (Q₂u)G(u), где Q₁, Q₂ кванторы $ или ", u не входит в H(x), а x не входит в G(u).

35. (" x)H(x) = (" z)H(z),

36. ($x)H(x) = ($z)H(z).

В законах 35 и 36 переменная 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 последовательно законы 26, 27 и 20, получим, что формула F равносильна формуле

 

F₁=($x)(" y)Ø [Ø (S(x)& P(x, y))Ú ($z)(T(z)& P(x, z))].

 

Далее, используя законы 18, 19 и 27 из F₁, получим формулу

 

F₂=($x)(" y)[S(x)& P(x, y)& (" z)Ø (T(z)& P(x, z))].

 

Осталось заметить, что в силу законов 17 и 20 в формуле F₂ подформулу Ø (T(z)& P(x, z)) можно заменить на T(z)®Ø P(x, z).

 

Подчеркнем, что доказательство равносильности двух формул будем проводить с помощью законов логики первого порядка. Доказательство того, что формулы неравносильны, будем осуществлять построением интерпретации, при которой одна формула истинна, другая ложна. Например, так, как это было сделано выше для доказательства неравносильности формул (" x)(F(x)Ú G(x)) и (" x)F(x)Ú (" x)G(x). Разумеется, до построения интерпретации формулы можно предварительно преобразовывать с помощью законов.

Логическое следствие

Определение. Формула G(x₁, …, x_n) называется логическим следствием формул F₁(x₁, …, x_n), …, F_k(x₁, …, x_n), если для любой интерпретации j с областью М и любых a₁, …, a_nÎ M из истинности высказываний (jF₁)(a₁, …, a_n), …, (jF_k)(a₁, …, a_n) следует истинность высказывания (jG)(a₁, …, a_n).

Приведем примеры. Пусть F₁=(" x)(P(x)®Q(x)& R(x)), F₂=P(c), G=Q(c). Покажем, что формула G является логическим следжствием формул F₁ и F₂. Возьмем интерпретацию j с областью М такую, что высказывания jF₁ и jF₂ истинны. Элемент j(c) обозначим буквой b. Истинность jF₂ означает, что высказывание (jP)(b) истинно. А истинность высказывания jF₁ означает, что для любого элемента xÎ M истинно высказывание (jP)(x)®(jQ)(x)& (jR)(x). Поскольку это высказывание истинно для любого х, то, в частности, истинно для x=b. Мы видим, что истинна импликация (jP)(b)®(jQ)(b)& (jR)(b) и ее посылка (jP)(b). Из таблицы истинности импликации следует истинность заключения (jQ)(b)& (jR)(b). Следовательно, истинно высказывание (jQ)(b). А это и есть jG. Мы доказали, что если истинны высказывания jF₁ и jF₂, то истинно высказывание jG, т.е. что G –логическое следствие F₁ и F₂.

В качестве второго примера докажем нелогичность рассуждения о первокурсниках. Мы записали это рассуждение в виде последовательности формул Н₁, Н₂, и Н₃. Для доказательства нелогичности рассуждения надо найти интерпретацию j, при которой формулы Н₁ и Н₂ истинны, а формула Н₃ ложна. Пусть множество М состоит из трех элементов 2, 3, 4. Символы С, Л и П проинтерпретируем следующим образом:

 

(jС)(х)=«х – простое число»,

(jЛ)(х)=«х – четное число»,

(jП)(х)=’’х> 4»,

 

т.е. П интерпретируется как тождественно ложный предикат. Тогда формулы Н₁ и Н₂ истинны, поскольку посылки импликаций этих формул ложны при любом х. А формула Н₃ ложна. Чтобы убедиться в этом достаточно взять х=2. Следовательно, рассуждение о первокурсниках нелогично.

Определение. Множество формул

K={F₁(x₁, …, x_l), …, F_m(x₁, …, x_l)}

называется выполнимым, если существует интерпретация j с областью М и элементы a₁, …, a_lÎ M такие, что все высказывания (jF₁)(a₁, …, a_l), …, (jF_m)(a₁, …, a_l) истинны.

Множество формул K = { F₁=(" x)($y)(P(y)& Q(x, y)), F₂=(" y)Q(c, y), F₃=Ø P(c) } выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P, Q и C проинтерпретируем следующим образом:

(jP)(u)=«u – простое число»,

(jQ)(u, v)=«u меньше или равно v»,

(j(C)=1.

Тогда высказывание jF₁ означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание jF₂ означает, что 1 –наименьшее натуральное число, а высказывание jF₃ означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.

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

Теорема 2. Формула G(x₁, …, x_n) является логическим следствием формул F₁(x₁, …, x_n), …, F_k(x₁, …, x_n) тогда и только тогда, когда множество формул {F₁(x₁, …, x_n), …, F_k(x₁, …, x_n), Ø G(x₁, …, x_n)} невыполнимо.

 

⇐ Предыдущая12

Поделиться:

Популярное:

1. I. Рабочее тело и параметры его состояния. Основные законы идеального газа.
2. Алгоритм управления разомкнутой системы первого типа имеет вид
3. БИЛЕТ 36. Состав атомного ядра. Характеристики ядра: заряд, масса. Энергия связи нуклонов. Радиоактивность. Виды и законы радиоактивного излучения.
4. Большинство законов содержат правовые нормы (законы материальные), иногда норм в законе нет, а только что-то констатируется (законы формальные).
5. В. Законы сохранения при прямолинейном движении.
6. Введение в упражнения по разрушению привычного распорядка дня
7. Введение и доказательство первого признака равенства прямоугольных треугольников
8. Внешний фотоэффект и его законы.
9. Вырабатывайте собственный стиль, при этом неукоснительно соблюдая законы интеллект-карт
10. Гегель Г.В. «Наука логики. Тождественность мышления и бытия»
11. Глава 1. Основные Законы и указания Генерального прокурора РФ
12. Глава 16 ПСИХИЧЕСКИЕ ЗАКОНЫ, СИЛЫ И ФЕНОМЕНЫ