Студопедия  
Главная страница | Контакты | Случайная страница

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

Перечислите схемы аксиом и правила вывода исчисления высказываний

Читайте также:
  1. I. Правила и приемы конспектирования лекций
  2. I.Выберите правильный ответ для обоснования вывода о социальной сущности человека.
  3. II. Основные принципы и правила служебного поведения государственных служащих
  4. II. Основные принципы и правила служебного поведения гражданского служащего органов прокуратуры
  5. II. Основные принципы и правила служебного поведения гражданского служащего органов прокуратуры
  6. III. Правила выполнения и оформления контрольной работы
  7. III. Рекомендательные правила поведения государственных служащих
  8. III. Рекомендательные правила поведения государственных служащих
  9. IV. Основные виды вопросов и правила их постановки и формулирования.
  10. IV. Правила судейства.

Какие выражения в алфавите исчисления высказываний называются формулами

Обозначим через V ars язык {V |V, V ||V, V

V,...} в алфавите {V, |}. Каждое слово языка V ars будем называть пропозицио- нальной переменной (или, короче, переменной). Пропозициональная фор- мула (формула логики высказываний или просто формула) задаётся следу- ющим индуктивным определением: 1) любая пропозициональная переменная является пропозициональной формулой; 2) символы F и T являются пропозициональными формулами и называ- ются истинностными константами (ложь и истина соответствен- но); 3) если A и B — пропозициональные формулы, то A, (A ∧ B), (A ∨ B) и (A ⊃ B) — пропозициональные формулы. Множество всех пропозициональных формул обозначим через PL и назовём языком логики высказываний (или пропозициональным языком).2 / Таким образом, алфавит языка PL есть множество символов {V, |, F, T,(,),, ∧, ∨, ⊃}.  

Перечислите схемы аксиом и правила вывода исчисления высказываний

В качестве аксиом выбираются формулы следующих видов:

(Al) (F->{G-+F))9

(А2) «F-+ (G-+H))-* ((F-+ G)->(F-> #)),

(A3) ((п(7 -> -ijF) -+ (bG -> F) -> (?)),

где F, G, Н— произвольные формулы. Таким образом, каждое из

выражений (Al), (A2), (A3) задает лишь форму аксиомы. Они

превращаются в аксиомы, если вместо F, G, Н подставить

конкретные формулы (в частности, пропозициональные переменные).

Следовательно, каждое из этих выражений задает бесконечное

множество формул. Все они называются аксиомами. Поэтому

каждое из выражений (Al), (A2), (A3) называют схемой аксиом. Далее

определяется следующее правило получения новых формул из

имеющихся. Если имеются формулы Fn (F -> G), то они дают

формулу G. Это правило называется modus ponens или правилом

отделения (сокращенно МР) и записывается так:

F, (F-+G)

Наконец определяется понятие доказательства или вывода.

Доказательством или выводом формулы F из множества формул

(гипотез) Г называется такая конечная последовательность Ви

52,..., Bs формул, каждая формула которой является либо

аксиомой, либо формулой из Г (гипотезой), либо получена из двух

предыдущих по правилу МР, а последняя формула Bs совпадает

с F. Если имеется вывод формулы /^из множества гипотез Г, то говорят, что F выводима из Г, и пишут Г ь-. Если же имеется

вывод.Риз пустого множества гипотез, то говорят, что

F выводима из аксиом или что F доказуема. В этом случае /'называют

теоремой и пишут I- F.

Если Г = {Fl9 F2,..., Fm}, то вместо {Fu F2,..., Fm) н- G будем

писать Fu F2,..., Fw h- G

Поскольку в аксиомах не участвуют связки л, v, <->, то нам

придется их определить. Эти связки вводятся с помощью

следующих определений:

(F л G) означает n(F->nG);

(F v G) означает (-iF-> G);

(F <-> G)означает \{F -> G)*(G-> F)).

Как и в алгебре высказываний, договоримся внешние скобки

у формулы не писать.

 

1) Всякая пропозициональная буква есть формула.

2) Если , – формулы, то формулами являются также , .

3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

3. Аксиомы задаются тремя схемами аксиом:

А1. .

А2. .

А3. .

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

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

.

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




Дата добавления: 2015-01-30; просмотров: 51 | Поможем написать вашу работу | Нарушение авторских прав

<== 1 ==> | 2 | 3 | 4 | 5 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав