Математическая логика и теория алгоритмов [Г. И. Анкудинов] (pdf) читать постранично, страница - 2
- Математическая логика и теория алгоритмов 858 Кб, 103с. скачать: (pdf) - (pdf+fbd) читать: (полностью) - (постранично) - Г. И. Анкудинов
Книга в формате pdf! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
- 1
- 2
- 3
- 4
- . . .
- последняя (9) »
тогда и только тогда, когда A и B
одновременно ложны, а в остальных случаях истинна (табл.1.3).
Дизъюнкцию также иногда именуют логической
Таблица 1.3
суммой.
A B
A\/B
Л Л
Л
Следует обратить внимание на то, что если в
Л И
И
таблице истинности для дизъюнкции заменим все
И Л
И
Л на И и все И на Л (как для операндов, так и для
И И
И
результата операции), то получим таблицу
истинности для конъюнкции).
Импликацией двух высказываний A и B
Таблица 1.4
называется
новое
высказывание,
которое
A B
A→B
обозначается A→B (варианты чтения: "Если A, то
Л Л
И
B"; "То, что A, влечет то, что B"; "A только тогда,
Л И
И
когда B"; "То, что A, есть достаточное условие
И Л
Л
того, что B"; "Чтобы A, необходимо, чтобы B").
И И
И
Высказывание A→B ложно тогда и только тогда,
когда A истинно, а B ложно (табл.1.4). В составе импликации A→B
88
высказывание A называется условием или посылкой, а высказывание
B – заключением или следствием.
Примечание. Импликация A→B может быть записана также как
B←A (читается: "B при условии, что A", "То, что B, есть необходимое
условие того, чтобы A", "Чтобы B, достаточно того, чтобы A".)
Эквивалентностью двух высказываний A и B называется новое
высказывание, которое обозначается A↔B ( читается: "A
эквивалентно B", "A, тогда и только тогда, когда
Таблица 1.5
B"; "A, если и только если B", "Чтобы A,
A B
A↔B
необходимо и достаточно, чтобы B"; "То, что A,
Л Л
И
есть необходимое и достаточное условие для
Л И
Л
И Л
Л
того, чтобы B"). Высказывание A↔B истинно
И И
И
тогда и только тогда, когда значения истинности
A и B совпадают (табл.1.5).
Часто в литературе, особенно в технических приложениях, для
логического значения "истина" вместо И используется обозначение
1, а для логического значения "ложь" вместо Л – обозначение 0.
1.2. Составные высказывания
С помощью логических операций, рассмотренных в п.1.1,
можно из простых высказываний строить различные составные
высказывания. Например, из высказываний A, B и C можно
построить составные высказывания
⎤(A & B) \/ C
и
A → [ B ↔ (A \/ C)].
Логическое значение составного высказывания зависит только от
логических значений образующих его элементарных высказываний.
Например, если A = 0, B = 1 и C = 0, то
⎤(A & B) \/ C = ⎤(0 & 1) \/ 0 =⎯0 \/ 0 =1 \/ 0= 1 и
A → [B ↔ (A \/ C)] = 0 → [1 ↔ (0 \/ 0)] =
0 → [1 ↔ 0] = 0 → 0 = 1.
Формулой исчисления высказываний называются
89
а) отдельные буквы, обозначающие переменные высказывания
(P1, P2,...,PN);
б) выражения вида ⎤(Ф), (Ф1)&(Ф2), (Ф1)\/(Ф2), (Ф1)→(Ф2),
(Ф1)↔(Ф2), где Ф, Ф1, Ф2 - некоторые формулы.
Формулу, состоящую из переменных P1, P2, ..., PN, логических
символов и скобок, будем обозначать
Таблица 1.6
Ф(P1, P2, ..., PN). Если в формулу Ф
P1 P2 P3
⎤(P1 & P2) \/ P3
вместо переменных P1, P2, ..., PN
0 0 0
1
0 0 1
1
подставить
высказывания A1, A2, ...,
0 1 0
1
то
получим
составное
AN,
0 1 1
1
высказывание Ф(A1, A2, ..., AN),
1 0 0
1
1 0 1
1
имеющее
конкретное
логическое
1 1 0
0
значение. Зависимость логического
1 1 1
1
значения Ф(A1, A2, ..., AN) от P1, P2, ...,
можно
выразить
таблицей
PN
истинности. Например, таблица 1.6 выражает такую зависимость для
формулы ⎤(P1 & P2 ) \/ P3. Формула исчисления высказываний Ф(P1,
P2,..., PN) называется тавтологией или тождественно истинной,
если ее значение для любых значений P1, P2,..., PN есть истина.
1.3. Основные тавтологии
Закон исключенного третьего:
⎯P \/ P .
(1.1)
Закон отрицания противоречия:
⎤(⎯P & P).
(1.2)
Закон двойного отрицания:
⎤ ⎤P↔ P.
Следующие
дизъюнкции.
законы
выражают
90
(1.3)
свойства
конъюнкции
и
Законы идемпотентности:
(P & P) ↔ P,
(1.4)
(P \/ P) ↔ P.
(1.5)
Законы упрощения:
(P1 & P2) → P1,
(1.6)
P1 → (P1 \/ P2).
(1.7)
Законы коммутативности:
(P1 & P2) ↔ (P2 & P1),
(1.8)
(P1 \/ P2) ↔ (P2 \/ P1).
(1.9)
Законы ассоциативности:
[(P1 & P2) & P3] ↔ [P1 & (P2 & P3)],
(1.10)
[(P1 \/ P2) \/ P3] ↔ [P1 \/ (P2 \/ P3)].
(1.11)
Законы дистрибутивности:
[(P1 \/ P2) & P3] ↔ [(P1 & P3) \/ (P2 & P3)],
(1.12)
[(P1&P2)\/P3]↔[(P1\/P3)&(P2\/P3)].
(1.13)
Закон де-Моргана:
⎤(P1 & P2) ↔ (⎯P1 \/⎯P2),
(1.14)
⎤(P1 \/ P2) ↔ (⎯P1 &⎯P2).
(1.15)
Следующие законы
эквивалентности.
Закон тождества:
выражают
свойства
P → P.
импликации
и
(1.16)
Закон контрапозиции:
(P1 → P2) ↔ (⎯P2 →⎯P1)).
(1.17)
Правило цепного заключения:
[(P1 → P2) & (P2 → P3)] → (P1 → P3).
91
(1.18)
Законы рефлексивности, симметричности и транзитивности:
P ↔ P,
(1.19)
(P1 ↔ P2) ↔ (P2 ↔ P1),
(1.20)
[(P1 ↔ P2) & (P2 ↔ P3)] → (P1 ↔ P3).
(1.21)
Закон противоположности:
(P1↔P2)↔(⎯P1↔⎯P2).
(1.22)
Следующие законы выражают зависимости между основными
логическими операциями.
Выражение конъюнкции через дизъюнкцию и отрицание и
дизъюнкции через конъюнкцию и отрицание:
(P1 & P2) ↔ ⎤(⎯P1 \/⎯P2),
(1.23)
(P1 \/ P2) ↔⎤ (⎯P1 &
одновременно ложны, а в остальных случаях истинна (табл.1.3).
Дизъюнкцию также иногда именуют логической
Таблица 1.3
суммой.
A B
A\/B
Л Л
Л
Следует обратить внимание на то, что если в
Л И
И
таблице истинности для дизъюнкции заменим все
И Л
И
Л на И и все И на Л (как для операндов, так и для
И И
И
результата операции), то получим таблицу
истинности для конъюнкции).
Импликацией двух высказываний A и B
Таблица 1.4
называется
новое
высказывание,
которое
A B
A→B
обозначается A→B (варианты чтения: "Если A, то
Л Л
И
B"; "То, что A, влечет то, что B"; "A только тогда,
Л И
И
когда B"; "То, что A, есть достаточное условие
И Л
Л
того, что B"; "Чтобы A, необходимо, чтобы B").
И И
И
Высказывание A→B ложно тогда и только тогда,
когда A истинно, а B ложно (табл.1.4). В составе импликации A→B
88
высказывание A называется условием или посылкой, а высказывание
B – заключением или следствием.
Примечание. Импликация A→B может быть записана также как
B←A (читается: "B при условии, что A", "То, что B, есть необходимое
условие того, чтобы A", "Чтобы B, достаточно того, чтобы A".)
Эквивалентностью двух высказываний A и B называется новое
высказывание, которое обозначается A↔B ( читается: "A
эквивалентно B", "A, тогда и только тогда, когда
Таблица 1.5
B"; "A, если и только если B", "Чтобы A,
A B
A↔B
необходимо и достаточно, чтобы B"; "То, что A,
Л Л
И
есть необходимое и достаточное условие для
Л И
Л
И Л
Л
того, чтобы B"). Высказывание A↔B истинно
И И
И
тогда и только тогда, когда значения истинности
A и B совпадают (табл.1.5).
Часто в литературе, особенно в технических приложениях, для
логического значения "истина" вместо И используется обозначение
1, а для логического значения "ложь" вместо Л – обозначение 0.
1.2. Составные высказывания
С помощью логических операций, рассмотренных в п.1.1,
можно из простых высказываний строить различные составные
высказывания. Например, из высказываний A, B и C можно
построить составные высказывания
⎤(A & B) \/ C
и
A → [ B ↔ (A \/ C)].
Логическое значение составного высказывания зависит только от
логических значений образующих его элементарных высказываний.
Например, если A = 0, B = 1 и C = 0, то
⎤(A & B) \/ C = ⎤(0 & 1) \/ 0 =⎯0 \/ 0 =1 \/ 0= 1 и
A → [B ↔ (A \/ C)] = 0 → [1 ↔ (0 \/ 0)] =
0 → [1 ↔ 0] = 0 → 0 = 1.
Формулой исчисления высказываний называются
89
а) отдельные буквы, обозначающие переменные высказывания
(P1, P2,...,PN);
б) выражения вида ⎤(Ф), (Ф1)&(Ф2), (Ф1)\/(Ф2), (Ф1)→(Ф2),
(Ф1)↔(Ф2), где Ф, Ф1, Ф2 - некоторые формулы.
Формулу, состоящую из переменных P1, P2, ..., PN, логических
символов и скобок, будем обозначать
Таблица 1.6
Ф(P1, P2, ..., PN). Если в формулу Ф
P1 P2 P3
⎤(P1 & P2) \/ P3
вместо переменных P1, P2, ..., PN
0 0 0
1
0 0 1
1
подставить
высказывания A1, A2, ...,
0 1 0
1
то
получим
составное
AN,
0 1 1
1
высказывание Ф(A1, A2, ..., AN),
1 0 0
1
1 0 1
1
имеющее
конкретное
логическое
1 1 0
0
значение. Зависимость логического
1 1 1
1
значения Ф(A1, A2, ..., AN) от P1, P2, ...,
можно
выразить
таблицей
PN
истинности. Например, таблица 1.6 выражает такую зависимость для
формулы ⎤(P1 & P2 ) \/ P3. Формула исчисления высказываний Ф(P1,
P2,..., PN) называется тавтологией или тождественно истинной,
если ее значение для любых значений P1, P2,..., PN есть истина.
1.3. Основные тавтологии
Закон исключенного третьего:
⎯P \/ P .
(1.1)
Закон отрицания противоречия:
⎤(⎯P & P).
(1.2)
Закон двойного отрицания:
⎤ ⎤P↔ P.
Следующие
дизъюнкции.
законы
выражают
90
(1.3)
свойства
конъюнкции
и
Законы идемпотентности:
(P & P) ↔ P,
(1.4)
(P \/ P) ↔ P.
(1.5)
Законы упрощения:
(P1 & P2) → P1,
(1.6)
P1 → (P1 \/ P2).
(1.7)
Законы коммутативности:
(P1 & P2) ↔ (P2 & P1),
(1.8)
(P1 \/ P2) ↔ (P2 \/ P1).
(1.9)
Законы ассоциативности:
[(P1 & P2) & P3] ↔ [P1 & (P2 & P3)],
(1.10)
[(P1 \/ P2) \/ P3] ↔ [P1 \/ (P2 \/ P3)].
(1.11)
Законы дистрибутивности:
[(P1 \/ P2) & P3] ↔ [(P1 & P3) \/ (P2 & P3)],
(1.12)
[(P1&P2)\/P3]↔[(P1\/P3)&(P2\/P3)].
(1.13)
Закон де-Моргана:
⎤(P1 & P2) ↔ (⎯P1 \/⎯P2),
(1.14)
⎤(P1 \/ P2) ↔ (⎯P1 &⎯P2).
(1.15)
Следующие законы
эквивалентности.
Закон тождества:
выражают
свойства
P → P.
импликации
и
(1.16)
Закон контрапозиции:
(P1 → P2) ↔ (⎯P2 →⎯P1)).
(1.17)
Правило цепного заключения:
[(P1 → P2) & (P2 → P3)] → (P1 → P3).
91
(1.18)
Законы рефлексивности, симметричности и транзитивности:
P ↔ P,
(1.19)
(P1 ↔ P2) ↔ (P2 ↔ P1),
(1.20)
[(P1 ↔ P2) & (P2 ↔ P3)] → (P1 ↔ P3).
(1.21)
Закон противоположности:
(P1↔P2)↔(⎯P1↔⎯P2).
(1.22)
Следующие законы выражают зависимости между основными
логическими операциями.
Выражение конъюнкции через дизъюнкцию и отрицание и
дизъюнкции через конъюнкцию и отрицание:
(P1 & P2) ↔ ⎤(⎯P1 \/⎯P2),
(1.23)
(P1 \/ P2) ↔⎤ (⎯P1 &
- 1
- 2
- 3
- 4
- . . .
- последняя (9) »
Последние комментарии
5 минут 18 секунд назад
17 минут 52 секунд назад
28 минут 34 секунд назад
33 минут 36 секунд назад
34 минут 46 секунд назад
37 минут 5 секунд назад