Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Теоретические сведения. Для алгебры высказываний существует в известном смысле адекватная аксиоматическая логическая система





 

Для алгебры высказываний существует в известном смысле адекватная аксиоматическая логическая система, которая называется исчислением высказываний. Описание всякого исчисления заключает в себе описание символов этого исчисления, формул, являющихся конечными конфигурациями символов, и после этого определение истинных формул (или выводимых формул).

Символами исчисления высказываний являются во-первых, заглавные латинские буквы, с индексами или без, которыми обозначаются высказывания, во-вторых, знаки логических операций и, в-третьих, пара скобок (). Иных символов, кроме указанных, исчисление высказываний не имеет. Формулы исчисления высказываний представляют собой конечные последовательности описанных символов. Эти последовательности, как правило, записываются в виде строчек. Не всякая строка символов является формулой. Полное определение формулы имеет рекурсивный характер: указываются некоторые исходные формулы и затем правила, позволяющие из формул образовывать новые формулы. Таким образом, определение формулы можно сформулировать следующим образом:

1. Переменное высказывание есть формула (элементарная формула).

2. Если X и Y – формулы, то , X Ù Y, X Ú Y, X ® Y

также формулы.

Следующим шагом в определении исчисления высказываний является определение некоторого класса формул, которые называются истинными или выводимыми в исчислении высказываний. Определение истинных формул имеет такой же рекурсивный характер, как и определение формулы. Сначала определяются исходные истинные формулы, а затем определяются правила, позволяющие из имеющихся истинных формул образовывать новые. Эти правила называются правилами вывода, а исходные истинные формулы – аксиомами. Образование истинной формулы из исходных истинных формул или аксиом путем применения правил вывода называется выводом данной формулы из аксиом.

Для полного набора логических связок: импликация, отрицание, конъюнкция и дизъюнкция система содержит десять аксиом. В силу полноты систем, использующих логические связки а) импликации и отрицания, б) импликации и дизъюнкции, в) импликации, отрицания, конъюнкции и дизъюнкции можно использовать в процессе дедуктивного вывода любую из указанных систем.

Ниже приведена одна из систем аксиом:

1. ├─ X ®(Y ® X);

2. ├─(X ® Y)®((X ®(Y ® Z))®(X ® Z));

3. ├─ X Ù Y ® X;

4. ├─ X Ù Y ® Y;

5. ├─(X ® Y)®((X ® Z)®(X ® Y Ù Z));

6. ├─ X ® X Ú Y;

7. ├─ Y ® X Ú Y;

8. ├─(X ® Z)®((Y ® Z)®(X Ú Y ® Z));

9. ├─(X ® Y)®((X ® );

10. ├─ ® X;

К правилам вывода в исчислении высказываний относятся следующие:

1. Правило подстановки. Если выводимая формула F содержит некоторую переменную A (обозначим этот факт F (A)) и существует произвольная формула B, то формула F (B), получающаяся заменой всех вхождений A на формулу B, также выводима в исчислении высказываний. Этот факт формально описывают так:

.

Если F (A)= A, то Если , то

Следует еще раз обратить внимание, что формула F должна быть выводимой в исчислении высказываний.

Пример. Пусть даны формулы F = A Ù C ® A и B = C ® .

Если выполнить подстановку формулы B в формулу F вместо формулы A, то получим новую формулу F`.

2. Правило заключения. Если и – истинные формулы в исчислении высказываний, то также истинная формула (modus ponens).

Если и – истинные формулы в исчислении высказываний, то также истинная формула (modus tollens).

Пример. Если формулы и истинны, то формула тоже истинна.

Указанием аксиом и правил вывода мы полностью определяем понятие истинной или выводимой в исчислении высказываний формулы. Пользуясь правилами вывода, мы можем исходя из аксиом, конструировать новые истинные формулы и получать таким образом каждую истинную формулу. Кроме основных правил вывода – правила подстановки и правила заключения, существуют и другие правила образования истинных формул, производные от основных правил и являющиеся сокращением многократного применения основных правил. Правила выражаются обычно в следующих терминах: «если формулы А, В,... истинны, то формулы Х, Y,... также истинны» и записываются в виде .

Утверждение, что формула Y выводима из формул X 1, X 2,..., Xn обозначается в виде X 1, X 2,..., Xn ├─ Y.

Выводом в исчислении называется последовательность формул такая, что для любого i формула Xi есть либо аксиома исчисления, либо непосредственное следствие каких-либо предыдущих формул.

Формула Y называется теоремой исчисления, выводимой в исчислении или доказуемой в исчислении, если существует вывод , Y, который называется выводом формулы Y или доказательством теоремы Y.

Пример. Покажем, что формула выводима в исчислении высказываний. Для этого построим вывод данной формулы:

1) в схеме аксиом 2 Y заменим на , Z – на X. Получим ;

2) в схеме аксиом 1 Y заменим на X. Получим ;

3) из 1 и 2 по правилу заключения получим

;

4) в схеме аксиом 1 заменим Y на , получим

;

5) из 3 и 4 по правилу заключения справедливо ├─ .

 

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

Теорема дедукции. Если формула Y выводима из формул X 1, X 2,..., Xn, то X 1 ®(X 2 ® (...(Xn ® Y)...)) истинная формула.

С помощью теоремы дедукции можно получать новые правила исчисления высказываний.

Пример. Рассмотрим формулы X ® (Y ® Z), Y, X.

Применяя два раза правило заключения, находим, что

X ® (Y ® Z), Y, X ├─ Z.

Применяя теорему дедукции, получим правило

├─ (X ® (Y ® Z)) ® (Y ® (X ® Z)),

которое носит название правила перестановки посылок.

Используя правила эквивалентных преобразований алгебры высказываний, можно показать дедуктивный характер вывода заключения:

1) ├─ (X 1Ù X 2Ù...Ù Xn ® Y);

2) ├─ ( Ú Y);

3) ├─ ( Ú Ú...Ú Ú Y);

4) ├─ ( Ú Ú...Ú Ú(Xn ® Y));

5) ├─ ( Ú Ú...Ú(Xn-1 ®(Xn ® Y)));

6) ├─ ( Ú (X2 ®...®(Xn-1 ®(Xn ® Y))...));

7) ├─ (X1 ®(X2 ®...®(Xn-1 ®(Xn ® Y))...).

Так формируется система де­дуктивного вывода от по­сылок до заключения.

Замечание. Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого свободные переменные исчисления высказываний будем трактовать как переменные алгебры высказываний, то есть переменные, принимающие значения «истина» или «ложь». Операции , Ù, Ú, ® определим также, как в алгебре высказываний. Тогда всякая формула при любых значениях переменных сама будет принимать одно из значений «истина» или «ложь», вычисляемое по правилам алгебры высказываний.

Теорема (о полноте исчисления высказываний). Формула Y доказуема тогда и только тогда, когда Y тождественно истинна.

Эта теорема сводит проверку доказуемости формулы к проверке ее тождественной истинности.

Таким образом, для того чтобы установить, доказуема ли формула, достаточно составить ее таблицу истинности. Как известно, существует алгоритм построения таблицы истинности, и, значит, исчисление высказываний разрешимо.

 

Date: 2015-06-06; view: 546; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию