Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 43 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

43
ИyyFЛxxF
n1n1
=
= ),...,(,),...,(
- необщезначима,
непротиворечива
ЛxxF
n1
≡),...,( - противоречива, необщезначима.
Определение
. Пусть даны формулы F
1
,…,F
n
и формула G. G
есть логическое следствие формул F
1
,…,F
n
тогда и только тогда,
когда для всякой интерпретации I, в которой F
1
∧
…
∧
F
n
истинна, G
также истинна. (F
1
,…,F
n
называется посылками).
Теорема 9
.1. G есть логическое следствие F
1
,…,F
n
тогда и
только тогда, когда формула ((F
1
∧
…
∧
F
n
)
→
G) общезначима.
Доказательство
. Обозначим H= ((F
1
∧
…
∧
F
n
)
→
G).
Необходимость
. Пусть G - логическое следствие F
1
,…,F
n
. Если
F
i
=И, n1i ,= , то ИG = , следовательно Н=И. Если некоторое F
i
=Л
в интерпретации I, то F
1
∧
…
∧
F
n
=Л в этой интерпретации,
следовательно при G= И или G=Л обязательно H=И, т.е. H –
общезначима.
Достаточность
. Пусть H–общезначима. Тогда если F
1
∧
…
∧
F
n
=И
в интерпретации I, то G=И в этой интерпретации, т.е. G -
логическое следствие.
Теорема 9.2
. G есть логическое следствие F
1
,…,F
n
тогда и
только тогда, когда формула (F
1
∧
…
∧
F
n
∧
(
⎤
G)) противоречива.
Доказательство
Из теоремы 9.1. G -логическое следствие ⇔
((F
1
∧
…
∧
F
n
)
→
G) общезначима, т.е. ))(( GFF
n1
→∧ -
противоречива. Но
).()(
))(())((
GFFGFF
GFFGFF
n1n1
n1n1
∧∧∧=∨∨∨=
=∨∧=→∧∧
Пример 9.1.
Если конгресс отказывается принять новые законы, то
забастовка не будет окончена, кроме может быть случая, когда
она длится более года и президент фирмы уйдет в отставку.
Допустим, что конгресс отказывается действовать, забастовка
оканчивается и президент фирмы не уходит. Длилась ли
забастовка более года?
Ответ на этот вопрос может быть дан
с помощью исчисления
высказываний.
Обозначим элементарные высказывания через

Страницы