Математическая логика

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

Высказывания обозначаются: $p$, $q$, $r$ …

Для того, чтобы не писать «истина» и «ложь» («true» и «false«) часто используют лишь начальные буквы этих слов «и» и «л» или «1« и «0«, или символы «$ \top $» и «$ \bot $«.

Основные логические операции

Введем следующие обозначения для операций: $ \wedge $ или & – конъюнкция, $ \vee $ – дизъюнкция, $\neg $ – отрицание, $ \Rightarrow $ – импликация, $ \Leftrightarrow $ – эквиваленция. Символы $ \wedge $ или &, $ \vee $, $\neg $, $ \Rightarrow $, $ \Leftrightarrow $, называются логическими операциями или связками.

операция	логическая операция	новое высказывание
конъюнкция ($p$ и $q$)	$ \wedge $	$p \wedge q$ ($p$ и $q$)
дизъюнкция ($p$ или $q$)	$ \vee $	$p \vee q$ ($p$ или $q$)
импликация (если $p$ … тогда $q$)	$ \Rightarrow $	$p \Rightarrow q$ (если $p$, тогда $q$)
эквиваленция($p$ тогда и только тогда, когда $q$)	$ \Leftrightarrow $	$p \Leftrightarrow q$ ($p$ тогда и только тогда, когда $q$)
отрицание (не)	$\neg $	$\neg p$ (не $p$)
дисјункција (или – или)	$\underline \vee $	$p \underline \vee q$ ($p$ или $q$, али не оба)

Таблица истинности логических операций

$p$	$q$	$p \wedge q$	$p \vee q$	$p \Rightarrow q$	$p \Leftrightarrow q$	$p \underline \vee q$
$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$ \bot $
$\top$	$ \bot $	$ \bot $	$\top$	$ \bot $	$ \bot $	$\top$
$ \bot $	$ \bot $	$\top$	$\top$	$\top$	$ \bot $	$\top$
$ \bot $	$ \bot $	$ \bot $	$ \bot $	$\top$	$\top$	$ \bot $

$p$	$\neg p$
$\top$	$ \bot $
$ \bot $	$\top$

Формулы логики высказываний

Формулами логики высказываний называются

атомаоные формулы логики высказываний (высказывания $p$, $q$, $r$… и символы истины и лжи «1» и «0«, или «$ \top $» и «$ \bot $»)
и выражения вида: $A \vee B$, $A \wedge B$, $A \Rightarrow B$, $A \Leftrightarrow B$, $\neg A$, где $A$ и $B$ формулы логики высказываний.

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

Тавтология

Тавтологией называется тождественно истинное высказывание относительно значений своих компонентов.

Свойства логтческих операций

Коммутативность конъюнкции, дизъюнкции и еквиваленции
$p \wedge q \Leftrightarrow q \wedge p$,
$p \vee q \Leftrightarrow q \vee p$,
$(p \Leftrightarrow q) \Leftrightarrow (q \Leftrightarrow p)$
Асоциативность конъюнкции, дизъюнкции и еквиваленции
$(p \wedge q) \wedge r \Leftrightarrow p \wedge (q \vee r)$,
$(p \vee q) \vee r \Leftrightarrow p \vee (q \vee r)$,
$(p \Leftrightarrow q) \vee r \Leftrightarrow p \Leftrightarrow (q \Leftrightarrow r)$.
Идемпотентность конъюнкции, дизъюнкции
$p \wedge p \Leftrightarrow p$,
$p \vee p \Leftrightarrow p$.
Дистрибутивность конконъюнкции относительно дизъюнкции и обратно
$p \wedge (q \vee r) \Leftrightarrow (p \wedge q) \vee (p \wedge r)$,
$p \vee (q \wedge r) \Leftrightarrow (p \vee q) \wedge (p \vee r)$.
Асоциативность конконъюнкции относительно дизъюнкции и обратно
$p \wedge (q \vee q) \Leftrightarrow p$,
$p \vee (q \wedge q) \Leftrightarrow p$.
Инволютивность отрицания
$\neg (\neg p) \Leftrightarrow p$.
Нейтральный элемент для операции конъюнкции и дизъюнкции
$p \wedge 0 \Leftrightarrow p$,
$p \vee 0 \Leftrightarrow p$.