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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
Следовательно, исходная формула – тавтология.
3. Доказать, что формула
(
)
(
)
CBACBA ∨∨
↔
∨∨ является тавтологией.
Доказательство. Допустим, что при некоторых значениях букв
()
0=∨∨ CBA
⎪
⎩
⎪
⎨
⎧
=
=∨
⇔
,0
,0
C
BA
⎪
⎩
⎪
⎨
⎧
=
=
=
⇔
,0
,0
,0
C
B
A
⎪
⎩
⎪
⎨
⎧
=∨
=
⇔
,0
,0
CB
A
()
.0=∨∨
⇔
CBA
Следовательно, исходная формула – тавтология.
Таким образом, тождественную истинность импликации удобно доказывать от
противного, а тождественную истинность эквиваленции установлением равенства
значений левой и правой части.
Теорема. Пусть формулы
A
и
B
A
→ – тавтологии. Тогда формула
B
–
тавтология.
Доказательство. Пусть
1
P
,
2
P
, …,
k
P
– буквы в формулах
A
и
B
A
→ . В
теории булевых функций было доказано, что все булевы функции, а, следовательно,
и формулы, можно считать зависящими от одного и того же количества букв.
Рассмотрим некоторый набор значений
1
σ
,
2
σ
, …,
k
σ
, где
{}
0,1∈
i
σ
,
k
i ,...,2,1
=
.
Подставим данный набор значений в формулы
A
и
B
A
→ вместо соответствующих
букв. Формулы являются тавтологиями по условию теоремы, следовательно,
()
1,...,,
21
=
k
A
σ
σ
σ
и
()
→
k
A
σ
σ
σ
,...,,
21
(
)
1,...,,
21
k
B
σ
σ
σ
. По таблице истинности
импликации получаем, что
()
1,...,,
21
k
B
σ
σ
σ
. Поскольку набор значений
1
σ
,
2
σ
,
…,
k
σ
был произволен, формула
B
– тавтология, что и требовалось доказать.
Теорема.
Пусть формула
A
– тавтология,
1
P
,
2
P , …,
k
P – буквы в формуле
A
,
1
A
,
2
A , …,
k
A – любые формулы. Тогда новая формула
()
k
AAAAB ,...,,
21
= –
тавтология.
Доказательство аналогично доказательству предыдущей теоремы.
В
Содержание.
Отношения логической эквивалентности и логического следствия.
Определение.
Формулы
A
и
B
называются логически эквивалентными тогда
и только тогда, когда формула
B
A
↔
– тавтология. 
       Следовательно, исходная формула – тавтология.

       3. Доказать, что формула ( A ∨ B ) ∨ C ↔ A ∨ (B ∨ C ) является тавтологией.
       Доказательство. Допустим, что при некоторых значениях букв
                     ⎧ A ∨ B = 0,   ⎧ A = 0,   ⎧ A = 0,
                                    ⎪
( A ∨ B ) ∨ C = 0 ⇔ ⎪⎨                         ⎪
                                  ⇔ ⎨ B = 0, ⇔ ⎨            ⇔ A ∨ (B ∨ C ) = 0.
                     ⎪ C = 0,       ⎪          ⎪ B ∨ C = 0,
                     ⎩              ⎩ C = 0,   ⎩
       Следовательно, исходная формула – тавтология.

     Таким образом, тождественную истинность импликации удобно доказывать от
противного, а тождественную истинность эквиваленции установлением равенства
значений левой и правой части.

        Теорема. Пусть формулы A и A → B – тавтологии. Тогда формула B –
тавтология.
        Доказательство. Пусть P1 , P2 , …, Pk – буквы в формулах A и A → B . В
теории булевых функций было доказано, что все булевы функции, а, следовательно,
и формулы, можно считать зависящими от одного и того же количества букв.
Рассмотрим некоторый набор значений σ 1 , σ 2 , …, σ k , где σ i ∈ {0,1} , i = 1,2,..., k .
Подставим данный набор значений в формулы A и A → B вместо соответствующих
букв. Формулы являются тавтологиями по условию теоремы, следовательно,
A(σ 1 , σ 2 ,..., σ k ) = 1 и A(σ 1 ,σ 2 ,...,σ k ) → B(σ 1 , σ 2 ,..., σ k ) = 1 . По таблице истинности
импликации получаем, что B(σ 1 , σ 2 ,..., σ k ) = 1 . Поскольку набор значений σ 1 , σ 2 ,
…, σ k был произволен, формула B – тавтология, что и требовалось доказать.

      Теорема. Пусть формула A – тавтология, P1 , P2 , …, Pk – буквы в формуле
A , A 1 , A2 , …, Ak – любые формулы. Тогда новая формула B = A( A1 , A2 ,..., Ak ) –
тавтология.
      Доказательство аналогично доказательству предыдущей теоремы.

В Содержание.




       Отношения логической эквивалентности и логического следствия.

      Определение. Формулы A и B называются логически эквивалентными тогда
и только тогда, когда формула A ↔ B – тавтология.




                                                   11

Страницы