Равносильные преобразования формул

Определение 17 Две формулы и алгебры логики предикатов называются равносильными на множестве М, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определённых на множестве М, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными и обозначать = .

В следующих теоремах приводятся наиболее важные равносильные формулы алгебры логики предикатов.

Теорема 8 (законы де Моргана для кванторов) Следующие формулы алгебры логики предикатов равносильны:

1) ;

2) ;

Доказательство. 1) Пусть А(х) – произвольный конкретный одноместный предикат, определённый на произвольном множестве М. Тогда и – высказывания.

Пусть =1. Тогда =0. Отсюда следует, что А(х) 1. А это значит, что 0. Теперь согласно определению 12 =1.

Пусть =0. Тогда =1. Отсюда следует, что А(х) 1. А это значит, что 0. Теперь, согласно определению 12 = 0.

Доказательство определения 2) приводится аналогично.

Следствие. Следующие формулы алгебры логики предикатов равносильны: =

Действительно, согласно теореме 8 и закону двойного отрицания получаем = = .

Теорема 9 (законы пронесения кванторов через конъюнкцию) Следующие формулы алгебры логики предикатов равносильны:

1 ) x(A (x) ·B (x))=( xA (x))·( xB (x));

2) x (A (x)· P)=( xA (x))· P.

Доказательство. 1) Пусть А(х),В(х) – произвольные одноместные предикаты, определённые на произвольном множестве М. Пусть x(А(х)·В(х)) =1. Тогда А(х)·В(х) ≡ 1. Согласно следствию из теоремы 2 А(х) ≡ 1 и В(х) ≡ 1 одновременно. Согласно определению 11 xA (x) = 1 и xВ (x) = 1. А это значит, что ( xA (x))·( xB (x)) = 1.

Пусть теперь x (А (х)· В (х)) = 0. Тогда согласно определению 11

А(х)·В(х) 1. Согласно следствию из теоремы 2 либо А(х) 1, либо

В(х) 1. Но тогда согласно определению 11 либо xA (x) = 0, либо xВ (x) = 0. А это значит, что ( xA (x))·( xB (x)) = 0.

2) Пусть А(х) – произвольный конкретный одноместный предикат, определённый на множестве М, а Р – произвольное конкретное высказывание.

Пусть x (А (х)· Р) = 1. Согласно определению 12 А(х)·Р 0. Отсюда нетрудно заметить, что А(х) 0 и Р =1. Тогда согласно определению 12 xА(х) = 1. А это значит, что ( xА (х))· Р = 1.

Пусть x (А (х)· Р) = 0. Тогда согласно определению 12 А(х)·Р ≡ 0. Но тогда либо А(х) ≡ 0, либо Р = 0. А это значит, что либо xА(х) = 0, либо Р =0. Отсюда следует, что ( xA (x))· P = 0. Теорема доказана.

Покажем, что квантор общности через дизъюнкцию проносить нельзя, т.е. .

Действительно, пусть А(х) – «х нечётное число», а В(х) – «х чётное число» два предиката, определённые на множестве натуральных чисел. Тогда x (А (х)Ú В (х)) – истинное высказывание «любое натуральное число либо чётно, либо нечётно». – ложное высказывание «любое натуральное число нечётно или натуральное число чётно».

Теорема 10 (законы пронесения кванторов через дизъюнкцию) Следующие формулы алгебры логики предикатов равносильны:

1 ) = ;

2 ) = ;

Доказательство. Пусть А(х), В(х) – произвольные конкретные одноместные предикаты, определённые на произвольном множестве М, а Р – произвольное конкретное высказывание.

1) Пусть = 1. Тогда 0. Согласно следствию из теоремы 3 либо А(х) 0, либо В(х) 0 одновременно. Согласно определению 12 либо =1, либо =1. А это значит, что = 1.

Пусть теперь = 0. Тогда согласно определению 12 ≡ 0. По следствию из теоремы 3 А(х) ≡ 0 и В(х) ≡ 0. Согласно определению 12 = 0 и = 0. А это значит, что = 0.

2) Пусть = 1. Тогда согласно определению 11 . А это значит, что либо А(х) ≡1, либо Р = 1. Отсюда либо = 1, либо

Р = 1. В любом случае = 1.

Пусть теперь = 0. Тогда согласно определению 11 1. Отсюда следует, что Р =0 и А(х) 1. Но тогда Р = 0 и = 0. Следовательно, = 0. Теорема доказана.

Покажем, что квантор существования через конъюнкцию проносить нельзя, т. е. .

Пусть А(х) = (x >2), определённый на R и В(х) = (х <2 ), определённый на R. Тогда = 1 и = 1. Следовательно, ()·() = 1. Очевидно, что = 0.

Теорема 11 (законы пронесения кванторов через импликацию) Следующие формулы алгебры логики предикатов равносильны:

1) = ;

2) = ;

3) = ;

4) = ;

Доказательство. Пусть А(х) – произвольный конкретный одноместный предикат, определённый на множестве М, а Р – произвольное конкретное высказывание.

1) Пусть = 1. Тогда согласно определению 11 ≡1. Отсюда нетрудно показать, что либо А(х) ≡ 0, либо Р = 1. А это значит, что либо = 0, либо Р = 1. В любом из этих случаев = 1.

Пусть теперь = 0. Тогда согласно определению 11 1. А это значит, что А(х) 1 и Р = 0. Тогда = 1 и Р = 0. Отсюда = 0.

2 ) Пусть = 1. Тогда согласно определению 11 0. Тогда либо Р = 1, либо А(х) 1. В любом случае = 1.

Пусть теперь = 0. Тогдасогласно определению 12 ≡0. А это значит, что А(х) ≡ 1 и Р = 0. Отсюда = 1 и Р = 0. А это значит, что = 0.

3) Пусть =1. Тогда согласно определению 11 ≡1. Отсюда либо Р = 0, либо А(х) 1. Следовательно, либо

Р = 0, либо = 1. В любом случае = 1.

Пусть теперь = 0. Тогда согласно определению 11 1. Тогда Р = 1 и А(х) 1. Отсюда Р = 1 и = 0. Следовательно = 0.

4) Пусть = 1. Тогда согласно определению 12 0. Отсюда либо Р = 0, либо А(х) 0. Следовательно, либо

Р = 0, либо =1. А это значит, что существует = 1.

Пусть теперь = 0. Тогда согласно определению 12 ≡ 0. Отсюда Р = 1 и А(х) ≡ 0. Следовательно Р = 1 и = 0. А это значит, что = 0. Теорема доказана.

Теорема 12 (законы коммутативности для кванторов): Следующие формулы алгебры логики предикатов равносильны:

1) = ;

2) .

Доказательство непосредственно следуют из определений 11 и 12.

Пример 1 Доказать, что следующая формула является тавтологией.

Доказательство. Пусть A (x)и B (x) ― произвольные конкретные предикаты, определённые на множестве M. Подставим их в исходную формулу, в результате получим высказывание. Покажем, что данное высказывание истинно.

Способ 1 Предположим противное. Пусть