Mathematical logic

Елементи формальної логіки

Формальна логіка досліджує судження. Судження — твердження, яке може бути або істинним, або хибним. Жодних інших варіантів. True or False. Судження можуть складати свою чергу з певних частин.

Судження = аргументи + логічні зв’язки.
Логічні зв’язки — ∧, ∨, ¬, →, ↔…
Аргументи — інше судження або атом, або змінна.
Атом — судження, яке не розбивається на інше судження.
Змінна — “Він є студентом КШЕ” - тут ‘він’ це хтось, невідомо хто, якийсь х. “Він є студентом КШЕ” це речення є предикатом — P(x), де х — ‘він’.

Приклад:
Якщо $x>2$, то $x^2>4$ ⇒ відповідно, якщо $x^2\le 4$, то $x\le 2$.

$P(x)=x>2$

$Q(x)=x^2>4$

$P(1)$ — хиба,
$P(10)$ — істина.
$P(x)\to Q(x)\Rightarrow \mathrm{\neg }Q(x)\to \mathrm{\neg }P(x)$

Логічні зв’язки (значки)

$\mathrm{\neg }$ — заперечення, ні
$\wedge$ — та (кон’юнкція) &
$\vee$ — або (диз’юнкція)
$\to$ — імплікація, відповідно (A $\to$ B - якщо А, то відповідно B)
$\leftrightarrow$ — еквівалентність, тільки і тільки тоді, if and only if
$\oplus$ — XOR, eXclusive OR
$\equiv$ — логічне дорівнює
$\Rightarrow$ — логічний наслідок
$\therefore$ — тому

Якщо…, то… — $P(x)\to Q(x)$

Квантори

$\mathrm{\forall }$ — квантор загальності, “будь-який, всі, для всіх”
$\mathrm{\exists }$ — квантор існування, “існує такий, хоча б один”
$\mathrm{\exists }!$ — квантор єдиності, “існує єдиний, він лише один, не більше, не менше”
$\nexists$ — “не існує, немає”

$P(x)=(\mathrm{\forall }x\mid x>2)$ — усі $x$ більше за два. хиба.
$P(x)=(\mathrm{\exists }x\mid x>2)$ — є такий $x$, який більше за два. істина.

$Q(x)=\mathrm{\forall }x\mid P(x)$

$Q(x)$ є істинним тоді і тільки тоді, коли для всіх значень $x$ виконується умова $P(x)$

$\mathrm{\neg }Q(x)=\mathrm{\exists }x\mid \mathrm{\neg }P(x)$

Таблиця істинності

Логічний наслідок ($\Rightarrow$) — це теж зв'язка, але вона специфічна.
Ми кажемо, що логічний наслідок виконується, якщо для всіх можливих випадків, коли ліва частина істинна, права частина теж істинна. Тобто це щось схоже на імплікацію, але відрізняється.

Властивості

Логічна еквівалентність

Правила логічного виводу