Шпаргалка по "Дискретной математике. Математической логике"

1. Высказывания и операц над ними. Примеры.

Алгебра высказываний – раздел мат. логики, в котором изучаются операции над высказываниями.

Выказывание-повествовательное предложение, в котором точно можно сказать истино оно или ложно.

Каждое высказ имеет только одно из 2 знач –  «И»,  или «Л».

2.Логические операции алгебры высказываний. Примеры:

Конъюнкцией высказываний A и B наз высказывание «A и B». Его считают истинным ↔, когда истинны оба высказывания A и B. (A  B)[pic 1]

Дизъюнкцией высказываний A и B наз высказывание «A или B». Его считают истинным ↔, когда истинно по крайней мере одно из высказываний A и B. (A  B)[pic 2]

Импликацией высказываний A и B наз высказывание «Если A, то B». Его считают ложным ↔, когда высказывание A истинно, а высказывание B ложно. При этом высказывание A называют посылкой, а B – заключением. Обозначают импликацию «Если A, то B» так: A → B.

Отрицанием высказывания A наз высказывание «Неверно, что A (не A)». Это высказывание считают истинным тогда и только тогда, когда высказывание A ложно . ¬А

Операция эквиваленции АВ определяется так: АВ истинно ↔, когда А и В или оба истинны или оба ложны.[pic 3][pic 4]

Примеры:

1) 2- простое число (истинное высказывание)

2) Неверно, что 2-простое число(ложное высказывание)

3) «2 меньше 3, или 2 равно 3»  - истинно  

4) «2 меньше 3, и 2 равно 3» -ложно

3. Пропозиционные формулы. Правила записи

 сложных формул.

Для обозначения высказываний будем применять прописные буквы латинского алфавита и буквы с индексами (А, В, С, ..., А1, А2, ... В1, В2), которые будем называть  пропозициональными  буквами.

 Пропозициональная формула представляет собой выражение, полученное по некоторым правилам из пропозициональных букв с помощью логических связок.

1)все пропозициональные буквы есть  пропозициональные формулы,

2)если А и В пропозициональные формы, то (А), (АВ), (АВ), (АB), (АB) тоже пропозициональные формы,[pic 6][pic 7][pic 8][pic 9][pic 10]

3)только те выражения являются пропозициональными формами, для которых это следует из пп.1,2.

Введем некоторые соглашения о более экономном употреблении скобок в записях формул

Во-первых, будем опускать в пропозициональной формуле внешнюю пару скобок.

Во-вторых, если форма содержит вхождения только одной связки , то для каждого вхождения этой связки опускаются внешние скобки у той из двух формул , которая стоит слева.

В-третьих, будем считать связки упорядоченными следующим образом: ¬, ˄, ˅, →, ↔ и будем опускать во всякой пропозициональной формуле все те пары скобок, без которых возможно восстановление этой формы на основе следующего правила. Каждое вхождение знака ¬ относится к наименьшей пропозициональной формуле, следующей за ним; после расстановки всех скобок, относящихся ко всем вхождениям знака ¬,  каждое вхождение знака  ˄ связывает наименьшие формы, окружающие это вхождение. При применении этого правила к одной и той же связке мы продвигаемся слева направо.