Файл: Учебник для сопровождения лекций и практических занятий.pdf

III.4. Импликация
Логическая функция импликация паре высказываний ???? и ????
сопоставляет высказывание ???? ⇒ ???? ,
логически эквивалент- ное высказыванию «если ????, то ???? ».
Высказывание ???? называется посылкой, а ???? — заключением.
Логической операции «импликация» соответ- ствует одноименная булева функция импли- кация (но обозначаемая ???? → ???? по сравнению с логической функцией ???? ⇒ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 0 1 1
1 0 0
1 1 1
Верна ли теорема Пифагора «в прямоугольном треугольнике квад- рат длины наибольшей стороны равен сумме квадратов длин других сторон» для равностороннего треугольника?
Если неверна, то получается, что равносторонний треугольник опровергает теорему Пифагора!
192

III.4. Импликация
Логическая функция импликация паре высказываний ???? и ????
сопоставляет высказывание ???? ⇒ ???? ,
логически эквивалент- ное высказыванию «если ????, то ???? ».
Высказывание ???? называется посылкой, а ???? — заключением.
Логической операции «импликация» соответ- ствует одноименная булева функция импли- кация (но обозначаемая ???? → ???? по сравнению с логической функцией ???? ⇒ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 0 1 1
1 0 0
1 1 1
Верна ли теорема Пифагора «в прямоугольном треугольнике квад- рат длины наибольшей стороны равен сумме квадратов длин других сторон» для равностороннего треугольника?
Если неверна, то получается, что равносторонний треугольник опровергает теорему Пифагора! Нонсенс!
193

III.4. Импликация
Логическая функция импликация паре высказываний ???? и ????
сопоставляет высказывание ???? ⇒ ???? ,
логически эквивалент- ное высказыванию «если ????, то ???? ».
Высказывание ???? называется посылкой, а ???? — заключением.
Логической операции «импликация» соответ- ствует одноименная булева функция импли- кация (но обозначаемая ???? → ???? по сравнению с логической функцией ???? ⇒ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 0 1 1
1 0 0
1 1 1
Верна ли теорема Пифагора «в прямоугольном треугольнике квад- рат длины наибольшей стороны равен сумме квадратов длин других сторон» для равностороннего треугольника?
Значит, надо считать, что для равностороннего треугольника тео- рему Пифагора (теорема «в целом»!) верна!
194

III.4. Импликация
Логическая функция импликация паре высказываний ???? и ????
сопоставляет высказывание ???? ⇒ ???? ,
логически эквивалент- ное высказыванию «если ????, то ???? ».
Высказывание ???? называется посылкой, а ???? — заключением.
Логической операции «импликация» соответ- ствует одноименная булева функция импли- кация (но обозначаемая ???? → ???? по сравнению с логической функцией ???? ⇒ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
0 1 1
1 0 0
1 1 1
Утверждение об истинности импликации с ложной посылкой на сленге звучит так: «из лжи следует вс¨е, что угодно».
195

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
196

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Отметим, что высказывание ???? ⇔ ????
логически эквивалент- но высказываниям «для ???? необходимо и достаточно, чтобы ???? »,
«???? равносильно ???? », «????, если и только если ???? ».
197

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
198

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
Если оба высказывания ???? и ???? истинны или оба высказывания ????
и ???? ложны, то очевидно, эквиваленция ???? ⇒ ???? является
199

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1 1
Если оба высказывания ???? и ???? истинны или оба высказывания ????
и ???? ложны, то очевидно, эквиваленция ???? ⇒ ???? является
200

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1 1
Если оба высказывания ???? и ???? истинны или оба высказывания ????
и ???? ложны, то очевидно, эквиваленция ???? ⇒ ???? является истинной.
201

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
1 1 1
Если оба высказывания ???? и ???? истинны или оба высказывания ????
и ???? ложны, то очевидно, эквиваленция ???? ⇒ ???? является истинной.
202

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
1 1 1
Если одно из высказываний ????, ???? истинно, а другое ложно, то оче- видно, эквиваленция ???? ⇒ ???? является
203

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
0 1 1 0 1 1 1
Если одно из высказываний ????, ???? истинно, а другое ложно, то оче- видно, эквиваленция ???? ⇒ ???? является
204

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
0 1 1 0 1 1 1
Если одно из высказываний ????, ???? истинно, а другое ложно, то оче- видно, эквиваленция ???? ⇒ ???? является ложной.
205

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
0 1 0
1 0 0
1 1 1
Если одно из высказываний ????, ???? истинно, а другое ложно, то оче- видно, эквиваленция ???? ⇒ ???? является ложной.
206

III.5. Эквиваленция
Логическая функция эквиваленция паре высказываний ???? и ????
сопоставляет высказывание ???? ⇔ ???? ,
логически эквивалент- ное высказыванию «???? тогда и только тогда, когда ???? ».
Логической операции «эквиваленция» соответ- ствует одноименная булева функция эквива- ленция (но обозначаемая ???? ↔ ???? по сравнению с логической функцией ???? ⇔ ???? ), которую можно задать таблицей истинности:
???? ???? ???? → ????
0 0 1
0 1 0
1 0 0
1 1 1
Очевидно, что эквиваленция является отрицанием «исключающего
ИЛИ», т.е. отрицанием к высказыванию «либо ????, либо ???? ».
207

III.6. Элементарные булевы и логические функции
???? ???? ¬???? = ???? ????&???? = ???? ∧ ???? ???? ∨ ???? ???? → ???? ???? ↔ ????
0 0 1
0 0
1 1
0 1 1
0 1
1 0
1 0 0
0 1
0 0
1 1 0
1 1
1 1
¬????
∼
????
∼
«НЕ ????»;
????&????
∼
???? ∧ ????
∼
«???? И ???? »;
???? ∨ ????
∼
«???? ИЛИ ???? »;
???? ⇒ ????
∼
«ЕСЛИ ????, ТО ???? »;
???? ⇔ ????
∼
«???? ТОГДА И ТОЛЬКО ТОГДА, КОГДА ???? ».
Восстановление высказывания ???? по его логическому значению ????:
????
∼
???? = 1.
(1)
208

IV. Отрицания к базовым логическим функциям
1) ¬ (¬????) = ????;
2) ¬ (????&????) = ¬ (???? ∧ ????) = (¬????) ∨ (¬????) :
}︂
законы
3) ¬ (???? ∨ ????) = (¬????)&(¬????) = (¬????) ∧ (¬????) : де-Моргана;
4) ¬ (???? → ????) = (¬????) ∨ ????;
5) ¬ (???? ↔ ????) = ((¬????) ∧ ????) ∨ (???? ∧ (¬????)) .
209

V. Предикаты и кванторы
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
210

V. Предикаты и кванторы
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Например, значение высказывания ???? < 0 определяется значением переменной ????:
при ???? = 3 высказывание ???? < 0 является
211

V. Предикаты и кванторы
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Например, значение высказывания ???? < 0 определяется значением переменной ????:
при ???? = 3 высказывание ???? < 0 является ложным;
212

V. Предикаты и кванторы
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Например, значение высказывания ???? < 0 определяется значением переменной ????:
при ???? = 3 высказывание ???? < 0 является ложным;
при ???? = −5 высказывание ???? < 0 является истинным;
213

V. Предикаты и кванторы
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Например, значение высказывания ???? < 0 определяется значением переменной ????:
при ???? = 3 высказывание ???? < 0 является ложным;
при ???? = −5 высказывание ???? < 0 является истинным;
при ???? = 0 высказывание ???? < 0 является ложным.
214

V.1. Предикат-высказывание и предикат-функция
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
215

V.1. Предикат-высказывание и предикат-функция
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Есть и принципиально другая трактовка понятия «предикат»: по- скольку в логике важна только истинность или ложность высказы- вания ???? (????
1
, ????
2
, . . . , ????
????
)
(
остальными характеристиками мы пре- небрегаем), то предикатом («предикатом-функцией») на множестве
Ω
1
× Ω
2
× . . . Ω
n называют ещ¨е и функцию ???? (????
1
, ????
2
, . . . , ????
????
)
, область значений которой включается во множество {0; 1}.
216

V.1. Предикат-высказывание и предикат-функция
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Высказыванию ???? (????
1
, ????
2
, . . . , ????
????
)
, где ????
????
∈ Ω
????
соответствует предикат («предикат-функция») ???? (????
1
, ????
2
, . . . , ????
????
)
, область значений которой включается во множество {0; 1}.
Есть и принципиально другая трактовка понятия «предикат»: по- скольку в логике важна только истинность или ложность высказы- вания ???? (????
1
, ????
2
, . . . , ????
????
)
(
остальными характеристиками мы пре- небрегаем), то предикатом («предикатом-функцией») на множестве
Ω
1
× Ω
2
× . . . Ω
n называют ещ¨е и функцию ???? (????
1
, ????
2
, . . . , ????
????
)
, область значений которой включается во множество {0; 1}.
217

V.1. Предикат-высказывание и предикат-функция
Если истинность (и ложность) высказывания ???? определяется значениям и некоторых параметров ????
1
, ????
2
, . . . , ????
????
, говорят, что за- дан предикат ???? (????
1
, ????
2
, . . . , ????
????
)
Высказыванию ???? (????
1
, ????
2
, . . . , ????
????
)
, где ????
????
∈ Ω
????
соответствует предикат («предикат-функция») ???? (????
1
, ????
2
, . . . , ????
????
)
, область значений которой включается во множество {0; 1}.
Здесь ???? (????
1
, ????
2
, . . . , ????
????
) = 1
означает истинность высказыва- ния ???? (????
1
, ????
2
, . . . , ????
????
)
, а ???? (????
1
, ????
2
, . . . , ????
????
) = 0
мы трактуем как лож- ность высказывания ???? (????
1
, ????
2
, . . . , ????
????
)
218