Математика, Логіка висловлювань, FANDOM powered by Wikia

Логіка висловлювань(інша назва - пропозиційна логіка) - розділ логіки, що займається вивченням логічних висловлювань, операцій над ними та їх властивостей.

Зміст

Основні поняття

Базовими поняттями логіки висловлювань єпропозиційна змінна— змінна, значенням якої може бути логічне висловлювання, — та(пропозиційна) формула, яка визначається індуктивно наступним чином:

  1. Якщо P — змінна змінна, то P — формула.
  2. Якщо A - формула, $ \ neg A $ - формула.
  3. Якщо A і B - формули, то $ (A \ wedge B) $, $ (A \ vee B) $ і $ (A \ to B) $ - Формули.
  4. Кожна формула може бути отримана за кінцеве число кроків за допомогою попередніх трьох правил.

Знаки $ \neg, \wedge, \vee $ і $ \to $ (заперечення, кон'юнкція, диз'юнкція та імплікація) називаютьсяпропозиційними зв'язками.Підформулоюназивається частина формули, що сама є формулою.Власною підформулоюназивається підформула, яка не збігається з усією формулою.

Угоди про дужки

Оскільки в побудованих за визначенням формулах виявляється занадто багато дужок, іноді і не обов'язкових для однозначного розуміння формули, математики прийнялиугоди про дужки, за якими деякі з дужок можна опускати. Записи з опущеними дужками відновлюються так:

  • Якщо опущені зовнішні дужки, вони відновлюються.
  • Якщо поруч стоять дві кон'юнкції або диз'юнкції (наприклад, $ A \ wedge B \ wedge C $ ), то в дужки полягає спочатку ліва частина (тобто дві підформули зі зв'язкою між ними). (Кажуть також, що ці зв'язкилівоасоціативні.)
  • Якщо порядстоять різні зв'язки, то дужки розставляються згідно з пріоритетами: $ \neg, \wedge, \vee $ і $ \to $ (від найвищого до нижчого).

Коли говорять продовжину формули, мають на увазі довжину мається на увазі (відновлюваної) формули, а не скороченого запису.

Наприклад:запис $ A \vee B \wedge \neg C $ означає формулу $ (A \vee (B \wedge \neg C)) $ , а її довжина дорівнює 10.

Справжнє значення

Оцінкоюпропозиціональних змінних називається функція з безлічі всіх пропозиціональних змінних у безліч (тобто безліч істиннісних значень). Основним завданням логіки висловлювань є встановленняістиннісного значенняформули, якщо дана оцінка (тобто визначені істиннісні значення змінних, що входять до неї). Істиннісне значення формули у разі визначається індуктивно (з кроками, які використовувалися при побудові формули) з допомогою таблиць істинності зв'язок.

Формула, яка при всіх оцінках змінної набуває значення 1, називаєтьсятавтологією, значення 0 -суперечністю.

Наприклад:формула $ A \vee \neg A $ у класичному обчисленні висловлювань є тавтологією, а $ A \wedge \neg A $ - протиріччям.