Основные правила логического вывода доказуемость формул исчисления высказываний
Обновлено: 22.12.2024
Давая описание алгебры высказываний, использовались логические значения высказываний (истина, ложь). Но понятия истинности и ложности не математические. Эти понятия во многих случаях субъективны и скорее относятся к философии.
В связи с этим желательно построить математическую логику, не пользуясь понятиями истинности и ложности. Необходимо также при этом построении не применять самих законов логики.
Исчисление высказываний – это аксиоматическая логическая система, интерпретацией которой является алгебра высказываний. И хотя в исчислении высказываний используется термин «высказывание», следует иметь в виду, что под этим термином подразумевается некий абстрактный объект, о природе которого нам ничего не известно (например то, что он может принимать только два значения 1 и 0).
Описание всякого исчисления включает в себя описание символов этого исчисления (алфавита), формул, являющихся конечными конфигурациями символов, и определение выводимых формул.
Алфавит исчисления высказываний состоит из символов трех категорий:
1. Символы первой категории: х, у, z, . х1, х2, .
Эти символы называются переменными высказываниями.
2. Символы второй категории: Ú , &, ® , –. Они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак импликации или логического следования и четвертый – знак отрицания.
3. Третью категорию составляет пара символов ( ), называемая скобками.
Других символов исчисление высказываний не имеет. Формулы исчисления высказываний представляют собой последовательности символов алфавита исчисления высказываний. Для обозначения формул используются большие буквы латинского алфавита. Эти буквы не являются символами исчисления. Они представляют собой только условные обозначения формул. Формулу исчисления высказываний можно задать с помощью следующих рекуррентных определений.
1. Всякая переменная х, у, z, . является формулой.
3. Никакая другая строчка символов не является формулой.
Эти три утверждения определяют любую формулу исчисления высказываний.
Приведем примеры формул исчисления высказываний.
Переменные высказывания x, у, z являются формулами согласно п. 1 определения формулы. Но тогда слова (х&у), (хÚz), (у®z), являются формулами согласно п. 2 определения. По этой же причине будут формулами слова: и др.
Очевидно, не являются формулами слова:
(в третьем из этих слов содержится не закрытая скобка, а в четвертом – нет скобок).
Заметим, что здесь никак не конкретизируются понятия логических связок.
Одновременно с понятием формулы вводится понятие подформулы или части формулы с помощью следующих определений.
1. Подформулой элементарной формулы является только она сама.
3. Если формула имеет вид (A*B) (здесь и в дальнейшем под символом * будем понимать любой из трех символов ® ,&,Ú), то ее подформулами являются: она сама, формулы A и B и все подформулы формул A и B.
Например, для формулы ее подформулами будут:
– подформула нулевой глубины, т.е. она сама;
– подформулы первой глубины (удалена одна логическая связка);
– подформулы второй глубины;
– подформулы третьей глубины;
z – подформула четвертой глубины.
Очевидно, что на самой большой глубине находятся лишь элементарные формулы. Однако элементарные формулы могут быть и на других глубинах.
Обычно в запись формул вводят некоторые упрощения. Например, в записи формул опускаются скобки по тем же правилам, что и в алгебре высказываний.
В связи с этими правилами формула ((A&B)Úc) записывается как A&BÚc.
Читайте также: