yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.6. Логическое следование и равносильность формул

Математическая логика

4.6. Логическое следование и равносильность формул

Определение 4.11. Говорят, что формула В логически следует из формулы А, если в любой интерпретации, в которой А принимает истинные значения, В также принимает истинные значения. Обозначение: А 1=В.

Определение 4.12. Говорят, что формула А равносильна, или логически эквивалентна формуле В тогда и только тогда, если А |=В & В|=А. Обозначение: АВ

Утверждения.

1.   формула А |=В тогда и только тогда, если |=АВ;

2.   А12,..,Аn|=В, тогда и только тогда, если |=А12&...&Аn В;

3.   АВ тогда и только тогда, если |=АВ             ,.

4.    если A|=B, |A|=T, то |В|=Т в некоторой интерпретации;

5.   если Г|=В, i(|Г1|=T), то |B|=Т.

4.7. Основные правила выхода алгебры предикатов.

1. Правило универсальной конкретизации

xA(x) |=A(y) если у свободно для х в А(х).

Доказательство: Нужно доказать, что если |xA'(x) |=T, то |А'(у)|=Т в некоторой интерпретации D. Допустим |A'(y) |=F. Тогда существует у=b, bD, такое что |A'(b) | =F. Но по условию на области D формула |хА'(х)|=Т, а т.к. bD то |xA'(x)|=F на D. Полученное противоречие доказывает теорему.

2. Правило экзистенциальной конкретизации

хА(х) |=A(b), bD

Доказательство: Допустим |хА'(х)|=Т на D. Тогда существует такое х=b, что |А'(b)|=Т, bD, и следовательно, хА'(х)|=Т.

3. Правило экзистенциального обобщения А(у) |=хА(х), где х -свободно для у в Л(у).

Доказательство: Если |A'(у)|=Т на D, то существует y=b, bD, такое что |А'(b) I =Т. Следовательно, | хА'(х) | =Т на D

4. Правило всеобщности.

СА(х) |=САх(А(х))

Доказательство: По условию |CA'(x)|=T на D. Это возможно, если

a) |C|=F. тогда |CA'(x) |=T и |CxA'(x) |=T;

b) |С|=T, |СА'(х)|=Т, следовательно, |А'(х)|=Т на D для любого х, значит |CxA'(x) |=T.

5. Правило существования

А(х) С |=хА(х) С

Доказательство: | А'(х) С | =Т на D. Допустим |хА'(х) С|=Р на D. Тогда |C|=F, (С не зависит от х) и |хА'(х)|=Т, следовательно, существует х=b, такое что |А'(b)|=Т и |A`(b) C|=F, в то время как по условию |A'(x) C|=T на D. Полученное противоречие доказывает теорему.

7. Правило обобщения (Gen)

Если Г |=А(х), то Г |=xA(x), если х не свободно в ни в одну из формул Г.

Доказательство: Предположим, выбрана область интерпретации D и произведена замена в А всех свободных переменных на элементы из D, например, x=bD. Тогда |А'(b)|=Т, т.к |Г1|=Т,У)..

Так как х не входит свободно в Г, .то следовательно во множестве Г замены х на Ь не было и, следовательно, для xD, такого что |А'(х)|=Т, |Г||=А'(х), следовательно Г |=xA'(x).

 

28