ВУЗ:
Составители:
Рубрика:
13
Таблица 1
AB
ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ИСТИНА
ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ
ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ
ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА
A
¬
()AB∧ ()AB∨ ()AB⇒ ()
A
B
⇔
Определение. Пусть G – формула. Таблицу, в которой ука-
заны все истинностные значения формулы
G при всевозможных
истинностных значениях атомов, входящих в
G , называют таб-
лицей истинности формулы
G .
Определение. Пусть
G – формула,
1
A ,
2
A , …,
n
A – вхо-
дящие в нее атомы. Приписывание истинностных значений ато-
мам
1
A ,
2
A , …,
n
A , при котором каждому из них приписано либо
ИСТИНА, либо ЛОЖЬ (но не оба вместе), называется интерпре-
тацией формулы
G
.
Определение. Говорят, что формула истинна при данной
интерпретации, если она принимает значение ИСТИНА в этой ин-
терпретации, в противном случае говорят, что
G ложна при этой
интерпретации.
Пример 2. Построим таблицу истинности для формулы
(( )) ( )
B
CA¬∧ ⇒¬
(табл. 2).
Таблица 2
ABC
1 ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА
2 ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ
3 ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ
4 ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА
5 ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ
6 ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА
7 ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА
A
¬
B
C∧
()BC¬∧ (( )) ( )BC A
¬
∧⇒¬
Из таблицы видим, что данная формула является истинной в
1, 4, 6, 7 и 8-й интерпретациях.
Определение. Говорят, что формула общезначима, если она
принимает значение ИСТИНА в любой интерпретации, то есть
при любых значениях входящих в нее атомов. Если формула лож-
14
на в каждой интерпретации, то говорят, что она противоречивая,
или невыполнимая.
Определение. Формула
B
является логическим следствием
формул
1
A ,
2
A , …,
n
A , если формула
12 n
AA A B
∧
∧∧ ⇒K об-
щезначима.
Определение. Формулы
A и
B
называются эквивалентны-
ми, если
A истинна тогда и только тогда, когда истинна .
B
Если
A
эквивалентна
B
, то будем писать A~B.
Теорема. Пусть формула
A
является частью формулы G ,
и A~B. Тогда формула
'
G , полученная из
G
заменой A на
B
, эк-
вивалентна
G .
Пример 3 (важный). Покажем, что формулы
()
PQ⇒ и
()
PQ¬∨
эквивалентны. Для этого составим таблицы истинности
обеих формул (табл. 3).
Таблица 3
PQ
ИСТИНА ИСТИНА ИСТИНА ИСТИНА
ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ
Л ОЖЬ ИСТИНА ИСТИНА ИСТИНА
()PQ⇒
()PQ¬∨
Из таблицы видим, что
(
)
PQ⇒ истинна тогда и только то-
гда, когда истинна
(
)
PQ¬∨ .
Пример 4. Рассмотрим два утверждения:
а)
1
F – Том не может быть хорошим студентом, если невер-
но, что он способный и его отец помогает ему.
б)
2
F – Том – хороший студент, только если отец помогает
ему.
Покажем, что второе утверждение есть логическое следст-
вие первого. Для этого запишем оба утверждения в виде формул.
Положим:
A – Том – хороший студент;
Таблица 1 на в каждой интерпретации, то говорят, что она противоречивая,
A B ¬A (A ∧ B) (A ∨ B) (A ⇒ B) (A ⇔ B) или невыполнимая.
ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ИСТИНА Определение. Формула B является логическим следствием
ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ формул A1 , A2 , …, An , если формула A1 ∧ A2 ∧ K ∧ An ⇒ B об-
ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ
ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА
щезначима.
Определение. Формулы A и B называются эквивалентны-
Определение. Пусть G – формула. Таблицу, в которой ука- ми, если A истинна тогда и только тогда, когда истинна B.
заны все истинностные значения формулы G при всевозможных Если A эквивалентна B , то будем писать A~B.
истинностных значениях атомов, входящих в G , называют таб- Теорема. Пусть формула A является частью формулы G ,
лицей истинности формулы G . и A~B. Тогда формула G ' , полученная из G заменой A на B , эк-
Определение. Пусть G – формула, A1 , A2 , …, An – вхо- вивалентна G .
дящие в нее атомы. Приписывание истинностных значений ато- Пример 3 (важный). Покажем, что формулы ( P ⇒ Q ) и
мам A1 , A2 , …, An , при котором каждому из них приписано либо ( ¬P ∨ Q ) эквивалентны. Для этого составим таблицы истинности
ИСТИНА, либо ЛОЖЬ (но не оба вместе), называется интерпре-
обеих формул (табл. 3).
тацией формулы G .
Определение. Говорят, что формула истинна при данной Таблица 3
интерпретации, если она принимает значение ИСТИНА в этой ин-
терпретации, в противном случае говорят, что G ложна при этой
P Q (P ⇒ Q) (¬ P ∨ Q )
интерпретации. ИСТИНА ИСТИНА ИСТИНА ИСТИНА
Пример 2. Построим таблицу истинности для формулы ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ
(¬( B ∧ C )) ⇒ (¬A) (табл. 2). ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА
Таблица 2 Из таблицы видим, что ( P ⇒ Q ) истинна тогда и только то-
A B C ¬A B∧C ¬ ( B ∧ C ) (¬( B ∧ C )) ⇒ ( ¬ A )
1 ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА гда, когда истинна ( ¬P ∨ Q ) .
2 ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ
3 ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ Пример 4. Рассмотрим два утверждения:
4 ЛОЖЬ ИСТИНА ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА а) F1 – Том не может быть хорошим студентом, если невер-
5 ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ
6 ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА но, что он способный и его отец помогает ему.
7 ЛОЖЬ ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА б) F2 – Том – хороший студент, только если отец помогает
ему.
Из таблицы видим, что данная формула является истинной в
Покажем, что второе утверждение есть логическое следст-
1, 4, 6, 7 и 8-й интерпретациях.
вие первого. Для этого запишем оба утверждения в виде формул.
Определение. Говорят, что формула общезначима, если она
Положим:
принимает значение ИСТИНА в любой интерпретации, то есть
при любых значениях входящих в нее атомов. Если формула лож- A – Том – хороший студент;
13 14
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
