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

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

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

Обозначим через 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) – правило отделения (лат.).

├ .

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