Математическая логика и теория алгоритмов. Сергиевская И.М. - 7 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

12
Замечание. Формула
B
A
↔ – тавтология, если таблицы истинности формул
A
и
B
совпадают.
Пример. По законам де Моргана, логически эквивалентны формулы
(
)
BA
∧
¬
и
B
A
¬∨¬
, а также формулы
(
)
BA ∨¬ и
B
A
¬
∧
¬
.
Теорема. Отношение логической эквивалентности является отношением
эквивалентности.
Рефлексивность, симметричность и транзитивность данного отношения
следуют из замечания.
Справедливы правило подстановки и правило замены.
Пусть
F
и
G
– формулы, содержащие букву
A
,
A
H
F и
A
H
G – формулы,
полученные из формул
F
и
G
соответственно подстановкой вместо буквы
A
формулы
.
Правило подстановки. Если формула
F
логически эквивалентна формуле
G
, то формула
A
H
F логически эквивалентна формуле
A
H
G .
Пусть
G
F – формула, в которой выделена некоторая подформула
G
,
H
F –
формула, полученная из формулы
G
F
заменой
G
на некоторую формулу
.
Правило замены. Если формулы
G
и
логически эквивалентны, то
логически эквивалентны и формулы
G
F
и
H
F
.
Доказательства правил подстановки и замены основано на сравнении таблиц
истинности соответствующих формул.
Пример.
Известна тавтология
(
)( )
BABA ∨¬
↔
→ (проверьте
самостоятельно). По правилу подстановки, формула
()
BA →¬ логически
эквивалентна формуле
()
BA ∨¬¬ . По правилу замены, примененному к закону
двойного отрицания, получаем, что формула
(
)
BA ∨
¬
¬ логически эквивалентна
формуле
()
BA ∨ . Следовательно, по свойству транзитивности, формулы
(
)
BA →
¬
и
()
BA ∨ логически эквивалентны.
Определение. Говорят, что формула
A
логически влечет формулу
B
(из
формулы
A
логически следует формула
B
), если формула
B
A
→ является
тавтологией.
Теорема. Отношение логического следствия является отношением
предпорядка, то есть рефлексивным и транзитивным отношением. 
    Замечание. Формула A ↔ B – тавтология, если таблицы истинности формул
A и B совпадают.

     Пример. По законам де Моргана, логически эквивалентны формулы ¬( A ∧ B )
и ¬A ∨ ¬B , а также формулы ¬( A ∨ B ) и ¬A ∧ ¬B .

     Теорема. Отношение логической эквивалентности является отношением
эквивалентности.
     Рефлексивность, симметричность и транзитивность данного отношения
следуют из замечания.

     Справедливы правило подстановки и правило замены.

     Пусть F и G – формулы, содержащие букву A , FHA и GHA – формулы,
полученные из формул F и G соответственно подстановкой вместо буквы A
формулы H .

       Правило подстановки. Если формула F логически эквивалентна формуле
G , то формула FHA логически эквивалентна формуле GHA .

     Пусть FG – формула, в которой выделена некоторая подформула G , FH –
формула, полученная из формулы FG заменой G на некоторую формулу H .

     Правило замены. Если формулы G и H логически эквивалентны, то
логически эквивалентны и формулы FG и FH .

     Доказательства правил подстановки и замены основано на сравнении таблиц
истинности соответствующих формул.

       Пример.       Известна     тавтология      ( A → B ) ↔ (¬A ∨ B ) (проверьте
самостоятельно). По правилу подстановки, формула (¬A → B ) логически
эквивалентна формуле (¬¬A ∨ B ) . По правилу замены, примененному к закону
двойного отрицания, получаем, что формула (¬¬A ∨ B ) логически эквивалентна
формуле ( A ∨ B ) . Следовательно, по свойству транзитивности, формулы (¬A → B ) и
( A ∨ B ) логически эквивалентны.
      Определение. Говорят, что формула A логически влечет формулу B (из
формулы A логически следует формула B ), если формула A → B является
тавтологией.

     Теорема. Отношение логического следствия является               отношением
предпорядка, то есть рефлексивным и транзитивным отношением.



                                        12

Страницы