Правила редукции. Метод аналитических таблиц

В предыдущих главах мы рассматривали умозаключения и подчеркивали, что условиями получения истинных заключений является истинность посылок и правильность построения самого умозаключения[13]. В логике предикатов умозаключениям соответствует логическое следование одних формул из других.

Определение логического следования:

Формула B логически следует из формул A ₁, A ₂, A ₃…, если при любых интерпретациях их предметных, предметно-функциональных и предикатных символов и истинности каждой из формул A ₁, A ₂, A ₃… формула B является истинной.

В 3 параграфе настоящей главы мы ввели общезначимые формулы, которые оказываются истинными высказываниями при любой интерпретации своих предметных, предметно-функциональных и предикатных символов.

Чтобы выяснить, следует ли данная формула логически из вот этих формул или является ли формула общезначимой, строятся так называемые аналитические таблицы на основе правил редукции [14]. Рассмотрим эти правила и поучимся строить аналитические таблицы.

Правила редукции

1. Замена конъюнкции. Допустим, мы имеем ряд истинных формул, среди которых находится формула A · B. Обозначим этот ряд как W, A · B, где W − формулы остальной части ряда, они могут и отсутствовать. Истинность конъюнкции A · B означает, что истинны по отдельности формула A и формула B. Поэтому конъюнкцию A · B можно заменить формулами A, B.

Правило записывается в виде двух строк, разделенных горизонтальной чертой: в верхней строке пишутся исходные формулы W, A · B, в нижнюю строку переносятся формулы W, а вместо A · B ставятся формулы A, B:

W, A · B . W, A, B

Пример:

" xF (x)," yG (y), " xH (x)· F (y) " xF (x)," yG (y), " xH (x), F (y)

[·]

Здесь и ниже " xF (x)," yG (y) − ряд формул, которые соответствуют W, формулы " xH (x) и F (y) соответствуют A и B. Знак [·] указывает, что совершена замена конъюнкции.

2. Замена отрицания конъюнкции. Допустим, мы имеем ряд истинных формул W, ù(A · B). Истинность формулы ù(A · B) означает ложность формулы A · B, а это возможно, по крайней мере, в двух случаях: либо ложна формула A, либо ложна формула B. Поэтому в верхней строке пишутся исходные формулы W, ù(A · B), а в нижней строке в виде столбцов, разделенных двойной вертикальной чертой, записываются обе возможности − ù A либо ù B, вместе с формулами W.

W, ù( A · B ). W, ù A || W,ù B

Пример:

" xF (x), " yG (y), ù(" xH (x) · F (y)) " xF (x)," yG (y), ù" xH (x) || " xF (x)," yG (y), ù F (y)

[ù·]

Знак [ù·] указывает, что совершена замена отрицания конъюнкции.

3. Замена дизъюнкции. Допустим, мы имеем ряд истинных формул W, A Ú B. Истинность формулы A Ú B означает истинность либо формулы A, либо формулы B, а это возможно, по крайней мере, в двух случаях: либо истинна формула A, либо истинна формула B. Поэтому в верхней строке пишутся исходные формулы W, A Ú B, а в нижней строке в виде столбцов, разделенных двойной вертикальной чертой, записываются обе возможности − A либо B, вместе с формулами W.

W, A Ú B . W, A || W, B

Пример:

" xF (x), " yG (y), " xH (x)Ú F (y) " xF (x)," yG (y), " xH (x) || " xF (x)," yG (y), F (y)

[Ú]

Знак [Ú] указывает, что совершена замена дизъюнкции.

4. Замена отрицания дизъюнкции. Допустим, мы имеем ряд истинных формул W, ù(A Ú B). Истинность формулы ù(A Ú B) означает ложность формулы A Ú B, а это возможно, если формулы A и B ложны. Поэтому формулу ù(A Ú B) можно заменить формулами ù A, ù B. В верхней строке пишутся исходные формулы W, ù(A Ú B), в нижнюю строку переносятся формулы W, а вместо ù(A Ú B) ставятся формулы ù A, ù B.

W, ù( A Ú B ) . W, ù A, ù B

Пример:

" xF (x)," yG (y), ù(" xH (x)Ú F (y)) " xF (x)," yG (y), ù" xH (x),ù F (y)

[ùÚ]

Знак [ùÚ] указывает, что совершена замена отрицания дизъюнкции.

5. Замена импликации. Допустим, мы имеем ряд истинных формул W, A → B. Истинность формулы A → B означает ложность формулы A либо истинность формулы B [15]. Поэтому в верхней строке пишутся исходные формулы W, A → B, а в нижней строке в виде столбцов, разделенных двойной вертикальной чертой, записываются обе возможности − ù A либо B, вместе с формулами W.

W, A → B . W, ù A || W, B

Пример:

" xF (x), " yG (y), " xH (x) → F (y) " xF (x)," yG (y), ù" xH (x) || " xF (x)," yG (y), F (y)

[→]

Знак [→] указывает, что совершена замена импликации.

6. Замена отрицания импликации. Допустим, мы имеем ряд истинных формул W, ù(A → B). Истинность формулы ù(A → B) означает ложность формулы A → B, а это возможно, если формула A истинна, а формула B ложна. Это означает, что формулу ù(A → B) можно заменить формулами A, ù B. В верхней строке пишутся исходные формулы W, ù(A → B), в нижнюю строку переносятся формулы W, а вместо ù(A → B) ставятся формулы A, ù B.

W, ù( A → B) . W, A, ù B

Пример:

" xF (x)," yG (y), ù(" xH (x)→ F (y)) " xF (x)," yG (y), " xH (x),ù F (y)

[ù→]

Знак [ù→] указывает, что совершена замена отрицания импликации.

7. Замена отрицания отрицания. Допустим, мы имеем ряд истинных формул W, ù ù A. Истинность формулы ù ù A означает ложность формулы ù A, что, в свою очередь, означает истинность формулы A. Поэтому формулу ù ù A можно заменить формулой A. В верхней строке пишутся исходные формулы W, ù ù A, в нижнюю строку переносятся формулы W, а вместо ù ù A ставится формула A.

W, ù ù A. W, A

Пример:

" xF (x)," yG (y), ù ù" xH (x). " xF (x)," yG (y), " xH (x)

[ù ù]

Знак [ù ù] указывает, что совершена замена отрицания отрицания.

8. Замена квантора общности. Допустим, мы имеем ряд истинных формул W, " xA. Истинность формулы " xA означает, что ее часть, формула A, превращается в истинное высказывание при замене всех свободных вхождений в ней переменной x произвольным замкнутым термом r [16]. Это означает, что формулу " xA можно заменить формулами " xA, A (r). Формула " xA сохраняется, чтобы в дальнейшем можно было, заменяя другие свободные переменные в формуле A, получать истинные формулы A (r ₁), A (r ₂) и т.д.

Поэтому в верхней строке пишутся исходные формулы W, " xA; эти же формулы переносятся в нижнюю строку с добавлением формулы A (r).

W, " xA . W, " xA (x), A (r)

Пример:

" xF (x)," yG (y), " xH (x) " xF (x)," yG (y), " xH (x), H (a)

["]

Знак ["] указывает, что совершена замена квантора общности.

9. Замена отрицания квантора общности. Допустим, мы имеем ряд истинных формул W, ù" xA. Истинность формулы ù" xA означает, что существует предмет, который не обладает соответствующим свойством. Обозначим этот предмет константой b. Подставляя ее вместо свободных вхождений переменной x в формулу A, получаем ложное высказывание A (b), что означает истинность высказывания ù A (b). Поэтому список W, ù" xA может быть заменен списком W, ù A (b).

Примечание: константа b должна отличаться от уже использованных констант в списке формул W, ù" xA, чтобы исключить возможность противоречащих высказываний относительно свойств предмета, соответствующего константе b, т.е. появления пары формул A (b) и ù A (b).

W, ù" xA . W,ù A (b)

Пример:

" xF (x, a)," yG (y, c), ù" xH (x) " xF (x, a)," yG (y, c), ù H (b)

[ù"]

Знак [ù"] указывает, что совершена замена отрицания квантора общности.

10. Замена квантора существования. Допустим, мы имеем ряд истинных формул W, $ xA. Истинность формулы $ xA означает, что существует, по крайней мере, один предмет, который обладает соответствующим свойством. Обозначим этот предмет константой b. Подставляя ее вместо свободных вхождений переменной x в формулу A, получаем истинное высказывание A (b). Поэтому список W, $ xA может быть заменен списком W, A (b).

Примечание: константа b должна отличаться от уже использованных констант в списке формул W, $ xA, чтобы исключить возможность противоречащих высказываний относительно свойств предмета, соответствующего константе b, т.е. появления пары формул A (b) и ù A (b).

W, $ xA . W, A (b)

Пример:

" xF (x, a)," yG (y, c), $ xH (x) " xF (x, a)," yG (y, c), H (b)

[$]

Знак [$] указывает, что совершена замена отрицания квантора общности.

11. Замена отрицания квантора существования. Допустим, мы имеем ряд истинных формул W, ù$ xA. Истинность формулы ù$ xA означает ложность формулы $ xA. Это, в свою очередь, означает, что ни один предмет не обладает соответствующим свойством, поэтому мы можем дополнить список W, ù$ xA формулой ù A (r), где r произвольный замкнутый терм. Формула ù$ xA сохраняется, чтобы в дальнейшем можно было, заменяя другие свободные переменные в формуле A, получать формулы ù A (r ₁), ù A (r ₂) и т.д.