§ Определение доказуемой (выводимой) формулы



Скачать 29.76 Kb.
Дата15.01.2013
Размер29.76 Kb.
ТипДокументы
§ 2. Определение доказуемой (выводимой) формулы.

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

Определение доказуемых формул имеет тот же характер , что и определение формулы.

Сначала определяются исходные доказуемые выводимые формулы (аксиомы), а затем определяются правила вывода, которые позволяют из имеющихся доказуемых формул получить новые доказуемые формулы.

Образование доказуемой формулы из исходных доказуемых формул путем применения правил вывода называется выводом (доказательством) данной формулы из аксиом.В основу исчисления высказываний могут быть положены различные системы аксиом, эквивалентные между собой в том смысле, что определяемый ими класс выводимых формул – один и тот же. Рассмотрим одну из них.

Система аксиом исчисления высказываний.

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

Первая группа аксиом (содержащая только импликацию).

: . :.

Вторая группа аксиом (к импликации присоединилась конъюнкция):

: : . : .

Третья группа аксиом (к импликации присоединилась дизъюнкция):

: : : .

Четвертая группа аксиом (к импликации присоединилось отрицание):

:gif" name="object18" align=absmiddle width=113 height=20> : :

    1. Правила вывода.

1 Правило подстановки(ПП).

Если формула А выводима (доказуема) в исчислении высказываний, х- переменная, В- произвольная формула исчисления высказываний, то формула , полученная в результате замены в формуле А переменной х всюду , где она входит, формулой В, является также выводимой(доказуемой) формулой (ситуация та же, что имела место в алгебре логики, которая является интерпретацией исчисления высказываний).

Операция замены в формуле А переменной х формулой В, носит название подстановки и символически записывается так:

или .

Уточним сформулированное правило:

а) если формула А есть собственно переменная х , то подстановка дает , очевидно, В;

б) если формула А есть переменная y , отличная от х ,то подстановка дает А;

в)подстановка формулы В вместо х в отрицание формулы А есть отрицание подстановки , т. е. подстановка дает;

г) если А1 и А2- некоторые формулы, то подстановка дает *, где через символ * обозначен любой из символов операций конъюнкция, дизъюнкция или отрицание

Если А- выводимая (доказуемая ) формула, то будем писать, как и ранее, ├А. Тогда ПП можно записать схематически следующим образом:

├А____ .



И читается эта запись так: “Если формула А выводима (доказуема), то выводима (доказуема) и формула .

2 Правило заключения (ПЗ).

Если формулы А и А→В выводимы (доказуемы) в исчислении высказываний, то формула В также выводима (доказуема). Схематическая запись этого правила имеет вид:

├А;├А→В (Modus ponens)

├В

Правомерность этого правила очевидна: если импликация и посылка истинны, то заключение в импликации может быть только истинным(см. таблицу истинности операции “импликация”).

    1. Определение выводимой (доказуемой ) формулы.

а) Всякая аксиома является доказуемой формулой.

б)Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х произвольной формулы В, есть доказуемая формула.

в) Формула В, полученная из доказуемых формул А и путем применения ПЗ, есть доказуемая формула.

г) Никакая другая формула исчисления высказываний не считается доказуемой .

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

Похожие:

§ Определение доказуемой (выводимой) формулы iconОпределение простейшей химической формулы вещества по известным массовым долям элемента
Асчетные формулы для определения индексов в химической формуле вещества, например для вещества Ax By
§ Определение доказуемой (выводимой) формулы iconСоставьте формулы оксидов и соответствующих гидроксидов, докажите характер оксидов соответствующими уравнениями реакций
Исходя из данных соединений составьте формулы средних, кислых и основных солей. Назовите их. Напишите графические формулы
§ Определение доказуемой (выводимой) формулы iconРешение задач по теме «Площади многоугольников»
Повторение словесных формул площадей многоугольников с помощью «логической шпаргалки»- «Шпаргалка» даёт не готовые формулы, а напоминает...
§ Определение доказуемой (выводимой) формулы iconМатематика Excel
Запись формулы в ячейке начинается со знака «равно» (=). Формулы записываются по определенным правилам. Формулы содержат числа, имена...
§ Определение доказуемой (выводимой) формулы iconФормулы сложения вероятностей
Из пункта 2 аксиомы, по которой вводилось определение вероятности события, следует, что если A1 и A2 несовместные события, то
§ Определение доказуемой (выводимой) формулы iconФормулы сложения вероятностей
Из пункта 2 аксиомы, по которой вводилось определение вероятности события, следует, что если A1 и A2 несовместные события, то
§ Определение доказуемой (выводимой) формулы icon1. 5 Формулы численного интегрирования
...
§ Определение доказуемой (выводимой) формулы iconХод урока Комментарий
Что такое формулы? (Формулы – это верные равенства, устанавливающие взаимосвязь между величинами)
§ Определение доказуемой (выводимой) формулы iconСамостоятельная работа по решению задач на определение формулы органического вещества
Определите молекулярную формулу органического соединения с со­ставом 80% углерода и 20% водорода, если плотность его по воздуху равна...
§ Определение доказуемой (выводимой) формулы iconI. к изучению мигрирующей интонационной формулы как структурно-семантического стереотипа 25 Глава II. Мигрирующие формулы с относительно устойчивой семантикой их источники
Ii. Мигрирующие формулы с относительно устойчивой семантикой их источники 57
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org