Всё для Учёбы — студенческий файлообменник
2 монеты
doc

Шпаргалка «Экзаменационная» по Математической логике (Дьячков А. М.)

1.Алгебра высказываний; пропозициональные связки и формы, истинностные таблицы

Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно. Значение «истинно» и «ложно» обычно обозначаются 1 или 0, или И и Л.

Содержательно логические операции обычно интерпретируют следующим образом:

отрицание (инверсия) (− ) − «не»

дизъюнкция − «или»

конъюнкция & (А&B или A.В) − «и»

импликация → − «если … , то»

эквивалентность ~ − «тогда и только тогда» (или «эквивалентно»)

приоритеты по выполнению действий: , &, , →, ~ .

Символы , &, , →, ~ наз-ся пропозициональными(или логическими) связками. Буквы, обозначающие высказывания, наз-ся пропозициональными буквами. Осмысленные формулы, составленные из пропозициональных букв, пропозициональных связок, а также скобок, указывающих порядок выполнения операций, наз-ся пропозициональными формами(ПФ).

Операции логики высказываний можно задать с помощью табл.:

А В А А В А&B A→B A~B

0 0 I 0 0 I I

0 I I I 0 I 0

I 0 0 I 0 0 0

I I 0 I I I I

Используя эту таблицу можно получить истинностную таблицу для произвольной ПФ.

2.Алгебра высказываний; тавтологии и противоречия

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

1) Если А – тавтология, то А – противоречие. И наоборот.

2) Если А и А→В – тавтологии, то В – тавтология.

3) Если А→В и А→В – тавтологии, то А – противоречие.

4) Если в тавтологии вместо пропозициональных букв подставить произвольные ПФ, то снова получится тавтология.

3.Алгебра высказываний; логическая эквивалентность и логическое следствие

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности" ~.

Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" → и выражается словами ЕСЛИ … , ТО …

4. Алгебра высказываний; дизъюнктивная и конъюнктивная нормальные формы

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

Теорема. Всякая истинностная функция F порождается некоторой ДНФ

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

Теорема. Всякая истинностная функция F порождается некоторой КНФ.

5. Алгебра высказываний; полные системы функций, базис

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

Сис-ма связок {, ,&} явл-ся полной.

Теорема. Система связок {, } явл-ся базисом

6. Понятие формальной аксиоматической теории. (ФАТ)

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

1)Алфавит теории-счетное множ-во, элементы которого служат символы для построения слов.

2) Формулы теории – те слова, которые считаются осмысленными.

3) Аксиомы теории – те формулы, которые счит-ся не нуждающимися в док-ве. Множ-во аксиом может быть бесконечным.

4) Правила вывода, определяющие, в каком случае мы считаем одну формулу непосредственным следствием других.

Если для формулы A сущ-ет вывод,то говорят, что она явл-ся теоремой ФАТ, и пишут так: .

7. Исчисление высказываний, как формальная аксиоматическая теория (ФАТ).

В кач-ве основного примера ФАТ рассмотрим исчисление высказываний (ИВ).

1)Алфавит ИВ состоит из пропозициональных букв, пропорциональных связок и –(не) и скобок.

2) Формулы ИВ – это все ПФ, содержащие лишь связки –(не) и

3)Аксиом в ИВ бесконечно много, но каждая из них пол-ся из одной из следующих 3 схем аксиом:

А1: ;

A2: ; A3:

Подстановкой вместо A,B,C произвольных формул ИВ.

4) Правило вывода в ИВ всего одна: формула B счит-ся непосредственным следствием формул A и . (modus ponens), сокращенно MP.

T1: ;

T2: (правило силлогизма ПС)

T3: (правило перестановки посылок ПП)

T4: T5: T6:

T7:

T8: T9: T10:

8. Формальная аксиоматическая теория (ФАТ), определение аксиомы, правило вывода

Аксио́ма— утверждение (факт), принимаемое истинным без доказательства, а также как «фундамент» для построения доказательств.

Аксиом в ИВ бесконечно много, но каждая из них пол-ся из одной из следующих 3 схем аксиом:

А1: ;

A2: ; A3: Подстановкой вместо A,B,C произвольных формул ИВ.

Правило вывода в ИВ всего одна: формула B счит-ся непосредственным следствием формул A и . (modus ponens), сокращенно MP.

T1: ; T2: (правило силлогизма ПС)

T3: (правило перестановки посылок ПП)

T4: T5: T6:

T7: T8: T9:

T10: 9. Формальная аксиоматическая теория (ФАТ), формализация понятий теоремы и ее док-ва.

В ФАТ выводом или док-ом формулы A наз-ся конечная цепочка формул, каждая из которых есть либо аксиома, либо непосредственное следствие каких-либо из предыдущих формул по одному из правил вывода, причем последняя формула этой цепочки- это и есть формула A.Если для формулы A сущ-ет вывод,то говорят, что она явл-ся теоремой ФАТ, и пишут так: .

Предложение : Всякая формула, полученная по схеме явл-ся теоремой ИВ.

Док-во: чтобы док-ть, что формула явл-ся теоремой, надо предъявить ее вывод. Вот он:

(1) схема ;

(2) схема ;

(3) из (1), (2) по MP (формула B счит-ся непосредственным следствием формул A и .)

(4) схема ;

(5) из (3), (4) по MP

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

(правило силлогизма ПС)

(правило перестановки посылок ПП)

Теорема дедукции: Если Г, A|-B, то Г|-A B.

Доказательство. Пусть последовательность формул B1, B2, …, Bm есть вывод B из Г,A. В ней Bm = B. Индукцией по i покажем, что Г|-A Bi для каждого i = 1, …, m. При i = m будем иметь утверждение теоремы. Сначала заметим, что, по определению вывода, для каждой формулы Bi при i {1, …, m} возможны следующие случаи: 1) Bi =A, 2) Bi – аксиома, 3) Bi Г. В случае 1), ввиду |-A A (пример 1), имеем |-A Bi и, следовательно, Г|-A Bi. В случаях 2) и 3) выводом A Bi из Г служит последовательность Bi, Bi (A Bi), A Bi, в которой первая формула является аксиомой или принадлежит Г, вторая формула есть аксиома 1 и третья получена из них по правилу отделения.

1. A (B A) В качестве единственного правила вывода в ИВ мы принимаем правило modus ponens, или правило отделения ,по которому, каковы бы ни были формулы A и B, из формул A и A B получается формула B.При i ≤ 2 других случаев нет, и база индукции установлена. При i > 2 возможен еще один случай: 4) Bi получена из Bj и Bk для некоторых j, k

Показать полностью…
Похожие документы в приложении