Введение в математическую логику

Лекция 8. Введение в математическую логику

Логика высказываний

Основными объектами математической логики являются простые и составные высказывания.

Высказывание – повествовательное предложение (утверждение, суждение), о котором имеет смысл говорить истинно оно или ложно. Научные знания: (законы и явления), события повседневной жизни и т.п. Например, «сегодня идет дождь», «сейчас 12:35».

Простое (элементарное) высказывание – высказывание, которое рассматривается как некое неделимое целое.

Сложное (составное) высказывание – высказывание, составленное из простых с помощью логических связок.

Из числа высказываний исключаются вопросы, приказы, лозунги, междометия, утверждения, выражающие субъективные чувства.

Обозначим истинное высказывание за 1, ложное – 0.

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

Основные логические связки (операции) логики высказываний

Конъюнкцией (операцией «И», логическим произведением) двух высказываний P и Q называется высказывание, истинное, когда оба высказывания истинны, и ложное во всех других случаях. Обозначается P & Q; P ∧ Q; P ⋅ Q.

Дизъюнкцией (операцией «ИЛИ», логической суммой) высказываний P и Q называется высказывание, ложное, когда оба высказывания ложны, и истинно в любых других случаях. Обозначение: P ∨ Q; P + Q.

Отрицанием (инверсией) высказывания P называется высказывание, истинное, когда P ложно, и ложное в противном случае. Обозначение: ~P, ¬P, [pic 1] (читается «не P»).

Импликацией (логическим следованием) высказываний P и Q называется высказывание, ложное, когда P истинно, а Q ложно; во всех остальных случаях – истинное. Обозначается P → Q; P ⊃ Q; P ⇒ Q (читается: «если P то Q», «P влечет Q», «из P следует Q»). P называют посылкой, Q – заключением (следствием).

Эквивалентностью (эквиваленцией, равнозначностью) двух высказываний P и Q называется высказывание, истинное, когда истинностные значения P и Q совпадают, и ложное в противном случае. Обозначается P ~ Q, P ≡ Q, P ↔ Q (читается «P эквивалентно Q», «P, если и только если Q», «P равнозначно Q»).

Неравнозначностью (исключающим «ИЛИ», сложением по модулю 2) двух высказываний P и Q называется высказывание, истинное, когда истинностные значения P и Q не совпадают, и ложное в противном случае. Обозначается: P ⊕ Q, P Δ Q и др. (читается: «либо P, либо Q», «или P, или Q»).