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

Определение 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Предположим противное. Пусть