Математическая логика и теория алгоритмов. Сергиевская И.М. - 12 стр.

Глава 3. Исчисление высказываний.

     Исчисление     высказываний      (теория   L)    определяется    следующими
компонентами.

     1. Алфавит составляют:
• Пропозициональные буквы (от англ. proposition – высказывание) – заглавные
  буквы латинского алфавита (иногда с индексами – натуральными числами):
  A, B , C ,... , A1 , B1 , C1 ,…
• Логические связки: ¬, → .
• Скобки: (, ).

     Иногда в исчислении высказываний допускаются формулы с другими
логическими связками, но при этом учитывается, как они выражаются через
инверсию и импликацию. Так, A ∧ B = ¬( A → ¬B ) , A ∨ B = ¬A → B . Такие записи
являются удобными сокращениями.

     2. Формулы определяются так же, как в главе 1.

     Определение. 1) Всякая пропозициональная буква есть формула.
2) Если A , B – формулы, то формулами являются также ¬A , A → B .
3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

       3. Аксиомы задаются тремя схемами аксиом:
А1. A → (B → A) .
А2. ( A → (B → C )) → (( A → B ) → ( A → C )).
А3. (¬B → ¬A) → ((¬B → A) → B ) .

     Существуют исчисления высказываний с другим набором логических связок и
другими схемами аксиом, но в данном пособии они не рассматриваются. Желающие
могут ознакомиться с ними в [12].

      4. Правило вывода Modus ponens (сокращенно MP) – правило отделения (лат.).
A, A → B ├ B .

     Здесь A , B – любые формулы. Таким образом, множество аксиом исчисления
высказываний, заданное тремя схемами аксиом, бесконечно. Множество правил
вывода задано одной схемой, и также бесконечно.

     Теорема. Все теоремы исчисления высказываний – тавтологии.


                                        17