Классическое определение исчисления высказываний.
1. Алфавит: ¬ и → — связки (логический базис Фреге)
(,) — служебные символы.
a, b, …, a1, b1,… — пропозициональные переменные.
2. Формулы: 1)переменные суть формулы.
2)если А,В — формулы, то (¬А) и (А→В) — формулы.
3. Аксиомы: А1:(A→B(B→A))
A2:((A→B→C))→((A→B)→(A→C))
A3:((¬B→¬A)→((¬B→A)→B).
4. Правило: (A, A→B)/B — Modus ponens
Здесь А и В — любые формулы. Таким образом, множество формул бесконечно, хотя задано трёмя схемами аксиом. Множество правил вывода бесконечно, хотя оно задано только одной схемой.
Другие связки вводятся определениями A&B:= ¬(A→¬B);A٧B:= ¬A→B.
Простейшим разделом математической логики является исчисление высказываний. Элементарные высказывания рассматриваются в ней как нерасчленяемые «атомы», а составные высказывания — как молекулы, образованные из «атомов» применением логических операций.
Пусть X, Y и Z — переменные, вместо которых можно подставлять любые элементарные высказывания (или их значения истинности). Такие переменные могут быть названы высказывательными (или булевыми). С помощью высказывательных переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить формулой, выражающей его логическую структуру. Например, «Если число делится на 2 и на 5, то оно делится на 10 (X Ù У) Þ 2”.
Понятие ПФ вводится индуктивно:
1. Символы логических констант 0, 1 являются ПФ.
2. Каждая логическая переменная является ПФ.
3. Если А и В суть ПФ то , А Ù В, А Ú В, А Þ В, А Û В также ПФ.
4. Никаких других ПФ в логике высказываний нет.
Определение закончено. В нем 1 и 2 являются базисными пунктами, где указываются объекты множества, 3 — индуктивный пункт, где даны правила получения из базисных объектов новых объектов, которые будут именоваться этим же термином, 4 — косвенный пункт, где указано, что заданный список исчерпывается.
Процедура формализации высказывания состоит из этапов:
1. Если высказывание простое, то ему ставится в соответствие элементарная формула.
2. Если высказывание составное, то нужно:
а) выделить все элементарные высказывания и логические связки, образующие составное высказывание;
б) заменить их соответствующими символами;
в) расставить скобки в соответствии с символами.
Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны, но не то и другое вместе. Такие утверждения называются (простыми) высказываниями. Простые высказывания считаются пропозициональными переменными, принимающими истинностные значения «И» и «Л». Из простых высказываний с помощью логических связок могут быть построены составные
высказывания. Обычно рассматривают следующие логические связки:
Название Прочтение Обозначение
Отрицание не Ø
Конъюнкция и &
Дизъюнкция или Ú
Импликация если … то ®
Формулы.
Правильно построенные составные высказывания называются (пропозициональными) формулами. Формулы имеют следующий синтаксис:
::=И | Л |
|
(Ø) |
( & ) |
( Ú ) |
( ® )
Для упрощения записи вводится старшинство связок (Ø,&, Ú, ®) и лишние связки не допускаются.